Tag Archive

You are currently browsing the tag archive for the ‘tiling’ tag.

A counterexample to the periodic tiling conjecture

19 September, 2022 in math.CO, paper | Tags: , , | by | 32 comments

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 that {F \subset {\bf Z}^d} is a finite set that tiles {{\bf Z}^d} by translations (i.e., {{\bf Z}^d} can be partitioned into translates of {F}). Then {F} also tiles {{\bf Z}^d} by translations periodically (i.e., the set of translations can be taken to be a periodic subset of {{\bf Z}^d}).

Conjecture 2 (Continuous periodic tiling conjecture) Suppose that {\Omega \subset {\bf R}^d} is a bounded measurable set of positive measure that tiles {{\bf R}^d} by translations up to null sets. Then {\Omega} also tiles {{\bf R}^d} by translations periodically up to null sets.

The discrete periodic tiling conjecture can be easily established for {d=1} by the pigeonhole principle (as first observed by Newman), and was proven for {d=2} by Bhattacharya (with a new proof given by Greenfeld and myself). The continuous periodic tiling conjecture was established for {d=1} 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 {F \subset {\bf Z}^d} 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 {{\bf Z}^2} which tile aperiodically. Recently, Rachel and I constructed a pair of tiles in {{\bf Z}^d} that tiled a periodic subset of {{\bf Z}^d} 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 {d}. Also, there is a finite abelian group {G_0} such that the analogue of the discrete periodic tiling conjecture for {{\bf Z}^2 \times G_0} is false.

