Decidability and Periodicity of Low Complexity Tilings
Jarkko Kari, Etienne Moutot · Theory of Computing Systems · 2021
Abstract In this paper we study colorings (or tilings) of the two-dimensional grid ${\mathbb {Z}}^{2}$ ℤ2 . A coloring is said to be valid with respect to a setPofn×mrectangular patterns if alln×msub-patterns of the coloring are inP. A coloringcis said to be of low complexity with respect to a rectangle if there exist $m,n\in \mathbb {N}$ m,n∈ℕ and a setPofn×mrectangular patterns such thatcis valid with respect toPand |P|≤nm. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. If Nivat’s conjecture is true, all valid colorings with respect toPsuch that |P|≤mnmust be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle. After that, we prove that thenmbound is multiplicatively optimal for the decidability of the domino problem, as for allε> 0 it is undecidable to determine if there exists a valid coloring for a given $m,n\in \mathbb {N}$ m,n∈ℕ and set of rectangular patternsPof sizen×msuch that |P|≤ (1 +ε)nm. We prove a slightly better bound in the case wherem=n, as well as constructing aperiodic SFTs of pretty low complexity. This paper is an extended version of a paper published in STACS 2020 (Kari and Moutot 12).