# Low-Complexity Tilings of the Plane

Jarkko Kari

► To cite this version:

Jarkko Kari. Low-Complexity Tilings of the Plane. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.35-45, 10.1007/978-3-030-23247-4_2 . hal-02387291

HAL Id: hal-02387291

https://inria.hal.science/hal-02387291

Submitted on 29 Nov 2019

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Low-Complexity Tilings of the Plane

Jarkko Kari* (✉)

Department of Mathematics and Statistics, University of Turku, Finland
jkari@utu.fi

**Abstract.** A two-dimensional configuration is a coloring of the infinite grid $Z^2$ with finitely many colors. For a finite subset $D$ of $Z^2$, the $D$-patterns of a configuration are the colored patterns of shape $D$ that appear in the configuration. The number of distinct $D$-patterns of a configuration is a natural measure of its complexity. A configuration is considered having low complexity with respect to shape $D$ if the number of distinct $D$-patterns is at most $|D|$, the size of the shape. This extended abstract is a short review of an algebraic method to study periodicity of such low complexity configurations.

**Keywords:** Pattern complexity, periodicity, Nivat's conjecture, low complexity configurations, low complexity subshifts, commutative algebra, algebraic subshifts, domino problem

## 1 Introduction

Commutative algebra provides powerful tools to analyze low complexity configurations, that is, colorings of the two-dimensional grid that have sufficiently low number of different local patterns. If the colors are represented as numbers, the low complexity assumption implies that the configuration is a linear combination of its translated copies. This condition can be expressed as an annihilation property under the multiplication of a power series representation of the configuration by a non-zero two-variate polynomial, leading to the study of the ideal of all annihilating polynomials. It turns out that the ideal of annihilators is essentially a principal ideal generated by a product of so-called line polynomials, i.e., univariate polynomials of two-variate monomials. This opens up the possibility to obtain results on global structures of the configuration, such as its periodicity. We first proposed this approach in [9, 10] to study Nivat's conjecture. It led to a number of subsequent results [6–8, 14]. In this presentation we review the main results without proofs – the given references can be consulted for more details. We start by briefly recalling the notations and basic concepts.

### 1.1 Configurations and Periodicity

A $d$-dimensional *configuration* over a finite alphabet $A$ is an assignment of symbols of $A$ on the infinite grid $Z^d$. For any configuration $c \in A^{Z^d}$ and any

<footnote>* Research supported by the Academy of Finland grant 296018</footnote>
cell $\mathbf{u} \in \mathbb{Z}^d$, we denote by $c_{\mathbf{u}}$ the symbol that $c$ has in cell $\mathbf{u}$. For any vector $\mathbf{t} \in \mathbb{Z}^d$, the translation $\tau^{\mathbf{t}}$ by $\mathbf{t}$ shifts a configuration $c$ so that $\tau^{\mathbf{t}}(c)_{\mathbf{u}} = c_{\mathbf{u}-\mathbf{t}}$ for all $\mathbf{u} \in \mathbb{Z}^d$. We say that $c$ is periodic if $\tau^{\mathbf{t}}(c) = c$ for some non-zero $\mathbf{t} \in \mathbb{Z}^d$. In this case $\mathbf{t}$ is a vector of periodicity and $c$ is also termed t-periodic. We mostly consider the two-dimensional setting $d=2$. In this case, if there are two linearly independent vectors of periodicity then $c$ is called two-periodic. A two-periodic $c \in A^{\mathbb{Z}^2}$ has automatically horizontal and vertical vectors of periodicity $(k, 0)$ and $(0, k)$ for some $k > 0$, and consequently a vector of periodicity in every ratio- nal direction. A two-dimensional periodic configuration that is not two-periodic is called one-periodic.

## 1.2 Pattern Complexity

Let $D \subseteq \mathbb{Z}^d$ be a finite set of cells, a shape. A D-pattern is an assignment $p \in A^D$ of symbols in shape $D$. A (finite) pattern is a D-pattern for some finite $D$. Let us denote by $A^*$ the set of all finite patterns over alphabet $A$, where the dimension $d$ is assumed to be known from the context. We say that a finite pattern $p$ of shape $D$ appears in configuration $c$ if for some $\mathbf{t} \in \mathbb{Z}^d$ we have $\tau^{\mathbf{t}}(c)|_D = p$. We also say that $c$ contains pattern $p$. For a fixed $D$, the set of D-patterns that appear in a configuration $c$ is denoted by $\mathcal{L}_D(c)$. We denote by $\mathcal{L}(c)$ the set of all finite patterns that appear in $c$, i.e., the union of $\mathcal{L}_D(c)$ over all finite $D \subseteq \mathbb{Z}^d$.

