Rachel Greenfeld and I have just uploaded to the arXiv our paper Some variants of the periodic tiling conjecture. This paper explores variants of the periodic tiling phenomenon that, in some cases, a tile that can translationally tile a group, must also be able to translationally tile the group periodically. For instance, for a given discrete abelian group 
, consider the following question:
Question 1 (Periodic tiling question) Let 
be a finite subset of . If there is a solution 
to the tiling equation 
, must there exist a periodic solution 
to the same equation 
?
We know that the answer to this question is positive for finite groups 
(trivially, since all sets are periodic in this case), one-dimensional groups 
with finite, and in 
, but it can fail for 
for certain finite , and also for 
for sufficiently large 
; see this previous blog post for more discussion. But now one can consider other variants of this question:
We are able to obtain positive answers to three such analogues of the periodic tiling conjecture for three cases of this question. The first result (which was kindly shared with us by Tim Austin), concerns the homogeneous problem 
. Here the results are very satisfactory:
Theorem 2 (First periodic tiling result) Let be a discrete abelian group, and let 
be integer-valued and finitely supported. Then the following are equivalent.
By combining this result with an old result of Henry Mann about sums of roots of unity, as well as an even older decidability result of Wanda Szmielew, we obtain
Corollary 3 Any of the statements (i), (ii), (iii) is algorithmically decidable; there is an algorithm that, when given and as input, determines in finite time whether any of these assertions hold.
Now we turn to the inhomogeneous problem in , which is the first difficult case (periodic tiling type results are easy to establish in one dimension, and trivial in zero dimensions). Here we have two results:
Theorem 4 (Second periodic tiling result) Let 
, let 
be periodic, and let be integer-valued and finitely supported. Then the following are equivalent.
- (i) There exists an integer-valued solution
to 
.
- (ii) There exists a periodic integer-valued solution
to 
.
Theorem 5 (Third periodic tiling result) Let , let be periodic, and let be integer-valued and finitely supported. Then the following are equivalent.
- (i) There exists an indicator function solution to
.
- (ii) There exists a periodic indicator function solution to
.
In particular, the previously established case of periodic tiling conjecture for level one tilings of , is now extended to higher level. By an old argument of Hao Wang, we now know that the statements mentioned in Theorem 5 are now also algorithmically decidable, although it remains open whether the same is the case for Theorem 4. We know from past results that Theorem 5 cannot hold in sufficiently high dimension (even in the classic case 
), but it also remains open whether Theorem 4 fails in that setting.
Following past literature, we rely heavily on a structure theorem for solutions to tiling equations , which roughly speaking asserts that such solutions must be expressible as a finite sum of functions 
that are one-periodic (periodic in a single direction). This already explains why tiling is easy to understand in one dimension, and why the two-dimensional case is more tractable than the case of general dimension. This structure theorem can be obtained by averaging a dilation lemma, which is a somewhat surprising symmetry of tiling equations that basically arises from finite characteristic arguments (viewing the tiling equation modulo 
for various large primes ).
For Theorem 2, one can take advantage of the fact that the homogeneous equation 
is preserved under finite difference operators 
: if solves , then 
also solves the same equation 
. This freedom to take finite differences one to selectively eliminate certain one-periodic components of a solution to the homogeneous equation until the solution is a pure one-periodic function, at which point one can appeal to an induction on dimension, to equate parts (i) and (ii) of the theorem. To link up with part (iii), we also take advantage of the existence of retraction homomorphisms from 
to 
to convert a vanishing Fourier coefficient 
into an integer solution to .
The inhomogeneous results are more difficult, and rely on arguments that are specific to two dimensions. For Theorem 4, one can also perform finite differences to analyze various components of a solution to a tiling equation , but the conclusion now is that the these components are determined (modulo 
) by polynomials of one variable. Applying a retraction homomorphism, one can make the coefficients of these polynomials rational, which makes the polynomials periodic. This turns out to reduce the original tiling equation to a system of essentially local combinatorial equations, which allows one to “periodize” a non-periodic solution by periodically repeating a suitable block of the (retraction homomorphism applied to the) original solution.
Theorem 5 is significantly more difficult to establish than the other two results, because of the need to maintain the solution in the form of an indicator function. There are now two separate sources of aperiodicity to grapple with. One is the fact that the polynomials involved in the components may have irrational coefficients (see Theorem 1.3 of our previous paper for an explicit example of this for a level 4 tiling). The other is that in addition to the polynomials (which influence the fractional parts of the components ), there is also “combinatorial” data (roughly speaking, associated to the integer parts of ) which also interact with each other in a slightly non-local way. Once one can make the polynomial coefficients rational, there is enough periodicity that the periodization approach used for the second theorem can be applied to the third theorem; the main remaining challenge is to find a way to make the polynomial coefficients rational, while still maintaining the indicator function property of the solution .
It turns out that the restriction homomorphism approach is no longer available here (it makes the components unbounded, which makes the combinatorial problem too difficult to solve). Instead, one has to first perform a second moment analysis to discern more structure about the polynomials involved. It turns out that the components of an indicator function can only utilize linear polynomials (as opposed to polynomials of higher degree), and that one can partition into a finite number of cosets on which only three of these linear polynomials are “active” on any given coset. The irrational coefficients of these linear polynomials then have to obey some rather complicated, but (locally) finite, sentence in the theory of first-order linear inequalities over the rationals, in order to form an indicator function . One can then use the Weyl equidistribution theorem to replace these irrational coefficients with rational coefficients that obey the same constraints (although one first has to ensure that one does not accidentally fall into the boundary of the constraint set, where things are discontinuous). Then one can apply periodization to the remaining combinatorial data to conclude.
A key technical problem arises from the discontinuities of the fractional part operator 
at integers, so a certain amount of technical manipulation (in particular, passing at one point to a weak limit of the original tiling) is needed to avoid ever having to encounter this discontinuity.
