2024/09/23 by Herva, Pyry, Kari, Jarkko · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.14948
We consider d-dimensional configurations, that is, colorings of the d-dimensional integer grid ℤd with finitely many colors. Moreover, we interpret the colors as integers so that configurations are functions ℤd → ℤ 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.