Undecidability of translational monotilings

What's new 2023-09-19

Rachel Greenfeld and I have just uploaded to the arXiv our paper “Undecidability of translational monotilings“. This is a sequel to our previous paper in which we constructed a translational monotiling ${A \oplus F = {\bf Z}^d}$ of a high-dimensional lattice ${{\bf Z}^d}$ (thus the monotile ${F}$ is a finite set and the translates ${a+F}$ , ${a \in A}$ of ${F}$ partition ${{\bf Z}^d}$ ) which was aperiodic (there is no way to “repair” this tiling into a periodic tiling ${A' \oplus F = {\bf Z}^d}$ , in which ${A'}$ is now periodic with respect to a finite index subgroup of ${{\bf Z}^d}$ ). This disproved the periodic tiling conjecture of Stein, Grunbaum-Shephard and Lagarias-Wang, which asserted that such aperiodic translational monotilings do not exist. (Compare with the “hat monotile“, which is a recently discovered aperiodic isometric monotile for of ${{\bf R}^2}$ , where one is now allowed to use rotations and reflections as well as translations, or the even more recent “spectre monotile“, which is similar except that no reflections are needed.)

One of the motivations of this conjecture was the observation of Hao Wang that if the periodic tiling conjecture were true, then the translational monotiling problem is (algorithmically) decidable: there is a Turing machine which, when given a dimension ${d}$ and a finite subset ${F}$ of ${{\bf Z}^d}$ , can determine in finite time whether ${F}$ can tile ${{\bf Z}^d}$ . This is because if a periodic tiling exists, it can be found by computer search; and if no tiling exists at all, then (by the compactness theorem) there exists some finite subset of ${{\bf Z}^d}$ that cannot be covered by disjoint translates of ${F}$ , and this can also be discovered by computer search. The periodic tiling conjecture asserts that these are the only two possible scenarios, thus giving the decidability.

On the other hand, Wang’s argument is not known to be reversible: the failure of the periodic tiling conjecture does not automatically imply the undecidability of the translational monotiling problem, as it does not rule out the existence of some other algorithm to determine tiling that does not rely on the existence of a periodic tiling. (For instance, even with the newly discovered hat and spectre tiles, it remains an open question whether the isometric monotiling problem for (say) polygons with rational coefficients in ${{\bf R}^2}$ is decidable, with or without reflections.)

The main result of this paper settles this question (with one caveat):

Theorem 1 There does not exist any algorithm which, given a dimension ${d}$ , a periodic subset ${E}$ of ${{\bf Z}^d}$ , and a finite subset ${F}$ of ${{\bf Z}^d}$ , determines in finite time whether there is a translational tiling ${A \oplus F = E}$ of ${E}$ by ${F}$ .

The caveat is that we have to work with periodic subsets ${E}$ of ${{\bf Z}^d}$ , rather than all of ${{\bf Z}^d}$ ; we believe this is largely a technical restriction of our method, and it is likely that can be removed with additional effort and creativity. We also remark that when ${d=2}$ , the periodic tiling conjecture was established by Bhattacharya, and so the problem is decidable in the ${d=2}$ case. It remains open whether the tiling problem is decidable for any fixed value of ${d>2}$ (note in the above result that the dimension ${d}$ is not fixed, but is part of the input).

Because of a well known link between algorithmic undecidability and logical undecidability (also known as logical independence), the main theorem also implies the existence of an (in principle explicitly describable) dimension ${d}$ , periodic subset ${E}$ of ${{\bf Z}^d}$ , and a finite subset ${F}$ of ${{\bf Z}^d}$ , such that the assertion that ${F}$ tiles ${E}$ by translation cannot be proven or disproven in ZFC set theory (assuming of course that this theory is consistent).

As a consequence of our method, we can also replace ${{\bf Z}^d}$ here by “virtually two-dimensional” groups ${{\bf Z}^2 \times G_0}$ , with ${G_0}$ a finite abelian group (which now becomes part of the input, in place of the dimension ${d}$ ).

We now describe some of the main ideas of the proof. It is a common technique to show that a given problem is undecidable by demonstrating that some other problem that was already known to be undecidable can be “encoded” within the original problem, so that any algorithm for deciding the original problem would also decide the embedded problem. Accordingly, we will encode the Wang tiling problem as a monotiling problem in ${{\bf Z}^d}$ :

Problem 2 (Wang tiling problem) Given a finite collection ${{\mathcal W}}$ of Wang tiles (unit squares with each side assigned some color from a finite palette), is it possible to tile the plane with translates of these tiles along the standard lattice ${{\bf Z}^2}$ , such that adjacent tiles have matching colors along their common edge?

It is a famous result of Berger that this problem is undecidable. The embedding of this problem into the higher-dimensional translational monotiling problem proceeds through some intermediate problems. Firstly, it is an easy matter to embed the Wang tiling problem into a similar problem which we call the domino problem:

Problem 3 (Domino problem) Given a finite collection ${{\mathcal R}_1}$ (resp. ${{\mathcal R}_2}$ ) of horizontal (resp. vertical) dominoes – pairs of adjacent unit squares, each of which is decorated with an element of a finite set ${{\mathcal W}}$ of “pips”, is it possible to assign a pip to each unit square in the standard lattice tiling of ${{\bf Z}^2}$ , such that every horizontal (resp. vertical) pair of squares in this tiling is decorated using a domino from ${{\mathcal R}_1}$ (resp. ${{\mathcal R}_2}$ )?

