TILING THE INTEGERS WITH

TRANSLATES OF ONE FINITE SET

Ethan M. Coven and Aaron Meyerowitz

Abstract. A set tiles the integers if and only if the integers can be written as a disjoint union of translates of that set. We consider the problem of finding necessary and sufficient conditions for a finite set to tile the integers. For sets of prime power size, it was solved by D. Newman [J. Number Theory 9 (1977), 107–111]. We solve it for sets of size having at most two prime factors. The conditions are always sufficient, but it is unknown whether they are necessary for all finite sets.

Introduction

Let A be a finite set of integers. A tiles the integers if and only if the integers can be written as a disjoint union of translates of A, equivalently, there is a set C such that every integer can be expressed uniquely a + c with a ∈ A and c ∈ C. In symbols, A ⊕ C = ℤ. In this case A is called a tile, A ⊕ C = ℤ a tiling, and C the translation set. For a survey of such tilings, see R. Tijdeman [Tij]. For connections with group theory and functional analysis, see [Haj] and [L-W].

We consider the problem of finding necessary and sufficient conditions for a finite set to tile the integers. For sets of prime power size (cardinality, denoted #), it was solved by D. Newman [New]. Newman remarked that “even for so simple a case as size six we do not know the answer.” We find necessary and sufficient conditions for A to tile the integers when #A has at most two prime factors.

There is no loss of generality in restricting attention to translates of a finite set A of nonnegative integers. Then A(x) = ∑_{a∈A} x^{a} is a polynomial such that #A = A(1). Let S_{A} be the set of prime powers s such that the s-th cyclotomic polynomial Φ_{s}(x) divides A(x). Consider the following conditions on A(x).

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

(T2) If s_{1}, …, s_{m} ∈ S_{A} are powers of distinct primes, then Φ_{s_{1}···s_{m}}(x) di-

vides A(x).

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05B45; Secondary 11B75, 20K01.

Part of this work was done while the first author was a member of the Mathematical Sciences Research Institute (MSRI), where research is supported in part by NSF grant DMS-9701755.

The authors thank J. Propp for putting them in touch with each other. The first author thanks J. Jungman and M. Keane for helpful conversations.

Theorem A. If A(x) satisfies (T1) and (T2), then A tiles the integers.

Theorem B1. If A tiles the integers, then A(x) satisfies (T1).

Theorem B2. If A tiles the integers and #A has at most two prime factors, then A(x) satisfies (T2).

Corollary. If #A has at most two prime factors, then A tiles the integers if and only if A(x) satisfies (T1) and (T2).

It is unknown whether the sufficient conditions (T1) and (T2) are necessary for any finite set to tile the integers. (T1) is necessary but not sufficient (see the example after Theorem B1 in Section 2). However, if #A is a prime power, then (T2) follows from (T1), so in this case (T1) is necessary and sufficient. An examination of Newman’s proof [New, Theorem 1] essentially yields this result.

Our proof of Theorem B2 provides a structure theory for finite sets A such that A tiles the integers and #A has at most two prime factors. We sketch this in Section 4.

If A is a finite set which tiles the integers, then ⋃_{a∈A}[a, a + 1) tiles the reals. J. Lagarias and Y. Wang [L-W] proved a structure theorem for closed subsets T of the reals with finite Lebesgue measure and boundary of measure zero such that the reals can be written as a countable union of measure-disjoint translates of T. It describes such sets in terms of finite sets which tile the integers.

1. Preliminaries

For A and B sets or multisets of integers, we denote the multiset {a + b : a ∈ A, b ∈ B} by A + B. We write A ⊕ B when every element can be expressed uniquely a + b. For k an integer, we write kA for {ka : a ∈ A}, we call {k} ⊕ A a translate of A, and when k is a factor of every a ∈ A, we write A/k for {a/k : a ∈ A}.

For s ≥ 1, the s-th cyclotomic polynomial Φ_{s}(x) is defined recursively by x^{s}−1 = ∏ Φ_{t}(x), where the product is taken over all factors t of s. The factors of s are positive and include both 1 and s.

Lemma 1.1. Let p be prime. Then (1) Φ_{s}(x) is the minimal polynomial of any primitive s-th root of unity.

(2) 1 + x + ⋯ + x^{s−1} = ∏ Φ_{t}(x), where the product is taken over all factors t > 1 of s.

(3) Φ_{p}(x) = 1 + x + ⋯ + x^{p−1} and Φ_{p^{α+1}}(x) = Φ_{p}(x^{p^{α}}).

(4) Φ_{s}(1) = \{ \begin{matrix}0 & if s = 1 \\ q & if s is a power of a prime q \\ 1 & otherwise. \end{matrix}

(5) Φ_{s}(x^{p}) = \{ \begin{matrix}Φ_{ps}(x) & if p is a factor of s \\ Φ_{s}(x)Φ_{ps}(x) & if p is not a factor of s. \end{matrix}

(6) If s and t are relatively prime, then Φ_{s}(x^{t}) = ∏ Φ_{rs}(x), where the product is taken over all factors r of t.

(7) If Ā(x) is a polynomial and A(x) = Ā(x^{p}), then {t : Φ_{t}(x) divides A(x)} = {s′ : Φ_{s}(x) divides Ā(x)} ∪ {ps : Φ_{s}(x) divides Ā(x)}, where s′ = ps or s according as p is or is not a factor of s.

Proof. (1) is a standard fact. (2) and (3) follow from the definition, (4) from (2) and (3), and (5) from (1) because the roots of Φ_{s}(x^{p}) are e^{2πik/ps} for k relatively prime to s. Repeated application of (5) yields (6). For (7), let ω = e^{2πi/t}. Then ω^{p} is a primitive s-th root of unity for some s and, from (5), t ∈ {s′, ps}. Φ_{t}(x) divides Ā(x^{p}) if and only Ā(ω^{p}) = 0 if and only if Φ_{s}(x) divides Ā(x). □

A set C of integers is periodic if and only if C ⊕ {n} = C for some n ≥ 1. Then C is a union of congruence classes modulo n and C = B ⊕ nℤ, where B is any set consisting of one representative from each class. If A ⊕ C = ℤ is a tiling and C is periodic, the smallest such n is called the period of the tiling. Note that n = (#A)(#B) and A ⊕ B is a complete set of residues modulo n. Conversely, if A ⊕ B is a complete set of residues modulo n, then A ⊕ (B ⊕ nℤ) = ℤ is a tiling of period n or less, as are B ⊕ (A ⊕ nℤ) = ℤ and A′ ⊕ C = ℤ for any A′ ≡ A (mod n).

The following basic result is due to G. Hajós [Haj] and N. deBruijn [deB-1], then C. Swenson [Swe], then Newman [New].

Lemma 1.2. Every tiling by translates of a finite set is periodic, i.e., if A is finite and A ⊕ C = ℤ, then there is a finite set B such that C = B ⊕ nℤ, where n = (#A)(#B). □

Remark. Newman’s proof shows that the period of any tiling by A is bounded by 2^{max(A)−min(A)}. The tiling {j} ⊕ ℤ = ℤ has period 1. The tiling A ⊕ C = ℤ, where A = {j} ⊕ {0, k} and C = {0, 1, …, k − 1} ⊕ 2kℤ, has period 2k. We know of no other tilings whose period is as large as 2 (max(A) − min(A)). See the remarks following Lemma 2.1.

The collection of all finite multisets of nonnegative integers is in one-to-one correspondence with the set of all polynomials with nonnegative integer coefficients. The correspondence is

A ⟷ A(x) = ∑_{a∈A} m_{a}x^{a},

where m_{a} is the multiplicity of a as an element of A. If B is another such multiset and k ≥ 1, then the polynomial corresponding to A + B is A(x)B(x), to A ∪ B is A(x) + B(x), and to kA is A(x^{k}). Using this language we get

Lemma 1.3. Let n be an integer and let A and B be finite multisets of nonnegative integers with corresponding polynomials A(x) and B(x). Then the following statements are equivalent. Each forces A and B to be sets such that (#A)(#B) = A(1)B(1) = n.

(1) A ⊕ (B ⊕ nℤ) = ℤ is a tiling.

(2) A ⊕ B is a complete set of residues modulo n.

(3) A(x)B(x) ≡ 1 + x + ⋯ + x^{n−1} (mod x^{n} − 1).

(4) n = A(1)B(1) and for every factor t > 1 of n, the cyclotomic polynomial Φ_{t}(x) is a divisor of A(x) or B(x). □

There is no loss is restricting attention to conditions for a finite set of nonnegative integers to tile the integers. We can further restrict to finite sets whose minimal element is 0 and to translation sets which contain 0, although we will not always do so. For if A′ and C′ are translations of A and C, then A ⊕ C = ℤ if and only if A′ ⊕ C′ = ℤ.

Recall that (T1) and (T2) concern the set S_{A} of prime powers s such that the cyclotomic polynomial Φ_{s}(x) divides A(x). When A and a translate A′ are finite sets of nonnegative integers, A(x) and A′(x) are divisible by the same cyclotomic polynomials, so

• A tiles the integers if and only if A′ tiles the integers.

• A(x) satisfies (T1) if and only if A′(x) satisfies (T1).

• A(x) satisfies (T2) if and only if A′(x) satisfies (T2). The next lemma allow us to further restrict attention to finite sets of integers

with greatest common divisor 1.

Lemma 1.4. Let k > 1 and let A = kĀ be a finite set of nonnegative integers. (1) A tiles the integers if and only if Ā tiles the integers.

(2) If p is prime, then S_{pĀ} = {p^{α+1} : p^{α} ∈ SĀ} ∪ {q^{β} ∈ SĀ: q prime, q ≠ p}.

(3) A(x) satisfies (T1) if and only if Ā(x) satisfies (T1).

(4) A(x) satisfies (T2) if and only if Ā(x) satisfies (T2).

Proof. For one direction of (1), let Ā ⊕ C = ℤ. Then kĀ ⊕ kC = kℤ and hence A⊕({0, 1, …, k−1}⊕kC) = ℤ. For the other, let kĀ⊕D = ℤ. Then kĀ⊕D_{0} = kℤ, where D_{0} = {d ∈ D : d ≡ 0 (mod k)}, and hence Ā ⊕ D_{0}/k = ℤ. (2) follows from Lemma 1.1(7).

It suffices to prove (3) and (4) when k is prime, say k = p. (3) follows from (2) and Lemma 1.1(4) since #A = #Ā. It remains to prove (4). Let s′ = ps or s according as p is or is not a factor of s. Let s_{1}, …, s_{m} be powers of distinct primes and s = s_{1} ⋯ s_{m}. Then s′_{1}, …, s′_{m} are powers of distinct primes and s′ = s′_{1} ⋯ s′_{m}. From (2), every s_{i} ∈ SĀ if and only if every s′_{i} ∈ S_{A} = S_{pĀ}. From 1.1(7), Φ_{s}(x) divides Ā(x) if and only if Φ_{s′}(x) divides A(x). Putting all this together yields (4). □

Remark. It follows from (2) that B is not contained in pℤ when Φ_{p}(x) divides B(x).

Lemma 1.4 deals with A ⊂ kℤ. The related situation that A ⊕ C = ℤ is a tiling with C ⊆ kℤ leads to an important construction. We defer it to Lemma 2.5.

2. Tiling results

Theorem A. Let A be a finite set of nonnegative integers with corresponding polynomial A(x) = ∑_{a∈A} x^{a} and let S_{A} be the set of prime powers s such that the cyclotomic polynomial Φ_{s}(x) divides A(x). If

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

(T2) If s_{1}, …, s_{m} ∈ S_{A} are powers of distinct primes, then Φ_{s_{1}···s_{m}}(x) di-

vides A(x),

then A tiles the integers.

Proof. We construct a set B such that condition (4) of Lemma 1.3 is satisfied. Define B(x) = ∏ Φ_{s}(x^{t(s)}), where the product is taken over all prime power factors s of lcm(S_{A}) which are not in S_{A} and t(s) is the largest factor of lcm(S_{A}) relatively prime to s. Since every such s is a prime power, B(x) has nonnegative coefficients. Since 1.3(4) will be shown to hold, these coefficients are all 0 and 1.

Let s > 1 be a factor of A(1)B(1) and write s = s_{1} ⋯ s_{m} as a product of powers of distinct primes. If every s_{i} ∈ S_{A}, then by (T2), Φ_{s}(x) divides A(x). Suppose then that some s_{i} ∉ S_{A}. Then Φ_{s_{i}}(x^{t(s_{i})}) divides B(x), r = s/s_{i} is a factor of t(s_{i}) and, by Lemma 1.1(6) (with s = s_{i} and t = t(s_{i})), Φ_{rs_{i}}(x) divides Φ_{s_{i}}(x^{t(s_{i})}). Thus Φ_{s}(x) divides B(x) since rs_{i} = s. □

Remarks. The set B constructed in the proof depends only on S = S_{A} and not on A. Defining C_{S} = B ⊕ lcm(S)ℤ, A ⊕ C_{S} = ℤ for all A with S_{A} = S which satisfy (T1) and (T2). Then C_{S} ⊆ pℤ for every prime p ∈ S, since p is a factor of n and every divisor Φ_{s}(x^{t(s)}) of B(x) is a polynomial in x^{p}. For either t(s) is a multiple of p, or s = p^{α+1} with α ≥ 1 and Φ_{s}(x^{t(s)}) = Φ_{p} (x^{t(s)p^{α}}), so every divisor Φ_{s}(x^{t(s)}) of B(x) is a polynomial in x^{p}.

Theorem B1. Let A be a finite set of nonnegative integers with corresponding polynomial A(x) = ∑_{a∈A} x^{a} and let S_{A} be the set of prime powers s such that the cyclotomic polynomial Φ_{s}(x) divides A(x). If A tiles the integers, then (T1) A(1) = ∏_{s∈S_{A}} Φ_{s}(1).

Remark. (T1) is not sufficient for A to tile the integers. A = {0, 1, 2, 4, 5, 6} does not tile the integers, but A(x) = Φ_{3}(x)Φ_{8}(x) satisfies (T1).

Theorem B1 follows from Lemma 2.1(1) below.

Lemma 2.1. Let A(x) and B(x) be polynomials with coefficients 0 and 1, n = A(1)B(1), and R the set of prime power factors of n. If Φ_{t}(x) divides A(x) or B(x) for every factor t > 1 of n, then

(1) A(1) = ∏_{s∈S_{A}} Φ_{s}(1) and B(1) = ∏_{s∈S_{B}} Φ_{s}(1).

(2) S_{A} and S_{B} are disjoint sets whose union is R.

Proof. For every factor t > 1 of n, Φ_{t}(x) divides A(x) or B(x), so R ⊆ S_{A} ∪ S_{B}. Clearly A(1) ≥ ∏_{s∈S_{A}} Φ_{s}(1) and B(1) ≥ ∏_{s∈S_{B}} Φ_{s}(1). Thus

A(1)B(1) ≥ ∏_{s∈S_{A}} Φ_{s}(1) ∏_{s∈S_{B}} Φ_{s}(1) ≥ ∏_{t∈R} Φ_{t}(1) = n,

the equality by Lemma 1.1(4). Hence all the inequalities and containments above are actually equalities, and S_{A} is disjoint from S_{B}. □

Remarks. If a tiling A⊕C = ℤ has period n and C = B⊕nℤ, then n = lcm(S_{A}∪S_{B}), so the period of any tiling by A is a multiple of lcm(S_{A}). A particular tiling by A may have period larger than lcm(S_{A}), however when A(x) satisfies (T1) and (T2), the tiling A ⊕ (B ⊕ (#A)(#B)ℤ) = ℤ constructed in the proof of Theorem A has period lcm(S_{A}). In all cases known to the authors both A(x) and B(x) satisfy (T1) and (T2).

We leave it to the interested reader to show that for any set A of nonnegative integers,

• lcm(S_{A}) ≤ \frac{p}{p−1} (max(A) − min(A)), where p is the smallest prime factor

of #A.

• The inequality is strict except when A = {j} ⊕ p^{α}{0, 1, …, p − 1}. We show in Lemma 2.3 that there is always a tiling whose period is a product

of powers of the prime factors of #A.

Theorem B2. Let A be a finite set of nonnegative integers with corresponding polynomial A(x) = ∑_{a∈A} x^{a} such that #A has at most two prime factors and let S_{A} be the set of prime powers s such that the cyclotomic polynomial Φ_{s}(x) divides A(x). If A tiles the integers, then

(T2) If s_{1}, …, s_{m} ∈ S_{A} are powers of distinct primes, then Φ_{s_{1}···s_{m}}(x) di-

vides A(x).

The following result is crucial to our proof of Theorem B2. We give an alternate proof of it in Section 3.

Lemma 2.2. [Tij, Theorem 1] Suppose that A is finite, 0 ∈ A∩C, and A⊕C = ℤ. If r and #A are relatively prime, then rA ⊕ C = ℤ. □

Remark. Translating A or C does not affect the conclusion. Thus the condition 0 ∈ A ∩ C is not needed.

Lemma 2.3. If a finite set A tiles the integers, then there is a tiling by A whose period is a product of powers of the prime factors of #A.

Proof. If A ⊕ C = ℤ is a tiling of period n and r > 1 is a factor of n relatively prime to #A, then by Lemma 2.2, rA ⊕ C = ℤ. Therefore rA ⊕ C_{0} = rℤ, where C_{0} = {c ∈ C : c ≡ 0 (mod r)}, and hence A⊕C_{0}/r = ℤ is a tiling of period n/r. □

The following result is essentially Theorem 4 of [San]. We prove a more general result which implies it in Section 3.

Lemma 2.4. [San] Let A ⊕ C = ℤ be a tiling of period n such that A is finite, 0 ∈ A ∩ C, and n has one or two prime factors. Then there is a prime factor p of n such that either A ⊂ pℤ or C ⊆ pℤ. □

Sands’ result is stated in the terms of direct sum decompositions of finite cyclic groups, but it is easy to translate it into the terminology of this paper.

Lemma 2.5. Suppose A ⊕ C = ℤ, where A is a finite set of nonnegative integers, k > 1, and C ⊆ kℤ. For i = 0, 1, …, k − 1, let A_{i} = {a ∈ A : a ≡ i (mod k)}, a_{i} = min(A_{i}), and Ā_{i} = {a − a_{i} : a ∈ A_{i}}/k. Then

(1) A(x) = x^{a_{0}} Ā_{0}(x^{k}) + x^{a_{1}} Ā_{1}(x^{k}) + ⋯ + x^{a_{k−1}} Ā_{k−1}(x^{k}).

(2) Every Ā_{i} ⊕ C/k = ℤ.

(3) The elements of A are equally distributed modulo k — every #Ā_{i} = (#A)/k.

(4) SĀ_{0} = SĀ_{1} = ⋯ = SĀ_{k−1}.

(5) When k is prime, S_{A} = {k} ∪ S_{kĀ_{0}} and if every Ā_{i}(x) satisfies (T2), then A(x) satisfies (T2).

Proof. (1) is clear. (2) follows from A_{i} ⊕ C = {i} ⊕ kℤ = {a_{i}} ⊕ kℤ. To prove (3), note that the translation set C/k has some period n, so there is a set B̄ such that Ā_{i} ⊕ (B̄ ⊕ nℤ) = ℤ and every Ā_{i} ⊕ B̄ is a complete set of residues modulo n. Thus the #Ā_{i} are equal, so (3) holds. (4) also follows since by Lemma 2.1, every SĀ_{i} is the complement of SB̄ in the set of prime power factors of n.

To prove (5), write p in place of k. From Lemma 1.4(2), S_{pĀ_{i}} = {s′ : s ∈ SĀ_{i}}, where s′ = ps or s according as p is or is not a factor of s. The polynomial corresponding to pĀ_{i} is Ā_{i}(x^{p}), so from (1) and (4), S_{pĀ_{0}} ⊇ S_{A}. Also p ∈ S_{A}, since if Φ_{p}(ω) = 0, then ω^{p} = 1, ω^{a_{i}} = ω^{i}, and A(ω) = ∑_{i=0}^{p−1} ω^{i}Ā_{i}(1) = (#A/k) ∑_{i=0}^{p−1} ω^{i} = 0, the next-to-last equality by (3). We have thus shown that S_{A} ⊇ {p} ∪ S_{pĀ_{0}}. Since A_{0} and A tile the integers, A_{0}(x) and A(x) satisfy (T1) and S_{A} = {p} ∪ S_{pĀ_{0}}.

Now assume that every Ā_{i}(x) satisfies (T2). Condition (T2) for A(x) is: if s_{1}, …, s_{m} ∈ SĀ_{0} are powers of distinct primes, then Φ_{s′_{1}···s′_{m}}(x) divides A(x) and Φ_{ps_{1}···s_{m}}(x) divides A(x). By (T2), Φ_{s_{1}···s_{m}}(x) divides every Ā_{i}(x). Hence by Lemma 1.1(7), Φ_{s′_{1}···s′_{m}}(x) and Φ_{ps_{1}···s_{m}}(x) divide all the Ā_{i}(x^{p}), so they divide A(x) as well. □

Corollary. If A is a finite set of integers and C ⊆ kℤ, then A ⊕ C = ℤ if and only if A = ⋃_{i=0}^{k−1} ({a_{i}} ⊕ kĀ_{i})for some complete set {a_{0}, a_{1}, …, a_{k−1}} of residues modulo k, and k sets Ā_{i}, each of which satisfies min(A_{i}) = 0 and tiles the integers with translation set C/k. □

The decomposition is unique. We can have gcd(A) = 1 although this may not be true for the Ā_{i}. If the Ā_{i} are equal, then the union is a direct sum, A = {a_{0}, a_{1} …, a_{k−1}} ⊕ kĀ_{0}. For some simple choices of translation set C, every tile has this form.

Proof of Theorem B2. From Lemma 1.4 and the comments before it there is no loss of generality in assuming that gcd(A) = 1 and 0 ∈ A.

By Lemma 2.3 there is a tiling A ⊕ C = ℤ whose period n is a product of powers of the prime factors of #A. We complete the proof by induction on n. If n = 1, then A = {0} and A(x) ≡ 1 satisfies (T2) vaccuously. If n > 1, then by Lemma 2.4, there is a prime factor p of n such that C ⊆ pℤ. Then by Lemma 2.5, A(x) = x^{a_{0}} Ā_{0}(x^{p}) + x^{a_{1}} Ā_{1}(x^{p}) + ⋯ + x^{a_{p−1}} Ā_{p−1}(x^{p}) and every Ā_{i} ⊕ C/p = ℤ is a tiling of period n/p. By the inductive hypothesis, every Ā_{i}(x) satisfies (T2), so by Lemma 2.5(5), A(x) satisfies (T2). □

Every set known to the authors, regardless of size, which tiles the integers satisfies the tiling conditions (T1) and (T2). However, our proof of Theorem B2 cannot be extended to sets whose size has more than two prime factors because Lemma 2.4 need not hold. For m a positive integer with more than two prime factors, a very general construction due to S. Szabó [Sza] gives sets A such that #A = m, min(A) = 0, gcd(A) = 1, and A tiles the integers, yet the members of A are not equally distributed modulo k for any k > 1. Hence, from Lemma 2.5(3), every set C such that 0 ∈ C and A ⊕ C = ℤ satisfies gcd(C) = 1. All these sets A satisfy (T1) and (T2).

These examples also show that both Tijdeman’s conjecture [Tij, p. 266] — if A ⊕ C = ℤ, 0 ∈ A ∩ C, and gcd(A) = 1, then C ⊆ pℤ for some prime factor of #A — and the weaker conjecture — if A tiles the integers, min(A) = 0 and gcd(A) = 1, then there is some translation set of the desired type — are false without further conditions. Tijdeman’s conjecture would have implied an inductive characterization of all tilings A ⊕ C = ℤ. The weaker conjecture would have implied an inductive characterization of the finite sets which tile the integers. We established the weaker conjecture in Lemma 2.4 for those A such that #A has one or two prime factors. We show how to use it in Section 4. Tijdeman [Tij, Theorem 3] proved his conjecture when #A is a prime power. We do not know whether it holds when #A has exactly two prime factors.

3. Alternate proofs of Tijdeman’s and Sands’ Theorems

Tijdeman’s Theorem (Lemma 2.2) follows from Lemma 1.3 and

Lemma 3.1. Let A and B be finite sets of nonnegative integers with corresponding polynomials A(x) and B(x) and let n = A(1)B(1). If

A(x)B(x) ≡ 1 + x + ⋯ + x^{n−1} (mod x^{n} − 1)

and p is a prime which is not a factor of A(1), then

A(x^{p})B(x) ≡ 1 + x + ⋯ + x^{n−1} (mod x^{n} − 1).

Proof. Since p is prime, A(x^{p}) ≡ (A(x))^{p} (mod p), i.e., when the coefficients are reduced modulo p. Let G_{n}(x) = 1 + x + ⋯ + x^{n−1}. Then

A(x^{p})B(x) = (A(x))^{p−1} A(x)B(x) ≡ (A(x))^{p−1} G_{n}(x),

where ≡ means the exponents are reduced modulo n and then the coefficients are reduced modulo p. Every x^{i}G_{n}(x) ≡ G_{n}(x) (mod x^{n} − 1), so

(A(x))^{p−1} G_{n}(x) ≡ (A(1))^{p−1} G_{n}(x) (mod x^{n} − 1).

By Fermat’s Little Theorem, (A(1))^{p−1} ≡ 1 (mod p). Therefore A(x^{p})B(x) ≡ G_{n}(x), where the exponents are reduced modulo n and then the coefficients are reduced modulo p. Both A(x^{p})B(x) and G_{n}(x) have nonnegative coefficients whose sum is n since A(1)B(1) = G_{n}(1) = n. Consider the following reductions. (R1) A(x^{p})B(x) is reduced modulo x^{n} − 1, yielding a polynomial G^{∗}(x). (R2) The coefficients of G^{∗}(x) are reduced modulo p, yielding G_{n}(x).

(R1) preserves the sum of the coefficients, but (R2) reduces the sum by some nonnegative multiple of p. Because the sum of the coefficients of both G^{∗}(x) and G_{n}(x) is n, that multiple is 0. Therefore G^{∗}(x) = G_{n}(x). □

We use the following result to prove Sands’ Theorem (Lemma 2.4). Let A − A be the difference set {a_{1} − a_{2} : a_{1}, a_{2} ∈ A}.

Lemma 3.2. Let A and B be finite, A, B ≠ {0}, and A ⊕ B a complete set of residues modulo (#A)(#B). Then at least one of the following is true.

(1) No member of A − A is relatively prime to #B.

(2) No member of B − B is relatively prime to #A.

Proof. Let n = (#A)(#B). By Lemma 1.3,

A(x)B(x) ≡ 1 + x + ⋯ + x^{n−1} (mod x^{n} − 1).

Suppose 0 < a_{1} −a_{2} = δ′ is relatively prime to #B and 0 < b_{1} −b_{2} = δ′′ is relatively prime to #A. Lemma 2.2 shows that

A(x^{δ′′})B(x^{δ′}) ≡ 1 + x + ⋯ + x^{n−1} (mod x^{n} − 1),

so by Lemma 1.3 again, δ′′A ⊕ δ′B is a complete set of residues modulo n. But

(b_{1} − b_{2})a_{1} + (a_{1} − a_{2})b_{2} = (b_{1} − b_{2})a_{2} + (a_{1} − a_{2})b_{1}.

Thus the same number can be expressed δ′′a + δ′b in two ways, which is impossible. □

Lemma 2.4. [San] Let A ⊕ C = ℤ be a tiling of period n such that A is finite, 0 ∈ A ∩ C, and n has one or two prime factors. Then there is a prime factor p of n such that either A ⊂ pℤ or C ⊆ pℤ.

Proof. Let C = B ⊕ nℤ and the prime factors of n be p and possibly q. Then at least one of 3.2(1) and 3.2(2) holds.

If 3.2(1) holds, then A ⊆ A − A ⊂ pℤ ∪ qℤ, the first containment because 0 ∈ A. If neither pℤ nor qℤ contains A, then there exist a_{1}, a_{2} ∈ A such that a_{1} ∈ pℤ \ qℤ and a_{2} ∈ qℤ \ pℤ. But then a_{1} − a_{2} is relatively prime to #B.

If 3.2(2) holds, the same argument shows that B ⊆ pℤ or B ⊆ qℤ. Then the same is true for C = B ⊕ nℤ. □

Lemma 3.3. Suppose A is finite, 0 ∈ A, A tiles the integers with period n, and n has two prime factors, p and q. If neither Φ_{p}(x) nor Φ_{q}(x) is a divisor of A(x), then A ⊂ pℤ or A ⊂ qℤ.

Proof. Let A ⊕ (B ⊕ nℤ) = ℤ be a tiling of period n. By Lemma 1.3(4), Φ_{p}(x) and Φ_{q}(x) are divisors of B(x). From the remark after Lemma 1.4, neither pℤ nor qℤ contains B. Then the conclusion follows by Lemma 2.4. □

4. A structure theory

In this section we describe the structure of those finite sets A such that A tiles the integers and #A has at most two prime factors. Equivalently, such that the set S_{A} of prime powers s such that the cyclotomic polynomial Φ_{s}(x) divides A(x) consists of powers of at most two primes. For S such a set of prime powers, let T_{S} be the collection of all subsets A of {0, 1, …, lcm(S)−1} which tile the integers and satisfy min(A) = 0 and S_{A} = S. Note that T_{∅} = {0} because lcm(∅) = 1, and that T_{{p^{α+1}}} is the set whose only member is p^{α}{0, 1, …, p−1}. We have seen that there is no loss in requiring min(A) = 0. We claim that a finite set A′ with min(A′) = 0 and S_{A′} = S tiles the integers if and only if A′ is congruent modulo lcm(S) to a member of T_{S}. For if A′ ≡ A (mod lcm(S)), then S_{A′} = S_{A} = S, and as noted after the proof of Lemma 1.1, A′ ⊕ C_{S} = ℤ if and only if A ⊕ C_{S} = ℤ. Recall that C_{S} is the universal translation set corresponding to S: A ⊕ C_{S} = ℤ for every A such that A tiles the integers and S_{A} = S.

For purposes of comparison we recall the simpler structure of all finite sets which tile the nonnegative integers ℕ_{0} = {0, 1, … }, due to deBruijn [deB-3]. Note that every such set has a unique translation set, so the unique associated tiling has a period. One such set is A = {0, 1, 2, 3, 4} ⊕ {0, 10, 20, 30} ⊕ {0, 120, 240}, which tiles ℕ_{0} with period 360. A can be written A = Ã ⊕ 120{0, 1, 2}, where Ã tiles ℕ_{0} with period 60, and it can be written A = {0, 1, 2, 3, 4} ⊕ 5Ā, where Ā tiles ℕ_{0} with period 72 = 360/5. If A ≠ {0} is any finite set which tiles ℕ_{0}, then there are always these two types of direct sum decompostions, A = Ã ⊕ (n/p){0, 1, …, p − 1} and A = k{0, 1, …, q − 1} ⊕ qĀ, where p and q are prime factors of the period n of the tiling, k = gcd(A), and Ã and Ā are shorter tiles. Iterating either decomposition, every tile is a direct sum, in one or more ways, of tiles of the form m{0, 1, …, p−1}. If the order is as above, then Ã is the direct sum of all but the last of the summands and qĀ is the direct sum of all but the first. A(x) is thus a product of terms (x^{mp} − 1)/(x^{m} − 1) = Φ_{p}(x^{m}) and can easily be shown to satisfy (T1) and (T2).

We return to T_{S} for the case that S consists of the powers of at most two primes. Both decompositions above generalize, the second more usefully than the first.

Corresponding to the first decomposition, we will see that every member of T_{S} is a disjoint union of translates of (n/p){0, 1, …, p − 1} and (n/q){0, 1, …, q − 1}, where n = lcm(S). The simplest case where both must be used is S = {p, p^{3}, q^{2}}. An important example of this with lcm(S) = 72 is given below. More usefully, we will show that when S ≠ ∅, every tile A ∈ T_{S} is, as in Lemma 2.5, a union of translates of multiples of p or q smaller tiles: A = m ⋃_{i=0}^{p−1} ({a_{i}} ⊕ pĀ_{i}), where m = gcd(A), a_{0} = 0, {a_{0}, a_{1}, …, a_{p−1}} is a complete set of residues modulo p, every {a_{i}} ⊕ pĀ_{i} ⊂ {0, 1, …, lcm(S) − 1}, and for some smaller set S̄, every Ā_{i} ∈ TS̄. We need not get a direct sum, as the Ā_{i} need not be equal. Every Ā_{i} in turn is a union of p or q translates of multiples of even shorter tiles. Iterating the procedure until S = ∅ gives the disjoint union referred to above.

Suppose that S contains powers of only p, so that lcm(S) is a power of p. If A ∈ T_{S}, then A ⊕ C_{S} = ℤ and either p ∈ S and C_{S} ⊆ pℤ, or p ∉ S and A ⊂ pℤ.

Let S̄ = {p^{α} : p^{α+1} ∈ S}. If p ∉ S, then #S̄ = #S and, as in Lemma 1.4, T_{S} = {pĀ : Ā ∈ TS̄}. If p ∈ S, then by the Corollary to Lemma 2.5, the members of T_{S} can be constructed by taking all unions ⋃_{i=0}^{p−1} ({a_{i}} ⊕ pĀ_{i}) with Ā_{i} ∈ TS̄, a_{0} = 0, {a_{0}, a_{1}, …, a_{p−1}} a complete set of residues modulo p, and every {a_{i}} ⊕ pĀ_{i} ⊂ {0, 1, …, lcm(S) − 1}. This procedure gives all of T_{S} and nothing else.

Suppose now that S contains powers of both p and q and let

S̄ = {p^{α} : p^{α+1} ∈ S} ∪ {q^{β} : q^{β} ∈ S}, S̄′ = {p^{α} : p^{α} ∈ S} ∪ {q^{β} : q^{β+1} ∈ S}.

We consider the three cases: p ∈ S, q ∈ S, and p, q ∉ S. If p ∈ S, then C_{S} ⊆ pℤ and T_{S} can be constructed as above by taking all unions ⋃_{i=0}^{p−1} ({a_{i}} ⊕ pĀ_{i}) with Ā_{i} ∈ TS̄, a_{0} = 0, {a_{0}, a_{1}, …, a_{p−1}} a complete set of residues modulo p, and every {a_{i}}⊕pĀ_{i} ⊂ {0, 1, …, lcm(S)−1}. If q ∈ S, then the analogous procedure, with the roles of p, S̄ and q, S̄′ interchanged, gives T_{S}. If both p and q are in S, then C_{S} ⊆ pqℤ and either procedure gives T_{S}. If neither p nor q is in S, then by Lemma 3.3, every member of T_{S} is contained in pℤ or qℤ. Then #S = #S̄ = #S̄′, and {A ∈ T_{S} : A ⊂ pℤ} = {pĀ : Ā ∈ TS̄}, while {A ∈ T_{S} : A ⊂ qℤ} = {qĀ : Ā ∈ TS̄′}. In all three cases, this procedure gives all of T_{S} and nothing else.

We examine a few cases in more detail, including the important example of deBruijn [deB-2].

When S contains only powers of p, every member of T_{S} is a union of translates of p^{α}{0, 1, …, p − 1}, where p^{α+1} is the largest member of S. Hence every member of T_{S} is a direct sum of this set and a set Ã which also tiles the integers. Then SÃ = S \ {p^{α+1}}, but Ã need not be a direct sum. An example with S = {2, 4, 32} is 16{0, 1} ⊕ {0, 1, 2, 11}.

It is easy to show that if S = {p^{α}, q^{β}}, then every member of T_{S} is

p^{α−1} (Ã ⊕ pq^{β−1}{0, 1, …, q − 1})

for Ã ⊆ {0, …, pq^{β−1} − 1} a complete set of residues modulo p containing 0, or an analogous set with the roles of p and q interchanged. Thus {k : Φ_{k}(x) divides A(x)} contains {p^{α}} ∪ {q^{β}, pq^{β}, p^{2}q^{β}, …, p^{α}q^{β}} or {q^{β}} ∪ {p^{α}, p^{α}q, p^{α}q^{2}, …, p^{α}q^{β}}. If α > 1 and β > 1, there are cyclotomic polynomial divisors of A(x) in addition to the three required by (T2).

The situation when S has at least three elements is different. In this case T_{S} has members whose corresponding polynomial has only the cyclotomic polynomial divisors required by (T2). We illustrate this with the promised example. Among the members of T_{{4,9}} are Ā_{0} = {0, 3, 6, 18, 21, 24} and Ā_{1} = {0, 2, 12, 14, 24, 26}. Each is a direct sum. Consider

A = ({0} ⊕ 2Ā_{0}) ∪ ({1} ⊕ 2Ā_{1})
= {0, 1, 5, 6, 12, 25, 29, 36, 42, 48, 49, 53} ∈ T_{{2,8,9}}.

The cyclotomic polynomial divisors of A(x) = Ā_{0}(x^{2}) + xĀ_{1}(x^{2}) are Φ_{2}(x) and those Φ_{k}(x) which divide both Ā_{0}(x^{2}) and Ā_{1}(x^{2}), i.e.,

{k : Φ_{k}(x) divides A(x)} = {2} ∪ ({8, 9, 18, 36, 72} ∩ {8, 9, 18, 24, 72})
= {2, 8, 9, 18, 72},

exactly the set required by (T2). Then as in Theorem A, A⊕(B⊕72ℤ) = ℤ for B = {0, 8, 16, 18, 26, 34}. deBruijn’s example was actually ({12} ⊕ 2Ā_{0})∪({17} ⊕ 2Ā_{1}). It was the first example where A ⊕ B is a complete set of residues modulo n but neither A nor B is periodic modulo n. Equivalently, neither A nor B is a disjoint union of translates of (n/p){0, 1, …, p − 1} for a single prime factor p of n.

References

[deB-1] deBruijn, N. G., On bases for the set of integers, Publ. Math. Debrecen 1 (1950), 232–242. [deB-2] , On the factorization of cyclic groups, Indag. Math. 17 (1955), 370–377. [deB-3] , On number systems, Nieuw Arch. Wisk. (3) 4 (1956), 15–17.

[Haj] Hajós, G., Sur la factorisation des groupes abéliens, Časopis Pěst. Mat. Fys. (3) 4 (1950), 157–162. (French)

[L-W] Lagarias, J. and Wang, Y., Tiling the line with translates of one tile, Invent. Math. 124

(1996), 341–365.

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

[San] Sands, A. D., On Keller’s conjecture for certain cyclic groups, Proc. Edinburgh Math. Soc. (2) 22 (1977), 17–21.

[Swe] Swenson, C., Direct sum subset decompositions of Z, Pacific J. Math. 53 (1974), 629–633.

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

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

Ethan M. Coven, Deparment of Mathematics, Wesleyan University, Middletown, CT 06459-0128

   E-mail address: ecoven@wesleyan.edu

Aaron Meyerowitz, Deparment of Mathematics, Florida Atlantic University, Boca Raton, FL 33431-0991

   E-mail address: meyerowi@fau.edu