A1 Refereed original research article in a scientific journal

An algebraic geometric approach to Nivat's conjecture




AuthorsJarkko Kari, Michal Szabados

PublisherElsevier Inc.

Publication year2020

JournalInformation and Computation

Journal name in sourceInformation and Computation

Volume271

eISSN1090-2651

DOIhttps://doi.org/10.1016/j.ic.2019.104481


Abstract

We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape D in the configuration is at most the size |D| of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes D.



Last updated on 2024-26-11 at 15:43