On the Periodic Decompositions of Multidimensional Configurations
: Herva, Pyry; Kari, Jarkko
: Královič, Rastislav; Kůrková, Věra
: International Conference on Current Trends in Theory and Practice of Computer Science
Publisher: Springer Nature Switzerland
: 2025
: Lecture Notes in Computer Science
: SOFSEM 2025: Theory and Practice of Computer Science: 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part II
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: 15539
: 45
: 57
: 978-3-031-82696-2
: 978-3-031-82697-9
: 0302-9743
: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-82697-9_4
: https://doi.org/10.1007/978-3-031-82697-9_4
We consider d-dimensional configurations, that is, colorings of the d-dimensional integer grid Zd with finitely many colors. Moreover, we interpret the colors as integers so that configurations are functions Zd→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.
:
This research was supported by the Academy of Finland grant 354965.