The pattern complexity of a configuration $c$ with respect to a shape $D$ is the number of D-patterns that $c$ contains. A sufficiently low pattern complexity forces global regularities in a configuration. A relevant threshold happens when the pattern complexity is at most $|D|$, the number of cells in shape $D$. Hence we say that $c$ has low complexity with respect to shape $D$ if

$$|\mathcal{L}_D(c)| \leq |D|.$$

We call $c$ a low complexity configuration if it has low complexity with respect to some finite shape $D$.

## 1.3 Nivat's Conjecture

The original motivation to this work is the famous conjecture presented by Maurice Nivat in his keynote address for the 25th anniversary of the European Association for Theoretical Computer Science at ICALP 1997. It concerns two-dimensional configurations that have low complexity with respect to a rectangular shape.

Conjecture 1 ([12]). Let $c \in A^{\mathbb{Z}^2}$ be a two-dimensional configuration. If $c$ has low complexity with respect to some rectangle $D = \{1, \dots, n\} \times \{1, \dots, m\}$ then $c$ is periodic.

The conjecture is still open but several partial and related results have been established. The best general bound was proved in [5] where it was shown that
for any rectangle $D$ the condition $|\mathcal{L}_D(c)| \le |D|/2$ is enough to guarantee that $c$ is periodic. This fact can also be proved using the algebraic approach [14].

The analogous conjecture in dimensions higher than two fails, as does a similar claim in two dimensions for many other shapes than rectangles [4]. We return to Nivat's conjecture and our results on this problem in Section 2.

## 1.4 Basic Concepts of Symbolic Dynamics

Let $p \in A^D$ be a finite pattern of shape $D$. The set $[p] = \{c \in A^{\mathbb{Z}^d} | c|_D = p\}$ of configurations that have $p$ in domain $D$ is called the *cylinder* determined by $p$. The collection of cylinders $[p]$ is a base of a compact topology on $A^{\mathbb{Z}^d}$, the *prodiscrete* topology. The topology is equivalently defined by a metric on $A^{\mathbb{Z}^d}$ where two configurations are close to each other if they agree with each other on a large region around cell $0$ – the larger the region the closer they are. Cylinders are clopen in the topology: they are both open and closed.

A subset $X$ of $A^{\mathbb{Z}^2}$ is called a *subshift* if it is closed in the topology and closed under translations. By a compactness argument, every configuration $c$ that is not in $X$ contains a finite pattern $p$ that prevents it from being in $X$: no configuration that contains $p$ is in $X$. We can then as well define subshifts using forbidden patterns: given a set $P \subseteq A^*$ of finite patterns we define

$$X_P = \{c \in A^{\mathbb{Z}^d} | \mathcal{L}(c) \cap P = \emptyset\},$$

the set of configurations that do not contain any of the patterns in $P$. Set $X_P$ is a subshift, and every subshift is $X_P$ for some $P$. If $X = X_P$ for some finite $P$ then $X$ is a *subshift of finite type* (SFT).

In this work we are interested in subshifts that have low pattern complexity. For a subshift $X \subseteq A^{\mathbb{Z}^d}$ (or actually for any set $X$ of configurations) we define its language $\mathcal{L}(X) \subseteq A^*$ to be the set of all finite patterns that appear in some element of $X$, that is, the union of sets $\mathcal{L}(c)$ over all $c \in X$. For a fixed shape $D$, we analogously define $\mathcal{L}_D(X) = \mathcal{L}(X) \cap A^D$, the union of all $\mathcal{L}_D(c)$ over $c \in X$. We say that $X$ has low complexity with respect to shape $D$ if $|\mathcal{L}_D(X)| \le |D|$. For example, in Theorem 8 we fix shape $D$ and a small set $P \subseteq A^D$ of at most $|D|$ allowed patterns of shape $D$. Then $X = X_{A^D \setminus P} = \{c \in A^{\mathbb{Z}^d} | \mathcal{L}_D(c) \subseteq P\}$ is a low complexity SFT since $\mathcal{L}_D(X) \subseteq P$ and $|P| \le |D|$.

