A counterexample to the periodic tiling conjecture

January 22, 2023

11

Rachel Greenfeld and I’ve simply uploaded to the arXiv our paper “A counterexample to the periodic tiling conjecture“. That is the total model of the outcome I introduced on this weblog a number of months in the past, wherein we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. The paper took just a little longer than anticipated to complete, as a consequence of a technical challenge that we didn’t understand on the time of the announcement that required a workaround.

In additional element: the unique technique, as described within the announcement, was to construct a “tiling language” that was able to encoding a sure “ ${p}$ -adic Sudoku puzzle”, after which present that the latter kind of puzzle had solely non-periodic options if ${p}$ was a sufficiently giant prime. Because it seems, the second half of this technique labored out, however there was a difficulty within the first half: our tiling language was in a position (utilizing ${2}$ -group-valued features) to encode arbitrary boolean relationships between boolean features, and was additionally in a position (utilizing ${{bf Z}/p{bf Z}}$ -valued features) to encode “clock” features comparable to ${n mapsto n hbox{ mod } p}$ that had been a part of our ${p}$ -adic Sudoku puzzle, however we weren’t capable of make these two forms of features “speak” to one another in the best way that was wanted to encode the ${p}$ -adic Sudoku puzzle (the essential downside being that if ${H}$ is a finite abelian ${2}$ -group then there aren’t any non-trivial subgroups of ${H times {bf Z}/p{bf Z}}$ that aren’t contained in ${H}$ or trivial within the ${{bf Z}/p{bf Z}}$ path). As a consequence, we needed to exchange our “ ${p}$ -adic Sudoku puzzle” by a “ ${2}$ -adic Sudoku puzzle” which principally quantities to changing the prime ${p}$ by a sufficiently giant energy of ${2}$ (we imagine ${2^{10}}$ will suffice). This solved the encoding challenge, however the evaluation of the ${2}$ -adic Sudoku puzzles was just a little bit extra difficult than the ${p}$ -adic case, for the next cause. The next is a pleasant train in evaluation:

Theorem 1 (Linearity in three instructions implies full linearity) Let ${F: {bf R}^2 rightarrow {bf R}}$ be a clean operate which is affine-linear on each horizontal line, diagonal (line of slope ${1}$ ), and anti-diagonal (line of slope ${-1}$ ). In different phrases, for any ${c in {bf R}}$ , the features ${x mapsto F(x,c)}$ , ${x mapsto F(x,c+x)}$ , and ${x mapsto F(x,c-x)}$ are every affine features on ${{bf R}}$ . Then ${F}$ is an affine operate on ${{bf R}^2}$ .

Certainly, the property of being affine in three instructions reveals that the quadratic kind related to the Hessian ${nabla^2 F(x,y)}$ at any given level vanishes at ${(1,0)}$ , ${(1,1)}$ , and ${(1,-1)}$ , and thus should vanish in every single place. Actually the smoothness speculation will not be crucial; we go away this as an train to the reader. The identical assertion seems to be true if one replaces ${{bf R}}$ with the cyclic group ${{bf Z}/p{bf Z}}$ so long as ${p}$ is odd; that is the important thing for us to displaying that our ${p}$ -adic Sudoku puzzles have an (approximate) two-dimensional affine construction, which on additional evaluation can then be used to indicate that it’s in truth non-periodic. Nonetheless, it seems that the corresponding declare for cyclic teams ${{bf Z}/q{bf Z}}$ can fail when ${q}$ is a sufficiently giant energy of ${2}$ ! Actually the final type of features ${F: ({bf Z}/q{bf Z})^2 rightarrow {bf Z}/q{bf Z}}$ which can be affine on each horizontal line, diagonal, and anti-diagonal takes the shape

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

for some integer coefficients ${A,B,C,D}$ . This extra “pseudo-affine” time period ${D frac{q}{4} y(x-y)}$ causes some extra technical issues however in the end seems to be manageable.

Through the writing course of we additionally found that the encoding a part of the proof turns into extra modular and conceptual as soon as one introduces two new definitions, that of an “expressible property” and a “weakly expressible property”. These ideas are considerably analogous to that of ${Pi^0_0}$ sentences and ${Sigma^0_1}$ sentences within the arithmetic hierarchy, or to algebraic units and semi-algebraic units in actual algebraic geometry. Roughly talking, an expressible property is a property of a tuple of features ${f_w: G rightarrow H_w}$ , ${w in {mathcal W}}$ from an abelian group ${G}$ to finite abelian teams ${H_w}$ , such that the property could be expressed by way of a number of 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 example, the property that two features ${f,g: {bf Z} rightarrow H}$ differ by a relentless could be expressed by way of the tiling equation

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

(the vertical line check), in addition to

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

the place ${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 features ${(f_w)_{w in W}}$ obeys the property ${P}$ if and provided that there exists an extension of this tuple by some extra features that obey the property ${P^*}$ . It seems that weakly expressible properties are closed below plenty of helpful operations, and permit us to simply assemble fairly difficult weakly expressible properties out of a “library” of easy weakly expressible properties, a lot as a posh pc program could be constructed out of easy library routines. Specifically we will “program” our Sudoku puzzle as a weakly expressible property.