Tag Archive

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

The structure of translational tilings in Z^d

8 October, 2020 in math.CO, paper | Tags: , | by | 12 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