The *orbit* of a configuration $c$ is the set $\mathcal{O}(c) = \{\tau^t(c) | t \in \mathbb{Z}^2\}$ of all its translates, and the *orbit closure* $\overline{\mathcal{O}}(c)$ of $c$ is the topological closure of its orbit. The orbit closure is a subshift, and in fact it is the intersection of all subshifts that contain $c$. In terms of finite patterns, $c' \in \overline{\mathcal{O}}(c)$ if and only if every finite pattern that appears in $c'$ appears also in $c$. Of course, the orbit closure of a low complexity configuration is a low complexity subshift.

A configuration $c$ is called *uniformly recurrent* if for every $c' \in \overline{\mathcal{O}}(c)$ we have $\overline{\mathcal{O}}(c') = \overline{\mathcal{O}}(c)$. This is equivalent to $\overline{\mathcal{O}}(c)$ being a *minimal subshift* in the sense that it has no proper non-empty subshifts inside it. A classical result by Birkhoff on dynamical systems implies that every non-empty subshift contains a minimal
subshift, so there is a uniformly recurrent configuration in every non-empty subshift [3].

## 1.5 Algebraic Concepts

To use commutative algebra we assume that $A \subseteq \mathbb{Z}$, i.e., the symbols in the configurations are integers. We also maintain the assumption that $A$ is finite. We express a $d$-dimensional configuration $c \in A^{\mathbb{Z}^d}$ as a formal power series over $d$ variables $x_1, \dots, x_d$ where the monomials address cells in a natural manner $x_1^{u_1} \cdots x_d^{u_d} \leftarrow \left( u_1, \dots, u_d \right) \in \mathbb{Z}^d$, and the coefficients of the monomials in the power series are the symbols at the corresponding cells. Using the convenient vector notation $\mathbf{x} = (x_1, \dots, x_d)$ we write $\mathbf{x}^{\mathbf{u}} = x_1^{u_1} \cdots x_d^{u_d}$ for the monomial that represents cell $\mathbf{u} = (u_1, \dots, u_d) \in \mathbb{Z}^d$. Note that all our power series and polynomials are *Laurent* as we allow negative as well as positive powers of variables. Now the configuration $c \in A^{\mathbb{Z}^d}$ can be coded as the formal power series

$$c(\mathbf{x}) = \sum_{\mathbf{u} \in \mathbb{Z}^d} c_{\mathbf{u}} \mathbf{x}^{\mathbf{u}}.$$

Because $A \subseteq \mathbb{Z}$ is finite, the power series $c(\mathbf{x})$ is *integral* (the coefficients are integers) and *finitary* (there are only finitely many different coefficients). Henceforth we treat configurations as integral, finitary power series.

Note that the power series are indeed formal: the role of the variables is only to provide the position information on the grid. We may sum up two power series, or multiply a power series with a polynomial, but we never plug in any values in the variables. Multiplying a power series $c(\mathbf{x})$ by a monomial $\mathbf{x}^t$ simply adds $t$ to the exponents of all monomials, thus producing the power series of the translated configuration $\tau^t(c)$. Hence the configuration $c(\mathbf{x})$ is $t$-periodic if and only if $\mathbf{x}^t c(\mathbf{x}) = c(\mathbf{x})$, that is, if and only if $(\mathbf{x}^t - 1)c(\mathbf{x}) = 0$, the zero power series. Thus we can express the periodicity of a configuration in terms of its *annihilation* under the multiplication with a *difference binomial* $\mathbf{x}^t - 1$. Very naturally then we introduce the *annihilator ideal*

$$\mathrm{Ann}(c) = \{ f(\mathbf{x}) \in \mathbb{C}[\mathbf{x}^{\pm 1}] \mid f(\mathbf{x})c(\mathbf{x}) = 0 \}$$

containing all the polynomials that annihilate $c$. Here we use the notation $\mathbb{C}[\mathbf{x}^{\pm 1}]$ for the set of Laurent polynomials with complex coefficients. Note that $\mathrm{Ann}(c)$ is indeed an ideal of the Laurent polynomial ring $\mathbb{C}[\mathbf{x}^{\pm 1}]$.

