Nivat's conjecture

Interview ---------

What field of research does your thesis fall within?

My work lies at the intersection of discrete mathematics and theoretical computer science. In practice, this means that I use techniques from mathematics to answer questions that are more closely tied to theoretical computer science (the theoretical limits of computers, algorithms, logic, and so on).

My thesis, entitled Autour du problème du domino – Structures combinatoires et outils algébriques (Around the domino problem—combinatorial structures and algebraic tools), was jointly supervised by Jarkko Kari (University of Turku, Finland), Stéphan Thomassé and Nathalie Aubrun (ENS de Lyon, France). I conducted my research at both the ENS de Lyon and in Finland, and defended my thesis on July 15, 2020.

Why did you choose this topic?

Nivat's conjecture immediately appealed to me because of its complexity, despite its simple statement. It is also connected with tilings—for example, with the domino problem mentioned in the title of my thesis—which have interested me ever since my first internship in a research laboratory.

**The domino problem is as follows (see Tangente 198, the article ["Éblouissants pavages de Penrose"). We are given a finite set of tiles and asked whether copies of them can tile the plane. The problem was proved undecidable in 1966 by the American mathematician Robert Berger.]**

What can we learn about an image if we can see only a tiny piece of it at a time? A digital image is generally represented by an array of pixels, each with its own color. To ensure that the image is large enough, we shall imagine it to be infinite. It may then seem surprising that anything can be inferred about this infinite image when only a finite part of it is visible at any one time. Yet Nivat's conjecture says that the image must repeat if it contains too few distinct local patterns.

A brief linear detour ----------------------------

Before turning to the infinite two-dimensional image, let's look at an infinite one-dimensional line. Let A be a finite set—or alphabet—of colors (or letters) used to color every cell of an infinite line. Such a line is called periodic with period m if shifting it by m cells leaves it unchanged: it repeats indefinitely.

Imagine that we can observe this line only through a window of fixed width n. The number of patterns of size n that appear in the line is called the line's complexity, denoted by P(n).

An example of a coloring of an infinite line.

There are five patterns of size 3 in all, so P(3) = 5.

If a line is periodic with period n, then P(n) ≤ n. In 1938, the American mathematicians Harold Calvin Marston Morse (1892–1977) and Gustav Arnold Hedlund (1904–1993) proved that this in fact characterizes periodicity: a line is periodic if and only if there exists an integer n such that P(n) ≤ n. The proof of the Morse–Hedlund theorem is fairly elementary and offers a fresh look at a classic technique: proof by induction (see box).

An example of a periodic coloring of a line.

Patterns of size 3: P(3) = 3. Then, for every n greater than 3, P(n ) = 3.

Proof of the Morse–Hedlund theorem --------------------------------------

Let w be any word, that is, a sequence of letters from the alphabet A (indexed by the set

\mathbb{Z}

of integers). We already have P (n + 1) ≤ P (n). Indeed, every pattern of size n+1 begins with a pattern of size n, so there are at least P(n) patterns of size n + 1.

If there exists an n such that P (n + 1) = P(n), there are as many words of length n as there are words of length n + 1. Thus, every word of length n has a unique extension to a word of length n + 1.

Furthermore, since there are P (n) different patterns of size n, we know that two equal patterns in w occur m letters apart, where m ≤ P (n). In other words, there exists an integer i such that:

*w_i*_{+ 1}… *w_i*₊*_n = w_i*_{+ 1 +}*_m… w_i*_{+ 1 +}*_m*₊*_n*.

From this relation, we can prove that for every integer r, *w_i*₊*_r = w_i*₊*_m*₊*_r. To begin with, this equality holds for r between 1 and n. We then prove by induction on r that it holds when r is greater than n. Suppose it holds for some fixed r. Then our equality also holds for r + 1, since every pattern of size n has a unique extension to a pattern of size n + 1. Now, w_i*₊*_k = w_i*₊*_m*₊*_k for k between 1 and r, with r greater than n*; the words *w_i*_{+ 1}…*w_i*₊*_n and w_i*_{+ 1 +}*_m…w_i*_{+ 1 +}*_m*₊*_n therefore have the same last n letters, so they have the same extension. Hence w_i*₊*_r*_{+ 1} = *w_i*₊*_m*₊*_r*_{+ 1}, completing the induction.

The same argument shows that the equality holds for negative r.

But this equality says precisely that w is periodic with period m: we have proved that if there exists an n such that P (n + 1) = P (n), then w is periodic.

