Some variants of the periodic tiling conjecture

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 ${G}$ , consider the following question:

Question 1 (Periodic tiling question) Let ${F}$ be a finite subset of ${G}$ . If there is a solution ${1_A}$ to the tiling equation ${1_F * 1_A = 1}$ , must there exist a periodic solution ${1_{A_p}}$ to the same equation ${1_F * 1_{A_p} = 1}$ ?

We know that the answer to this question is positive for finite groups ${H}$ (trivially, since all sets are periodic in this case), one-dimensional groups ${{\bf Z} \times H}$ with ${H}$ finite, and in ${{\bf Z}^2}$ , but it can fail for ${{\bf Z}^2 \times H}$ for certain finite ${H}$ , and also for ${{\bf Z}^d}$ for sufficiently large ${d}$ ; 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 ${f*a = 0}$ . Here the results are very satisfactory:

Theorem 2 (First periodic tiling result) Let ${G}$ be a discrete abelian group, and let ${f}$ 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 ${G}$ and ${f}$ as input, determines in finite time whether any of these assertions hold.

Now we turn to the inhomogeneous problem in ${{\bf Z}^2}$ , 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 ${G={\bf Z}^2}$ , let ${g}$ be periodic, and let ${f}$ be integer-valued and finitely supported. Then the following are equivalent.

(i) There exists an integer-valued solution ${a}$ to ${f*a=g}$ .

(ii) There exists a periodic integer-valued solution ${a_p}$ to ${f * a_p = g}$ .

Theorem 5 (Third periodic tiling result) Let ${G={\bf Z}^2}$ , let ${g}$ be periodic, and let ${f}$ be integer-valued and finitely supported. Then the following are equivalent.

(i) There exists an indicator function solution ${1_A}$ to ${f*1_A=g}$ .

(ii) There exists a periodic indicator function solution ${1_{A_p}}$ to ${f * 1_{A_p} = g}$ .

In particular, the previously established case of periodic tiling conjecture for level one tilings of ${{\bf Z}^2}$ , 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 ${g=1}$ ), but it also remains open whether Theorem 4 fails in that setting.

Following past literature, we rely heavily on a structure theorem for solutions ${a}$ to tiling equations ${f*a=g}$ , which roughly speaking asserts that such solutions ${a}$ must be expressible as a finite sum of functions ${\varphi_w}$ 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 ${p}$ for various large primes ${p}$ ).

For Theorem 2, one can take advantage of the fact that the homogeneous equation ${f*a=0}$ is preserved under finite difference operators ${\partial_h a(x) := a(x+h)-a(x)}$ : if ${a}$ solves ${f*a=0}$ , then ${\partial_h a}$ also solves the same equation ${f * \partial_h a = 0}$ . This freedom to take finite differences one to selectively eliminate certain one-periodic components ${\varphi_w}$ of a solution ${a}$ to the homogeneous equation ${f*a=0}$ 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 ${{\bf C}}$ to ${{\bf Q}}$ to convert a vanishing Fourier coefficient ${\hat f(\xi)= 0}$ into an integer solution to ${f*a=0}$ .

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 ${\varphi_w}$ of a solution ${a}$ to a tiling equation ${f*a=g}$ , but the conclusion now is that the these components are determined (modulo ${1}$ ) 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 ${f*a=g}$ 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 ${\varphi_w}$ 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 ${\varphi_w}$ ), there is also “combinatorial” data (roughly speaking, associated to the integer parts of ${\varphi_w}$ ) 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 ${a}$ .

It turns out that the restriction homomorphism approach is no longer available here (it makes the components ${\varphi_w}$ 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 ${\varphi_w}$ of an indicator function ${1_A}$ can only utilize linear polynomials (as opposed to polynomials of higher degree), and that one can partition ${{\bf Z}^2}$ 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 ${1_A}$ . 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 ${\{x\}}$ 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.

Source link

What's Hot

Emails Shed Light on UNC’s Plans to Create a New Accreditor

Wolfram|Alpha, Now in Simplified Chinese and Korean!—Wolfram Blog

June’s full ‘Strawberry Moon’ illuminates the night sky next week: Here’s how to see it

Some variants of the periodic tiling conjecture

Wolfram|Alpha, Now in Simplified Chinese and Korean!—Wolfram Blog

Case Study: How One School’s First World Maths Day Sparked Outstanding Results

Towards a Computational Formalization for Foundations of Medicine—Stephen Wolfram Writings

Worksheet on Percentage of a Number

January 2025 (with bad drawings) – Math with Bad Drawings

A Lean companion to “Analysis I”

10 Student Engagement Strategies That Empower Learners –

Do You Hear What I Hear? Audio Illusions and Misinformation

Improve your speech with immersive lessons!

Arabic poetry, with a special focus on Palestine – Global Studies Blog

Alexis’s Spring Semester in Granada

Balancing Study and Student Life | Study in Ireland

Archives, Libraries, Memory and Narrative – Global Studies Blog

Postgraduate Medical Education in Germany

Our Picks

Emails Shed Light on UNC’s Plans to Create a New Accreditor

Wolfram|Alpha, Now in Simplified Chinese and Korean!—Wolfram Blog

Subscribe to Updates

What's Hot

Some variants of the periodic tiling conjecture

Related Posts

Subscribe to Updates