Our first observation relates the low complexity assumption to annihilators. Namely, it is easy to see using elementary linear algebra that any low complexity configuration has at least some non-trivial annihilators:

**Lemma 2** ([9]). Let $c$ be a low complexity configuration. Then $\mathrm{Ann}(c)$ contains a non-zero polynomial.

One of the main results of [9] states that if a configuration $c$ is annihilated by a non-zero polynomial (e.g., due to low complexity) then it is automatically annihilated by a product of difference binomials.
**Theorem 3** ([9]). Let $c$ be a configuration annihilated by some non-zero polynomial. Then there exist pairwise linearly independent $\mathbf{t}_1, \dots, \mathbf{t}_m \in \mathbb{Z}^d$ such that

$$ (\mathbf{x}^{\mathbf{t}_1} - 1) \cdots (\mathbf{x}^{\mathbf{t}_m} - 1) \in \mathrm{Ann}(c). $$

Note that if $m = 1$ then the configuration is $\mathbf{t}_1$-periodic. Otherwise, for $m \ge 2$, annihilation by $(\mathbf{x}^{\mathbf{t}_1} - 1) \cdots (\mathbf{x}^{\mathbf{t}_m} - 1)$ can be considered a form of generalized periodicity.

In the two-dimensional setting $d = 2$ we find it sometimes more convenient to work with the *periodizer ideal*

$$ \mathrm{Per}(c) = \{ f(\mathbf{x}) \in \mathbb{C}[\mathbf{x}^{\pm 1}] \mid f(\mathbf{x})c(\mathbf{x}) \text{ is two-periodic} \} $$

that contains those two-variate Laurent polynomials whose product with configuration $c$ is two-periodic. Clearly also $\mathrm{Per}(c)$ is an ideal of the Laurent polynomial ring $\mathbb{C}[\mathbf{x}^{\pm 1}]$, and we have $\mathrm{Ann}(c) \subseteq \mathrm{Per}(c)$. In the two-dimensional case we have a very good understanding of the structure of the ideals $\mathrm{Ann}(c)$ and $\mathrm{Per}(c)$, see Theorems 9 and 10 in Section 3.

## 2 Contributions to Nivat's Conjecture

In [9] we reported an asymptotic result on Nivat's conjecture. The complete proof appeared in [10]. Recall that the Nivat's conjecture claims – taking the contrapositive of the original statement – that every non-periodic configuration has high complexity with respect to every rectangle. Our result states that this indeed holds for all sufficiently large rectangles:

**Theorem 4** ([9, 10]). Let $c$ be a two-dimensional configuration that is not periodic. Then $\mathcal{L}_D(c) > |D|$ holds for all but finitely many rectangles $D$.

Recall that Theorem 3 gives for a low complexity configuration an annihilator of the form $(\mathbf{x}^{\mathbf{t}_1} - 1) \cdots (\mathbf{x}^{\mathbf{t}_m} - 1)$. If $m = 1$ then $c$ is periodic, so it is interesting to consider the cases of $m \ge 2$. Szabados proved in [14] that Nivat's conjecture holds in the case $m = 2$. Note that this case is equivalent to $c$ being the sum of two periodic configurations [9].

**Theorem 5** ([14]). Let $c$ be a two-dimensional configuration that has low complexity with respect to some rectangle. If $c$ is the sum of two periodic configurations then $c$ itself is periodic.

We have also considered other types of configurations. Particularly interesting are uniformly recurrent configurations since they occur in all non-empty subshifts. Recently we proved that they satisfy Nivat's conjecture, even when rectangles are generalized to other *discrete convex shapes*. We call shape $D \subseteq \mathbb{Z}^2$ convex if $D = S \cap \mathbb{Z}^2$ for some convex set $S \subseteq \mathbb{R}^2$. In particular, every rectangle is convex.
**Theorem 6 ([6]).** *Two-dimensional uniformly recurrent configuration that has low complexity with respect to a finite discrete convex shape D is periodic.*

The presence of uniformly recurrent configurations in subshifts then directly
yields the following corollary.

**Theorem 7 ([6]).** Let $X$ be a non-empty two-dimensional subshift that has low complexity with respect to a finite discrete convex shape $D$. Then $X$ contains a periodic configuration. In particular, the orbit closure of a configuration that has low complexity with respect to $D$ contains a periodic configuration.

