On the Periodic Decompositions of Multidimensional Configurations
摘要
We consider d-dimensional configurations, that is, colorings of the d-dimensional integer grid \(\mathbb {Z}^d\) with finitely many colors. Moreover, we interpret the colors as integers so that configurations are functions \(\mathbb {Z}^d \rightarrow \mathbb {Z}\) of finite range. We say that such function is k-periodic if it is invariant under translations in k linearly independent directions. It is known that if a configuration has a non-trivial annihilator, that is, if some non-trivial linear combination of its translations is the zero function, then it is a sum of finitely many periodic functions. This result is known as the periodic decomposition theorem. We prove two different improvements of it. The first improvement gives a characterization on annihilators of a configuration to guarantee the k-periodicity of the functions in its periodic decomposition—for any k. The periodic decomposition theorem is then a special case of this result with \(k=1\) . The second improvement concerns so called sparse configurations for which the number of non-zero values in patterns grows at most linearly with respect to the diameter of the pattern. We prove that a sparse configuration with a non-trivial annihilator is a sum of finitely many periodic fibers where a fiber means a function whose non-zero values lie on a unique line.