A counterexample to the periodic tiling conjecture

What's new 2022-11-30

Rachel Greenfeld and I have just uploaded to the arXiv our paper “A counterexample to the periodic tiling conjecture“. This is the full version of the result I announced on this blog a few months ago, in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. The paper took a little longer than expected to finish, due to a technical issue that we did not realize at the time of the announcement that required a workaround.

In more detail: the original strategy, as described in the announcement, was to build a “tiling language” that was capable of encoding a certain “ ${p}$ -adic Sudoku puzzle”, and then show that the latter type of puzzle had only non-periodic solutions if ${p}$ was a sufficiently large prime. As it turns out, the second half of this strategy worked out, but there was an issue in the first part: our tiling language was able (using ${2}$ -group-valued functions) to encode arbitrary boolean relationships between boolean functions, and was also able (using ${{\bf Z}/p{\bf Z}}$ -valued functions) to encode “clock” functions such as ${n \mapsto n \hbox{ mod } p}$ that were part of our ${p}$ -adic Sudoku puzzle, but we were not able to make these two types of functions “talk” to each other in the way that was needed to encode the ${p}$ -adic Sudoku puzzle (the basic problem being that if ${H}$ is a finite abelian ${2}$ -group then there are no non-trivial subgroups of ${H \times {\bf Z}/p{\bf Z}}$ that are not contained in ${H}$ or trivial in the ${{\bf Z}/p{\bf Z}}$ direction). As a consequence, we had to replace our “ ${p}$ -adic Sudoku puzzle” by a “ ${2}$ -adic Sudoku puzzle” which basically amounts to replacing the prime ${p}$ by a sufficiently large power of ${2}$ (we believe ${2^{10}}$ will suffice). This solved the encoding issue, but the analysis of the ${2}$ -adic Sudoku puzzles was a little bit more complicated than the ${p}$ -adic case, for the following reason. The following is a nice exercise in analysis:

Theorem 1 (Linearity in three directions implies full linearity) Let ${F: {\bf R}^2 \rightarrow {\bf R}}$ be a smooth function which is affine-linear on every horizontal line, diagonal (line of slope ${1}$ ), and anti-diagonal (line of slope ${-1}$ ). In other words, for any ${c \in {\bf R}}$ , the functions ${x \mapsto F(x,c)}$ , ${x \mapsto F(x,c+x)}$ , and ${x \mapsto F(x,c-x)}$ are each affine functions on ${{\bf R}}$ . Then ${F}$ is an affine function on ${{\bf R}^2}$ .

Indeed, the property of being affine in three directions shows that the quadratic form associated to the Hessian ${\nabla^2 F(x,y)}$ at any given point vanishes at ${(1,0)}$ , ${(1,1)}$ , and ${(1,-1)}$ , and thus must vanish everywhere. In fact the smoothness hypothesis is not necessary; we leave this as an exercise to the interested reader. The same statement turns out to be true if one replaces ${{\bf R}}$ with the cyclic group ${{\bf Z}/p{\bf Z}}$ as long as ${p}$ is odd; this is the key for us to showing that our ${p}$ -adic Sudoku puzzles have an (approximate) two-dimensional affine structure, which on further analysis can then be used to show that it is in fact non-periodic. However, it turns out that the corresponding claim for cyclic groups ${{\bf Z}/q{\bf Z}}$ can fail when ${q}$ is a sufficiently large power of ${2}$ ! In fact the general form of functions ${F: ({\bf Z}/q{\bf Z})^2 \rightarrow {\bf Z}/q{\bf Z}}$ that are affine on every horizontal line, diagonal, and anti-diagonal takes the form

$\displaystyle F(x,y) = Ax + By + C + D \frac{q}{4} y(x-y)$

for some integer coefficients ${A,B,C,D}$ . This additional “pseudo-affine” term ${D \frac{q}{4} y(x-y)}$ causes some additional technical complications but ultimately turns out to be manageable.

During the writing process we also discovered that the encoding part of the proof becomes more modular and conceptual once one introduces two new definitions, that of an “expressible property” and a “weakly expressible property”. These concepts are somewhat analogous to that of ${\Pi^0_0}$ sentences and ${\Sigma^0_1}$ sentences in the arithmetic hierarchy, or to algebraic sets and semi-algebraic sets in real algebraic geometry. Roughly speaking, an expressible property is a property of a tuple of functions ${f_w: G \rightarrow H_w}$ , ${w \in {\mathcal W}}$ from an abelian group ${G}$ to finite abelian groups ${H_w}$ , such that the property can be expressed in terms of one or more tiling equations on the graph

$\displaystyle A := \{ (x, (f_w(x))_{w \in {\mathcal W}} \subset G \times \prod_{w \in {\mathcal W}} H_w.$

For instance, the property that two functions ${f,g: {\bf Z} \rightarrow H}$ differ by a constant can be expressed in terms of the tiling equation

$\displaystyle A \oplus (\{0\} \times H^2) = {\bf Z} \times H^2$

(the vertical line test), as well as

$\displaystyle A \oplus (\{0\} \times \Delta \cup \{1\} \times (H^2 \backslash \Delta)) = G \times H^2,$

where ${\Delta = \{ (h,h): h \in H \}}$ is the diagonal subgroup of ${H^2}$ . A weakly expressible property ${P}$ is an existential quantification of some expressible property ${P^*}$ , so that a tuple of functions ${(f_w)_{w \in W}}$ obeys the property ${P}$ if and only if there exists an extension of this tuple by some additional functions that obey the property ${P^*}$ . It turns out that weakly expressible properties are closed under a number of useful operations, and allow us to easily construct quite complicated weakly expressible properties out of a “library” of simple weakly expressible properties, much as a complex computer program can be constructed out of simple library routines. In particular we will be able to “program” our Sudoku puzzle as a weakly expressible property.