Note that the periodic element in the orbit closure of $c$ means that $c$ contains
arbitrarily large periodic regions.

The existence of periodic elements provides us with an algorithm to determine if a given low complexity SFT is empty. This is a classical argument by Hao Wang [16]: There is a semi-algorithm for non-emptiness of arbitrary SFTs, and there is a semi-algorithm for the existence of a periodic configuration in a two-dimensional SFT. The latter semi-algorithm is based on the fact that if a two-dimensional SFT contains a periodic configuration then it also contains a two-periodic configuration, and these can be effectively enumerated and tested. Now, since we know that a two-dimensional SFT that has low complexity with respect to a convex shape is either empty or contains a periodic configuration, the two semi-algorithms together yield an algorithm to test emptiness.

**Theorem 8 ([6]).** There is an algorithm that – given a set of at most $|D|$ patterns $P \subseteq A^D$ over a two-dimensional convex shape $D$ – determines whether there exists a configuration $c \in A^{\mathbb{Z}^2}$ such that $\mathcal{L}_D(c) \subseteq P$.

**3 Line Polynomials and the Structure of the Annihilator Ideal**

For a polynomial $f(\mathbf{x}) = \sum f_{\mathbf{u}}\mathbf{x}^{\mathbf{u}}$, we call $\text{Supp}(f) = \{\mathbf{u} \in \mathbb{Z}^d \mid f_{\mathbf{u}} \neq 0\}$ its *support*. A *line polynomial* is a polynomial with all its terms aligned on the same line: $f$ is a line polynomial in direction $\mathbf{u} \in \mathbb{Z}^d$ if and only if $\text{supp}(f)$ contains at least two elements and $\text{supp}(f) \subseteq \mathbb{Z}\mathbf{u}$. (Note that this definition differs slightly from the one in [9, 10] where the line containing the non-zero terms was not required to go through the origin. The definitions are the same up to multiplication by a monomial, i.e. a translation.) Multiplying a configuration by a line polynomial is a one-dimensional process: different discrete lines $\mathbf{v} + \mathbb{Z}\mathbf{u}$ in the direction $\mathbf{u}$ of the line polynomial get multiplied independently of each other.

Difference binomials $\mathbf{x}^t - 1$ are line polynomials so the special annihilator
provided by Theorem 3 is a product of line polynomials. Annihilation by a
difference binomial means periodicity – and this fact generalizes to any line
polynomial: a configuration that is annihilated by a line polynomial in direction $\mathbf{u}$
is $n\mathbf{u}$-periodic for some $n \in \mathbb{Z}$. This is due to the fact that the line polynomial
annihilator specifies a linear recurrence along the discrete lines in direction $\mathbf{u}$.
The annihilator and the periodizer ideals of a configuration have particularly nice forms in the two-dimensional setting. Recall that $\langle f \rangle = \{gf \mid g \in \mathbb{C}[\mathbf{x}^{\pm 1}]\}$ is the *principal ideal* generated by Laurent polynomial $f$. It turns out that a two-dimensional periodizer ideal is a principal ideal generated by a product of line polynomials.

**Theorem 9 (adapted from [10]).** Let $c$ be a two-dimensional configuration with a non-trivial annihilator. Then $\text{Per}(c) = \langle f \rangle$ for a product $f = f_1 \cdots f_m$ of some line polynomials $f_1, \ldots, f_m$.

By merging line polynomials in the same directions we can choose $f_i$ in the theorem above so that they are in pairwise linearly independent directions. In this case $m$, the number of line polynomial factors, only depends on $c$. We denote $m = \text{Ord}(c)$ and call it the *order of $c$*. If $\text{Ord}(c) = 1$ then $c$ is periodic, and Theorem 5 states that the Nivat's conjecture is true among configurations of order two.

Theorem 9 directly implies a simple structure on the annihilator ideal: any annihilation of $c$ factors through the two-periodic configuration $f_1 \cdots f_m c$.

**Theorem 10 ([10]).** Let $c$ be a two-dimensional configuration with a non-trivial annihilator. Then $\text{Ann}(c) = f_1 \cdots f_m H$ where $f_1, \ldots, f_m$ are line polynomials and $H$ is the annihilator ideal of the two-periodic configuration $f_1 \cdots f_m c$.

