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

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

Tiles can be quite complicated, particularly when the group is “high-dimensional”. We will therefore restrict to the simple case of a cyclic group , and restrict even further to the special case when the modulus 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 be square-free, and let be a tile of . Then there exists a subgroup of such that consists of a single representative from each coset of .

Note that in the square-free case, every subgroup of has a complementary subgroup (thus ). In particular, consists of a single representative from each coset of , and so the examples of subgroups of 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 is a prime, then the multiples of in 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 be a natural number, and let be a tile of . Then there exists a set of prime powers with such that the Fourier transformvanishes whenever is a non-zero element of whose order is the product of elements of that are powers of distinct primes. Equivalently, the generating polynomial is divisible by the cyclotomic polynomials whenever is the product of elements of 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 be a compact subset of of positive measure which is a tile (thus for some set ). Then (with Lebesgue measure) has a spectrum, that is to say an orthogonal set of plane waves .

Indeed, it was shown by Laba that Conjecture 2 implies Conjecture 3 in the case when 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 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.

## Recent Comments