{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T04:55:46Z","timestamp":1696395346899},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Turku (UTU) including Turku University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>d<\/jats:italic>-dimensional configuration <jats:inline-formula><jats:alternatives><jats:tex-math>$$c:\\mathbb {Z}^d\\longrightarrow A$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mo>:<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>Z<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>d<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>\u27f6<\/mml:mo>\n                    <mml:mi>A<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a coloring of the <jats:italic>d<\/jats:italic>-dimensional infinite grid by elements of a finite alphabet <jats:inline-formula><jats:alternatives><jats:tex-math>$$A\\subseteq \\mathbb {Z}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>Z<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The configuration <jats:italic>c<\/jats:italic> has an annihilator if a non-trivial linear combination of finitely many translations of <jats:italic>c<\/jats:italic> is the zero configuration. Writing <jats:italic>c<\/jats:italic> as a <jats:italic>d<\/jats:italic>-variate formal power series, the annihilator is conveniently expressed as a <jats:italic>d<\/jats:italic>-variate Laurent polynomial <jats:italic>f<\/jats:italic> whose formal product with <jats:italic>c<\/jats:italic> is the zero power series. More generally, if the formal product is a strongly periodic configuration, we call the polynomial <jats:italic>f<\/jats:italic> a periodizer of <jats:italic>c<\/jats:italic>. A common annihilator (periodizer) of a set of configurations is called an annihilator (periodizer, respectively) of the set. In particular, we consider annihilators and periodizers of <jats:italic>d<\/jats:italic>-dimensional subshifts, that is, sets of configurations defined by disallowing some local patterns. We show that a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(d-1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-dimensional linear subspace <jats:inline-formula><jats:alternatives><jats:tex-math>$$S\\subseteq \\mathbb {R}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>S<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>R<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>d<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is expansive for a subshift if the subshift has a periodizer whose support contains exactly one element of <jats:italic>S<\/jats:italic>. As a subshift is known to be finite if all <jats:inline-formula><jats:alternatives><jats:tex-math>$$(d-1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-dimensional subspaces are expansive, we obtain a simple necessary condition on the periodizers that guarantees finiteness of a subshift or, equivalently, strong periodicity of a configuration. We provide examples in terms of tilings of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Z}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>Z<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by translations of a single tile.<\/jats:p>","DOI":"10.1007\/s00224-023-10139-7","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T04:02:00Z","timestamp":1690344120000},"page":"976-994","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Expansivity and Periodicity in Algebraic Subshifts"],"prefix":"10.1007","volume":"67","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"10139_CR1","doi-asserted-by":"crossref","unstructured":"Kari, J., Szabados, M.: An Algebraic Geometric Approach to Nivat\u2019s Conjecture. In: Proceedings of ICALP 2015, part II. vol. 9135 of Lecture Notes in Computer Science p. 273\u2013285, (2015)","DOI":"10.1007\/978-3-662-47666-6_22"},{"key":"10139_CR2","unstructured":"Nivat, M.: Invited talk at the 24th International Colloquium on Automata, Languages, and Programming (ICALP 1997)"},{"key":"10139_CR3","unstructured":"Greenfeld, R., Tao, T.: A counterexample to the periodic tiling conjecture. arXiv:2211.15847"},{"key":"10139_CR4","doi-asserted-by":"crossref","unstructured":"Heikkil\u00e4, E., Herva, P., Kari, J.: On Perfect Coverings of Two-Dimensional Grids. In: Diekert V, Volkov MV, editors. Developments in Language Theory -26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings. vol. 13257 of Lecture Notes in Computer Science. Springer; p. 152\u2013163 (2022)","DOI":"10.1007\/978-3-031-05578-2_12"},{"key":"10139_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104481","volume":"271","author":"J Kari","year":"2020","unstructured":"Kari, J., Szabados, M.: An algebraic geometric approach to Nivat\u2019s conjecture. Information and Computation. 271, 104481 (2020)","journal-title":"Information and Computation."},{"key":"10139_CR6","doi-asserted-by":"crossref","unstructured":"Kari, J.: Low-Complexity Tilings of the Plane. In: Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019. vol. 11612 of Lecture Notes in Computer Science. Springer; p. 35\u201345 (2019)","DOI":"10.1007\/978-3-030-23247-4_2"},{"issue":"1","key":"10139_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/S0002-9947-97-01634-6","volume":"349","author":"M Boyle","year":"1997","unstructured":"Boyle, M., Lind, D.: Expansive Subdynamics. Trans. Am. Math Soc. 349(1), 55\u2013102 (1997)","journal-title":"Expansive Subdynamics. Trans. Am. Math Soc."},{"key":"10139_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1","volume-title":"Cellular Automata and Groups","author":"T Ceccherini-Silberstein","year":"2010","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin Heidelberg (2010)"},{"key":"10139_CR9","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/0118025","volume":"18","author":"SW Golomb","year":"1970","unstructured":"Golomb, S.W., Welch, L.R.: Perfect Codes in the Lee Metric and the Packing of Polyominoes. Siam J Appl Math. 18, 302\u2013317 (1970)","journal-title":"Siam J Appl Math."},{"issue":"4","key":"10139_CR10","doi-asserted-by":"publisher","first-page":"3048","DOI":"10.1109\/TIT.2017.2786675","volume":"64","author":"P Horak","year":"2018","unstructured":"Horak, P., Kim, D.: 50 Years of the Golomb-Welch Conjecture. IEEE Transactions on Information Theory. 64(4), 3048\u20133061 (2018)","journal-title":"IEEE Transactions on Information Theory."},{"key":"10139_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s002220050056","volume":"124","author":"JC Lagarias","year":"1996","unstructured":"Lagarias, J.C., Wang, Y.: Tiling the Line with Translates of One Tile. Invent. Math. 124, 341\u2013365 (1996)","journal-title":"Invent. Math."},{"key":"10139_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1353\/ajm.2020.0006","volume":"142","author":"S Bhattacharya","year":"1996","unstructured":"Bhattacharya, S.: Periodicity and decidability of tilings of $$\\mathbb{Z} ^{2}$$. Am J Math. 142, 255\u2013266 (1996)","journal-title":"Am J Math."},{"key":"10139_CR13","unstructured":"Greenfeld, R., Tao, T.: The structure of translational tilings in $$\\mathbb{Z} ^d$$. Discrete Anal. (2021)"},{"key":"10139_CR14","unstructured":"Szegedy, M.: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat No98CB36280). p. 137\u2013145 (1998)"},{"issue":"9","key":"10139_CR15","doi-asserted-by":"publisher","first-page":"6487","DOI":"10.1090\/S0002-9947-2015-06391-0","volume":"367","author":"V Cyr","year":"2015","unstructured":"Cyr, V., Kra, B.: Nonexpansive $$\\mathbb{Z} ^d$$-subdynamics and Nivat\u2019s conjecture. Trans. Am. Math Soc. 367(9), 6487\u20136537 (2015)","journal-title":"Trans. Am. Math Soc."},{"key":"10139_CR16","unstructured":"Ballier, A., Durand B., Jeandal. E. Structural aspects of tilings. In: Albers S, Weil P, editors. 25th International Symposium on Theoretical Aspects of Computer Science. vol.\u00a01 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, p. 61\u201372 (2008)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10139-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10139-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10139-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T09:03:57Z","timestamp":1696323837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10139-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10139"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10139-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"25 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}}]}}