A characterization of finite sets that tile the integers

Andrew Granville, Izabella Łaba, and Yang Wang

October 1, 2001

Abstract

We say that a finite set of integers A tiles Z by translations if Z can be written as a disjoint union of translates of A. Coven and Meyerowitz (J. Algebra 212 (1999), 161–174) found necessary and sufficient conditions for A to tile Z if |A| has at most two distinct prime factors. The purpose of this paper is to extend their result to certain three-prime cases.

Mathematics Subject Classification: 11B75.

1 Introduction

A set of integers A is said to tile the integers if there is a set C ⊂ Z such that every integer n can be written in a unique way as n = a + c with a ∈ A and c ∈ C. Throughout this paper we will assume that A is finite. It is well known (see [7]) that any tiling of Z by a finite set A must be periodic: C = B + MZ for some finite set B ⊂ Z such that |A| |B| = M. We then write A ⊕ B = Z/MZ.

Newman [7] gave a characterization of all sets A which tile the integers and such that |A| is a prime power. Coven and Meyerowitz [1] found necessary and sufficient conditions for A to tile Z if |A| has at most two prime factors. To state their result we need to introduce some notation. Without loss of generality we may assume that A, B ⊂ {0, 1, …} and that 0 ∈ A ∩ B. Define the characteristic polynomials

A(x) = ∑_{a∈A} x^{a}, B(x) = ∑_{b∈B} x^{b}.

Then A ⊕ B = Z/MZ is equivalent to

A(x)B(x) = 1 + x + … + x^{M−1} (mod (x^{M} − 1)).  (1.1)

Let Φ_{s}(x) denote the s-th cyclotomic polynomial, i.e. the monic, irreducible polynomial whose roots are the primitive s-th roots of unity. We then have x^{n} − 1 = ∏_{s|n} Φ_{s}(x), and (1.1) holds if and only if

|A||B| = M and Φ_{s}(x) | A(x)B(x) for all s|M, s ≠ 1.  (1.2)

Let S_{A} be the set of prime powers p^{α} such that Φ_{p^{α}}(x) divides A(x). Then the Coven-Meyerowitz conditions are:

(T1) A(1) = ∏_{s∈S_{A}} Φ_{s}(1),

(T2) if s_{1}, …, s_{k} ∈ S_{A} are powers of different primes, then Φ_{s_{1}...s_{k}}(x) divides A(x).

It is proved in [1] that:

• if A satisfies (T1), (T2), then it tiles Z;

• if A tiles Z then (T1) holds;

• if A tiles Z and |A| has at most two prime factors, then (T2) holds.

The first two statements are relatively simple to prove and hold regardless of the size of A; the main difficulty is in proving the third one. The proof given by Coven and Meyerowitz relies crucially on a result of Sands [8]: if A ⊕ B = Z/MZ and M has at most two prime divisors, then one of A, B must be contained in mZ for some m|M, m ≠ 1. A theorem of Tijdeman [10] implies that if A tiles the integers, then there exists a tiling A ⊕ B such that |B| has the same prime factors as |A|. Therefore if A tiles Z and |A| has at most two prime factors, then there is a tiling of Z by A to which Sands’ result applies. The authors then decompose this tiling and proceed by induction in |A|.

It seems very hard to verify whether (T2) holds for all sets which tile the integers. There is no analogue of Sands’ result if M has three or more prime factors, as shown in [9], [4]; hence the methods of Coven and Meyerowitz do not extend to more general sets. The purpose of this paper is to settle, for the first time, a three-prime case.

Theorem 1.1 Let A, B be two sets of integers such that |A| = p^{α}q^{β}r^{γ} and |B| = pqr, where p, q, r are distinct primes. Assume that A⊕B = Z/MZ, where M = |A| |B|. If Φ_{p}(x), Φ_{q}(x), Φ_{r}(x) divide A(x), then so do Φ_{pq}(x), Φ_{pr}(x), Φ_{qr}(x), Φ_{pqr}(x).

Equivalently, if the elements of A are equi-distributed modulo p, q, and r, then they are also equi-distributed modulo pqr. Observe that this reformulation of (T2) does not require the elements of A to be nonnegative.

We remark that by the results of [5], [6], [3], proving (T2) for all finite sets which tile the integers would essentially resolve one part of Fuglede’s spectral set conjecture [2] in dimension 1.

Our main tool in proving Theorem 1.1 is the following identity.

Theorem 1.2 For any finite A, B ⊂ Z, let

A_{m} = #{(a, a′) ∈ A × A : (a − a′, N) = m}, B_{m} = #{(b, b′) ∈ B × B : (b − b′, N) = m}.

Then

∑_{m|N} \frac{A_{m}B_{m}}{ϕ(N/m)} = \frac{1}{N} ∑_{d|N} \frac{A_{d}B_{d}}{ϕ(d)} ,  (1.3)

where

A_{d} = ∑_{ξ:Φ_{d}(ξ)=0} |A(ξ)|^{2}, B_{d} = ∑_{ξ:Φ_{d}(ξ)=0} |B(ξ)|^{2}.

Here, as usual, ϕ(n) is the Euler function and (m, n) denotes the greatest common divisor of m and n. We adopt the convention that (n, 0) = n for any n ≠ 0.

We also observe that Theorem 1.2 extends the following result of Sands [8].

Theorem 1.3 [8] Let A, B be two subsets of Z such that the elements of each of them are distinct modulo M. Define D_{A} = {(a − a′, M) : a, a′ ∈ A, a ≠ a′} and D_{B} = {(b − b′, M) : b, b′ ∈ B, b ≠ b′}. Then A ⊕ B = Z/MZ if and only if |A| |B| = M and D_{A} ∩ D_{B} = ∅.

Our Theorem 1.2 provides an alternative proof of Theorem 1.3; furthermore, it implies Theorem 1.4 below.

Theorem 1.4 Let A, B, D_{A}, D_{B} be as in Theorem 1.3. Assume that D_{A} ∩ D_{B} = ∅. Then |A| |B| ≤ M, and the equality holds if and only if A ⊕ B = Z/MZ.

2 Proofs of Theorems 1.2–1.4

