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 sourceLecture 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.