This suggests that the techniques used to prove the discrete periodic conjecture in {{\bf Z}^2} are already close to the limit of their applicability, as they cannot handle even virtually two-dimensional discrete abelian groups such as {{\bf Z}^2 \times G_0}. The main difficulty is in constructing the counterexample in the {{\bf Z}^2 \times G_0} 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” {A \oplus F = {\bf Z}^2 \times G_0} (where one should think of {F} and {G_0} as given, and the tiling set {A} 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

\displaystyle A \oplus F^{(m)} = {\bf Z}^2 \times G_0, m=1,\dots,M

of tiling equations, which admits solutions, all of which are non-periodic. This is basically because one can “stack” together a system of tiling equations into an essentially equivalent single tiling equation in a slightly larger group. The advantage of this reformulation is that it creates a “tiling language”, in which each sentence {A \oplus F^{(m)} = {\bf Z}^2 \times G_0} in the language expresses a different type of constraint on the unknown set {A}. The strategy then is to locate a non-periodic set {A} which one can try to “describe” by sentences in the tiling language that are obeyed by this non-periodic set, and which are “structured” enough that one can capture their non-periodic nature through enough of these sentences.

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

\displaystyle A \oplus (\{0\} \times H) = G \times H

for some abelian groups {G, H} is precisely asserting that {A} is a graph

\displaystyle A = \{ (x, f(x)): x \in G \}

of some function {f: G \rightarrow H} (this sometimes referred to as the “vertical line test” in U.S. undergraduate math classes). Using this translation, it is possible to encode a variety of functional equations relating one or more functions {f_i: G \rightarrow H} taking values in some finite group {H} (such as a cyclic group).

The non-periodic behaviour that we ended up trying to capture was that of a certain “{p}-adically structured function” {f_p: {\bf Z} \rightarrow ({\bf Z}/p{\bf Z})^\times} associated to some fixed and sufficiently large prime {p} (in fact for our arguments any prime larger than {48}, e.g., {p=53}, would suffice), defined by the formula

\displaystyle f_p(n) := \frac{n}{p^{\nu_p(n)}} \hbox{ mod } p

for {n \neq 0} and {f_p(0)=1}, where {\nu_p(n)} is the number of times {p} divides {n}. In other words, {f_p(n)} is the last non-zero digit in the base {p} expansion of {n} (with the convention that the last non-zero digit of {0} is {1}). This function is not periodic, and yet obeys a lot of functional equations; for instance, one has {f_p(pn) = f_p(n)} for all {n}, and also {f_p(pn+j)=j} for {j=1,\dots,p-1} (and in fact these two equations, together with the condition {f_p(0)=1}, completely determine {f_p}). Here is what the function {f_p} looks like (for {p=5}):

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 {(n,m) \mapsto f_p(An+Bm+C)} for some coefficients {A,B,C} 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 “{p}-adic structure” in the sense that it behaves like a rescaled version of {f_p}; 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 {p}-adic structure along (non-vertical) lines must behave like one of the functions {(n,m) \mapsto f_p(An+Bm+C)} 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 {p}-adic structure.

Measurable tilings by abelian group actions

3 March, 2022 in math.DS, math.MG, paper | Tags: , , , | by | 9 comments


Jan Grebik, Rachel Greenfeld, Vaclav Rozhon and I have just uploaded to the arXiv our preprint “Measurable tilings by abelian group actions“. This paper is related to an earlier paper of Rachel Greenfeld and myself concerning tilings of lattices {{\bf Z}^d}, but now we consider the more general situation of tiling a measure space {X} by a tile {A \subset X} shifted by a finite subset {F} of shifts of an abelian group {G = (G,+)} that acts in a measure-preserving (or at least quasi-measure-preserving) fashion on {X}. For instance, {X} could be a torus {{\bf T}^d = {\bf R}^d/{\bf Z}^d}, {A} could be a positive measure subset of that torus, and {G} could be the group {{\bf R}^d}, acting on {X} by translation.


If {F} is a finite subset of {G} with the property that the translates {f+A}, {f \in F} of {A \subset X} partition {X} up to null sets, we write {F \oplus A =_{a.e.} X}, and refer to this as a measurable tiling of {X} by {A} (with tiling set {F}). For instance, if {X} is the torus {{\bf T}^2}, we can create a measurable tiling with {A = [0,1/2]^2 \hbox{ mod } {\bf Z}^2} and {F = \{0,1/2\}^2}. Our main results are the following:

  • By modifying arguments from previous papers (including the one with Greenfeld mentioned above), we can establish the following “dilation lemma”: a measurable tiling {F \oplus A =_{a.e.} X} automatically implies further measurable tilings {rF \oplus A =_{a.e.} X}, whenever {r} is an integer coprime to all primes up to the cardinality {\# F} of {F}.
  • By averaging the above dilation lemma, we can also establish a “structure theorem” that decomposes the indicator function {1_A} of {A} into components, each of which are invariant with respect to a certain shift in {G}. We can establish this theorem in the case of measure-preserving actions on probability spaces via the ergodic theorem, but one can also generalize to other settings by using the device of “measurable medial means” (which relates to the concept of a universally measurable set).
  • By applying this structure theorem, we can show that all measurable tilings {F \oplus A = {\bf T}^1} of the one-dimensional torus {{\bf T}^1} are rational, in the sense that {F} lies in a coset of the rationals {{\bf Q} = {\bf Q}^1}. This answers a recent conjecture of Conley, Grebik, and Pikhurko; we also give an alternate proof of this conjecture using some previous results of Lagarias and Wang.
  • For tilings {F \oplus A = {\bf T}^d} of higher-dimensional tori, the tiling need not be rational. However, we can show that we can “slide” the tiling to be rational by giving each translate {f + A} of {A} a “velocity” {v_f \in {\bf R}^d}, and for every time {t}, the translates {f + tv_f + A} still form a partition of {{\bf T}^d} modulo null sets, and at time {t=1} the tiling becomes rational. In particular, if a set {A} can tile a torus in an irrational fashion, then it must also be able to tile the torus in a rational fashion.
  • In the two-dimensional case {d=2} one can arrange matters so that all the velocities {v_f} are parallel. If we furthermore assume that the tile {A} is connected, we can also show that the union of all the translates {f+A} with a common velocity {v_f = v} form a {v}-invariant subset of the torus.
  • Finally, we show that tilings {F \oplus A = {\bf Z}^d \times G} of a finitely generated discrete group {{\bf Z}^d \times G}, with {G} a finite group, cannot be constructed in a “local” fashion (we formalize this probabilistically using the notion of a “factor of iid process”) unless the tile {F} is contained in a single coset of {\{0\} \times G}. (Nonabelian local tilings, for instance of the sphere by rotations, are of interest due to connections with the Banach-Tarski paradox; see the aforementioned paper of Conley, Grebik, and Pikhurko. Unfortunately, our methods seem to break down completely in the nonabelian case.)

Perfectly packing a square by squares of nearly harmonic sidelength

8 February, 2022 in math.MG, paper | Tags: | by | 41 comments

I’ve just uploaded to the arXiv my preprint “Perfectly packing a square by squares of nearly harmonic sidelength“. This paper concerns a variant of an old problem of Meir and Moser, who asks whether it is possible to perfectly pack squares of sidelength {1/n} for {n \geq 2} into a single square or rectangle of area {\sum_{n=2}^\infty \frac{1}{n^2} = \frac{\pi^2}{6} - 1}. (The following variant problem, also posed by Meir and Moser and discussed for instance in this MathOverflow post, is perhaps even more well known: is it possible to perfectly pack rectangles of dimensions {1/n \times 1/(n+1)} for {n \geq 1} into a single square of area {\sum_{n=1}^\infty \frac{1}{n(n+1)} = 1}?) For the purposes of this paper, rectangles and squares are understood to have sides parallel to the axes, and a packing is perfect if it partitions the region being packed up to sets of measure zero. As one partial result towards these problems, it was shown by Paulhus that squares of sidelength {1/n} for {n \geq 2} can be packed (not quite perfectly) into a single rectangle of area {\frac{\pi^2}{6} - 1 + \frac{1}{1244918662}}, and rectangles of dimensions {1/n \times 1/n+1} for {n \geq 1} can be packed (again not quite perfectly) into a single square of area {1 + \frac{1}{10^9+1}}. (Paulhus’s paper had some gaps in it, but these were subsequently repaired by Grzegorek and Januszewski.)

Another direction in which partial progress has been made is to consider instead the problem of packing squares of sidelength {n^{-t}}, {n \geq 1} perfectly into a square or rectangle of total area {\sum_{n=1}^\infty \frac{1}{n^{2t}}}, for some fixed constant {t > 1/2} (this lower bound is needed to make the total area {\sum_{n=1}^\infty \frac{1}{n^{2t}}} finite), with the aim being to get {t} as close to {1} as possible. Prior to this paper, the most recent advance in this direction was by Januszewski and Zielonka last year, who achieved such a packing in the range {1/2 < t \leq 2/3}.

In this paper we are able to get {t} arbitrarily close to {1} (which turns out to be a “critical” value of this parameter), but at the expense of deleting the first few tiles:

Theorem 1 If {1/2 < t < 1}, and {n_0} is sufficiently large depending on {t}, then one can pack squares of sidelength {n^{-t}}, {n \geq n_0} perfectly into a square of area {\sum_{n=n_0}^\infty \frac{1}{n^{2t}}}.

As in previous works, the general strategy is to execute a greedy algorithm, which can be described somewhat incompletely as follows.

  • Step 1: Suppose that one has already managed to perfectly pack a square {S} of area {\sum_{n=n_0}^\infty \frac{1}{n^{2t}}} by squares of sidelength {n^{-t}} for {n_0 \leq n < n_1}, together with a further finite collection {{\mathcal R}} of rectangles with disjoint interiors. (Initially, we would have {n_1=n_0} and {{\mathcal R} = \{S\}}, but these parameter will change over the course of the algorithm.)
  • Step 2: Amongst all the rectangles in {{\mathcal R}}, locate the rectangle {R} of the largest width (defined as the shorter of the two sidelengths of {R}).
  • Step 3: Pack (as efficiently as one can) squares of sidelength {n^{-t}} for {n_1 \leq n < n_2} into {R} for some {n_2>n_1}, and decompose the portion of {R} not covered by this packing into rectangles {{\mathcal R}'}.
  • Step 4: Replace {n_1} by {n_2}, replace {{\mathcal R}} by {({\mathcal R} \backslash \{R\}) \cup {\mathcal R}'}, and return to Step 1.

The main innovation of this paper is to perform Step 3 somewhat more efficiently than in previous papers.

The above algorithm can get stuck if one reaches a point where one has already packed squares of sidelength {1/n^t} for {n_0 \leq n < n_1}, but that all remaining rectangles {R} in {{\mathcal R}} have width less than {n_1^{-t}}, in which case there is no obvious way to fit in the next square. If we let {w(R)} and {h(R)} denote the width and height of these rectangles {R}, then the total area of the rectangles must be

\displaystyle \sum_{R \in {\mathcal R}} w(R) h(R) = \sum_{n=n_0}^\infty \frac{1}{n^{2t}} - \sum_{n=n_0}^{n_1-1} \frac{1}{n^{2t}} \asymp n_1^{1-2t}

and the total perimeter {\mathrm{perim}({\mathcal R})} of these rectangles is

\displaystyle \mathrm{perim}({\mathcal R}) = \sum_{R \in {\mathcal R}} 2(w(R)+h(R)) \asymp \sum_{R \in {\mathcal R}} h(R).

Thus we have

\displaystyle n_1^{1-2t} \ll \mathrm{perim}({\mathcal R}) \sup_{R \in {\mathcal R}} w(R)

and so to ensure that there is at least one rectangle {R} with {w(R) \geq n_1^{-t}} it would be enough to have the perimeter bound

\displaystyle \mathrm{perim}({\mathcal R}) \leq c n_1^{1-t}

for a sufficiently small constant {c>0}. It is here that we now see the critical nature of the exponent {t=1}: for {t<1}, the amount of perimeter we are permitted to have in the remaining rectangles increases as one progresses with the packing, but for {t=1} the amount of perimeter one is “budgeted” for stays constant (and for {t>1} the situation is even worse, in that the remaining rectangles {{\mathcal R}} should steadily decrease in total perimeter).

In comparison, the perimeter of the squares that one has already packed is equal to

\displaystyle \sum_{n=n_0}^{n_1-1} 4 n^{-t}

which is comparable to {n_1^{1-t}} for {n_1} large (with the constants blowing up as {t} approaches the critical value of {1}). In previous algorithms, the total perimeter of the remainder rectangles {{\mathcal R}} was basically comparable to the perimeter of the squares already packed, and this is the main reason why the results only worked when {t} was sufficiently far away from {1}. In my paper, I am able to get the perimeter of {{\mathcal R}} significantly smaller than the perimeter of the squares already packed, by grouping those squares into lattice-like clusters (of about {M^2} squares arranged in an {M \times M} pattern), and sliding the squares in each cluster together to almost entirely eliminate the wasted space between each square, leaving only the space around the cluster as the main source of residual perimeter, which will be comparable to about {M n_1^{-t}} per cluster, as compared to the total perimeter of the squares in the cluster which is comparable to {M^2 n_1^{-t}}. This strategy is perhaps easiest to illustrate with a picture, in which {3 \times 4} squares {S_{i,j}} of slowly decreasing sidelength are packed together with relatively little wasted space:

By choosing the parameter {M} suitably large (and taking {n_0} sufficiently large depending on {M}), one can then prove the theorem. (In order to do some technical bookkeeping and to allow one to close an induction in the verification of the algorithm’s correctness, it is convenient to replace the perimeter {\sum_{R \in {\mathcal R}} 2(w(R)+h(R))} by a slightly weighted variant {\sum_{R \in {\mathcal R}} w(R)^\delta h(R)} for a small exponent {\delta}, but this is a somewhat artificial device that somewhat obscures the main ideas.)

Undecidable translational tilings with only two tiles, or one nonabelian tile

19 August, 2021 in math.CO, math.LO, paper | Tags: , , | by | 19 comments

Rachel Greenfeld and I have just uploaded to the arXiv our preprint “Undecidable translational tilings with only two tiles, or one nonabelian tile“. This paper studies the following question: given a finitely generated group {G}, a (periodic) subset {E} of {G}, and finite sets {F_1,\dots,F_J} in {G}, is it possible to tile {E} by translations {a_j+F_j} of the tiles {F_1,\dots,F_J}? That is to say, is there a solution {\mathrm{X}_1 = A_1, \dots, \mathrm{X}_J = A_J} to the (translational) tiling equation

\displaystyle (\mathrm{X}_1 \oplus F_1) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J) = E \ \ \ \ \ (1)

for some subsets {A_1,\dots,A_J} of {G}, where {A \oplus F} denotes the set of sums {\{a+f: a \in A, f \in F \}} if the sums {a+f} are all disjoint (and is undefined otherwise), and {\uplus} denotes disjoint union. (One can also write the tiling equation in the language of convolutions as {1_{\mathrm{X}_1} * 1_{F_1} + \dots + 1_{\mathrm{X}_J} * 1_{F_J} = 1_E}.)

A bit more specifically, the paper studies the decidability of the above question. There are two slightly different types of decidability one could consider here:

  • Logical decidability. For a given {G, E, J, F_1,\dots,F_J}, one can ask whether the solvability of the tiling equation (1) is provable or disprovable in ZFC (where we encode all the data {G, E, F_1,\dots,F_J} by appropriate constructions in ZFC). If this is the case we say that the tiling equation (1) (or more precisely, the solvability of this equation) is logically decidable, otherwise it is logically undecidable.
  • Algorithmic decidability. For data {G,E,J, F_1,\dots,F_J} in some specified class (and encoded somehow as binary strings), one can ask whether the solvability of the tiling equation (1) can be correctly determined for all choices of data in this class by the output of some Turing machine that takes the data as input (encoded as a binary string) and halts in finite time, returning either YES if the equation can be solved or NO otherwise. If this is the case, we say the tiling problem of solving (1) for data in the given class is algorithmically decidable, otherwise it is algorithmically undecidable.

Note that the notion of logical decidability is “pointwise” in the sense that it pertains to a single choice of data {G,E,J,F_1,\dots,F_J}, whereas the notion of algorithmic decidability pertains instead to classes of data, and is only interesting when this class is infinite. Indeed, any tiling problem with a finite class of data is trivially decidable because one could simply code a Turing machine that is basically a lookup table that returns the correct answer for each choice of data in the class. (This is akin to how a student with a good memory could pass any exam if the questions are drawn from a finite list, merely by memorising an answer key for that list of questions.)

The two notions are related as follows: if a tiling problem (1) is algorithmically undecidable for some class of data, then the tiling equation must be logically undecidable for at least one choice of data for this class. For if this is not the case, one could algorithmically decide the tiling problem by searching for proofs or disproofs that the equation (1) is solvable for a given choice of data; the logical decidability of all such solvability questions will ensure that this algorithm always terminates in finite time.

One can use the Gödel completeness theorem to interpret logical decidability in terms of universes (also known as structures or models) of ZFC. In addition to the “standard” universe {{\mathfrak U}} of sets that we believe satisfies the axioms of ZFC, there are also other “nonstandard” universes {{\mathfrak U}^*} that also obey the axioms of ZFC. If the solvability of a tiling equation (1) is logically undecidable, this means that such a tiling exists in some universes of ZFC, but not in others.

(To continue the exam analogy, we thus see that a yes-no exam question is logically undecidable if the answer to the question is yes in some parallel universes, but not in others. A course syllabus is algorithmically undecidable if there is no way to prepare for the final exam for the course in a way that guarantees a perfect score (in the standard universe).)

Questions of decidability are also related to the notion of aperiodicity. For a given {G, E, J, F_1,\dots,F_J}, a tiling equation (1) is said to be aperiodic if the equation (1) is solvable (in the standard universe {{\mathfrak U}} of ZFC), but none of the solutions (in that universe) are completely periodic (i.e., there are no solutions {\mathrm{X}_1 = A_1,\dots, \mathrm{X}_J = A_J} where all of the {A_1,\dots,A_J} are periodic). Perhaps the most well-known example of an aperiodic tiling (in the context of {{\bf R}^2}, and using rotations as well as translations) come from the Penrose tilings, but there are many others besides.

It was (essentially) observed by Hao Wang in the 1960s that if a tiling equation is logically undecidable, then it must necessarily be aperiodic. Indeed, if a tiling equation fails to be aperiodic, then (in the standard universe) either there is a periodic tiling, or there are no tilings whatsoever. In the former case, the periodic tiling can be used to give a finite proof that the tiling equation is solvable; in the latter case, the compactness theorem implies that there is some finite fragment of {E} that is not compatible with being tiled by {F_1,\dots,F_J}, and this provides a finite proof that the tiling equation is unsolvable. Thus in either case the tiling equation is logically decidable.

This observation of Wang clarifies somewhat how logically undecidable tiling equations behave in the various universes of ZFC. In the standard universe, tilings exist, but none of them will be periodic. In nonstandard universes, tilings may or may not exist, and the tilings that do exist may be periodic (albeit with a nonstandard period); but there must be at least one universe in which no tiling exists at all.

In one dimension when {G={\bf Z}} (or more generally {G = {\bf Z} \times G_0} with {G_0} a finite group), a simple pigeonholing argument shows that no tiling equations are aperiodic, and hence all tiling equations are decidable. However the situation changes in two dimensions. In 1966, Berger (a student of Wang) famously showed that there exist tiling equations (1) in the discrete plane {E = G = {\bf Z}^2} that are aperiodic, or even logically undecidable; in fact he showed that the tiling problem in this case (with arbitrary choices of data {J, F_1,\dots,F_J}) was algorithmically undecidable. (Strictly speaking, Berger established this for a variant of the tiling problem known as the domino problem, but later work of Golomb showed that the domino problem could be easily encoded within the tiling problem.) This was accomplished by encoding the halting problem for Turing machines into the tiling problem (or domino problem); the latter is well known to be algorithmically undecidable (and thus have logically undecidable instances), and so the latter does also. However, the number of tiles {J} required for Berger’s construction was quite large: his construction of an aperiodic tiling required {J = 20426} tiles, and his construction of a logically undecidable tiling required an even larger (and not explicitly specified) collection of tiles. Subsequent work by many authors did reduce the number of tiles required; in the {E=G={\bf Z}^2} setting, the current world record for the fewest number of tiles in an aperiodic tiling is {J=8} (due to Amman, Grunbaum, and Shephard) and for a logically undecidable tiling is {J=11} (due to Ollinger). On the other hand, it is conjectured (see Grunbaum-Shephard and Lagarias-Wang) that one cannot lower {J} all the way to {1}:

Conjecture 1 (Periodic tiling conjecture) If {E} is a periodic subset of a finitely generated abelian group {G}, and {F} is a finite subset of {G}, then the tiling equation {\mathrm{X} \oplus F = E} is not aperiodic.

This conjecture is known to be true in two dimensions (by work of Bhattacharya when {G=E={\bf Z}^2}, and more recently by us when {E \subset G = {\bf Z}^2}), but remains open in higher dimensions. By the preceding discussion, the conjecture implies that every tiling equation with a single tile is logically decidable, and the problem of whether a given periodic set can be tiled by a single tile is algorithmically decidable.

In this paper we show on the other hand that aperiodic and undecidable tilings exist when {J=2}, at least if one is permitted to enlarge the group {G} a bit:

Theorem 2 (Logically undecidable tilings)
  • (i) There exists a group {G} of the form {G = {\bf Z}^2 \times G_0} for some finite abelian {G_0}, a subset {E_0} of {G_0}, and finite sets {F_1, F_2 \subset G} such that the tiling equation {(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = {\bf Z}^2 \times E_0} is logically undecidable (and hence also aperiodic).
  • (ii) There exists a dimension {d}, a periodic subset {E} of {{\bf Z}^d}, and finite sets {F_1, F_2 \subset G} such that tiling equation {(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = E} is logically undecidable (and hence also aperiodic).
  • (iii) There exists a non-abelian finite group {G_0} (with the group law still written additively), a subset {E_0} of {G_0}, and a finite set {F \subset {\bf Z}^2 \times G_0} such that the nonabelian tiling equation {\mathbf{X} \oplus F = {\bf Z}^2 \times E_0} is logically undecidable (and hence also aperiodic).

We also have algorithmic versions of this theorem. For instance, the algorithmic version of (i) is that the problem of determining solvability of the tiling equation {(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = {\bf Z}^2 \times E_0} for a given choice of finite abelian group {G_0}, subset {E_0} of {G_0}, and finite sets {F_1, F_2 \subset {\bf Z}^2 \times G_0} is algorithmically undecidable. Similarly for (ii), (iii).

This result (together with a negative result discussed below) suggest to us that there is a significant qualitative difference in the {J=1} theory of tiling by a single (abelian) tile, and the {J \geq 2} theory of tiling with multiple tiles (or one non-abelian tile). (The positive results on the periodic tiling conjecture certainly rely heavily on the fact that there is only one tile, in particular there is a “dilation lemma” that is only available in this setting that is of key importance in the two dimensional theory.) It would be nice to eliminate the group {G_0} from (i) (or to set {d=2} in (ii)), but I think this would require a fairly significant modification of our methods.

Like many other undecidability results, the proof of Theorem 2 proceeds by a sequence of reductions, in which the undecidability of one problem is shown to follow from the undecidability of another, more “expressive” problem that can be encoded inside the original problem, until one reaches a problem that is so expressive that it encodes a problem already known to be undecidable. Indeed, all three undecidability results are ultimately obtained from Berger’s undecidability result on the domino problem.

The first step in increasing expressiveness is to observe that the undecidability of a single tiling equation follows from the undecidability of a system of tiling equations. More precisely, suppose we have non-empty finite subsets {F_j^{(m)}} of a finitely generated group {G} for {j=1,\dots,J} and {m=1,\dots,M}, as well as periodic sets {E^{(m)}} of {G} for {m=1,\dots,M}, such that it is logically undecidable whether the system of tiling equations

\displaystyle (\mathrm{X}_1 \oplus F_1^{(m)}) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J^{(m)}) = E^{(m)} \ \ \ \ \ (2)

for {m=1,\dots,M} has no solution {\mathrm{X}_1 = A_1,\dots, \mathrm{X}_J = A_J} in {G}. Then, for any {N>M}, we can “stack” these equations into a single tiling equation in the larger group {G \times {\bf Z}/N{\bf Z}}, and specifically to the equation

\displaystyle (\mathrm{X}_1 \oplus F_1) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J) = E \ \ \ \ \ (3)

 where

\displaystyle F_j := \biguplus_{m=1}^M F_j^{(m)} \times \{m\}

and

\displaystyle E := \biguplus_{m=1}^M E^{(m)} \times \{m\}.

It is a routine exercise to check that the system of equations (2) admits a solution in {G} if and only if the single equation (3) admits a equation in {G \times {\bf Z}/N{\bf Z}}. Thus, to prove the undecidability of a single equation of the form (3) it suffices to establish undecidability of a system of the form (2); note here how the freedom to select the auxiliary group {G_0} is important here.

We view systems of the form (2) as belonging to a kind of “language” in which each equation in the system is a “sentence” in the language imposing additional constraints on a tiling. One can now pick and choose various sentences in this language to try to encode various interesting problems. For instance, one can encode the concept of a function {f: {\bf Z}^2 \rightarrow G_0} taking values in a finite group {G_0} as a single tiling equation

\displaystyle \mathrm{X} \oplus (\{0\} \times G_0) = {\bf Z}^2 \times G_0 \ \ \ \ \ (4)

since the solutions to this equation are precisely the graphs

\displaystyle \mathrm{X} = \{ (n, f(n)): n \in {\bf Z}^2 \}

of a function {f: {\bf Z}^2 \rightarrow G_0}. By adding more tiling equations to this equation to form a larger system, we can start imposing additional constraints on this function {f}. For instance, if {x+H} is a coset of some subgroup {H} of {G_0}, we can impose the additional equation

\displaystyle \mathrm{X} \oplus (\{0\} \times H) = {\bf Z}^2 \times (x+H) \ \ \ \ \ (5)

 to impose the additional constraint that {f(n) \in x+H} for all {n \in {\bf Z}^2}, if we desire. If {G_0} happens to contain two distinct elements {1, -1}, and {h \in {\bf Z}^2}, then the additional equation

\displaystyle \mathrm{X} \oplus (\{0,h\} \times \{0\}) = {\bf Z}^2 \times \{-1,1\} \ \ \ \ \ (6)

 imposes the additional constraints that {f(n) \in \{-1,1\}} for all {n \in {\bf Z}^2}, and additionally that

\displaystyle f(n+h) = -f(n)

for all {n \in {\bf Z}^2}.

This begins to resemble the equations that come up in the domino problem. Here one has a finite set of Wang tiles – unit squares {T} where each of the four sides is colored with a color {c_N(T), c_S(T), c_E(T), c_W(T)} (corresponding to the four cardinal directions North, South, East, and West) from some finite set {{\mathcal C}} of colors. The domino problem is then to tile the plane with copies of these tiles in such a way that adjacent sides match. In terms of equations, one is seeking to find functions {c_N, c_S, c_E, c_W: {\bf Z}^2 \rightarrow {\mathcal C}} obeying the pointwise constraint

\displaystyle (c_N(n), c_S(n), c_E(n), c_W(n)) \in {\mathcal W} \ \ \ \ \ (7)

for all {n \in {\bf Z}^2} where {{\mathcal W}} is the set of colors associated to the set of Wang tiles being used, and the matching constraints

\displaystyle c_S(n+(0,1)) = c_N(n); \quad c_W(n+(1,0)) = c_E(n) \ \ \ \ \ (8)

 for all {{\bf Z}^2}. As it turns out, the pointwise constraint (7) can be encoded by tiling equations that are fancier versions of (4), (5), (6) that involve only one unknown tiling set {{\mathrm X}}, but in order to encode the matching constraints (8) we were forced to introduce a second tile (or work with nonabelian tiling equations). This appears to be an inherent feature of the method, since we found a partial rigidity result for tilings of one tile in one dimension that obstructs this encoding strategy from working when one only has one tile available. The result is as follows:

Proposition 3 (Swapping property) Consider the solutions to a tiling equation

\displaystyle \mathrm{X} \oplus F = E \ \ \ \ \ (9)

 in a one-dimensional group {G = {\bf Z} \times G_0} (with {G_0} a finite abelian group, {F} finite, and {E} periodic). Suppose there are two solutions {\mathrm{X} = A_0, \mathrm{X} = A_1} to this equation that agree on the left in the sense that

\displaystyle A_0 \cap (\{0, -1, -2, \dots\} \times G_0) = A_1 \cap (\{0, -1, -2, \dots\} \times G_0).

For any function {\omega: {\bf Z} \rightarrow \{0,1\}}, define the “swap” {A_\omega} of {A_0} and {A_1} to be the set

\displaystyle A_\omega := \{ (n, g): n \in {\bf Z}, (n,g) \in A_{\omega(n)} \}

Then {A_\omega} also solves the equation (9).

One can think of {A_0} and {A_1} as “genes” with “nucleotides” {\{ g \in G_0: (n,g) \in A_0\}}, {\{ g \in G_0: (n,g) \in A_1\}} at each position {n \in {\bf Z}}, and {A_\omega} is a new gene formed by choosing one of the nucleotides from the “parent” genes {A_0}, {A_1} at each position. The above proposition then says that the solutions to the equation (9) must be closed under “genetic transfer” among any pair of genes that agree on the left. This seems to present an obstruction to trying to encode equation such as

\displaystyle c(n+1) = c'(n)

for two functions {c, c': {\bf Z} \rightarrow \{-1,1\}} (say), which is a toy version of the matching constraint (8), since the class of solutions to this equation turns out not to obey this swapping property. On the other hand, it is easy to encode such equations using two tiles instead of one, and an elaboration of this construction is used to prove our main theorem.

The structure of translational tilings in Z^d

8 October, 2020 in math.CO, paper | Tags: , | by | 18 comments

Rachel Greenfeld and I have just uploaded to the arXiv our paper “The structure of translational tilings in {{\bf Z}^d}“. This paper studies the tilings {1_F * 1_A = 1} of a finite tile {F} in a standard lattice {{\bf Z}^d}, that is to say sets {A \subset {\bf Z}^d} (which we call tiling sets) such that every element of {{\bf Z}^d} lies in exactly one of the translates {a+F, a \in A} of {F}. We also consider more general tilings of level {k} {1_F * 1_A = k} for a natural number {k} (several of our results consider an even more general setting in which {1_F * 1_A} is periodic but allowed to be non-constant).

In many cases the tiling set {A} will be periodic (by which we mean translation invariant with respect to some lattice (a finite index subgroup) of {{\bf Z}^d}). For instance one simple example of a tiling is when {F \subset {\bf Z}^2} is the unit square {F = \{0,1\}^2} and {A} is the lattice {2{\bf Z}^2 = \{ 2x: x \in {\bf Z}^2\}}. However one can modify some tilings to make them less periodic. For instance, keeping {F = \{0,1\}^2} one also has the tiling set

\displaystyle A = \{ (2x, 2y+a(x)): x,y \in {\bf Z} \}

where {a: {\bf Z} \rightarrow \{0,1\}} is an arbitrary function. This tiling set is periodic in a single direction {(0,2)}, but is not doubly periodic. For the slightly modified tile {F = \{0,1\} \times \{0,2\}}, the set

\displaystyle A = \{ (2x, 4y+2a(x)): x,y \in {\bf Z} \} \cup \{ (2x+b(y), 4y+1): x,y \in {\bf Z}\}

for arbitrary {a,b: {\bf Z} \rightarrow \{0,1\}} can be verified to be a tiling set, which in general will not exhibit any periodicity whatsoever; however, it is weakly periodic in the sense that it is the disjoint union of finitely many sets, each of which is periodic in one direction.

The most well known conjecture in this area is the Periodic Tiling Conjecture:

Conjecture 1 (Periodic tiling conjecture) If a finite tile {F \subset {\bf Z}^d} has at least one tiling set, then it has a tiling set which is periodic.

This conjecture was stated explicitly by Lagarias and Wang, and also appears implicitly in this text of Grunbaum and Shepard. In one dimension {d=1} there is a simple pigeonhole principle argument of Newman that shows that all tiling sets are in fact periodic, which certainly implies the periodic tiling conjecture in this case. The {d=2} case was settled more recently by Bhattacharya, but the higher dimensional cases {d > 2} remain open in general.

We are able to obtain a new proof of Bhattacharya’s result that also gives some quantitative bounds on the periodic tiling set, which are polynomial in the diameter of the set if the cardinality {|F|} of the tile is bounded:

Theorem 2 (Quantitative periodic tiling in {{\bf Z}^2}) If a finite tile {F \subset {\bf Z}^2} has at least one tiling set, then it has a tiling set which is {M{\bf Z}^2}-periodic for some {M \ll_{|F|} \mathrm{diam}(F)^{O(|F|^4)}}.

Among other things, this shows that the problem of deciding whether a given subset of {{\bf Z}^2} of bounded cardinality tiles {{\bf Z}^2} or not is in the NP complexity class with respect to the diameter {\mathrm{diam}(F)}. (Even the decidability of this problem was not known until the result of Bhattacharya.)

We also have a closely related structural theorem:

Theorem 3 (Quantitative weakly periodic tiling in {{\bf Z}^2}) Every tiling set of a finite tile {F \subset {\bf Z}^2} is weakly periodic. In fact, the tiling set is the union of at most {|F|-1} disjoint sets, each of which is periodic in a direction of magnitude {O_{|F|}( \mathrm{diam}(F)^{O(|F|^2)})}.

We also have a new bound for the periodicity of tilings in {{\bf Z}}:

Theorem 4 (Universal period for tilings in {{\bf Z}}) Let {F \subset {\bf Z}} be finite, and normalized so that {0 \in F}. Then every tiling set of {F} is {qn}-periodic, where {q} is the least common multiple of all primes up to {2|F|}, and {n} is the least common multiple of the magnitudes {|f|} of all {f \in F \backslash \{0\}}.

We remark that the current best complexity bound of determining whether a subset of {{\bf Z}} tiles {{\bf Z}} or not is {O( \exp(\mathrm{diam}(F)^{1/3+o(1)}))}, due to Biro. It may be that the results in this paper can improve upon this bound, at least for tiles of bounded cardinality.

On the other hand, we discovered a genuine difference between level one tiling and higher level tiling, by locating a counterexample to the higher level analogue of (the qualitative version of) Theorem 3:

Theorem 5 (Counterexample) There exists an eight-element subset {F \subset {\bf Z}^2} and a level {4} tiling {1_F * 1_A = 4} such that {A} is not weakly periodic.

We do not know if there is a corresponding counterexample to the higher level periodic tiling conjecture (that if {F} tiles {{\bf Z}^d} at level {k}, then there is a periodic tiling at the same level {k}). Note that it is important to keep the level fixed, since one trivially always has a periodic tiling at level {|F|} from the identity {1_F * 1 = |F|}.

The methods of Bhattacharya used the language of ergodic theory. Our investigations also originally used ergodic-theoretic and Fourier-analytic techniques, but we ultimately found combinatorial methods to be more effective in this problem (and in particular led to quite strong quantitative bounds). The engine powering all of our results is the following remarkable fact, valid in all dimensions:

Lemma 6 (Dilation lemma) Suppose that {A} is a tiling of a finite tile {F \subset {\bf Z}^d}. Then {A} is also a tiling of the dilated tile {rF} for any {r} coprime to {n}, where {n} is the least common multiple of all the primes up to {|F|}.

Versions of this dilation lemma have previously appeared in work of Tijdeman and of Bhattacharya. We sketch a proof here. By the fundamental theorem of arithmetic and iteration it suffices to establish the case where {r} is a prime {p>|F|}. We need to show that {1_{pF} * 1_A = 1}. It suffices to show the claim {1_{pF} * 1_A = 1 \hbox{ mod } p}, since both sides take values in {\{0,\dots,|F|\} \subset \{0,\dots,p-1\}}. The convolution algebra {{\bf F}_p[{\bf Z}^d]} (or group algebra) of finitely supported functions from {{\bf Z}^d} to {{\bf F}_p} is a commutative algebra of characteristic {p}, so we have the Frobenius identity {(f+g)^{*p} = f^{*p} + g^{*p}} for any {f,g}. As a consequence we see that {1_{pF} = 1_F^{*p} \hbox{ mod } p}. The claim now follows by convolving the identity {1_F * 1_A = 1 \hbox{ mod } p} by {p-1} further copies of {1_F}.

In our paper we actually establish a more general version of the dilation lemma that can handle tilings of higher level or of a periodic set, and this stronger version is useful to get the best quantitative results, but for simplicity we focus attention just on the above simple special case of the dilation lemma.

By averaging over all {r} in an arithmetic progression, one already gets a useful structural theorem for tilings in any dimension, which appears to be new despite being an easy consequence of Lemma 6:

Corollary 7 (Structure theorem for tilings) Suppose that {A} is a tiling of a finite tile {F \subset {\bf Z}^d}, where we normalize {0 \in F}. Then we have a decomposition

\displaystyle 1_A = 1 - \sum_{f \in F \backslash 0} \varphi_f \ \ \ \ \ (1)

 where each {\varphi_f: {\bf Z}^d \rightarrow [0,1]} is a function that is periodic in the direction {nf}, where {n} is the least common multiple of all the primes up to {|F|}.

Proof: From Lemma 6 we have {1_A = 1 - \sum_{f \in F \backslash 0} \delta_{rf} * 1_A} for any {r = 1 \hbox{ mod } n}, where {\delta_{rf}} is the Kronecker delta at {rf}. Now average over {r} (extracting a weak limit or generalised limit as necessary) to obtain the conclusion. \Box

The identity (1) turns out to impose a lot of constraints on the functions {\varphi_f}, particularly in one and two dimensions. On one hand, one can work modulo {1} to eliminate the {1_A} and {1} terms to obtain the equation

\displaystyle \sum_{f \in F \backslash 0} \varphi_f = 0 \hbox{ mod } 1

which in two dimensions in particular puts a lot of structure on each individual {\varphi_f} (roughly speaking it makes the {\varphi_f \hbox{ mod } 1} behave in a polynomial fashion, after collecting commensurable terms). On the other hand we have the inequality

\displaystyle \sum_{f \in F \backslash 0} \varphi_f \leq 1 \ \ \ \ \ (2)

 which can be used to exclude “equidistributed” polynomial behavior after a certain amount of combinatorial analysis. Only a small amount of further argument is then needed to conclude Theorem 3 and Theorem 2.

For level {k} tilings the analogue of (2) becomes

\displaystyle \sum_{f \in F \backslash 0} \varphi_f \leq k

which is a significantly weaker inequality and now no longer seems to prohibit “equidistributed” behavior. After some trial and error we were able to come up with a completely explicit example of a tiling that actually utilises equidistributed polynomials; indeed the tiling set we ended up with was a finite boolean combination of Bohr sets.

We are currently studying what this machinery can tell us about tilings in higher dimensions, focusing initially on the three-dimensional case.

Some notes on the Coven-Meyerowitz conjecture

19 November, 2011 in expository, math.CO, math.GR, question | Tags: , , | by | 9 comments

Let {G = (G,+)} be a finite additive group. A tiling pair is a pair of non-empty subsets {A, B} such that every element of {G} can be written in exactly one way as a sum of an element {a} of {A} and an element {b} of {B}, in which case we write {G = A \oplus B}. The sets {A, B} are then called tiles, with {B} being a complementary tile to {A} and vice versa. For instance, every subgroup {H} of {G} is a tile, as one can pick one representative from each coset of {H} to form the complementary tile. Conversely, any set formed by taking one representative from each coset of {H} is also a tile.

Tiles can be quite complicated, particularly when the group {G} is “high-dimensional”. We will therefore restrict to the simple case of a cyclic group {G = {\bf Z}/N{\bf Z}}, and restrict even further to the special case when the modulus {N} is square-free. Here, the situation should be much simpler. In particular, we have the following conjecture of Coven and Meyerowitz, which asserts that the previous construction of a tile is, in fact, the only such construction:

Conjecture 1 (Coven-Meyerowitz conjecture, square-free case) Let {N} be square-free, and let {A} be a tile of {{\bf Z}/N{\bf Z}}. Then there exists a subgroup {H} of {{\bf Z}/N{\bf Z}} such that {A} consists of a single representative from each coset of {H}.

Note that in the square-free case, every subgroup {H} of {{\bf Z}/N{\bf Z}} has a complementary subgroup {H^\perp} (thus {{\bf Z}/N{\bf Z} = H \oplus H^\perp}). In particular, {H} consists of a single representative from each coset of {H^\perp}, and so the examples of subgroups of {{\bf Z}/N{\bf Z}} are covered by the above conjecture in the square-free case.

In the non-square free case, the above assertion is not true; for instance, if {p} is a prime, then the multiples of {p} in {{\bf Z}/p^2{\bf Z}} are a tile, but cannot be formed from taking a single representative from all the cosets of a given subgroup. There is a more general conjecture of Coven and Meyerowitz to handle this more general case, although it is more difficult to state:

Conjecture 2 (Coven-Meyerowitz conjecture, general case) Let {N} be a natural number, and let {A} be a tile of {{\bf Z}/N{\bf Z}}. Then there exists a set {S_A} of prime powers with {|A| = \prod_{p^j \in S_A} p} such that the Fourier transform

\displaystyle \hat 1_A(k) := \sum_{n \in A} e^{2\pi i kn / N}

vanishes whenever {k} is a non-zero element of {{\bf Z}/N{\bf Z}} whose order is the product of elements of {S_A} that are powers of distinct primes. Equivalently, the generating polynomial {\sum_{n \in A} x^n} is divisible by the cyclotomic polynomials {\phi_m} whenever {m} is the product of elements of {S_A} that are powers of distinct primes.

It can be shown (with a modest amount of effort) that Conjecture 2 implies Conjecture 1, but we will not do so here, focusing instead exclusively on the square-free case for simplicity.

It was observed by Laba that Conjecture 2 is connected to the following well-known conjecture of Fuglede:

Conjecture 3 (One-dimensional Fuglede conjecture, tiling to spectral direction) Let {E} be a compact subset of {{\bf R}} of positive measure which is a tile (thus {{\bf R} = E \oplus \Lambda} for some set {\Lambda \subset {\bf R}}). Then {L^2(E)} (with Lebesgue measure) has a spectrum, that is to say an orthogonal set of plane waves {x \mapsto e^{2\pi i \xi x}}.

Indeed, it was shown by Laba that Conjecture 2 implies Conjecture 3 in the case when {E} is the finite union of unit intervals. Actually, thanks to the more recent work of Farkas, Matolcsi, and Mora we know that Conjecture 2 in fact implies the universal spectrum conjecture of Lagarias and Wang, which in turn was known to imply Conjecture 3 in full generality. (On the other hand, the conjecture fails in four and higher dimensions; see the papers of Kolountzakis-Matolcsi and of Farkas-Revesz.)

Given the simple statement of Conjecture 1, it is perhaps somewhat surprising that it remains open, even in simple cases such as when {N} is the product of just four primes. One reason for this is that some plausible strengthenings of this conjecture (such as the Tijdeman-Sands conjecture) are known to be false, as we will review below. On the other hand, as we shall see, tiling sets have a lot of combinatorial structure, and in principle one should be able to work out a lot of special cases of the conjecture. Given the combinatorial nature of this problem, it may well be quite suitable for a polymath project in fact, if there is sufficient interest.

Read the rest of this entry »

Archives