Now suppose that w is not periodic. By the preceding result, P (n + 1) > P (n) for every n. Let us prove by induction on n that P (n + 1) ≥ n + 1 when n is greater than 1.

We have P (1) ≥ 2, since w must contain at least two different letters if it is not to be periodic.

For the induction step, suppose that for some fixed n, P (n) ≥ n + 1. By the preceding result, P (n + 1) > P (n), so P (n) ≥ P (n) + 1. Combining this with the induction hypothesis gives P (n + 1) ≥ n + 1 + 1 = n + 2, completing the induction.

Taking the contrapositive and using the fact that every periodic word has complexity satisfying P (n) ≤ n, we obtain the Morse–Hedlund theorem.

In two dimensions ----------------------

Let's return to our original image. Instead of a line, we now have an infinite grid, colored using some finite alphabet A; such a coloring is called a configuration. A configuration is periodic with period vector

\vec{u}

(rather than just a number) if it is unchanged by translation by the vector

\vec{u}

A configuration with period vectors (1, 3) and (4, 0).

A pattern is now a rectangular portion of a configuration, of size m × n, and the complexity of a configuration is the number of different such rectangles that can be observed through this m × n "window." The complexity is denoted by P (m, n). As with the line, we would like to characterize the periodicity of a configuration in terms of its complexity. The analogue of the condition P (n) ≤ n would be P (m, n) ≤ mn, since mn is the area of the rectangle being observed.

Unfortunately, there can be no characterization like the Morse–Hedlund theorem: for example, there exists a periodic configuration with complexity P (m, n) = 2 *^m*⁺*ⁿ*^{+ 1}.

The converse direction of the characterization is the subject of a conjecture formulated in 1997 by Maurice Nivat (1937–2017), which now bears his name: every configuration for which there exist two integers m and n such that P(m, n) ≤ mn—a configuration said to have low complexity—must be periodic. Moreover, this bound is optimal, since there exist non-periodic configurations of complexity mn + 1.

Every window of size mn reveals mn different patterns containing one black cell (one for each cell in the rectangle), plus an entirely white pattern, giving a complexity of mn + 1. The configuration is not periodic: any translation moves the black cell to a different position.

What about dimension 3? -----------------------

A statement analogous to the Morse–Hedlund theorem is true in dimension 1 and conjectured in dimension 2. What about dimension 3? It is false!

In 3D, a configuration has low complexity relative to a parallelepiped of size mnk if its complexity P (m, n, k) is at most mnk. We can construct a non-periodic 3D configuration of low complexity: fix an integer n and consider an entirely white configuration except for two perpendicular infinite lines separated by n cells.

First, it is not periodic, since any translation will move at least one of the two lines. Moreover, its complexity relative to a cube of side n is P (n, n, n) = 2*n ² + 1, since the cube intersects at most one line. For n ≥ 3, we do indeed have P(n, n, n) < *n ³, so the configuration has low complexity.

Polynomial algebra to the rescue ------------------------------------------

A complete proof of Nivat's conjecture continues to withstand mathematicians' best efforts. As often happens, considerable progress was made when the problem was linked to another, a priori unrelated field: polynomial algebra. This connection, as surprising as it is fruitful, was brought to light by Jarkko Kari and Michal Szabados in 2015.

To understand this connection, let's see how a finite pattern can be represented by a polynomial. First, take an alphabet A made up of numbers—for example, a subset of the integers. A pattern p is a coloring (a "labeling") of an m × n rectangle by elements of A; the color—or rather, the number—at position (i, j) is denoted by *p_i*_,*_j*. The polynomial representing this pattern is then:

\text{Q}(x, y) = p_{1,1}xy + p_{2,1}x^2y + p_{1,2}xy^2 + ... = \sum^m_{i=1} \sum^n_{j=1} p_{i, j} x^{i}y^{j}.

We can now take a purely algebraic view of patterns by studying these polynomials!

The positions of the different monomials in a 3 × 2 pattern.

The pattern represented by 3xy + xy ² + 2x ² y + 3x ² y ²+ x³ y + 2x ² y ².

Generalizing this idea, we can represent configurations as "infinite polynomials" (called formal power series), whose coefficients are the numbers in the cells of the configuration. Kari and Szabados showed that polynomials whose product with a series is 0 are particularly important; they are called annihilating polynomials (see box).

Why annihilating polynomials? ------------------------------------

Take two configurations c and d, and construct the series C and D that represent them:

\text{C} = \sum^{+\infty}_{i=-\infty} \; \sum^{+\infty}_{j=-\infty} c_{i, j} \, x^{i}y^{j},

\text{D} = \sum^{+\infty}_{i=-\infty} \; \sum^{+\infty}_{j=-\infty} d_{i, j} \, x^{i}y^{j}.

With this formalism, we can see without calculation that multiplying a series by a monomial *x ^ay ^b amounts to translating the configuration by the vector (a, b*):

x^a y^b \text{C} = \sum^{+\infty}_{i=-\infty} \; \sum^{+\infty}_{j=-\infty} c_{i, j} \, x^{i + a }y^{j + b} = \sum^{+\infty}_{i=-\infty} \; \sum^{+\infty}_{j=-\infty} c_{i - a, \, j-b} \, x^{i}y^{j}.

This gives a purely algebraic characterization of periodicity: c is periodic if and only if there exist two integers a and b such that c equals its own translate by (a, b), which is equivalent to C = *x ^a y ^b C, or equivalently (x ^a y ^b* — 1) C = 0.

In short, c is periodic if and only if there is an annihilating polynomial of the form *x ^ay ^b* — 1. Studying annihilating polynomials thus provides an algebraic way to prove that a configuration is periodic.

Better still, all the annihilating polynomials of a configuration form a polynomial ideal, a mathematical object whose structure is relatively well understood.

By gaining a clearer picture of what annihilating polynomials can look like, Kari and Szabados were able to prove several new results.

First, every low-complexity configuration c can be written as a sum of periodic configurations c₁, c₂… *c_r, although these may have an infinite alphabet: c = c*₁ + c₂ +… + *c_r*.

They also prove an asymptotic version of Nivat's conjecture: if P(m, n) ≤ mn for infinitely many pairs of integers m and n, then the configuration is periodic.

Finally, by combining their algebraic approach with tools developed by Van Cyr and Bryna Kra, they prove that if a configuration is the sum of just two periodic configurations, then Nivat's conjecture holds for it.

In the thesis Around the Domino Problem—Combinatorial Structures and Algebraic Tools, these algebraic tools are developed further to obtain new results that come closer to Nivat's conjecture. Part of the research focused on uniformly recurrent configurations—that is, configurations containing no isolated patterns.

Eliminating troublesome directions --------------------------------------

The techniques developed by Cyr and Kra rely on the notion of determinism for a set X of configurations. X is said to be deterministic in a direction

\overrightarrow{u} \in \mathbb{Z}^2

if any two configurations in X that agree on a half-plane in that direction agree everywhere.

In other words, the restriction of a configuration to a half-plane in direction

\vec{u}

determines the entire configuration.

A half-plane in direction

\vec{u}

= (−1, 2). If at most one configuration in X has a given set of values on this half-plane, then X is deterministic in direction

\vec{u}

Maurice Paul Nivat (1937–2017).

Every direction is therefore either deterministic or non-deterministic. The last case left open by Cyr and Kra's work concerns directions

\vec{u}

for which X is deterministic in direction

\vec{u}

but non-deterministic in direction

-\vec{u}

. One of the thesis's most important results shows that, for uniformly recurrent configurations, these troublesome directions can in fact be "eliminated." This proves that Nivat's conjecture holds for uniformly recurrent configurations.

Uniformly what? -----------------------

Starting from a configuration c, we can construct its orbit O(c), which contains the translates of c by every vector

\vec{u}

\mathbb{Z}^2

. Taking the closure

\overline{O(c)}

of the orbit then gives a set containing every translate of c, together with the limits of these translates. A configuration is uniformly recurrent if, for every configuration c′ in

\overline{O(c)}

, we have

\overline{O(c')} = \overline{O(c)} .

In other words, no pattern in c can be "erased" even by translating it infinitely far.

The precise result proved in the thesis with Jarkko Kari shows that, for every low-complexity configuration,

\overline{O(c)}

contains a periodic configuration d. Note that if Nivat's conjecture is true, then every configuration in

\overline{O(c)}

is periodic.

Since d is periodic,

\overline{O(d)}

contains only periodic configurations. Now, because c is uniformly recurrent,

\overline{O(d)} = \overline{O(c)},

so every configuration in

\overline{O(c)}

is periodic, including c itself.

The last step in proving Nivat's conjecture is therefore to study configurations that are not uniformly recurrent. But these remain poorly understood, leaving the conjecture out of reach for now.