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.

— 1. Some facts about tiling pairs —

Let {A \oplus B = {\bf Z}/N{\bf Z}} be a tiling pair for a cyclic group {{\bf Z}/N{\bf Z}} 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.

The first fact is an obvious cardinality identity:

\displaystyle |A| |B| = N. \ \ \ \ \ (1)

In particular, {|A|} and {|B|} are divisors of {N}, and thus are products of disjoint sets of prime factors of {N}.

The next fact is a physical space separation proeprty

\displaystyle (A-A) \cap (B-B) = \{0\}. \ \ \ \ \ (2)

Indeed, if there is a collision {a-a'=b-b'} between a non-zero difference {a-a'} of elements of {A}, and a difference {b-b'} of elements of {B}, then one also has a collision {a+b'=a'+b} in the sumset {A+B}, so that {A} and {B} is no longer a tiling pair.

Example 1 If {A} is a subgroup {H}, and {B} is formed by taking a single representative from each coset of {H}, then {A-A} is equal to {H}, while {B-B} can take arbitrary values in {({\bf Z}/N{\bf Z} \backslash H) \cup \{0\}}.

In the converse direction, if two non-empty subsets {A, B} of {{\bf Z}/N{\bf Z}} obey both (1) and (2), then they must be a tiling pair, since the sums in {A+B} are disjoint and have the same cardinality as {{\bf Z}/N{\bf Z}}.

Now we use Fourier analysis to get more structural information. Observe that the relationship {A \oplus B = {\bf Z}/N{\bf Z}} can be rewritten as

\displaystyle 1_A * 1_B = 1

and hence (by taking Fourier transforms) as

\displaystyle \hat 1_A(k) \hat 1_B(k) = N 1_{k=0}.

Note that the {k=0} case of this identity is again (1). The remaining cases of this identity can be reformulated equivalently as a frequency space separation property

\displaystyle \hbox{supp}(\hat 1_A) \cap \hbox{supp}(\hat 1_B) = \{0\} \ \ \ \ \ (3)

where {\hbox{supp}(\hat 1_A) := \{ k \in {\bf Z}/N{\bf Z}: \hat 1_A(k) \neq 0 \}} is the support of {\hat 1_A}. Conversely, if {A, B} obey both (3) and (1), then the above argument shows that {A \oplus B = {\bf Z}/N{\bf Z}}.

Example 2 Continuing Example 1, {\hat 1_A} is supported on {H^\perp}, while {\hat 1_B} vanishes on {H^\perp \backslash \{0\}}.

Now we use some basic Galois theory to obtain an important structural control on the Fourier supports. Let us call two elements {a, b} of {{\bf Z}/N{\bf Z}} equivalent if one has {a=mb} for some {m} coprime to {N} (or equivalently, if {(a,N) = (b,N)}).

Lemma 4 {\hbox{supp}(\hat 1_A)} and {\hbox{supp}(\hat 1_B)} are unions of equivalence classes, with {\{0\}} being the only equivalence class in common.

Proof: By (3) and symmetry, it suffices to show that {\hbox{supp}(1_A)} is the union of equivalence classes. In other words, if {k \in {\bf Z}/N{\bf Z}} and {m} is coprime to {N}, it suffices to show that {\hat 1_A(k)=0} if and only if {\hat 1_A(km)=0}. But observe that {\hat 1_A(k) = \sum_{a \in A} \omega^{ka}} is an integer polynomial in the {N^{th}} root of unity {\omega := e^{2\pi i/N}}, and {\hat 1_{A}(ma)} is the same polynomial but with {\omega} replaced by another primitive {N^{th}} root {\omega^m} of unity. But from the Galois theory of the cyclotomic field {{\bf Q}(\omega)}, we know that there is a field automorphism that maps {\omega} to {\omega^m}, and so {\hat 1_B(k)} is non-zero precisely when {\hat 1_{A}(ma)} is non-zero, and the claim follows. \Box

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 {\sum_{n \in A} z^n} and {\sum_{n \in B} z^n} form a multiple of {(z^N-1)/(z-1) = \prod_{k|N} \Phi_k(z)}, and that each cyclotomic polynomial {\Phi_k} is irreducible and has zeroes corresponding to a single equivalence class in {{\bf Z}/N{\bf Z}}.

