A4 Refereed article in a conference publication
On the Periodic Decompositions of Multidimensional Configurations
Authors: Herva, Pyry; Kari, Jarkko
Editors: Královič, Rastislav; Kůrková, Věra
Conference name: International Conference on Current Trends in Theory and Practice of Computer Science
Publisher: Springer Nature Switzerland
Publication year: 2025
Journal: Lecture Notes in Computer Science
Book title : 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
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 15539
First page : 45
Last page: 57
ISBN: 978-3-031-82696-2
eISBN: 978-3-031-82697-9
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-82697-9_4
Web address : 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.
Funding information in the publication:
This research was supported by the Academy of Finland grant 354965.