Indeed, one just has to interpet each Wang tile as a separate “pip”, and define the domino sets ${{\mathcal R}_1}$ , ${{\mathcal R}_2}$ to be the pairs of horizontally or vertically adjacent Wang tiles with matching colors along their edge.

Next, we embed the domino problem into a Sudoku problem:

Problem 4 (Sudoku problem) Given a column width ${N}$ , a digit set ${\Sigma}$ , a collection ${{\mathcal S}}$ of functions ${g: \{0,\dots,N-1\} \rightarrow \Sigma}$ , and an “initial condition” ${{\mathcal C}}$ (which we will not detail here, as it is a little technical), is it possible to assign a digit ${F(n,m)}$ to each cell ${(n,m)}$ in the “Sudoku board” ${\{0,1,\dots,N-1\} \times {\bf Z}}$ such that for any slope ${j \in {\bf Z}}$ and intercept ${i \in {\bf Z}}$ , the digits ${n \mapsto F(n,jn+i)}$ along the line ${\{(n,jn+i): 0 \leq n \leq N-1\}}$ lie in ${{\mathcal S}}$ (and also that ${F}$ obeys the initial condition ${{\mathcal C}}$ )?

The most novel part of the paper is the demonstration that the domino problem can indeed be embedded into the Sudoku problem. The embedding of the Sudoku problem into the monotiling problem follows from a modification of the methods in our previous papers, which had also introduced versions of the Sudoku problem, and created a “tiling language” which could be used to “program” various problems, including the Sudoku problem, as monotiling problems.

To encode the domino problem into the Sudoku problem, we need to take a domino function ${{\mathcal T}: {\bf Z}^2 \rightarrow {\mathcal W}}$ (obeying the domino constraints associated to some domino sets ${{\mathcal R}_1, {\mathcal R}_2}$ ) and use it to build a Sudoku function ${F: \{0,\dots,N-1\} \times {\bf Z} \rightarrow \Sigma}$ (obeying some Sudoku constraints relating to the domino sets); conversely, every Sudoku function obeying the rules of our Sudoku puzzle has to arise somehow from a domino function. The route to doing so was not immediately obvious, but after a helpful tip from Emmanuel Jeandel, we were able to adapt some ideas of Aanderaa and Lewis, in which certain hierarchical structures were used to encode one problem in another. Here, we interpret hierarchical structure ${p}$ -adically (using two different primes due to the two-dimensionality of the domino problem). The Sudoku function ${F}$ that will exemplify our embedding is then built from ${{\mathcal T}}$ by the formula

$\displaystyle F(n,m) := ( f_{p_1}(m), f_{p_2}(m), {\mathcal T}(\nu_{p_1}(m), \nu_{p_2}(m)) ) \ \ \ \ \ (1)$ where ${p_1,p_2}$ are two large distinct primes (for instance one can take ${p_1=53}$ , ${p_2=57}$ for concreteness), ${\nu_p(m)}$ denotes the number of times ${p}$ divides ${m}$ , and ${f_p(m) \in {\bf Z}/p{\bf Z} \backslash \{0\}}$ is the last non-zero digit in the base ${p}$ expansion of ${m}$ :

$\displaystyle f_p(m) := \frac{m}{p^{\nu_p(m)}} \hbox{ mod } p$ (with the conventions ${\nu_p(0)=+\infty}$ and ${f_p(0)=1}$ ). In the case ${p_1=3, p_2=5}$ , the first component of (1) looks like this:

and a typical instance of the final component ${{\mathcal T}(\nu_{p_1}(m), \nu_{p_2}(m))}$ looks like this:

Amusingly, the decoration here is essentially following the rules of the children’s game “Fizz buzz“.

To demonstrate the embedding, we thus need to produce a specific Sudoku rule ${{\mathcal S}}$ (as well as a more technical initial condition ${{\mathcal C}}$ , which is basically required to exclude degenerate Sudoku solutions such as a constant solution) that can “capture” the target function (1), in the sense that the only solutions to this specific Sudoku puzzle are given by variants of ${F}$ (e.g., ${F}$ composed with various linear transformations). In our previous paper we were able to build a Sudoku puzzle that could similarly capture either of the first two components ${f_{p_1}(m)}$ , ${f_{p_2}(m)}$ of our target function (1) (up to linear transformations), by a procedure very akin to solving an actual Sudoku puzzle (combined with iterative use of a “Tetris” move in which we eliminate rows of the puzzle that we have fully solved, to focus on the remaining unsolved rows). Our previous paper treated the case when ${p}$ was replaced with a power of ${2}$ , as this was the only case that we know how to embed in a monotiling problem of the entirety of ${{\bf Z}^d}$ (as opposed to a periodic subset ${E}$ of ${{\bf Z}^d}$ ), but the analysis is in fact easier when ${p}$ is a large odd prime, instead of a power of ${2}$ . Once the first two components ${f_{p_1}(m), f_{p_2}(m)}$ have been solved for, it is a relatively routine matter to design an additional constraint in the Sudoku rule that then constrains the third component to be of the desired form ${{\mathcal T}(\nu_{p_1}(m), \nu_{p_2}(m))}$ , with ${{\mathcal T}}$ obeying the domino constraints.