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:
vanishes 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.
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.
— 1. Some facts about tiling pairs —
Let be a tiling pair for a cyclic group of cyclic order. In this section we collect some well-known facts about such pairs, which can be found for instance in the previously cited paper of Coven and Meyerowitz.
In particular, and are divisors of , and thus are products of disjoint sets of prime factors of .
Indeed, if there is a collision between a non-zero difference of elements of , and a difference of elements of , then one also has a collision in the sumset , so that and is no longer a tiling pair.
Now we use Fourier analysis to get more structural information. Observe that the relationship can be rewritten as
and hence (by taking Fourier transforms) as
Note that the case of this identity is again (1). The remaining cases of this identity can be reformulated equivalently as a frequency space separation property
Example 2 Continuing Example 1, is supported on , while vanishes on .
Now we use some basic Galois theory to obtain an important structural control on the Fourier supports. Let us call two elements of equivalent if one has for some coprime to (or equivalently, if ).
Proof: By (3) and symmetry, it suffices to show that is the union of equivalence classes. In other words, if and is coprime to , it suffices to show that if and only if . But observe that is an integer polynomial in the root of unity , and is the same polynomial but with replaced by another primitive root of unity. But from the Galois theory of the cyclotomic field , we know that there is a field automorphism that maps to , and so is non-zero precisely when is non-zero, and the claim follows.
Remark 1 One can also obtain the above lemma from the theory of cyclotomic polynomials and unique factorisation, noting that the product of the generating polynomials and form a multiple of , and that each cyclotomic polynomial is irreducible and has zeroes corresponding to a single equivalence class in .
This feature of Fourier supports has an important corollary:
Corollary 5 (Dilation invariance) Let for some . If is an integer coprime to , then , where is the dilation of by .
Applying this dilation invariance to the physical space separation property, we conclude
We can rephrase this corollary in the following more combinatorial way, taking advantage of the square-free hypothesis. We factor the square-free integer as for some finite set of primes . By the Chinese remainder theorem, we may then identify with the Cartesian product , where is the cyclic group of order (but we shall downplay the group structure and often view simply as a set of points), which each residue class being identified with its quotients . Define a diagonal in to be a pair such that for all ; we say that a subset of is diagonal-free if it contains no diagonals. Observe that if contains a diagonal , then contains an element with all coefficients non-zero, or equivalently an invertible element of . As all invertible elements are equivalent, we conclude from Corollary 6 that at least one of is diagonal-free. More generally, if is a non-empty subset of , define a -slice of to be a subset of of the form
where is a fixed element of for each . Thus, for instance, if one has three primes in , then is a subset of , and a slice would be a set of the form
for some .
- All -slices of are diagonal-free.
- All -slices of are diagonal-free.
Indeed, a diagonal in a -slice of would create an element of in the equivalence class of -tuples whose support was precisely .
Conversely, we see that any subsets of with obeying the conclusion of Corollary 7 will necessarily obey (2) and thus be a tiling pair. Thus we see the rather remarkable fact that the property of being a tiling pair is in fact not dependent on the underlying group structure of , but only on the Cartesian product structure of ; for instance, one can arbitrarily apply a permutation (or relabeling) of one of the factors of to or (or both) and still get a tiling pair.
Remark 2 One can make the above independence of the underlying group structure even more striking, as follows. For each prime in , let be an arbitrary quasigroup (or latin square) operation on , that is to say a binary operation (not assumed to be either commutative or associative) with the property that for each , the maps and are permutations of . (This quasigroup assumption is of course obeyed by the addition law on after identifying with a cyclic group of order , but clearly there are also many other quasigroup laws than these.) We can then define a law in the obvious manner:
The remarkable thing is then that and form a tiling pair with respect to the usual addition law on if and only if they form a tiling pair with respect to this more general law , thanks to Corollary 7 and its inverse.
Example 3 Let us partition , and let be an element of . Then one can create a tiling pair by setting (identifying with in the obvious manner), and setting to consist of a single representative of each slice for each . Observe that if is non-empty and contained in , then all -slices of are diagonal-free; but if is non-empty and not contained in , then all -slices of are diagonal-free.
where is a constant and , , and are arbitrary functions. One easily verifies that and are a tiling pair. If is a non-empty subset of , one can check that the -slices of are diagonal-free whenever the first element of is either or , and the -slices of are diagonal-free whenever the first element of is either or .
One can generalise these sorts of examples to more complicated tiling pairs in general products , in which each coordinate is free for one of , and a function of the previous coordinates for the other .
We isolate one particular instance of Corollary 7: that at least one of or is a partial graph in any given direction.
Indeed, we know that either one of or obeys the vertical line test, in the sense that its -slices are diagonal-free (and thus have cardinality at most one).
Now we convert the Fourier-analytic tiling criterion (Lemma 4) into a combinatorial form. We need a definition:
Definition 9 Let be a product set. A cube in is a collection of elements of of the form for , where for each , are elements of . A function is said to be balanced if the alternating sum of on any cube vanishes, thus
whenever for .
Example 5 If is a function, then is balanced if and only if
for all and . Equivalently, takes the form for some functions and .
We have the following equivalent characterisations of balanced functions:
Lemma 10 Let be the product of cyclic groups, and let be a function. Then the following are equivalent:
- (i) is balanced.
- (ii) is the sum of functions which depend on all but one of the coordinates in (i.e. they factor through for some ).
- (iii) vanishes on the equivalence class .
Proof: It is easy to see that (ii) implies (i) or (iii), and from the Fourier inversion formula we see that (iii) implies (ii). To see that (i) implies (ii), we apply (4) with (say) to rewrite in terms of functions that depend on a proper subset of the .
Combining this with Lemma 4 applied to the equivalence class in the above lemma, we conclude that at least one of and is balanced. We can also reach the other equivalence classes by projection. Given a subset of , let be the projection map, and given a function , let be the pushforward function
Note that the Fourier transform of is essentially the Fourier transform of restricted to . From Lemma 4 we conclude that
Conversely, if obey the conclusions of (11) and are such that , then are a tiling pair.
Example 6 Continuing Example 3, is balanced whenever is contained in , and is balanced otherwise.
Example 7 Continuing Example 4, is balanced whenever the largest element of is or , and is balanced whenever the largest element of is or .
A one-dimensional function is balanced if and only if it is constant. This leads to the following conclusion:
Corollary 12 Let . Then is balanced if and only if divides , and similarly for .
Proof: If does not divide , then cannot be constant (since it takes integer values on and has a total norm of ), and so is not balanced; by Corollary 11, this implies that is balanced. Since divides exactly one of and , the claim follows.
This already gives a simple case of the Coven-Meyerowitz conjecture:
Proof: Write . Then is constant on and has norm , and is thus equal to everywhere. In other words, meets every coset of exactly once, and the claim follows.
Corollary 14 The square-free Coven-Meyerowitz conjecture is true when is the product of at most two primes.
Proof: The claim is trivial when or , and the only remaining case is covered by Proposition 13.
Remark 3 The paper of Coven-Meyerowitz in fact establishes the general (not necessarily square-free) conjecture when has at most two distinct prime factors.
— 2. The codimension one case —
Now we give a slightly more difficult case of the conjecture.
We now prove this proposition. We induct on , assuming the claim has been proven for smaller .
Write , and let be a tiling complement of , thus . As in the proof of Proposition 13, meets each coset of exactly once, thus takes the form
where is a function.
Suppose first that takes values in a proper coset of (or equivalently, that takes values in a proper coset of ). Thus takes values in a translate of for some containing . Then every -slice of is essentially a tiling complement of in , which among other things implies that is the product of some primes in , and each slice of then has cardinality . By the inductive hypothesis, each such slice of must then consist of one representative from each coset of in (note that this is the only subgroup of that would give the correct cardinality for each slice of ). Gluing the slices together we conclude that consists of one representative from each coset of in as desired. So we may assume that does not take values in a proper coset of , and so does not take values in a proper coset of . (To put it another way, each component of is a non-constant function.)
Suppose contains at least one other element than . Then is non-constant, so can find such that . It is then not difficult to see that one can construct a cube which contains and no other elements of except possibly for . Furthermore, the only time cannot be avoided is if and differ only in the coordinate. In either case we see that cannot be balanced. More generally, the same argument shows that is not balanced for any containing and at least one other element, which by Corollary 11 implies that is balanced for all such . In other words, the Fourier transform is supported on . By the Fourier inversion formula, this implies a decomposition
for some functions , and all , . But as only takes the values or , we see that at least one of or is constant, thus is either just a function of or a function of . In the latter case this would imply that is a multiple of , which is absurd since is square-free; so must be a function of ; since , this implies that is a coset of and the claim follows.
Corollary 16 The square-free Coven-Meyerowitz conjecture is true when is the product of at most three primes.
— 3. Slices —
There is an interesting property of the slices of a tiling pair which seems like it should be exploitable further. Pick a prime in , and for each , let be the slice of (identifying with in the usual manner). Similarly define for .
for all .
Proof: Since all the sums in are distinct, we see for each that the sums in are also distinct, and so is well-defined. If are distinct elements of , and are distinct elements of , then from Corollary 7 we see that and are disjoint. Thus, for any , the set is diagonal-free. But this set also must have cardinality , since . Thus, this set is either a vertical line or a horizontal line . Letting denote the set where the former case occurs for a given , and the set where the latter case occurs, one obtains the claim.
Here is one small application of the above proposition.
Corollary 18 Suppose the square-free Coven-Meyerowitz conjecture is true for . Then the square-free Coven-Meyerowitz conjecture is true for any tiling of for which at least one of the slices with is empty.
Proof: Suppose for instance that is empty. Then by (5), we see that is empty for all ; thus is independent of . As the are disjoint, this implies that the are disjoint. Thus, if , then for any . In particular, the all have the same cardinality. Thus, by hypothesis, consists of one representative of each coset of some subgroup of ; multiplying this subgroup by , we conclude that also meets one representative of each coset of a subgroup of . Similarly, each of the consists of one representative of each coset of some subgroup of ; as all the have the same cardinality and is square-free, this subgroup must be independent of . Thus also consists of exactly one representative of each coset of the same subgroup in , and the claim follows.
— 4. A counterexample —
This conjecture would imply the (square-free) Coven-Meyerowitz conjecture, as can be seen from Corollary 18. All the preceding examples of tilings listed previously satisfy this conjecture. However, Szabo showed that this conjecture fails when consists of six primes . The idea is to start with a base tiling which does not directly counter the conjecture, but then modify it to disprove the conjecture. The base example is given by the sets
where , , are arbitrary functions.
It is easy to see that , regardless of what the functions . Furthermore, if are chosen to be non-constant, then is not contained in any proper coset of . On the other hand, is clearly contained in a coset of a proper subgroup of , namely itself. However, this can be remedied by modifying slightly. If we let be the line
and be the translated line
then one easily verifies that
In particular, if we remove from and replace it with , then the new set obtained is still a tiling complement to . In a similar spirit, if we let
then , and if
then . Furthermore, are disjoint. Thus if we let be the set
then we see that remains a tiling complement of . However, it is not difficult to see that unlike , is not contained in any coset of a proper subgroup of .
Remark 4 This construction does not prohibit the weaker conjecture that, given a tiling , that there is a prime such that one of the slices with is empty; this would still be enough to obtain the Coven-Meyerowitz conjecture, at least in the square-free case.
Remark 5 As noted by Szabo, the same construction also counters a conjecture of Corrádi that if , then at least one of or consists of unions of cosets of a non-trivial subgroup of .
Remark 6 Curiously, even though Conjecture 19 is false as stated, it is true in a “density” sense. Indeed, from Corollary 7 we know that at least one of and is diagonal-free. If say is diagonal-free, we may translate so that , and then is contained in the union of all the “hyperplanes” through . If consists of primes, then there are such hyperplanes, so by the pigeonhole principle, one of the hyperplanes contains at least of the elements of . Perhaps it may be possible to exploit this sort of observation in the regime where is bounded and the primes were large, though I was unable to get any particularly strong control on or out of this.
— 5. Some sub-problems —
The full Coven-Meyerowitz conjecture seems difficult, even in the square-free case, but some subproblems seem feasible. For instance:
Problem 21 Suppose we already know that a tile obeys the square-free Coven-Meyerowitz conjecture (i.e. it consists of one representative of each coset of a subgroup of ). Does this imply that every tiling complement of also obeys the conjecture (replacing with , of course?).