As pointed out above, if $c$ is annihilated by a line polynomial then $c$ is periodic. The structure of $\text{Per}(c)$ and $\text{Ann}(c)$ allows us to generalize this to other annihilators. If a two-dimensional configuration $c$ is annihilated (or even periodized) by a polynomial without any line polynomial factors then it follows from Theorem 9 that $\text{Per}(c)$ is generated by polynomial 1, that is, $c$ itself is already two-periodic. Similarly, if $\text{Per}(c)$ contains a polynomial whose line polynomial factors are all in a common direction then $\text{Per}(c) = \langle f \rangle$ is generated by a line polynomial $f$ in this direction, implying that $c$ has a line polynomial annihilator and is therefore periodic. Such situations have come up in the literature under the theme of covering codes on the grid [1].

**Example 11.** Consider the problem of placing identical broadcasting antennas on the grid $\mathbb{Z}^2$ in such a way that each cell that does not contain an antenna receives broadcast from exactly $a$ antennas and every cell containing an antenna receives exactly $b$ broadcasts. Assume that $D \subseteq \mathbb{Z}^2$ is the shape of coverage by an antenna at the origin. Let us represent this broadcast range as the Laurent polynomial $f(\mathbf{x}) = \sum_{\mathbf{u} \in D} \mathbf{x}^{\mathbf{u}}$. Let $c$ be a configuration over $A = \{0, 1\}$ where we interpret $c_{\mathbf{u}} = 1$ as the presence of an antenna in cell $\mathbf{u}$. Now, $c$ is a solution to the antenna placement problem if and only if $f(\mathbf{x})c(\mathbf{x})$ is the power series $(b-a)c(\mathbf{x})+a1(\mathbf{x})$ where $1(\mathbf{x})$ is the constant one power series $1(\mathbf{x}) = \sum_{\mathbf{u} \in \mathbb{Z}^2} \mathbf{x}^{\mathbf{u}}$. Indeed, $(b-a)c(\mathbf{x})+a1(\mathbf{x})$ has values $b$ and $a$ in cells containing and not containing an antenna, respectively. In other words, $c$ is a valid placement of antennas if and only if multiplying $c(\mathbf{x})$ with polynomial $f(\mathbf{x}) - (b-a)$ results in the two-periodic configuration $a1(\mathbf{x})$. If $f(\mathbf{x}) - (b-a)$ has no line polynomial factors
then we know that this condition forces $c$ to be two-periodic. For example, if $D = \{(x, y) \mid |x| + |y| \le 1\}$ so that each antenna only broadcasts to its own cell and the four neighboring cells, then $b-a \ne 1$ implies two-periodicity of any solution. $\square$

# 4 Low Complexity Configurations in Algebraic Subshifts

In [7] we considered low complexity configurations in algebraic subshifts where the alphabet $A$ is a finite field $\mathbb{F}_p$. As Lemma 2 works as well in this setup, we have that every low complexity configuration $c$ is annihilated by a non-zero polynomial $f \in \mathbb{F}_p[\mathbf{x}^{\pm 1}]$. We then have that $c$ is an element of the *algebraic subshift* $S_f = \{c \in A^{\mathbb{Z}^d} \mid fc = 0\}$ of all configurations over $A = \mathbb{F}_p$ that are annihilated by $f$. So, to prove Nivat's conjecture it is enough to prove it for elements of algebraic subshifts. Clearly $S_f$ is of finite type, defined by forbidden patterns of shape $D = -\text{Supp}(f)$. We remark that the theory of this type of algebraically defined subshifts is well developed, see for example [13].

**Example 12.** Let $A = \mathbb{F}_2$. The Ledrappier subshift (also known as the 3-dot system) is $S_f$ for $f = 1 + x_1 + x_2$. Elements of $S_f$ are the space-time diagrams of the binary state XOR cellular automaton that adds to the state of each cell modulo 2 the state of its left neighbor. $\square$