Proof of Theorem 1.2. Fix A, B ⊂ Z and N ∈ N. As usual, μ(n) is the Möbius function and e(t) = e^{2πit}. Let d|N, then for any t ∈ Z

\frac{1}{d} N−1 ; ∑ ; \begin{matrix}j = 0 \\ \frac{N}{d} | j \end{matrix} e(\frac{tj}{N} ) = \{ \begin{matrix}1 & if d | t, \\ 0 & if d |̸ t. \end{matrix}  (2.1)

Let χ_{I} denote the characteristic function of the set I. Then for m|N,

χ_{(N,t)=m} = χ_{m|t} χ_{( \frac{N}{m} , \frac{t}{m})=1} = χ_{m|t} ∑_{l| \frac{N}{m} , l| \frac{t}{m}} μ(l)

= ∑_{l| \frac{N}{m}} μ(l)χ_{lm|t}

= ∑_{l| \frac{N}{m}} \frac{μ(l)}{lm} N−1 ; ∑ ; \begin{matrix}j = 0 \\ \frac{N}{lm}|j \end{matrix} e(\frac{tj}{N} )

= ∑_{j=0}^{N−1} e(\frac{tj}{N} ) ∑_{l| \frac{N}{m} , \frac{N}{lm} |j} \frac{μ(l)}{lm},  (2.2)

where we used (2.1) and that ∑_{v|u} μ(v) = χ_{u=1}. Taking v = N/m, we deduce that

A_{m} = #{(a, a′) ∈ A × A : (a − a′, N) = m} = ∑_{a,a′∈A} χ_{(a−a′,N)=N/v}

= ∑_{a,a′∈A} ∑_{j=0}^{N−1} e(\frac{(a − a′)j}{N} ) ∑_{l|v, \frac{v}{l} |j} \frac{μ(l)}{l}

= \frac{1}{N} ∑_{j=0}^{N−1} | ∑_{a∈A} e(\frac{aj}{N} )|^{2} ∑_{d|v, d|j} dμ(v/d),  (2.3)

where we substituted d = v/l. Let

s_{J} = |A(e(\frac{J}{N} ))| = | ∑_{a∈A} e(\frac{aJ}{N} )|, t_{J} = |B(e(\frac{J}{N} ))| = | ∑_{b∈B} e(\frac{bJ}{N} )|,

then from (2.3) we have

∑_{m|N} \frac{A_{m} B_{m}}{ϕ(N/m)} = ∑_{v|N} \frac{1}{ϕ(v)} (\frac{1}{N} ∑_{J=0}^{N−1} s_{J}^{2} ∑_{d|v, d|J} dμ(v/d)) (\frac{1}{N} ∑_{I=0}^{N−1} t_{I}^{2} ∑_{e|v, e|I} eμ(v/e))

= \frac{1}{N^{2}} ∑_{I,J=0}^{N−1} s_{J}^{2} t_{I}^{2} (∑_{v|N} \frac{1}{ϕ(v)} ∑_{d|v, d|J} dμ(v/d) ∑_{e|v, e|I} eμ(v/e)) .  (2.4)

Let g = (I, J, N), r = (J, N)/g, and s = (I, N)/g so that (r, s) = 1. Then

∑_{v|N} \frac{1}{ϕ(v)} ∑_{d|v, d|J} dμ(v/d) ∑_{e|v, e|I} eμ(v/e) = ∑_{v|N} \frac{1}{ϕ(v)} ∑_{d|(v,rg)} dμ(v/d) ∑_{e|(v,sg)} eμ(v/e)

= ∏_{p^{α}||N} (∑_{i=0}^{α} \frac{1}{ϕ(p^{i})} ∑_{d|(p^{i},rg)} dμ(\frac{p^{i}}{d} ) ∑_{e|(p^{i},sg)} eμ(\frac{p^{i}}{e} )) ,  (2.5)

since all the functions involved are multiplicative. Now

∑_{d|(p^{i},t)} dμ(\frac{p^{i}}{d} ) = \{ \begin{matrix}1 & if i = 0, \\ p^{i} − p^{i−1} & if i ≥ 1 & and & p^{i} | t, \\ −p^{i−1} & if i ≥ 1 & and & p^{i−1} || t, \\ 0 & if i ≥ 1 & and & p^{i} |̸ t. \end{matrix}

Write p^{γ}||g and p^{δ}||rs so that γ + δ ≤ α. Therefore

∑_{i=0}^{α} \frac{1}{ϕ(p^{i})} ∑_{d|(p^{i},rg)} dμ(\frac{p^{i}}{d} ) ∑_{e|(p^{i},sg)} eμ(\frac{p^{i}}{e} )

= 1 + ∑_{i=1}^{γ} \frac{1}{ϕ(p^{i})}(p^{i} − p^{i−1})^{2} + \{ \begin{matrix}0 & if γ = a, \\ \frac{1}{ϕ(p^{γ+1})}(−p^{γ})^{2} & if γ < α & and δ = 0, \\ \frac{1}{ϕ(p^{γ+1})}(−p^{γ})(p^{γ+1} − p^{γ}) & if γ < α & and δ ≥ 1 \end{matrix}

= \{ \begin{matrix}p^{γ} & if γ = a & (hence δ = 0), \\ p^{γ+1}/(p − 1) & if γ < α & and δ = 0, \\ 0 & if γ < α & and δ ≥ 1. \end{matrix}

We thus have a non-zero term in (2.5) if and only if δ = 0 for all p, that is r = s = 1, in other words (I, N) = (J, N) = g. In this case our answer is p^{γ} p^{α−γ}/ϕ(p^{α−γ}) = p^{α}/ϕ(p^{α−γ}). Therefore (2.5) becomes

∏_{p^{α}||N} \frac{p^{α}}{ϕ(p^{α−γ})} = \frac{N}{ϕ(N/g)}.

Substituting this into (2.4) gives

∑_{m|N} \frac{A_{m} B_{m}}{ϕ(N/m)} = \frac{1}{N} ∑_{g|N} \frac{1}{ϕ(N/g)}( ∑_{\begin{matrix}I=0 \\ (I,N)=g \end{matrix}}^{N−1} s_{I}^{2})( ∑_{\begin{matrix}J=0 \\ (J,N)=g \end{matrix}}^{N−1} t_{J}^{2}).  (2.6)

Let N/g = d and I = gi, so that (i, N/g) = (i, d) = 1. Then

∑_{\begin{matrix}I=0 \\ (I,N)=g \end{matrix}}^{N−1} s_{I}^{2} = ∑_{\begin{matrix}i=0 \\ (i,d)=1 \end{matrix}}^{N−1} |A(e(ig/N))|^{2} = ∑_{\begin{matrix}i=0 \\ (i,d)=1 \end{matrix}}^{N−1} |A(e(i/d))|^{2} = A_{d},

and similarly for ∑ t_{J}^{2}. Hence the right side of (2.6) equals

\frac{1}{N} ∑_{d|N} \frac{1}{ϕ(d)}A_{d} B_{d}.

The theorem follows.

Proof of Theorems 1.3 and 1.4. Apply Theorem 1.2 with M = N. We then have

\frac{1}{N} \frac{A_{1} B_{1}}{ϕ(1)} = \frac{|A|^{2} |B|^{2}}{M} ,  (2.7)

and, since all elements of A and B are distinct modulo M,

\frac{A_{M} B_{M}}{ϕ(N/M)} = |A| |B| = M.

In particular, the left side of (1.3) is greater or equal to M, since all the remaining terms are nonnegative.

We first deduce Theorem 1.3. We have A ⊕ B = Z/MZ if and only if (1.2) holds. (1.2) is in turn equivalent to

|A| |B| = M and A_{d} B_{d} = 0 for all d|M, d ≠ 1.

Thus A ⊕ B = Z/MZ if and only if |A| |B| = M and the right side of (1.3) equals |A|^{2} |B|^{2}/M = M. But the left side of (1.3) equals M if and only if A_{m} B_{m} = 0 for all m|M, m ≠ M, which in turn is equivalent to D_{A} ∩ D_{B} = ∅.

Assume now that D_{A} ∩ D_{B} = ∅. Then the left side of (1.3) equals M, therefore so does the right side. Using (2.7) and that all other terms on the right side of (1.3) are nonnegative, we find that M ≥ |A|^{2} |B|^{2}/M. It follows that |A| |B| ≤ M and equality holds if and only if

A_{d} B_{d} = 0 for all d|M, d ≠ 1.

By the same argument as above, this together with the equality |A| |B| = M is equivalent to A ⊕ B = Z/MZ. Theorem 1.4 is proved.

Our proof of Theorem 1.1 will be based on the following corollary of Theorem 1.2.

Corollary 2.1 Assume that A ⊕ B = Z/MZ. Define A_{m} as in Theorem 1.2. Let N|M, c ∈ Z \ B, and

b_{m} = b_{m}(c) = #{b ∈ B : (b − c, N) = m}.

Then the quantity

∑_{m|N} \frac{b_{m}(c)A_{m}}{ϕ(N/m)}  (2.8)

is independent of the choice of c.

Proof. Fix N such that N|M. Apply Theorem 1.2 with B replaced by C = B ∪ {c}, where c ∈ Z \ B will be allowed to vary later on. Define C(x) and C_{d} in the obvious way.

We first evaluate the terms on the right of (1.3). We have

\frac{A_{d} C_{d}}{N} = \frac{(|B| + 1)^{2}|A|^{2}}{N} .

If d ≠ 1, d|N, then d|M, hence Φ_{d}(x) divides at least one of A(x) or B(x). If it divides A(x), then A_{d} = 0. If it divides B(x), then for all roots ξ of Φ_{d}(x) we have |C(ξ)|^{2} = |B(ξ)+ξ^{c}|^{2} = |ξ^{c}|^{2} = 1, hence C_{d} = #{ξ : Φ_{d}(ξ) = 0} = ϕ(d). Combining all this we find that the right side of (1.3) equals

\frac{1}{N} (|B| + 1)^{2}|A|^{2} + \frac{1}{N} ∑_{d|N,d≠1} A_{d}.  (2.9)

Observe that this is independent of the choice of c.

Next, we have C_{m} = B_{m} + 2b_{m}, hence the left side of (1.3) equals

∑_{m|N} \frac{A_{m}B_{m}}{ϕ(N/m)} + ∑_{m|N} \frac{2b_{m}A_{m}}{ϕ(N/m)}.  (2.10)

Comparing (2.10) and (2.9) we obtain (2.8).

We remark that (2.8) can be computed explicitly if N = M. Namely, choose c so that c = b + kN ∈ B + NZ. If m|N, m ≠ N, then b_{m} ≠ 0 implies that there is an b′ ∈ B such that (c − b′, M) = m, hence (b − b′, M) = m and m ∈ D_{B}. By Theorem 1.4, m ∉ D_{A} and A_{m} = 0. It follows that b_{m}A_{m} = 0 for all m ≠ M. Moreover, b_{M} = 1 and A_{M} = |A|. Hence

∑_{m|N} \frac{b_{m}(c)A_{m}}{ϕ(N/m)} = |A| if N = M.  (2.11)

3 The tiling result

In this section we prove Theorem 1.1. Let A, B, M be as in the statement of the theorem.

Throughout the proof we will assume that B is not contained in dZ for any d|M, d ≠ 1, for otherwise we may decompose the tiling as in Lemma 2.5 of [1] and proceed by induction. More precisely, suppose that the theorem is true for all sets A′ whose cardinality |A′| divides, but is not equal to, |A|. Suppose further that B ⊂ pZ. By Lemma 2.5 of [1] we have

A(x) = ∑_{i=0}^{p−1} x^{a_{i}} Ā^{(i)}(x^{p}),

where A^{(i)} = {a ∈ A : a ≡ i (mod p)}, a_{i} = min(A^{(i)}), and Ā^{(i)} = {(a − a_{i})/p : a ∈ A^{(i)}}. Moreover, we have

|A^{(0)}| = |A^{(1)}| = … = |A^{(p−1)}| = |A|/p,  (3.1)
Ā^{(i)} ⊕ p^{−1}B = Z/Mp^{−1}Z, i = 0, 1, …, p − 1,  (3.2)
SĀ^{(0)} = SĀ^{(1)} = … = SĀ^{(p−1)}  (3.3)

and

S_{A} = {p} ∪ S_{pĀ^{(0)}}.  (3.4)

Suppose that Φ_{p}(x), Φ_{q}(x), Φ_{r}(x) divide A(x). By (3.4), Φ_{q}(x) and Φ_{r}(x) divide Ā^{(0)}(x^{p}). By Lemma 1.1(7) of [1], Φ_{q}(x) and Φ_{r}(x) divide Ā^{(0)}(x), hence also Ā^{(i)}(x) for all i by (3.3). Since Ā^{(i)} tiles Z by (3.2), it follows from the inductive assumption that Φ_{qr}(x) divides Ā^{(i)}(x) for each i. Using Lemma 1.1(7) of [1] again, we deduce that Φ_{pq}(x), Φ_{pr}(x), Φ_{qr}(x), Φ_{pqr}(x) divide Ā^{(i)}(x^{p}) for each i, hence they also divide A(x). Thus if we assume A to be a set of the smallest cardinality for which the theorem fails, the corresponding B cannot be a subset of pZ, qZ, or rZ.

The following notation will be used throughout this section. We write [i, j, k] = n_{i,j,k} +pqrZ, where n_{i,j,k} is the unique integer in {0, 1, …, pqr − 1} equal to i(mod p), j(mod q), k(mod r). We also write [∗, j, k] = ⋃_{i}[i, j, k], [∗, ∗, k] = ⋃_{i,j}[i, j, k], etc. One can think of the residues modulo p, q, r as three-dimensional “coordinates”, so that for example [i, j, k] is a point, [i, j, ∗] is a vertical line, and [∗, ∗, k] is a horizontal plane.

Lemma 3.1 Let B ⊂ Z. Assume that 0 ∈ B and

B − B ⊂ pZ ∪ qZ ∪ rZ.  (3.5)

Then at least one of the following holds:

B ⊂ [∗, j, k] ∪ [i, ∗, k] ∪ [i, j, ∗] for some i, j, k,  (3.6)

B ⊂ [0, 0, 0] ∪ [i, j, 0] ∪ [i, 0, k] ∪ [0, j, k] for some i, j, k,  (3.7)
B ⊂ [∗, ∗, 0], or B ⊂ [∗, 0, ∗], or B ⊂ [0, ∗, ∗].  (3.8)

Proof. Suppose that (3.6) and (3.8) fail. Then in particular there is an b ∈ B which is not in the set on the right of (3.6) with i = j = k = 0, say b ∈ [i, j, 0] for some i, j ≠ 0. From our assumptions we have B − b ⊂ pZ ∪ qZ ∪ rZ. Hence

\begin{aligned}B & ⊂ ([∗, ∗, 0] ∪ [0, ∗, ∗] ∪ [∗, 0, ∗]) ∩ ([∗, ∗, 0] ∪ [i, ∗, ∗] ∪ [∗, j, ∗]) \\ & = [∗, ∗, 0] ∪ [i, 0, ∗] ∪ [0, j, ∗]. \end{aligned}

From the failure of (3.8) we deduce that at least one of the following holds:

(a) there is a b′ ∈ B such that b′ ∈ [i, 0, ∗] \ [∗, ∗, 0],

(b) there is a b′′ ∈ B such that b′′ ∈ [0, j, ∗] \ [∗, ∗, 0].

Suppose that (a) holds, then B − b′ ⊂ pZ ∪ qZ ∪ rZ, hence B ∩ [0, ∗, ∗] ⊂ [∗, 0, 0] ∪ [i, ∗, 0]. Thus we have (3.6) unless (a) and (b) both hold. In the latter case, b′ ∈ [i, 0, k] and b′′ ∈ [0, j, k′] for some k, k′ ≠ 0. We then see from (3.5) that k = k′ and that (3.7) holds.

By Theorem 1.3, at least one of the sets D_{A}, D_{B} does not contain 1. We deduce that at least one of A − A, B − B satisfies (3.5), hence at least one of A, B obeys the conclusions of Lemma 3.1. We will now show that A cannot obey these conclusions. Indeed, we are assuming that the elements of A are distributed uniformly mod p, mod q, and mod r. Hence each plane [i, ∗, ∗] contains exactly |A|/p elements of A, etc. This immediately contradicts (3.7) and (3.8), since in both of these cases there are planes which do not contain any elements of A. Suppose now that (3.6) holds. Assume that p < r and let i′ ≠ i. By uniformity mod r and mod p, the planes [∗, ∗, k] and [i′, ∗, ∗] contain exactly |A|/r and |A|/p elements of A. But by (3.6), all the elements of A which belong to [i′, ∗, ∗] are in fact in [i′, j, k], hence in [∗, ∗, k]. This implies |A|/p ≤ |A|/r, which contradicts the assumption that p < r.

Thus B satisfies one of (3.6), (3.7) (recall that we assume that (3.8) fails).

We record a simple lemma.

Lemma 3.2 Let A ⊂ Z. Then for any m we have

|\{(a, a′) ∈ A × A : m|a − a′\}| ≥ \frac{|A|^{2}}{m} ,

with equality if and only if the elements of A are equi-distributed mod m.

Let N = pqr. For m|N, we write α_{m} = \frac{A_{m}}{ϕ(N/m)}. It suffices to prove that

α_{m} = α_{m′} for all m, m′|N.  (3.9)

Indeed, (3.9) implies that

|A|^{2} = ∑_{m|pqr} A_{m} = ∑_{m|pqr} ϕ(\frac{pqr}{m})A_{pqr} = pqrA_{pqr},

and the theorem follows by Lemma 3.2.

It remains to deduce (3.9) from Corollary 2.1.

Case 1a. Assume that B satisfies (3.7) and that p, q, r > 2. We may then choose I, J, K such that I ≠ 0, i, J ≠ 0, j, K ≠ 0, k, and the planes [I, ∗, ∗], [∗, J, ∗], [∗, ∗, K] contain no elements of B. We first compare (2.8) with c ∈ [I, J, K] and c′ ∈ [0, J, K]. We then have

b_{1}(c) = |B|, b_{m}(c) = 0 if m ≠ 1,
b_{1}(c′) = |B ∩ [i, ∗, ∗]|, b_{p}(c′) = |B ∩ [0, ∗, ∗]| ≠ 0, b_{m}(c′) = 0 if m ≠ 1, p.

Substituting this in (2.8) we see that

|B|α_{1} = |B ∩ [i, ∗, ∗]|α_{1} + |B ∩ [0, ∗, ∗]|α_{p},

hence α_{1} = α_{p}. Repeating this argument with p replaced by q and r, we obtain

α_{p} = α_{q} = α_{r} = α_{1}.  (3.10)

With I, J, K as above, let c′′ ∈ [0, 0, K], then

b_{pq} = |B ∩ [0, 0, 0]| ≠ 0, b_{pr} = b_{qr} = b_{pqr} = 0.

Comparing (2.8) for c and c′′, and using also (3.10), we find that α_{pq} = α_{1}. Similarly for α_{qr} and α_{pr}, hence

α_{1} = α_{pq} = α_{pr} = α_{qr}.  (3.11)

It only remains to prove that α_{pqr} = α_{1}. But this follows by applying (2.8) and (3.10), (3.11) to c as above and c′′′ ∈ [0, 0, 0].

Case 1b. Assume now that B satisfies (3.7) and that p = 2. Let

t = |B ∩ [0, 0, 0]|, x = |B ∩ [i, j, 0]|, y = |B ∩ [0, j, k]|, z = |B ∩ [i, 0, k]|.

Since the case when (3.6) holds will be considered below, we may now assume that (3.6) fails, and in particular that t, x, y, z are all nonzero. Choose J, K such that J ≠ 0, j, K ≠ 0, k, and the planes [∗, J, ∗], [∗, ∗, K] contain no elements of B. We first evaluate (2.8) with c ∈ [0, J, K], [0, J, 0], [0, J, k], and find that the following are all equal:

\begin{aligned}(t + y)α_{2} + (x + z)α_{1} & = C, \\ tα_{2r} + yα_{2} + xα_{r} + zα_{1} & = C, \\ yα_{2r} + tα_{2} + xα_{r} + zα_{1} & = C. \end{aligned}

Therefore

\begin{aligned}t(α_{2} − α_{2r}) + x(α_{1} − α_{r}) & = 0, \\ y(α_{2} − α_{2r}) + z(α_{1} − α_{r}) & = 0. \end{aligned}  (3.12)

Similarly, by considering (2.8) with c in [1, J, K], [1, J, 0], [1, J, k] we obtain that

\begin{aligned}x(α_{2} − α_{2r}) + t(α_{1} − α_{r}) & = 0, \\ z(α_{2} − α_{2r}) + y(α_{1} − α_{r}) & = 0. \end{aligned}  (3.13)

Combining the first equations in (3.12), (3.13) we deduce that (x − t)(α_{2} − α_{2r} − α_{1} + α_{r}) = 0. Similarly, combining the second equations we deduce that (y − z)(α_{2} − α_{2r} − α_{1} + α_{r}) = 0. It follows that

α_{2} − α_{2r} = α_{1} − α_{r}.  (3.14)

Indeed, if (3.14) fails, we must have x = t and y = z, in which case B is equi-distributed mod 2 and Φ_{2}(ξ) divides both A(ξ) and B(ξ). This is easily seen to be impossible, e.g. by (T1). We now substitute (3.14) in the first equation in (3.13):

(t + x)(α_{2} − α_{2r}) = (t + x)(α_{1} − α_{r}) = 0.

Since t + x > 0, it follows that α_{1} = α_{r} and α_{2} = α_{2r}. We now repeat the same argument with r replaced by q, and conclude that

α_{1} = α_{r} = α_{q}, α_{2} = α_{2r} = α_{2q}.  (3.15)

Next, we evaluate (2.8) for c in [0, 0, 0], [1, 0, 0], [0, j, 0], [1, j, 0], [0, 0, k], [1, j, k]. Using also (3.15), we obtain that

\begin{aligned}tα_{2qr} + xα_{r} + yα_{2} + zα_{q} & = tα_{2qr} + (x + z)α_{1} + yα_{2} & = C, \\ tα_{qr} + zα_{2q} + xα_{2r} + yα_{1} & = tα_{qr} + (x + z)α_{2} + yα_{1} & = C, \\ tα_{2r} + xα_{qr} + yα_{2q} + zα_{1} & = xα_{qr} + (y + t)α_{2} + zα_{1} & = C, \\ xα_{2qr} + tα_{r} + yα_{q} + zα_{2} & = xα_{2qr} + (y + t)α_{1} + zα_{2} & = C, \\ tα_{2q} + zα_{qr} + yα_{2r} + xα_{1} & = zα_{qr} + (t + y)α_{2} + xα_{1} & = C, \\ yα_{qr} + xα_{2q} + zα_{2r} + tα_{1} & = yα_{qr} + (x + z)α_{2} + tα_{1} & = C. \end{aligned}  (3.16)

From equations 2,6 we have (t − y)(α_{qr} − α_{1}) = 0, and from equations 3,5 (x − z)(α_{qr} − α_{1}) = 0. Suppose first that t ≠ y or x ≠ z, hence α_{qr} = α_{1}. Then we deduce from equations 2,4 that α_{2} = α_{2qr}. Substituting this in equations 1 and 2, we find that

(x + z)α_{1} + (t + y)α_{2} = (x + z)α_{2} + (t + y)α_{1},

hence (x+z−t−y)(α_{1} −α_{2}) = 0. Now x+z ≠ t+y, since otherwise B would be equi-distributed mod 2 and we have already noted that this is impossible. Therefore α_{1} = α_{2}, hence all the α_{m} are equal and we are done.

It remains to consider the case when t = y and x = z. Then we rewrite equations 1,2,3,5 in (3.16) as

\begin{aligned}2xα_{1} & +tα_{2} & & +tα_{2qr} & = C, \\ tα_{1} & +2xα_{2} & +tα_{qr} & & = C, \\ 2tα_{1} & +xα_{2} & & +xα_{2qr} & = C, \\ xα_{1} & +2tα_{2} & +xα_{qr} & & = C. \end{aligned}  (3.17)

The determinant of the coefficient matrix is −4(t^{2} − x^{2})^{2}. If it were 0, we would have x = t = y = z, and in particular |B| = x + y + z + t = 4t would be divisible by 4, which contradicts the assumption that |B| = 2qr. Hence (3.17) has only the trivial solution α_{1} = α_{2} = α_{qr} = α_{2qr}. This together with (3.15) implies that all the α_{m} are equal, which completes the proof for Case 1b.

Case 2. Assume that B satisfies (3.6). Translating B if necessary, we may assume that (3.6) holds with i = j = k = 0. Denote

t = |B ∩ [0, 0, 0]|,
x_{i} = |B ∩ [i, 0, 0]|, y_{j} = |B ∩ [0, j, 0]|, z_{k} = |B ∩ [0, 0, k]|, i, j, k > 0,
X = ∑ x_{i}, Y = ∑ y_{i}, Z = ∑ z_{i}.

Since we are assuming that (3.8) fails, we have X, Y, Z ≠ 0.

Applying Corollary 2.1 to c in [i, j, k], [i, j, 0], [i, 0, k], [0, j, k], [i, 0, 0], [0, j, 0], [0, 0, k], [0, 0, 0], where i, j, k ≠ 0, we obtain that the following are all equal (denote the right-hand side by C):

\begin{aligned}(X − x_{i} + Y − y_{j} + Z − z_{k} + t)α_{1} + x_{i}α_{p} + y_{j}α_{q} + z_{k}α_{r} & = C, \\ (X − x_{i} + Y − y_{j} + t)α_{r} + x_{i}α_{pr} + y_{j}α_{qr} + Zα_{1} & = C, \\ (X − x_{i} + Z − z_{k} + t)α_{q} + x_{i}α_{pq} + z_{k}α_{qr} + Y α_{1} & = C, \\ (Y − y_{j} + Z − z_{k} + t)α_{p} + y_{j}α_{pq} + z_{k}α_{pr} + Xα_{1} & = C, \\ x_{i}α_{pqr} + (X − x_{i} + t)α_{qr} + (Y + Z)α_{1} & = C, \\ y_{j}α_{pqr} + (Y − y_{j} + t)α_{pr} + (X + Z)α_{1} & = C, \\ z_{k}α_{pqr} + (Z − z_{k} + t)α_{pq} + (X + Y)α_{1} & = C, \\ tα_{pqr} + Xα_{qr} + Y α_{pr} + Zα_{pq} & = C. \end{aligned}  (3.18)

We have to prove that this is possible if and only if all the α_{m} are equal. We begin with a few lemmas.

Lemma 3.3 Let A ⊂ Z, |A|^{2} = pqrL, N = prq. Define α_{m} as above. Assume that Φ_{p}, Φ_{q}, Φ_{r}, Φ_{pr} divide A(x). Then:

(q − 1)α_{pr} + α_{pqr} = qL,  (3.19)
(q − 1)α_{r} + α_{qr} = (q − 1)α_{p} + α_{pq} = qL,  (3.20)
(q − 1)α_{1} + α_{q} = qL.  (3.21)

Proof. We will first prove that if Φ_{p}, Φ_{q}, Φ_{r} divide A(x), then:

\begin{matrix}(q − 1)(r − 1)α_{p} + (r − 1)α_{pq} + (q − 1)α_{pr} + α_{pqr} = qrL, \\ (p − 1)(r − 1)α_{q} + (r − 1)α_{pq} + (p − 1)α_{qr} + α_{pqr} = prL, \\ (p − 1)(q − 1)α_{r} + (q − 1)α_{pr} + (p − 1)α_{qr} + α_{pqr} = pqL, \end{matrix}  (3.22)

and

\begin{matrix}(q − 1)(r − 1)α_{1} + (r − 1)α_{q} + (q − 1)α_{r} + α_{qr} = qrL, \\ (p − 1)(r − 1)α_{1} + (r − 1)α_{p} + (p − 1)α_{r} + α_{pr} = prL, \\ (p − 1)(q − 1)α_{1} + (q − 1)α_{p} + (p − 1)α_{q} + α_{pq} = pqL. \end{matrix}  (3.23)

Indeed, from Lemma 3.2 with m = p we have

A_{p} + A_{pq} + A_{pr} + A_{pqr} = \frac{|A|^{2}}{p} = qrL,

and the first equation in (3.22) follows by converting the A_{m} to α_{m}. Also, since ∑_{m|pqr} A_{m} = |A|^{2}, from the displayed equation above we have

A_{1} + A_{q} + A_{r} + A_{qr} = (1 − \frac{1}{p})|A|^{2} = (p − 1)qrL,

and the first equation in (3.23) follows. The remaining equations in (3.22), (3.23) are similar. Assume now that also Φ_{pr}(x)|A(x). Applying Lemma 3.2 with m = pr, we obtain

A_{pr} + A_{pqr} = \frac{|A|}{pr} = qL,

which implies (3.19). (3.20) follows by combining (3.19) with the first and third equations in (3.22), and (3.21) by combining the first equation in (3.20) with the first equation in (3.23).

Lemma 3.4 Suppose that α_{m} solve (3.18) with X, Y, Z ≠ 0, and that

α_{1} = α_{p}, α_{r} = α_{pr}, α_{q} = α_{pq}, α_{qr} = α_{pqr}.  (3.24)

Then the α_{m} are all equal.

Proof. Fix i, j, k. Plugging (3.24) into (3.18), we obtain

\begin{aligned}(X + Y − y_{j} + Z − z_{k} + t)α_{1} + y_{j}α_{q} + z_{k}α_{r} & = C, \\ (X + Y − y_{j} + t)α_{r} + y_{j}α_{qr} + Zα_{1} & = C, \\ (X + Z − z_{k} + t)α_{q} + z_{k}α_{qr} + Y α_{1} & = C, \\ (Y − y_{j} + Z − z_{k} + t)α_{p} + y_{j}α_{q} + z_{k}α_{r} + Xα_{1} & = C, \\ (X + t)α_{qr} + (Y + Z)α_{1} & = C, \\ y_{j}α_{qr} + (Y − y_{j} + t)α_{r} + (X + Z)α_{1} & = C, \\ z_{k}α_{qr} + (Z − z_{k} + t)α_{q} + (X + Y)α_{1} & = C, \\ (t + X)α_{qr} + Y α_{r} + Zα_{q} & = C. \end{aligned}  (3.25)

From equations 2 and 6 in (3.25) we have Xα_{r} = Xα_{1}, hence α_{r} = α_{1}. Similarly, from equations 3 and 7 we have Xα_{q} = Xα_{1}, hence α_{q} = α_{1}. We now have α_{1} = α_{p} = α_{q} = α_{r} = α_{pr} = α_{pq}. Plugging this into equation 1 we obtain (X + Y + Z + t)α_{1} = C; this together with equation 5 yields that (X + t)α_{qr} = (X + t)α_{1}, hence α_{qr} = α_{1}. By the last part of (3.24) we also have α_{pqr} = α_{1}, which ends the proof.

We now begin the proof of Theorem 1.1 under the assumption that B satisfies (3.6). It suffices to consider the case when

x_{i} = x, y_{j} = y, z_{k} = z  (3.26)

for some x, y, z ≠ 0 and all i, j, k ≠ 0. (Hence X = (p − 1)x, Y = (q − 1)y, Z = (r − 1)z.) Indeed, suppose for instance that x_{i} ≠ x_{i′} for some i, i′. Fix some j, k, and apply (3.18) with i, j, k and i′, j, k. From equations 1, 2, 3, 5 in (3.18) we find that (3.24) holds, hence by Lemma 3.4 all the α_{m} are equal and we are done.

Lemma 3.5 Assume that B satisfies (3.6) and that (3.26) holds. Then:

• Φ_{pq}(ξ)|B(ξ) if and only if t = x + y + z − zr;

• Φ_{qr}(ξ)|B(ξ) if and only if t = x + y + z − xp;

• Φ_{pr}(ξ)|B(ξ) if and only if t = x + y + z − yq;

• Φ_{pqr}(ξ)|B(ξ) if and only if t = x + y + z.

Proof. We have

B(ξ) = t + x(ξ^{qr} + ξ^{2qr} + … + ξ^{(p−1)qr}) + y(ξ^{pr} + ξ^{2pr} + … + ξ^{(q−1)pr})

+z(ξ^{pq} + ξ^{2pq} + … + ξ^{(r−1)pq})
= t + x(Φ_{p}(ξ^{qr}) − 1) + y(Φ_{q}(ξ^{pr}) − 1) + z(Φ_{r}(ξ^{pq}) − 1).

Hence

B(e^{2πi/pq}) = t + xΦ_{p}(e^{2πir/p}) + yΦ_{q}(e^{2πir/q}) + zΦ_{r}(1) − x − y − z = t + zr − x − y − z,

and similarly

B(e^{2πi/qr}) = t − x − y − z + px,
B(e^{2πi/pr}) = t − x − y − z + qy,
B(e^{2πi/pqr}) = t − x − y − z.

The lemma follows.

Corollary 3.6 Let B be as in Lemma 3.5.

• If Φ_{pqr}(ξ)|B(ξ), then none of Φ_{pq}(ξ), Φ_{qr}(ξ), Φ_{pr}(ξ) can divide B(ξ).

• Assume that |B| = pqr, then at most one of Φ_{pq}(ξ), Φ_{qr}(ξ), Φ_{pr}(ξ) can divide B(ξ).

Proof. The first part is obvious from Lemma 3.5, since x, y, z ≠ 0. Suppose now that |B| = pqr and that Φ_{pq}, Φ_{qr} divide B(ξ). By Lemma 3.5 we have t = x + y + z − zr = x + y + z − px, hence px = zr, and in particular p|z, r|x. Moreover, adding up the elements of B we obtain

|B| = pqr = t + (p − 1)x + (q − 1)y + (r − 1)z = px + qy = qy + rz,

hence qr|x and pr|y. But then pqr = pqr \frac{x}{qr} + pqr \frac{y}{pr} , therefore x = 0 or y = 0 – a contradiction.

We return to the proof of Theorem 1.1. If Φ_{pq}(x), Φ_{qr}(x), Φ_{pr}(x), Φ_{pqr}(x) divide A(x), we are done. Assume therefore that at least one of them divides B(x). By Corollary 3.6, we only need to consider two cases.

Case 2a: Φ_{pq}(ξ)|B(ξ), Φ_{pr}(ξ)Φ_{qr}(ξ)|A(ξ). From Lemma 3.5 we have t = x + y − Z, which we substitute in (3.18):

\begin{aligned}(X + Y − z)α_{1} + xα_{p} + yα_{q} + zα_{r} & = C, \\ (X + Y − Z)α_{r} + xα_{pr} + yα_{qr} + Zα_{1} & = C, \\ (X + y − z)α_{q} + xα_{pq} + zα_{qr} + Y α_{1} & = C, \\ (Y + x − z)α_{p} + yα_{pq} + zα_{pr} + Xα_{1} & = C, \\ xα_{pqr} + (X + y − Z)α_{qr} + (Y + Z)α_{1} & = C, \\ yα_{pqr} + (Y + x − Z)α_{pr} + (X + Z)α_{1} & = C, \\ zα_{pqr} + (x + y − z)α_{pq} + (X + Y)α_{1} & = C, \\ (x + y − Z)α_{pqr} + Xα_{qr} + Y α_{pr} + Zα_{pq} & = C. \end{aligned}  (3.27)

We also have from Lemma 3.3:

\begin{matrix}Y α_{pr} + yα_{pqr} = Y α_{p} + yα_{pq} = Y α_{r} + yα_{qr} = Y α_{1} + yα_{q} = qyL, \\ Xα_{qr} + xα_{pqr} = Xα_{q} + xα_{pq} = Xα_{r} + xα_{pr} = Xα_{1} + xα_{p} = pxL, \end{matrix}  (3.28)

where as before we denote L = |A|^{2}/pqr. Plugging (3.28) into (3.27), we obtain:

\begin{aligned}z(α_{r} − α_{1}) + pxL + qyL & = C, \\ Z(α_{1} − α_{r}) + pxL + qyL & = C, \\ z(α_{qr} − α_{q}) + pxL + qyL & = C, \\ z(α_{pr} − α_{p}) + pxL + qyL & = C, \\ (y − Z)α_{qr} + (Y + Z)α_{1} + pxL & = C, \\ (x − Z)α_{pr} + (X + Z)α_{1} + qyL & = C, \\ zα_{pqr} + (x + y − z)α_{pr} + (X + Y)α_{1} & = C, \\ Z(α_{pq} − α_{pqr}) + pxL + qyL & = C. \end{aligned}  (3.29)

From equations 1,2 in (3.29) we have α_{1} = α_{r} and C = pxL + qyL. From equations 3,4,8 respectively we then have α_{q} = α_{qr}, α_{p} = α_{pr}, α_{pq} = α_{pqr}. Thus we may apply Lemma 3.4 (with p and r interchanged) and conclude that all the α_{m} are equal.

Case 2b. Φ_{pqr}(ξ)|B(ξ), Φ_{pq}(ξ)Φ_{qr}(ξ)Φ_{pr}(ξ)|A(ξ). By (3.19)–(3.21) we have

\begin{matrix}(p − 1)α_{qr} + α_{pqr} = (p − 1)α_{q} + α_{pq} = (p − 1)α_{r} + α_{pr} = (p − 1)α_{1} + α_{p} = pL, \\ (q − 1)α_{pr} + α_{pqr} = (q − 1)α_{p} + α_{pq} = (q − 1)α_{r} + α_{qr} = (q − 1)α_{1} + α_{q} = qL, \\ (r − 1)α_{pq} + α_{pqr} = (r − 1)α_{r} + α_{pr} = (r − 1)α_{q} + α_{qr} = (r − 1)α_{1} + α_{r} = rL. \end{matrix}  (3.30)

Thus we can compute all the α_{m} if α_{1} = α is given:

\begin{matrix}α_{p} = pL − (p − 1)α, \\ α_{q} = qL − (q − 1)α, \\ α_{r} = rL − (r − 1)α, \\ α_{pq} = (p − 1)(q − 1)α − (pq − p − q)L, \\ α_{pr} = (p − 1)(r − 1)α − (pr − p − r)L, \\ α_{qr} = (q − 1)(r − 1)α − (qr − q − r)L, \\ α_{pqr} = ((p − 1)(q − 1)(r − 1) + 1)L − (p − 1)(q − 1)(r − 1)α. \end{matrix}  (3.31)

If Φ_{pqr} does not divide A(ξ), by Lemma 3.2 with m = pqr we have A_{pqr} = α_{pqr} > L, hence (from the last equation above) L > α. We have to show that this is impossible.

By Lemma 3.5 we have t = x + y + z. We substitute this in the last four equations in (3.18):

\begin{aligned}xα_{pqr} + (X + y + z)α_{qr} + (Y + Z)α_{1} & = C, \\ yα_{pqr} + (Y + x + z)α_{pr} + (X + Z)α_{1} & = C, \\ zα_{pqr} + (x + y + Z)α_{pq} + (X + Y)α_{1} & = C, \\ (x + y + z)α_{pqr} + Xα_{qr} + Y α_{pr} + Zα_{pq} & = C. \end{aligned}  (3.32)

(the remaining equations are equivalent). We now plug in (3.30). From the last equation we

have

xpL + yqL + zrL = C.  (3.33)

The remaining equations become

\begin{aligned}xpL + (y + z)α_{qr} + (Y + Z)α_{1} & = C, \\ yqL + (x + z)α_{pr} + (X + Z)α_{1} & = C, \\ zrL + (x + y)α_{pq} + (X + Y)α_{1} & = C. \end{aligned}  (3.34)

This adds up to

xpL + yqL + zrL + (y + z)α_{qr} + (x + z)α_{pr} + (x + y)α_{pq} + 2(X + Y + Z)α_{1} = 3C,

hence by (3.33)

(y + z)α_{qr} + (x + z)α_{pr} + (x + y)α_{pq} = 2(pxL + qyL + rzL − Xα_{1} − Y α_{1} − Zα_{1}).

By (3.30), the left side equals

2(pxL − Xα_{p} + qyL − Y α_{q} + rzL − Zα_{r}).

But now we can use (3.31). If L > α, we have

α_{p} = pL − (p − 1)α > α = α_{1}

and similarly α_{q} > α_{1}, α_{r} > α_{1}, which clearly contradicts the above.

Acknowledgement. The first and third authors are supported in part by the NSF. The second author is supported in part by NSERC.

References

[1] E. Coven, A. Meyerowitz: Tiling the integers with translates of one finite set, J. Algebra 212 (1999), 161–174.

[2] B. Fuglede: Commuting self-adjoint partial differential operators and a group-theoretic problem, J. Funct. Anal. 16 (1974), 101–121.

[3] I. Łaba: The spectral set conjecture and multiplicative properties of roots of polynomials, preprint, 2000.

[4] J.C. Lagarias, S. Szabó: Universal spectra and Tijdeman’s conjecture on factorization of cyclic groups, J. Fourier Anal. Appl., to appear.

[5] J.C. Lagarias, Y. Wang: Tiling the line with translates of one tile, Invent. Math. 124 (1996), 341–365.

[6] J.C. Lagarias, Y. Wang: Spectral sets and factorization of finite abelian groups, J. Funct. Anal. 145 (1997), 73–98.

[7] D.J. Newman: Tesselation of integers, J. Number Theory 9 (1977), 107–111.

[8] A. Sands: On Keller’s conjecture for certain cyclic groups, Proc. Edinburgh Math. Soc. 2 (1979), 17–21.

[9] S. Szabó: A type of factorization of finite abelian groups, Discrete Math. 54 (1985), 121– 124.

[10] R. Tijdeman: Decomposition of the integers as a direct sum of two subsets, in Number Theory (Paris 1992–1993), London Math. Soc. Lecture Note Ser., vol. 215, 261–276, Cambridge Univ. Press, Cambridge, 1995.

Department of Mathematics, University of Georgia, Athens, GA 30602, U.S.A.

E-mail address: andrew@math.uga.edu

Department of Mathematics, University of British Columbia, Vancouver, B.C. V6T 1Z2, Canada

E-mail address: ilaba@math.ubc.ca

School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, U.S.A.

E-mail address: wang@math.gatech.edu