A counterexample to the periodic tiling conjecture

What's new 2022-09-20

Rachel Greenfeld and I have just uploaded to the arXiv our announcement “A counterexample to the periodic tiling conjecture“. This is an announcement of a longer paper that we are currently in the process of writing up (and hope to release in a few weeks), in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. This conjecture can be formulated in both discrete and continuous settings:

Conjecture 1 (Discrete periodic tiling conjecture) Suppose that ${F \subset {\bf Z}^d}$ is a finite set that tiles ${{\bf Z}^d}$ by translations (i.e., ${{\bf Z}^d}$ can be partitioned into translates of ${F}$ ). Then ${F}$ also tiles ${{\bf Z}^d}$ by translations periodically (i.e., the set of translations can be taken to be a periodic subset of ${{\bf Z}^d}$ ).

Conjecture 2 (Continuous periodic tiling conjecture) Suppose that ${\Omega \subset {\bf R}^d}$ is a bounded measurable set of positive measure that tiles ${{\bf R}^d}$ by translations up to null sets. Then ${\Omega}$ also tiles ${{\bf R}^d}$ by translations periodically up to null sets.

The discrete periodic tiling conjecture can be easily established for ${d=1}$ by the pigeonhole principle (as first observed by Newman), and was proven for ${d=2}$ by Bhattacharya (with a new proof given by Greenfeld and myself). The continuous periodic tiling conjecture was established for ${d=1}$ by Lagarias and Wang. By an old observation of Hao Wang, one of the consequences of the (discrete) periodic tiling conjecture is that the problem of determining whether a given finite set ${F \subset {\bf Z}^d}$ tiles by translations is (algorithmically and logically) decidable.

On the other hand, once one allows tilings by more than one tile, it is well known that aperiodic tile sets exist, even in dimension two – finite collections of discrete or continuous tiles that can tile the given domain by translations, but not periodically. Perhaps the most famous examples of such aperiodic tilings are the Penrose tilings, but there are many other constructions; for instance, there is a construction of Ammann, Grümbaum, and Shephard of eight tiles in ${{\bf Z}^2}$ which tile aperiodically. Recently, Rachel and I constructed a pair of tiles in ${{\bf Z}^d}$ that tiled a periodic subset of ${{\bf Z}^d}$ aperiodically (in fact we could even make the tiling question logically undecidable in ZFC).

Our main result is then

Theorem 3 Both the discrete and continuous periodic tiling conjectures fail for sufficiently large ${d}$ . Also, there is a finite abelian group ${G_0}$ such that the analogue of the discrete periodic tiling conjecture for ${{\bf Z}^2 \times G_0}$ is false.

This suggests that the techniques used to prove the discrete periodic conjecture in ${{\bf Z}^2}$ are already close to the limit of their applicability, as they cannot handle even virtually two-dimensional discrete abelian groups such as ${{\bf Z}^2 \times G_0}$ . The main difficulty is in constructing the counterexample in the ${{\bf Z}^2 \times G_0}$ setting.

The approach starts by adapting some of the methods of a previous paper of Rachel and myself. The first step is make the problem easier to solve by disproving a “multiple periodic tiling conjecture” instead of the traditional periodic tiling conjecture. At present, Theorem 3 asserts the existence of a “tiling equation” ${A \oplus F = {\bf Z}^2 \times G_0}$ (where one should think of ${F}$ and ${G_0}$ as given, and the tiling set ${A}$ is known), which admits solutions, all of which are non-periodic. It turns out that it is enough to instead assert the existence of a system

$\displaystyle A \oplus F^{(m)} = {\bf Z}^2 \times G_0, m=1,\dots,M$

of tiling equations, which admits solutions, all of which are non-periodic. This is basically because one can “stack” together a system of tiling equations into an essentially equivalent single tiling equation in a slightly larger group. The advantage of this reformulation is that it creates a “tiling language”, in which each sentence ${A \oplus F^{(m)} = {\bf Z}^2 \times G_0}$ in the language expresses a different type of constraint on the unknown set ${A}$ . The strategy then is to locate a non-periodic set ${A}$ which one can try to “describe” by sentences in the tiling language that are obeyed by this non-periodic set, and which are “structured” enough that one can capture their non-periodic nature through enough of these sentences.

It is convenient to replace sets by functions, so that this tiling language can be translated to a more familiar language, namely the language of (certain types of) functional equations. The key point here is that the tiling equation

$\displaystyle A \oplus (\{0\} \times H) = G \times H$

for some abelian groups ${G, H}$ is precisely asserting that ${A}$ is a graph

$\displaystyle A = \{ (x, f(x)): x \in G \}$

of some function ${f: G \rightarrow H}$ (this sometimes referred to as the “vertical line test” in U.S. undergraduate math classes). Using this translation, it is possible to encode a variety of functional equations relating one or more functions ${f_i: G \rightarrow H}$ taking values in some finite group ${H}$ (such as a cyclic group).

The non-periodic behaviour that we ended up trying to capture was that of a certain “ ${p}$ -adically structured function” ${f_p: {\bf Z} \rightarrow ({\bf Z}/p{\bf Z})^\times}$ associated to some fixed and sufficiently large prime ${p}$ (in fact for our arguments any prime larger than ${48}$ , e.g., ${p=53}$ , would suffice), defined by the formula

$\displaystyle f_p(n) := \frac{n}{p^{\nu_p(n)}} \hbox{ mod } p$

for ${n \neq 0}$ and ${f_p(0)=1}$ , where ${\nu_p(n)}$ is the number of times ${p}$ divides ${n}$ . In other words, ${f_p(n)}$ is the last non-zero digit in the base ${p}$ expansion of ${n}$ (with the convention that the last non-zero digit of ${0}$ is ${1}$ ). This function is not periodic, and yet obeys a lot of functional equations; for instance, one has ${f_p(pn) = f_p(n)}$ for all ${n}$ , and also ${f_p(pn+j)=j}$ for ${j=1,\dots,p-1}$ (and in fact these two equations, together with the condition ${f_p(0)=1}$ , completely determine ${f_p}$ ). Here is what the function ${f_p}$ looks like:

It turns out that we cannot describe this one-dimensional non-periodic function directly via tiling equations. However, we can describe two-dimensional non-periodic functions such as ${(n,m) \mapsto f_p(An+Bm+C)}$ for some coefficients ${A,B,C}$ via a suitable system of tiling equations. A typical such function looks like this:

A feature of this function is that when one restricts to a row or diagonal of such a function, the resulting one-dimensional function exhibits “ ${p}$ -adic structure” in the sense that it behaves like a rescaled version of ${f_p}$ ; see the announcement for a precise version of this statement. It turns out that the converse is essentially true: after excluding some degenerate solutions in which the function is constant along one or more of the columns, all two-dimensional functions which exhibit ${p}$ -adic structure along (non-vertical) lines must behave like one of the functions ${(n,m) \mapsto f_p(An+Bm+C)}$ mentioned earlier, and in particular is non-periodic. The proof of this result is strongly reminiscent of the type of reasoning needed to solve a Sudoku puzzle, and so we have adopted some Sudoku-like terminology in our arguments to provide intuition and visuals. One key step is to perform a shear transformation to the puzzle so that many of the rows become constant, as displayed in this example,

and then perform a “Tetris” move of eliminating the constant rows to arrive at a secondary Sudoku puzzle which one then analyzes in turn:

It is the iteration of this procedure that ultimately generates the non-periodic ${p}$ -adic structure.