Tag Archive

You are currently browsing the tag archive for the ‘periodic tiling conjecture’ tag.

A counterexample to the periodic tiling conjecture

29 November, 2022 in math.CO, paper | Tags: , | by | 46 comments

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.

A counterexample to the periodic tiling conjecture

19 September, 2022 in math.CO, paper | Tags: , , | by | 32 comments

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 (for {p=5}):

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.

Archives