You are currently browsing the tag archive for the ‘periodic tiling conjecture’ tag.
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 “-adic Sudoku puzzle”, and then show that the latter type of puzzle had only non-periodic solutions if
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
-group-valued functions) to encode arbitrary boolean relationships between boolean functions, and was also able (using
-valued functions) to encode “clock” functions such as
that were part of our
-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
-adic Sudoku puzzle (the basic problem being that if
is a finite abelian
-group then there are no non-trivial subgroups of
that are not contained in
or trivial in the
direction). As a consequence, we had to replace our “
-adic Sudoku puzzle” by a “
-adic Sudoku puzzle” which basically amounts to replacing the prime
by a sufficiently large power of
(we believe
will suffice). This solved the encoding issue, but the analysis of the
-adic Sudoku puzzles was a little bit more complicated than the
-adic case, for the following reason. The following is a nice exercise in analysis:
Theorem 1 (Linearity in three directions implies full linearity) Letbe a smooth function which is affine-linear on every horizontal line, diagonal (line of slope
), and anti-diagonal (line of slope
). In other words, for any
, the functions
,
, and
are each affine functions on
. Then
is an affine function on
.
Indeed, the property of being affine in three directions shows that the quadratic form associated to the Hessian at any given point vanishes at
,
, and
, 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
with the cyclic group
as long as
is odd; this is the key for us to showing that our
-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
can fail when
is a sufficiently large power of
! In fact the general form of functions
that are affine on every horizontal line, diagonal, and anti-diagonal takes the form
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 sentences and
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
,
from an abelian group
to finite abelian groups
, such that the property can be expressed in terms of one or more tiling equations on the graph
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 thatis a finite set that tiles
by translations (i.e.,
can be partitioned into translates of
). Then
also tiles
by translations periodically (i.e., the set of translations can be taken to be a periodic subset of
).
Conjecture 2 (Continuous periodic tiling conjecture) Suppose thatis a bounded measurable set of positive measure that tiles
by translations up to null sets. Then
also tiles
by translations periodically up to null sets.
The discrete periodic tiling conjecture can be easily established for by the pigeonhole principle (as first observed by Newman), and was proven for
by Bhattacharya (with a new proof given by Greenfeld and myself). The continuous periodic tiling conjecture was established for
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
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 which tile aperiodically. Recently, Rachel and I constructed a pair of tiles in
that tiled a periodic subset of
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. Also, there is a finite abelian group
such that the analogue of the discrete periodic tiling conjecture for
is false.
This suggests that the techniques used to prove the discrete periodic conjecture in are already close to the limit of their applicability, as they cannot handle even virtually two-dimensional discrete abelian groups such as
. The main difficulty is in constructing the counterexample in the
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” (where one should think of
and
as given, and the tiling set
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
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
The non-periodic behaviour that we ended up trying to capture was that of a certain “-adically structured function”
associated to some fixed and sufficiently large prime
(in fact for our arguments any prime larger than
, e.g.,
, would suffice), defined by the formula
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 for some coefficients
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 “-adic structure” in the sense that it behaves like a rescaled version of
; 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
-adic structure along (non-vertical) lines must behave like one of the functions
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 -adic structure.
Recent Comments