This feature of Fourier supports has an important corollary:

Corollary 5 (Dilation invariance) Let {A \oplus B = {\bf Z}/N{\bf Z}} for some {N}. If {m} is an integer coprime to {N}, then {A \oplus mB = {\bf Z}/N{\bf Z}}, where {mB := \{mb: b \in B \}} is the dilation of {B} by {m}.

Proof: From Lemma 4 one has {\hbox{supp}(\hat 1_B) = \hbox{supp}(\hat 1_{mB})}. Since tiling is equivalent to the conditions (1) and (3), the claim follows. \Box

Applying this dilation invariance to the physical space separation property, we conclude

Corollary 6 (Strong physical space separation) The sets {(A-A) \backslash \{0\}} and {(B-B) \backslash \{0\}} lie in disjoint equivalence classes; thus any non-zero equivalence class may contain an element of {A-A} or an element of {B-B}, but not both.

We can rephrase this corollary in the following more combinatorial way, taking advantage of the square-free hypothesis. We factor the square-free integer {N} as {N = \prod_{p \in P} p} for some finite set of primes {P}. By the Chinese remainder theorem, we may then identify {{\bf Z}/N{\bf Z}} with the Cartesian product {V_P := \prod_{p \in P} V_p}, where {V_p ={\bf Z}/p{\bf Z}} is the cyclic group of order {p} (but we shall downplay the group structure and often view {V_p} simply as a set of {p} points), which each residue class {a \hbox{ mod } N} being identified with its quotients {(a \hbox{ mod } p)_{p \in P}}. Define a diagonal in {V_P} to be a pair {(a_p)_{p \in P}, (b_p)_{p \in P}} such that {a_p \neq b_p} for all {p \in P}; we say that a subset of {V_P} is diagonal-free if it contains no diagonals. Observe that if {A} contains a diagonal {(a_p)_{p \in P}, (b_p)_{p \in P}}, then {(A-A) \backslash \{0\}} contains an element {(a_p-b_p)_{p \in P}} with all coefficients non-zero, or equivalently an invertible element of {{\bf Z}/N{\bf Z}}. As all invertible elements are equivalent, we conclude from Corollary 6 that at least one of {A, B} is diagonal-free. More generally, if {P'} is a non-empty subset of {P}, define a {P'}-slice of {A} to be a subset of {V_{P'} := \prod_{p \in P'} V_p} of the form

\displaystyle \{ (a_p)_{p \in P'} \in \prod_{p \in P'} V_p: (a_p)_{p \in P} \in \prod_{p \in P} V_p \},