While Lemma 2 works just fine over finite fields $\mathbb{F}_p$, Theorem 3 does not: it is not true that every element of every algebraic subshift would be annihilated by a product of difference polynomials. However, configurations over $\mathbb{F}_p$ can be also considered as configurations over $\mathbb{Z}$, without making calculations modulo $p$. If a configuration $c$ over $\mathbb{F}_p$ has low complexity then it also has low complexity as a configuration over $\mathbb{Z}$, and thus in $\mathbb{Z}$ it has a special annihilator $(\mathbf{x}^{t_1}-1)\cdots(\mathbf{x}^{t_m}-1)$ provided by Theorem 3. Now, considering all calculations modulo $p$ we see that this special annihilator is also an annihilator over $\mathbb{F}_p$. We conclude that even over $\mathbb{F}_p$, every low complexity configuration has an annihilator that is a product of difference binomials.

**Example 13.** Let $c$ be a low complexity configuration in the Ledrappier subshift of Example 12. It is then annihilated by $f = 1 + x_1 + x_2$ and by some $g = (\mathbf{x}^{t_1}-1)\cdots(\mathbf{x}^{t_m}-1)$ that is a product of difference binomials. Because $f$ does not have line polynomial factors while all irreducible factors of $g$ are line polynomials, we have that $f$ and $g$ do not have any common factors. Replacing $x_2$ by $f-1-x_1$ in $g$, we can entirely eliminate variable $x_2$ from $g$, obtaining a new annihilator $g' = g - f'f$ of $c$ having no occurrence of variable $x_2$. This annihilator $g'(x_1)$ is non-zero because $f$ and $g$ do not have common factors, which implies that $c$ is horizontally periodic. We can repeat the same reasoning in the vertical direction, obtaining that $c$ is two periodic. $\square$

The reasoning in the example above can be generalized to other algebraic subshifts.
**Theorem 14** ([7]). Let $c$ be a low complexity configuration of an algebraic subshift $S_f$.

- If $f$ has no line polynomial factors then $c$ is two-periodic.

- If all line polynomial factors of $f$ are in a common direction then $c$ is periodic.

Note that in the theorem there is no assumption about the low complexity shape $D$, so the applicability of the theorem is not restricted to rectangles or convex shapes.

# 5 Conclusions and Perspectives

There remains many open questions for future study. Obviously, the full version of Nivat's conjecture is still unsolved. Our Theorem 6 suggests that perhaps periodicity is forced by the low complexity condition not only on rectangles but on other convex shapes as well, as conjectured by Julien Cassaigne in [4]. In his examples of non-periodic low complexity configurations, the low complexity shape $D$ is always non-convex. Moreover, all two-dimensional low complexity configurations that we know consist of periodic sublattices [4, 7]. For example, even lattice cells may form a configuration that is horizontally but not vertically periodic while the odd cells may have a vertical but no horizontal period. The interleaved non-periodic configuration may have low complexity with respect to a scatted shape $D$ that only sees cells of equal parity. We wonder if there exist any low complexity configurations without a periodic sublattice structure.

Theorem 5 proves Nivat's conjecture for configurations of order two. However, $\text{Ord}(c) = 2$ case is special in the sense that $c$ is then a sum of periodic configurations, that is, finitary power series. In general, any configuration with a non-trivial annihilator is a sum of periodic power series [9], but already when $\text{Ord}(c) = 3$ these power series may be necessarily non-finitary [8]. It seems then that proving Nivat's conjecture for configurations of order three would reflect the general case better than the order two case. We also remark that proving Nivat's conjecture (for all convex shapes) would render the results of Section 2 obsolete.

There are also very interesting questions concerning general low complexity SFTs. By Theorem 7, a two-dimensional SFT that is low complexity with respect to a convex shape contains periodic configurations. Might this be true for non-convex shapes as well ? If so, analogously to Theorem 8, this would yield and algorithm to decide emptiness of general low complexity SFTs. What about higher dimensions ? We do not know of any aperiodic low complexity SFT in any dimension $d$ of the space. The following example recalls a family of particularly interesting low complexity SFTs.

*Example 15.* A $d$-dimensional cluster tile is a finite subset $D \subseteq \mathbb{Z}^d$, and a co-tiler is a subset $C \subseteq \mathbb{Z}^d$ such that $C \oplus D = \mathbb{Z}^d$. Visually, $C$ gives positions where copies of tiles $D$ can be placed so that every cell gets covered by exactly one
tile. Looking at the situation from an arbitrary covered cell $\mathbf{u}$, we see that $C$ is
a co-tiler of $D$ if and only if the set $\mathbf{u} - D$ contains precisely one element of $C$,
for every $\mathbf{u} \in Z^d$. Representing a co-tiler $C$ as the indicator configuration $c_{\mathbf{u}} = 1$
if $\mathbf{u} \in C$ and $c_{\mathbf{u}} = 0$ if $\mathbf{u} \notin C$, we have that the set of valid co-tilers for tile $D$
is a low complexity SFT: The only allowed patterns of shape $-D$ are those that
contain single 1, and there are $|D|$ such patterns.

