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

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.