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 “-adic Sudoku puzzle”, after which present that the latter kind of puzzle had solely non-periodic options if 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 -group-valued features) to encode arbitrary boolean relationships between boolean features, and was additionally in a position (utilizing -valued features) to encode “clock” features comparable to that had been a part of our -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 -adic Sudoku puzzle (the essential downside being that if is a finite abelian -group then there aren’t any non-trivial subgroups of that aren’t contained in or trivial within the path). As a consequence, we needed to exchange our “-adic Sudoku puzzle” by a “-adic Sudoku puzzle” which principally quantities to changing the prime by a sufficiently giant energy of (we imagine will suffice). This solved the encoding challenge, however the evaluation of the -adic Sudoku puzzles was just a little bit extra difficult than the -adic case, for the next cause. The next is a pleasant train in evaluation:

Theorem 1 (Linearity in three instructions implies full linearity)Let be a clean operate which is affine-linear on each horizontal line, diagonal (line of slope ), and anti-diagonal (line of slope ). In different phrases, for any , the features , , and are every affine features on . Then is an affine operate on .

Certainly, the property of being affine in three instructions reveals that the quadratic kind related to the Hessian at any given level vanishes at , , and , 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 with the cyclic group so long as is odd; that is the important thing for us to displaying that our -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 can fail when is a sufficiently giant energy of ! Actually the final type of features which can be affine on each horizontal line, diagonal, and anti-diagonal takes the shape

for some integer coefficients . This extra “pseudo-affine” time period 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 sentences and 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 , from an abelian group to finite abelian teams , such that the property could be expressed by way of a number of tiling equations on the graph

For example, the property that two features differ by a relentless could be expressed by way of the tiling equation

(the vertical line check), in addition to

the place is the diagonal subgroup of . A weakly expressible property is an existential quantification of some expressible property , so {that a} tuple of features obeys the property if and provided that there exists an extension of this tuple by some extra features that obey the property . 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.