The periodic cluster tiling problem asks whether every tile that has a co-tiler also has a periodic co-tiler [11, 15]. This is a special case of the more general question on arbitrary low complexity SFTs discussed above. The periodic cluster tiling problem was recently answered affirmatively in the two-dimensional case [2]. In [9] we gave a simple algebraic proof in any number of dimensions for the case – originally handled in [15] – where $|D|$ is a prime number. □

Finally, the structure of the annihilator ideal is not known in dimension higher
than two. We wonder how Theorem 10 might generalize to the three-dimensional
setting.

References

1. Axenovich, M.A.: On multiple coverings of the infinite rectangular grid with balls of constant radius. Discrete Math. **268**(1), 31–48 (2003). https://doi.org/10.1016/S0012-365X(02)00744-6

2. Bhattacharya, S.: Periodicity and decidability of tilings of $Z^2$. CoRR abs/1602.05738 (2016). https://arxiv.org/abs/1602.05738

3. Birkhoff, G.D.: Quelques théorèmes sur le mouvement des systèmes dynamiques. Bull. Soc. Math. France **40**, 305–323 (1912). https://doi.org/10.24033/bsmf.909

4. Cassaigne, J.: Subword complexity and periodicity in two or more dimensions. In: Rozenberg, G., Thomas, W. (eds.) Developments in Language Theory. Foundations, Applications, and Perspectives. pp. 14–21. World Scientific (1999)

5. Cyr, V., Kra, B.: Nonexpansive $Z^2$-subdynamics and Nivat's Conjecture. Trans. Amer. Math. Soc. **367**(9), 6487–6537 (2015). https://doi.org/10.1090/S0002-9947-2015-06391-0

6. Kari, J., Moutot, E.: Decidability and periodicity of low complexity tilings. CoRR abs/1904.01267 (2019). http://arxiv.org/abs/1904.01267

7. Kari, J., Moutot, E.: Nivat's conjecture and pattern complexity in algebraic sub-shifts. Theoret. Comput. Sci. (2019), to appear. https://doi.org/10.1016/j.tcs.2018.12.029

8. Kari, J., Szabados, M.: An algebraic geometric approach to multidimensional words. In: Maletti, A. (ed.) CAI 2015. LNCS, vol. 9270, pp. 29–42. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23021-4_3

9. Kari, J., Szabados, M.: An algebraic geometric approach to Nivat's conjecture. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part II. LNCS, vol. 9135, pp. 273–285. Springer, Cham (2015). https://doi.org/10.1007/978-3-662-47666-6_22

10. Kari, J., Szabados, M.: An algebraic geometric approach to Nivat's conjecture. CoRR abs/1605.05929 (2016). http://arxiv.org/abs/1605.05929

11. Lagarias, J.C., Wang, Y.: Tiling the line with translates of one tile. Invent. Math. **124**, 341–365 (1996). https://doi.org/10.1007/s002220050056
12. Nivat, M.: Keynote address at the 25th anniversary of EATCS, during ICALP 1997

13. Schmidt, K.: Dynamical systems of algebraic origin. Progress in mathematics, Birkhäuser, Basel (1995). https://doi.org/10.1007/978-3-0348-0277-2

14. Szabados, M.: Nivat's conjecture holds for sums of two periodic configurations. In: Tjoa, A.M., Bellatreche, L., Biffl, S., Leeuwen van, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 539–551. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73117-9_38

15. Szegedy, M.: Algorithms to tile the infinite grid with finite clusters. In: Proc. 39th Annual Symposium on Foundations of Computer Science, FOCS 1998. pp. 137–147. IEEE Computer Society (1998). https://doi.org/10.1109/SFCS.1998.743437

16. Wang, H.: Proving theorems by pattern recognition – II. Bell Syst. Tech. J. 40(1), 1–41 (1961). https://doi.org/10.1002/j.1538-7305.1961.tb03975.x