where {a_p} is a fixed element of {V_p} for each {p \in P \backslash P'}. Thus, for instance, if one has three primes {p,q,r} in {P}, then {A} is a subset of {V_{\{p,q,r\}} := V_p \times V_q \times V_r}, and a {\{q,r\}} slice would be a set of the form

\displaystyle \{ (q,r) \in V_q \times V_r: (p,q,r) \in A \}

for some {p \in V_p}.

Corollary 7 (Strong physical space separation, combinatorial formulation) Let us view {A, B} as subsets of {V_P}, and let {P'} be a non-empty subset of {P}. Then one of the following statements is true:

  • All {P'}-slices of {A} are diagonal-free.
  • All {P'}-slices of {B} are diagonal-free.

Indeed, a diagonal in a {P'}-slice of {A} would create an element of {A-A \backslash \{0\}} in the equivalence class of {P}-tuples whose support was precisely {P \backslash P'}.

Conversely, we see that any subsets {A, B} of {V_P} with {|A| |B| = |V_P|} 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 {{\bf Z}/N{\bf Z}}, but only on the Cartesian product structure of {V_P}; for instance, one can arbitrarily apply a permutation (or relabeling) of one of the factors {V_p} of {V_P} to {A} or {B} (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 {p} in {P}, let {\ast_p: V_p \times V_p \rightarrow V_p} be an arbitrary quasigroup (or latin square) operation on {V_p}, that is to say a binary operation (not assumed to be either commutative or associative) with the property that for each {a \in V_p}, the maps {x \mapsto a \ast_p x} and {x \mapsto x \ast_p a} are permutations of {V_p}. (This quasigroup assumption is of course obeyed by the addition law {+} on {V_p} after identifying {V_p} with a cyclic group of order {p}, but clearly there are also many other quasigroup laws than these.) We can then define a law {\ast: V_P \times V_P \rightarrow V_P} in the obvious manner:

\displaystyle (a_p)_{p \in P} \ast (b_p)_{p \in P} := (a_p \ast_p b_p)_{p \in P}.

The remarkable thing is then that {A} and {B} form a tiling pair with respect to the usual addition law {+} on {V_P} if and only if they form a tiling pair with respect to this more general law {\ast}, thanks to Corollary 7 and its inverse.

Example 3 Let us partition {P = P_1 \cup P_2}, and let {x_2} be an element of {V_{P_2}}. Then one can create a tiling pair by setting {A = V_{P_1} \times \{x_2\}} (identifying {V_P} with {V_{P_1} \times V_{P_2}} in the obvious manner), and setting {B} to consist of a single representative of each slice {\{x_1\} \times V_{P_2}} for each {x \in V_{P_1}}. Observe that if {P'} is non-empty and contained in {P_1}, then all {P'}-slices of {B} are diagonal-free; but if {P' \subset P} is non-empty and not contained in {P_1}, then all {P'}-slices of {A} are diagonal-free.

Example 4 Suppose {P = \{p_1,p_2,p_3,p_4\}}. We consider the sets

\displaystyle A := \{ (f_1, x_2, f_3(x_2), x_4): x_2 \in V_{p_2}, x_4 \in V_{p_4} \}

and

\displaystyle B := \{ (x_1, f_2(x_1), x_3, f_4(x_1,x_3)): x_1 \in V_{p_1}, x_3 \in V_{p_3} \}

where {f_1 \in V_{p_1}} is a constant and {f_2: V_{p_1} \rightarrow V_{p_2}}, {f_3: V_{p_2} \rightarrow V_{p_3}}, and {f_4: V_{p_1} \times V_{p_3} \rightarrow V_{p_4}} are arbitrary functions. One easily verifies that {A} and {B} are a tiling pair. If {P'} is a non-empty subset of {P}, one can check that the {P'}-slices of {A} are diagonal-free whenever the first element of {P'} is either {p_1} or {p_3}, and the {P'}-slices of {B} are diagonal-free whenever the first element of {P'} is either {p_2} or {p_4}.

One can generalise these sorts of examples to more complicated tiling pairs in general products {V_P}, in which each coordinate is free for one of {A,B}, and a function of the previous coordinates for the other {A,B}.

We isolate one particular instance of Corollary 7: that at least one of {A} or {B} is a partial graph in any given direction.

Corollary 8 (Graph structure) Let {p \in P}, and view {V_P} as {V_{P \backslash \{p\}} \times V_p}. Then at least one of {A} and {B} is contained in a graph {\{ (x, f(x)): x \in V_{P \backslash \{p\}} \}} for some function {f: V_{P \backslash \{p\}} \rightarrow V_p}.

Indeed, we know that either one of {A} or {B} obeys the vertical line test, in the sense that its {V_p}-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 {V_P = \prod_{p \in P} V_p} be a product set. A cube in {V_P} is a collection of {2^{|P|}} elements of {V_P} of the form {(a_p^{i_p})_{p \in P}} for {i_p \in \{0,1\}}, where for each {p \in P}, {a_p^0, a_p^1} are elements of {V_p}. A function {f: V_P \rightarrow {\bf R}} is said to be balanced if the alternating sum of {f} on any cube vanishes, thus

\displaystyle \sum_{(i_p)_{p \in P} \in \{0,1\}^P} (-1)^{\sum_{p \in P} i_p} f((a_p^{i_p})_{p \in P}) = 0 \ \ \ \ \ (4)

whenever {a_p^0, a_p^1 \in V_p} for {p \in P}.

Example 5 If {f: V_p \times V_q \rightarrow {\bf R}} is a function, then {f} is balanced if and only if

\displaystyle f(a,b) - f(a',b) - f(a,b') + f(a',b')=0

for all {a,a' \in V_p} and {b,b' \in V_q}. Equivalently, {f} takes the form {f(a,b) = g(a) + h(b)} for some functions {g: V_p \rightarrow {\bf R}} and {h: V_q \rightarrow {\bf R}}.

We have the following equivalent characterisations of balanced functions:

Lemma 10 Let {V_P = \prod_{p \in P} V_p} be the product of cyclic groups, and let {f: V_P \rightarrow {\bf R}} be a function. Then the following are equivalent:

  • (i) {f} is balanced.
  • (ii) {f} is the sum of functions which depend on all but one of the coordinates in {V_P} (i.e. they factor through {V_{P \backslash \{p\}}} for some {p \in P}).
  • (iii) {\hat f} vanishes on the equivalence class {\{ (k_p)_{p \in P} \in V_P : k_p \neq 0 \hbox{ for all } p \in P \}}.

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 {a_p^0 := 0} (say) to rewrite {f((a_p^1)_{p \in P})} in terms of functions that depend on a proper subset of the {a_p^1}. \Box

Combining this with Lemma 4 applied to the equivalence class in the above lemma, we conclude that at least one of {1_A} and {1_B} is balanced. We can also reach the other equivalence classes by projection. Given a subset {P'} of {P}, let {\pi_{P'}: V_P \rightarrow V_{P'}} be the projection map, and given a function {f: V_P \rightarrow {\bf R}}, let {(\pi_{P'})_* f: V_{P'} \rightarrow {\bf R}} be the pushforward function

\displaystyle (\pi_{P'})_* f(x') = \sum_{x \in V_P: \pi_{P'}(x)=x'} f(x).

Note that the Fourier transform of {(\pi_{P'})_* f} is essentially the Fourier transform of {f} restricted to {V_P}. From Lemma 4 we conclude that

Corollary 11 (Strong frequency space separation, combinatorial formulation) Let {P'} be a non-empty subset of {P}. Then at least one of {(\pi_{P'})_* 1_A} and {(\pi_{P'})_* 1_B} is balanced.

Conversely, if {A, B \subset V_P} obey the conclusions of (11) and are such that {|A| |B| = |V_P|}, then {A, B} are a tiling pair.

Example 6 Continuing Example 3, {(\pi_{P'})_* 1_B} is balanced whenever {P'} is contained in {P_2}, and {(\pi_{P'})_* 1_A} is balanced otherwise.

Example 7 Continuing Example 4, {(\pi_{P'})_* 1_A} is balanced whenever the largest element of {P'} is {p_2} or {p_4}, and {(\pi_{P'})_* 1_B} is balanced whenever the largest element of {P'} is {p_1} or {p_3}.

A one-dimensional function {f: V_p \rightarrow {\bf R}} is balanced if and only if it is constant. This leads to the following conclusion:

Corollary 12 Let {p \in P}. Then {(\pi_p)_* 1_A} is balanced if and only if {p} divides {|A|}, and similarly for {B}.

Proof: If {p} does not divide {|A|}, then {(\pi_p)_* 1_A} cannot be constant (since it takes integer values on {V_p} and has a total {\ell^1} norm of {|A|}), and so is not balanced; by Corollary 11, this implies that {(\pi_p)_* 1_B} is balanced. Since {p} divides exactly one of {|A|} and {|B|}, the claim follows. \Box

This already gives a simple case of the Coven-Meyerowitz conjecture:

Proposition 13 The square-free Coven-Meyerowitz conjecture is true when {|A|} is a prime.

Proof: Write {|A|=p}. Then {(\pi_p)_* 1_A} is constant on {V_p} and has {\ell^1} norm {|A|=p}, and is thus equal to {1} everywhere. In other words, {A} meets every coset of {V_{P \backslash \{p\}}} exactly once, and the claim follows. \Box

Corollary 14 The square-free Coven-Meyerowitz conjecture is true when {N} is the product of at most two primes.

Proof: The claim is trivial when {|A|=1} or {|A|=N}, and the only remaining case is covered by Proposition 13. \Box

Remark 3 The paper of Coven-Meyerowitz in fact establishes the general (not necessarily square-free) conjecture when {N} has at most two distinct prime factors.

— 2. The codimension one case —

Now we give a slightly more difficult case of the conjecture.

Proposition 15 The square-free Coven-Meyerowitz conjecture is true when {N/|A|} is a prime.

We now prove this proposition. We induct on {N}, assuming the claim has been proven for smaller {N}.

Write {N/|A|=p}, and let {B} be a tiling complement of {A}, thus {|B|=p}. As in the proof of Proposition 13, {B} meets each coset of {V_{P \backslash \{p\}}} exactly once, thus {B} takes the form

\displaystyle B = \{ ( b, f(b) ): b \in V_p \}

where {f: V_p \rightarrow V_{P \backslash \{p\}}} is a function.

Suppose first that {B} takes values in a proper coset of {V_P} (or equivalently, that {f} takes values in a proper coset of {V_{P \backslash\{p\}}}). Thus {B} takes values in a translate of {V_{P'}} for some {P' \subsetneq P} containing {p}. Then every {P \backslash P'}-slice of {A} is essentially a tiling complement of {B} in {V_{P'}}, which among other things implies that {|B|} is the product of some primes {P''} in {P'}, and each slice of {A} then has cardinality {|V_{P' \backslash P''}|}. By the inductive hypothesis, each such slice of {A} must then consist of one representative from each coset of {V_{P''}} in {V_{P'}} (note that this is the only subgroup of {V_{P'}} that would give the correct cardinality for each slice of {A}). Gluing the slices together we conclude that {A} consists of one representative from each coset of {V_{P''}} in {V_P} as desired. So we may assume that {B} does not take values in a proper coset of {V_P}, and so {f} does not take values in a proper coset of {V_{P \backslash \{p\}}}. (To put it another way, each component of {f} is a non-constant function.)

Suppose {P} contains at least one other element than {p}. Then {f} is non-constant, so can find {b, b' \in V_p} such that {f(b) \neq f(b')}. It is then not difficult to see that one can construct a cube which contains {(b,f(b))} and no other elements of {B} except possibly for {(b',f(b'))}. Furthermore, the only time {(b',f(b'))} cannot be avoided is if {f(b)} and {f(b')} differ only in the {V_2} coordinate. In either case we see that {1_B} cannot be balanced. More generally, the same argument shows that {(\pi_{P'})_* 1_B} is not balanced for any {P'} containing {p} and at least one other element, which by Corollary 11 implies that {(\pi_{P'})_* 1_A} is balanced for all such {P'}. In other words, the Fourier transform {\hat 1_A} is supported on {V_p \times \{0\} \cup \{0\} \times V_{P \backslash \{p\}}}. By the Fourier inversion formula, this implies a decomposition

\displaystyle 1_A( x, y ) = F(x) + G(y)

for some functions {F: V_p \rightarrow {\bf R}}, {G: V_{P \backslash \{p\}} \rightarrow {\bf R}} and all {x \in V_p}, {y \in V_{P \backslash \{p\}}}. But as {1_A} only takes the values {0} or {1}, we see that at least one of {F} or {G} is constant, thus {1_A(x,y)} is either just a function of {x} or a function of {y}. In the latter case this would imply that {|A| = N/p} is a multiple of {p}, which is absurd since {N} is square-free; so {1_A(x,y)} must be a function of {x}; since {|A|=N/p}, this implies that {A} is a coset of {V_{P \backslash \{p\}}} and the claim follows.

Corollary 16 The square-free Coven-Meyerowitz conjecture is true when {N} is the product of at most three primes.

— 3. Slices —

There is an interesting property of the slices of a tiling pair {A \oplus B = V_P} which seems like it should be exploitable further. Pick a prime {p} in {P}, and for each {i \in V_p}, let {A_i \subset V_{P \backslash \{p\}}} be the slice {A_i := \{ x \in V_{P \backslash \{p\}}: (i,x) \in A \}} of {A} (identifying {V_P} with {V_p \times V_{P \backslash \{p\}}} in the usual manner). Similarly define {B_j} for {j \in V_p}.

Proposition 17 (Sums of slices) There exists a partition of {V_{P \backslash \{p\}}} into sets {E_i} for {i \in V_p} and {F_j} for {j \in V_p} such that

\displaystyle A_i \oplus B_j = E_i \cup F_j \ \ \ \ \ (5)

for all {i,j \in V_p}.

Proof: Since all the sums in {A+B} are distinct, we see for each {i,j \in V_p} that the sums in {A_i+B_j} are also distinct, and so {A_i \oplus B_j} is well-defined. If {i,i'} are distinct elements of {V_p}, and {j,j'} are distinct elements of {V_p}, then from Corollary 7 we see that {A_i \oplus B_j} and {A_{i'} \oplus B_{j'}} are disjoint. Thus, for any {x \in V_{P \backslash \{p\}}}, the set {\{ (i,j) \in V_p \times V_p: x \in A_i \oplus B_j \}} is diagonal-free. But this set also must have cardinality {p}, since {A \oplus B = V_P}. Thus, this set is either a vertical line {\{i\} \times V_p} or a horizontal line {V_p \times \{j\}}. Letting {E_i} denote the set where the former case occurs for a given {i \in V_p}, and {F_j} the set where the latter case occurs, one obtains the claim. \Box

Here is one small application of the above proposition.

Corollary 18 Suppose the square-free Coven-Meyerowitz conjecture is true for {V_{P \backslash \{p\}}}. Then the square-free Coven-Meyerowitz conjecture is true for any tiling {A \oplus B} of {V_P} for which at least one of the slices {A_i, B_j} with {i,j \in V_p} is empty.

Proof: Suppose for instance that {A_0} is empty. Then by (5), we see that {F_j} is empty for all {j}; thus {A_i \oplus B_j = E_i} is independent of {j}. As the {E_i} are disjoint, this implies that the {A_i} are disjoint. Thus, if {A' := \bigcup_{i \in V_p} A_i}, then {A' \oplus B_j = V_{P \backslash \{p\}}} for any {j}. In particular, the {B_j} all have the same cardinality. Thus, by hypothesis, {A'} consists of one representative of each coset of some subgroup of {V_{P \backslash \{p\}}}; multiplying this subgroup by {V_p}, we conclude that {A} also meets one representative of each coset of a subgroup of {V_P}. Similarly, each of the {B_j} consists of one representative of each coset of some subgroup of {V_{P \backslash \{p\}}}; as all the {B_j} have the same cardinality and {N} is square-free, this subgroup must be independent of {j}. Thus {B} also consists of exactly one representative of each coset of the same subgroup in {V_P}, and the claim follows. \Box

— 4. A counterexample —

In this section we note a counterexample of Szabo to a natural conjecture (due to Sands, with a very similar conjecture also formulated by Tijdeman). In the square-free case, the conjecture reads:

Conjecture 19 (Tijdeman-Sands conjecture) Let {A \otimes B = V_P} be a tiling of a square-free cyclic group {V_P}. Then at least one of {A} or {B} is contained in a coset of a proper subgroup of {V_P}.

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 {P} consists of six primes {p_1,\ldots,p_6}. 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

\displaystyle A := \{ (a,b,c,F(a),G(b),H(c)): a \in V_{p_1}, b \in V_{p_2}, c \in V_{p_3} \}

and

\displaystyle B := \{ (0,0,0,d,e,f): d \in V_{p_4}, e \in V_{p_5}, f \in V_{p_6} \}

where {F: V_{p_1} \rightarrow V_{p_4}}, {G: V_{p_2} \rightarrow V_{p_5}}, {H: V_{p_3} \rightarrow V_{p_6}} are arbitrary functions.

It is easy to see that {A \oplus B = V_P}, regardless of what the functions {F,G,H}. Furthermore, if {F,G,H} are chosen to be non-constant, then {A} is not contained in any proper coset of {V_P}. On the other hand, {B} is clearly contained in a coset of a proper subgroup of {V_P}, namely itself. However, this can be remedied by modifying {B} slightly. If we let {\ell_1} be the line

\displaystyle \ell_1 := \{ (0,0,0,0,0,f): f \in V_{p_6} \}

and {\ell'} be the translated line

\displaystyle \ell'_1 := \{ (0,0,1,0,0,f): f \in V_{p_6} \}

then one easily verifies that

\displaystyle A \oplus \ell_1 = A \oplus \ell'_1 = \{ (a,b,c,F(a),G(b),f): a \in V_{p_1}, b \in V_{p_2}, c \in V_{p_3}, f \in V_{p_6} \}.

In particular, if we remove {\ell_1} from {B} and replace it with {\ell'_1}, then the new set obtained is still a tiling complement to {A}. In a similar spirit, if we let

\displaystyle \ell_2 := \{ (0,0,0,1,e,0): e \in V_{p_5} \}

and

\displaystyle \ell'_2 := \{ (0,1,0,1,e,0): e \in V_{p_5} \}

then {A \oplus \ell_2 = A \oplus \ell'_2}, and if

\displaystyle \ell_3 := \{ (0,0,0,d,1,1): d \in V_{p_4} \}

and

\displaystyle \ell'_3 := \{ (1,0,0,d,1,1): d \in V_{p_4} \}

then {A \oplus \ell_3 = A \oplus \ell'_3}. Furthermore, {\ell_1,\ell_2,\ell_3, \ell'_1, \ell'_2, \ell'_3} are disjoint. Thus if we let {B'} be the set

\displaystyle B' := B \backslash (\ell_1 \cup \ell_2 \cup \ell_3) \cup (\ell'_1 \cup \ell'_2 \cup \ell'_3)

then we see that {B'} remains a tiling complement of {B}. However, it is not difficult to see that unlike {B}, {B'} is not contained in any coset of a proper subgroup of {V}.

Remark 4 This construction does not prohibit the weaker conjecture that, given a tiling {A \oplus B = V_P}, that there is a prime {p} such that one of the slices {A_i, B_j} with {i,j \in V_p} 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 {A \oplus B = V_P}, then at least one of {A} or {B} consists of unions of cosets of a non-trivial subgroup of {V_P}.

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 {A} and {B} is diagonal-free. If say {A} is diagonal-free, we may translate so that {0 \in A}, and then {A} is contained in the union of all the “hyperplanes” {V_{P \backslash \{p\}}} through {0}. If {P} consists of {k} primes, then there are {k} such hyperplanes, so by the pigeonhole principle, one of the hyperplanes contains at least {|A|/k} of the elements of {A}. Perhaps it may be possible to exploit this sort of observation in the regime where {k} is bounded and the primes {p_1,\ldots,p_k} were large, though I was unable to get any particularly strong control on {A} or {B} 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 20 Is the square-free Coven-Meyerowitz conjecture true when {N} is the product of four primes, {N = p_1 p_2 p_3 p_4}? In view of Proposition 13 and Proposition 15, one may assume that {|A| = p_1 p_2} and {|B| = p_3 p_4}.

Or:

Problem 21 Suppose we already know that a tile {A} obeys the square-free Coven-Meyerowitz conjecture (i.e. it consists of one representative of each coset of a subgroup {H} of {G}). Does this imply that every tiling complement {B} of {A} also obeys the conjecture (replacing {H} with {H^\perp}, of course?).