# Tiling the integers with translates of one finite set

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 nding necessary and su cient conditions for a nite 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 su cient, but it is unknown whether they are necessary for all nite sets.

Introduction

Let A be a nite 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 2 A and c 2 C . In symbols, A C = Z. In this case A is called a tile , A C = Z 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 nding necessary and su cient conditions for a nite 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 nd necessary and su cient 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 nite P set A of nonnegative integers. Then A(x) = a2A xa is a polynomial such that #A = A(1). Let SA 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). Q (T1) A(1) = s2SA s (1). (T2) If s1; : : :; sm 2 SA are powers of distinct primes, then s1 sm (x) divides A(x).
1991 Mathematics Subject Classi cation. Primary 05B45; Secondary 11B75, 20K01. Part of this work was done while the rst 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 rst author thanks J. Jungman and M. Keane for helpful conversations. 1 Typeset by AMS-TEX

2

ETHAN M. COVEN AND AARON MEYEROWITZ

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

A(x) satis es (T2). Corollary. If #A has at most two prime factors, then A tiles the integers if and only if A(x) satis es (T1) and (T2). It is unknown whether the su cient conditions (T1) and (T2) are necessary for any nite set to tile the integers. (T1) is necessary but not su cient (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 su cient. An examination of Newman's proof New, Theorem 1] essentially yields this result. Our proof of Theorem B2 provides a structure theory for nite sets A such that A tiles the integers and #A has at most two prime factors. We sketch this in Section 4. S If A is a nite set which tiles the integers, then a2A 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 nite 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 nite sets which tile the integers.
For A and B sets or multisets of integers, we denote the multiset fa + b : a 2 A; b 2 B g by A + B . We write A B when every element can be expressed uniquely a + b. For k an integer, we write kA for fka : a 2 Ag, we call fkg A a translate of A, and when k is a factor of every a 2 A, we write A=k for fa=k : a 2 Ag. s Q For s 1, the s-th cyclotomic polynomial s (x) is de ned recursively by x ? 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. Q (2) 1 + x + + xs?1 = t (x), where the product is taken over all factors t > 1 of s. (3) p (x) = 8+ x + + xp?1 and p +1 (x) = p (xp ). 1 > 0 if s = 1 < (4) s(1) = > q if s is a power of a prime q : 1 otherwise: (x) if p is a factor of s (5) s(xp ) = ps s (x) ps (x) if p is not a factor of s: Q (6) If s and t are relatively prime, then s(xt ) = rs (x), where the product is taken over all factors r of t.
1. Preliminaries

TILING THE INTEGERS WITH TRANSLATES OF ONE FINITE SET

3

(7) If A(x) is a polynomial and A(x) = A(xp ), then ft : t (x) divides A(x)g = fs0 : s(x) divides A(x)g fps : s (x) divides A(x)g, where s0 = 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 de nition, (4) from (2) and (3), and (5) from (1) because the roots of s(xp ) are e2 ik=ps for k relatively prime to s. Repeated application of (5) yields (6). For (7), let ! = e2 i=t. Then !p is a primitive s-th root of unity for some s and, from (5), t 2 fs0; psg. t (x) divides A(xp ) if and only A(!p ) = 0 if and only if s (x) divides A(x). A set C of integers is periodic if and only if C fng = C for some n 1. Then C is a union of congruence classes modulo n and C = B nZ, where B is any set consisting of one representative from each class. If A C = Z 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 nZ) = Z is a tiling of period n or less, as are B (A nZ) = Z and A0 C = Z for any A0 A (mod n). The following basic result is due to G. Hajos Haj] and N. deBruijn deB-1], then C. Swenson Swe], then Newman New]. Lemma 1.2. Every tiling by translates of a nite set is periodic, i.e., if A is nite and A C = Z, then there is a nite set B such that C = B nZ, where n = (#A)(#B ). Remark. Newman's proof shows that the period of any tiling by A is bounded by 2max(A)?min(A) . The tiling fj g Z = Z has period 1. The tiling A C = Z, where A = fj g f0; kg and C = f0; 1; : : :; k ? 1g 2kZ, 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 nite multisets of nonnegative integers is in one-to-one correspondence with the set of all polynomials with nonnegative integer coe cients. The correspondence is X A ! A(x) = ma xa ; where ma 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(xk ). Using this language we get Lemma 1.3. Let n be an integer and let A and B be nite 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 nZ) = Z is a tiling. (2) A B is a complete set of residues modulo n. (3) A(x)B (x) 1 + x + + xn?1 (mod xn ? 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).
a2A

4

ETHAN M. COVEN AND AARON MEYEROWITZ

There is no loss is restricting attention to conditions for a nite set of nonnegative integers to tile the integers. We can further restrict to nite sets whose minimal element is 0 and to translation sets which contain 0, although we will not always do so. For if A0 and C 0 are translations of A and C , then A C = Z if and only if A0 C 0 = Z. Recall that (T1) and (T2) concern the set SA of prime powers s such that the cyclotomic polynomial s (x) divides A(x). When A and a translate A0 are nite sets of nonnegative integers, A(x) and A0 (x) are divisible by the same cyclotomic polynomials, so A tiles the integers if and only if A0 tiles the integers. A(x) satis es (T1) if and only if A0(x) satis es (T1). A(x) satis es (T2) if and only if A0(x) satis es (T2). The next lemma allow us to further restrict attention to nite sets of integers with greatest common divisor 1. Lemma 1.4. Let k > 1 and let A = kA be a nite set of nonnegative integers. (1) A tiles the integers if and only if A tiles the integers. (2) If p is prime, then SpA = fp +1 : p 2 SA g fq 2 SA : q prime ; q 6= pg. (3) A(x) satis es (T1) if and only if A(x) satis es (T1). (4) A(x) satis es (T2) if and only if A(x) satis es (T2). Proof. For one direction of (1), let A C = Z. Then kA kC = kZ and hence A (f0; 1; : : :; k ? 1g kC ) = Z. For the other, let kA D = Z. Then kA D0 = kZ, where D0 = fd 2 D : d 0 (mod k)g, and hence A D0 =k = Z. (2) follows from Lemma 1.1(7). It su ces to prove (3) and (4) when k is prime, say k = p. (3) follows from (2) and Lemma 1.1(4) since #A = #A. It remains to prove (4). Let s0 = ps or s according as p is or is not a factor of s. Let s1; : : :; sm be powers of distinct primes and s = s1 sm . Then s01; : : :; s0m are powers of distinct primes and s0 = s01 s0m. From (2), every si 2 SA if and only if every s0i 2 SA = SpA . From 1.1(7), s (x) divides A(x) if and only if s0 (x) divides A(x). Putting all this together yields (4). Remark. It follows from (2) that B is not contained in pZ when p (x) divides B (x). Lemma 1.4 deals with A kZ. The related situation that A C = Z is a tiling with C kZ leads to an important construction. We defer it to Lemma 2.5.

Theorem A. Let A be a nite set of nonnegative integers with corresponding polyP

2. Tiling results

nomial A(x) = a2A xa and let SA be the set of prime powers s such that the cyclotomic polynomial s (x) divides A(x). If Q (T1) A(1) = s2SA s(1). (T2) If s1 ; : : :; sm 2 SA are powers of distinct primes, then s1 sm (x) divides A(x),

TILING THE INTEGERS WITH TRANSLATES OF ONE FINITE SET

5

then A tiles the integers. Proof. We construct a set B such that condition (4) of Lemma 1.3 is satis ed. Q De ne B (x) = s (xt(s) ), where the product is taken over all prime power factors s of lcm(SA) which are not in SA and t(s) is the largest factor of lcm(SA ) relatively prime to s. Since every such s is a prime power, B (x) has nonnegative coe cients. Since 1.3(4) will be shown to hold, these coe cients are all 0 and 1. Let s > 1 be a factor of A(1)B (1) and write s = s1 sm as a product of powers of distinct primes. If every si 2 SA , then by (T2), s (x) divides A(x). Suppose then that some si 2 SA . Then si (xt(si) ) divides B (x), r = s=si is a factor of t(si ) = and, by Lemma 1.1(6) (with s = si and t = t(si )), rsi (x) divides si (xt(si) ). Thus s (x) divides B (x) since rsi = s. Remarks. The set B constructed in the proof depends only on S = SA and not on A. De ning CS = B lcm(S )Z, A CS = Z for all A with SA = S which satisfy (T1) and (T2). Then CS pZ for every prime p 2 S , since p is a factor of n and every divisor s(xt(s) ) of B (x) is a polynomial in xp . For either t(s) is a ? multiple of p, or s = p +1 with 1 and s(xt(s) ) = p xt(s)p , so every divisor s (xt(s) ) of B (x) is a polynomial in xp . Theorem B1. LetP be a nite set of nonnegative integers with corresponding A polynomial A(x) = a2A xa and let SA be the set of prime powers s such that the cyclotomic polynomial s (x) divides A(x). If A tiles the integers, then Q (T1) A(1) = s2SA s (1).

Remark. (T1) is not su cient for A to tile the integers. A = f0; 1; 2; 4; 5; 6g does not tile the integers, but A(x) = 3 (x) 8(x) satis es (T1). Theorem B1 follows from Lemma 2.1(1) below. Lemma 2.1. Let A(x) and B (x) be polynomials with coe cients 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 Q Q (1) A(1) = s2SA s (1) and B (1) = s2SB s(1). (2) SA and SB are disjoint sets whose union is R. Proof. For every factor t > 1 of n, t (x)Q divides A(x) or B (x), so R Q Clearly A(1) (1) and B (1) s2SA s s2SB s (1). Thus

S A SB .

A(1)B (1)

Y

s2SA

s (1)

Y

s2SB

s (1)

Y

t2R

t (1) = n;

the equality by Lemma 1.1(4). Hence all the inequalities and containments above are actually equalities, and SA is disjoint from SB . Remarks. If a tiling A C = Z has period n and C = B nZ, then n = lcm(SA SB ), so the period of any tiling by A is a multiple of lcm(SA ). A particular tiling by A

6

ETHAN M. COVEN AND AARON MEYEROWITZ

may have period larger than lcm(SA ), however when A(x) satis es (T1) and (T2), the tiling A (B (#A)(#B )Z) = Z constructed in the proof of Theorem A has period lcm(SA ). 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, p lcm(SA) p?1 (max(A) ? min(A)), where p is the smallest prime factor of #A. The inequality is strict except when A = fj g p f0; 1; : : :; p ? 1g: 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 P be a nite set of nonnegative integers with corresponding A polynomial A(x) = a2A xa such that #A has at most two prime factors and let SA 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 s1 ; : : :; sm 2 SA are powers of distinct primes, then s1 sm (x) divides 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 nite, 0 2 A \ C , and A C = Z. If r and #A are relatively prime, then rA C = Z. Remark. Translating A or C does not a ect the conclusion. Thus the condition 0 2 A \ C is not needed. Lemma 2.3. If a nite 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 = Z 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 = Z. Therefore rA C0 = rZ, where C0 = fc 2 C : c 0 (mod r)g, and hence A C0 =r = Z 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 = Z be a tiling of period n such that A is nite, 0 2 A \ C , and n has one or two prime factors. Then there is a prime factor p of n such that either A pZ or C pZ. Sands' result is stated in the terms of direct sum decompositions of nite cyclic groups, but it is easy to translate it into the terminology of this paper. Lemma 2.5. Suppose A C = Z, where A is a nite set of nonnegative integers, k > 1, and C kZ. For i = 0; 1; : : :; k ? 1, let Ai = fa 2 A : a i (mod k)g, ai = min(Ai), and Ai = fa ? ai : a 2 Ai g=k. Then (1) A(x) = xa0 A0(xk ) + xa1 A1(xk ) + + xak?1 Ak?1(xk ).

TILING THE INTEGERS WITH TRANSLATES OF ONE FINITE SET

7

(2) (3) (4) (5)

Every Ai C=k = Z. The elements of A are equally distributed modulo k | every #Ai = (#A)=k: SA0 = SA1 = = SAk?1 . When k is prime, SA = fkg SkA0 and if every Ai (x) satis es (T2), then A(x) satis es (T2).

Proof. (1) is clear. (2) follows from Ai C = fig kZ = faig kZ. To prove (3), note that the translation set C=k has some period n, so there is a set B such that Ai (B nZ) = Z and every Ai B is a complete set of residues modulo n. Thus the #Ai are equal, so (3) holds. (4) also follows since by Lemma 2.1, every SAi 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), SpAi = fs0 : s 2 SAi g, where s0 = ps or s according as p is or is not a factor of s. The polynomial corresponding to pAi is Ai (xp), so from (1) and (4), SpA0 SA . Also p 2 SA , P ? since if Pp (!) = 0, then !p = 1, !ai = !i , and A(!) = ip=01 !i Ai(1) = ? (#A=k) ip=01 !i = 0, the next-to-last equality by (3). We have thus shown that SA fpg SpA0 . Since A0 and A tile the integers, A0(x) and A(x) satisfy (T1) and SA = fpg SpA0 . Now assume that every Ai (x) satis es (T2). Condition (T2) for A(x) is: if s1; : : : ; sm 2 SA0 are powers of distinct primes, then s01 s0m (x) divides A(x) and ps1 sm (x) divides A(x). By (T2), s1 sm (x) divides every Ai (x). Hence by Lemma 1.1(7), s01 s0m (x) and ps1 sm (x) divide all the Ai (xp), so they divide A(x) as well. Corollary. Sk?1 ? a nite set of integers and C kZ, then A C = Z if and If A is only if A = i=0 fai g kAi for some complete set fa0; a1; : : :; ak?1g of residues modulo k, and k sets Ai , each of which satis es min(Ai) = 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 Ai . If the Ai are equal, then the union is a direct sum, A = fa0 ; a1 : : : ; ak?1g kA0. 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 2 A. By Lemma 2.3 there is a tiling A C = Z 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 = f0g and A(x) 1 satis es (T2) vaccuously. If n > 1, then by Lemma 2.4, there is a prime factor p of n such that C pZ. Then by Lemma 2.5, A(x) = xa0 A0(xp ) + xa1 A1(xp ) + + xap?1 Ap?1 (xp) and every Ai C=p = Z is a tiling of period n=p. By the inductive hypothesis, every Ai (x) satis es (T2), so by Lemma 2.5(5), A(x) satis es (T2). Every set known to the authors, regardless of size, which tiles the integers satis es the tiling conditions (T1) and (T2). However, our proof of Theorem B2 cannot be

8

ETHAN M. COVEN AND AARON MEYEROWITZ

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. Szabo 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 2 C and A C = Z satis es 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 = Z, 0 2 A \ C , and gcd(A) = 1, then C pZ 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 = Z. The weaker conjecture would have implied an inductive characterization of the nite 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 nite 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 + + xn?1 (mod xn ? 1) and p is a prime which is not a factor of A(1), then A(xp )B (x) 1 + x + + xn?1 (mod xn ? 1):
Proof. Since p is prime, A(xp ) (A(x))p (mod p), i.e., when the coe cients are reduced modulo p. Let Gn (x) = 1 + x + + xn?1 . Then

A(xp)B (x) = (A(x))p?1 A(x)B (x) (A(x))p?1 Gn (x); where means the exponents are reduced modulo n and then the coe cients are reduced modulo p. Every xi Gn (x) Gn (x) (mod xn ? 1), so (A(x))p?1 Gn (x) (A(1))p?1 Gn (x) (mod xn ? 1): By Fermat's Little Theorem, (A(1))p?1 1 (mod p). Therefore A(xp)B (x) Gn (x), where the exponents are reduced modulo n and then the coe cients are reduced modulo p. Both A(xp)B (x) and Gn (x) have nonnegative coe cients whose sum is n since A(1)B (1) = Gn (1) = n. Consider the following reductions. (R1) A(xp)B (x) is reduced modulo xn ? 1, yielding a polynomial G (x). (R2) The coe cients of G (x) are reduced modulo p, yielding Gn (x).

TILING THE INTEGERS WITH TRANSLATES OF ONE FINITE SET

9

(R1) preserves the sum of the coe cients, but (R2) reduces the sum by some nonnegative multiple of p. Because the sum of the coe cients of both G (x) and Gn (x) is n, that multiple is 0. Therefore G (x) = Gn (x). We use the following result to prove Sands' Theorem (Lemma 2.4). Let A ? A be the di erence set fa1 ? a2 : a1; a2 2 Ag. Lemma 3.2. Let A and B be nite, A; B 6= f0g, 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 +

+ xn?1 (mod xn ? 1):

Suppose 0 < a1 ? a2 = 0 is relatively prime to #B and 0 < b1 ? b2 = 00 is relatively prime to #A. Lemma 2.2 shows that

A(x 00 )B (x 0 ) 1 + x +
so by Lemma 1.3 again, 00 A

+ xn?1 (mod xn ? 1);

0 B is a complete set of residues modulo n. But

(b1 ? b2 )a1 + (a1 ? a2 )b2 = (b1 ? b2)a2 + (a1 ? a2)b1 : Thus the same number can be expressed 00 a + 0 b in two ways, which is impossible. Lemma 2.4. San] Let A C = Z be a tiling of period n such that A is nite, 0 2 A \ C , and n has one or two prime factors. Then there is a prime factor p of n such that either A pZ or C pZ. Proof. Let C = B nZ 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 pZ qZ, the rst containment because 0 2 A. If neither pZ nor qZ contains A, then there exist a1; a2 2 A such that a1 2 pZ n qZ and a2 2 qZ n pZ. But then a1 ? a2 is relatively prime to #B . If 3.2(2) holds, the same argument shows that B pZ or B qZ. Then the same is true for C = B nZ. Lemma 3.3. Suppose A is nite, 0 2 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 pZ or A qZ. Proof. Let A (B nZ) = Z 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 pZ nor qZ contains B . Then the conclusion follows by Lemma 2.4.

10

ETHAN M. COVEN AND AARON MEYEROWITZ

4. A structure theory

In this section we describe the structure of those nite sets A such that A tiles the integers and #A has at most two prime factors. Equivalently, such that the set SA 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 TS be the collection of all subsets A of f0; 1; : : :; lcm(S ) ? 1g which tile the integers and satisfy min(A) = 0 and SA = S . Note that T? = f0g because lcm(?) = 1, and that Tfp +1 g is the set whose only member is p f0; 1; : : :; p ? 1g. We have seen that there is no loss in requiring min(A) = 0. We claim that a nite set A0 with min(A0) = 0 and SA0 = S tiles the integers if and only if A0 is congruent modulo lcm(S ) to a member of TS . For if A0 A (mod lcm(S )), then SA0 = SA = S , and as noted after the proof of Lemma 1.1, A0 CS = Z if and only if A CS = Z. Recall that CS is the universal translation set corresponding to S : A CS = Z for every A such that A tiles the integers and SA = S . For purposes of comparison we recall the simpler structure of all nite sets which tile the nonnegative integers N 0 = f0; 1; : : : g, 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 = f0; 1; 2; 3; 4g f0; 10; 20; 30g f0; 120; 240g, which ~ ~ tiles N 0 with period 360. A can be written A = A 120f0; 1; 2g, where A tiles N 0 with period 60, and it can be written A = f0; 1; 2; 3; 4g 5A, where A tiles N 0 with period 72 = 360=5. If A 6= f0g is any nite set which tiles N 0 , then there are always ~ these two types of direct sum decompostions, A = A (n=p)f0; 1; : : :; p ? 1g and A = kf0; 1; : : :; q ? 1g qA, where p and q are prime factors of the period n of the ~ tiling, k = gcd(A), and A and A are shorter tiles. Iterating either decomposition, every tile is a direct sum, in one or more ways, of tiles of the form mf0; 1; : : :; p ? 1g. ~ If the order is as above, then A is the direct sum of all but the last of the summands and qA is the direct sum of all but the rst. A(x) is thus a product of terms (xmp ? 1)=(xm ? 1) = p (xm) and can easily be shown to satisfy (T1) and (T2). We return to TS for the case that S consists of the powers of at most two primes. Both decompositions above generalize, the second more usefully than the rst. Corresponding to the rst decomposition, we will see that every member of TS is a disjoint union of translates of (n=p)f0; 1; : : :; p ? 1g and (n=q)f0; 1; : : :; q ? 1g, where n = lcm(S ). The simplest case where both must be used is S = fp; p3; q2g. An important example of this with lcm(S ) = 72 is given below. More usefully, we will show that when S 6= ?, every tile A 2 TS is, as in Lemma 2.5, a union S ? ? of translates of multiples of p or q smaller tiles: A = m ip=01 fai g pAi , where m = gcd(A), a0 = 0, fa0 ; a1; : : :; ap?1g is a complete set of residues modulo p, every fai g pAi f0; 1; : : :; lcm(S ) ? 1g, and for some smaller set S , every Ai 2 TS . We need not get a direct sum, as the Ai need not be equal. Every Ai 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 2 TS , then A CS = Z and either p 2 S and CS pZ, or p 2 S and A pZ. =

TILING THE INTEGERS WITH TRANSLATES OF ONE FINITE SET

11

Let S = fp : p +1 2 S g. If p 2 S , then #S = #S and, as in Lemma 1.4, = TS = fpA : A 2 TS g. If p 2 S , then by the S ? to Lemma 2.5, the members of Corollary ? TS can be constructed by taking all unions ip=01 fai g pAi with Ai 2 TS , a0 = 0, fa0; a1; : : :; ap?1g a complete set of residues modulo p, and every fai g pAi f0; 1; : : :; lcm(S ) ? 1g. This procedure gives all of TS and nothing else. Suppose now that S contains powers of both p and q and let

S = fp : p

+1 2 S g

fq : q 2 S g; S 0 = fp : p 2 S g fq : q

+1

2 S g:

We consider the three cases: p 2 S , q 2 S , and p; q 2 S . If p 2?S , then CS pZ = S ? and TS can be constructed as above by taking all unions ip=01 fai g pAi with Ai 2 TS , a0 = 0, fa0; a1; : : :; ap?1g a complete set of residues modulo p, and every fai g pAi f0; 1; : : :; lcm(S ) ? 1g. If q 2 S , then the analogous procedure, with the roles of p; S and q; S 0 interchanged, gives TS . If both p and q are in S , then CS pqZ and either procedure gives TS . If neither p nor q is in S , then by Lemma 3.3, every member of TS is contained in pZ or qZ. Then #S = #S = #S 0, and fA 2 TS : A pZg = fpA : A 2 TS g, while fA 2 TS : A qZg = fqA : A 2 TS0 g. In all three cases, this procedure gives all of TS 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 TS is a union of translates of p f0; 1; : : :; p ? 1g, where p +1 is the largest member of S . Hence every member ~ of TS is a direct sum of this set and a set A which also tiles the integers. Then +1 g, but A need not be a direct sum. An example with S = f2; 4; 32g ~ SA = S n fp ~ is 16f0; 1g f0; 1; 2; 11g. It is easy to show that if S = fp ; q g, then every member of TS is ~ p ?1 A pq ?1 f0; 1; : : :; q ? 1g ~ for A f0; : : :; pq ?1 ? 1g a complete set of residues modulo p containing 0, or an analogous set with the roles of p and q interchanged. Thus fk : k (x) divides A(x)g contains fp g fq ; pq ; p2q ; : : :; p q g or fq g fp ; p q; p q2 ; : : :; p q g. 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 di erent. In this case TS 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 Tf4;9g are A0 = f0; 3; 6; 18; 21; 24g and A1 = f0; 2; 12; 14; 24; 26g. Each is a direct sum. Consider

A = f0g 2A0 f1g 2A1 = f0; 1; 5; 6; 12; 25; 29; 36; 42; 48; 49; 53g 2 Tf2;8;9g:

?

?

12

ETHAN M. COVEN AND AARON MEYEROWITZ
2 (x)

The cyclotomic polynomial divisors of A(x) = A0 (x2) + xA1 (x2) are those k (x) which divide both A0(x2) and A1 (x2), i.e.,

and

fk : k (x) divides A(x)g = f2g (f8; 9; 18; 36; 72g \ f8; 9; 18; 24; 72g) = f2; 8; 9; 18; 72g;
exactly the set required by (T2). Then as in Theorem ? A (B 72Z? = Z for B = A, ) f0; 8; 16; 18; 26; 34g. deBruijn's example was actually f12g 2A0 f17g 2A1 . It was the rst 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)f0; 1; : : :; p ? 1g for a single prime factor p of n.
deB-1] deB-2] deB-3] Haj] L-W] New] San] Swe] Sza] Tij]

References deBruijn, N. G., On bases for the set of integers, Publ. Math. Debrecen 1 (1950), 232{242. , On the factorization of cyclic groups, Indag. Math. 17 (1955), 370{377. , On number systems, Nieuw Arch. Wisk. (3) 4 (1956), 15{17. Hajos, G., Sur la factorisation des groupes abeliens, Casopis Pest. Mat. Fys. (3) 4 (1950), 157{162. (French) Lagarias, J. and Wang, Y., Tiling the line with translates of one tile, Invent. Math. 124 (1996), 341{365. Newman, D. J., Tesselation of integers, J. Number Theory 9 (1977), 107{111. Sands, A. D., On Keller's conjecture for certain cyclic groups, Proc. Edinburgh Math. Soc. (2) 22 (1977), 17{21. Swenson, C., Direct sum subset decompositions of Z , Paci c J. Math. 53 (1974), 629{633. Szabo, S., A type of factorization of nite abelian groups, Discrete Math. 54 (1985), 121{124. 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

ecoven@wesleyan.edu

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

meyerowi@fau.edu

### When can you tile a box with translates of two give....pdf

Tiling the integers with... 暂无评价 12页 免费...When can you tile a box with translates of two...One characterization is geometric. The other is ...

### Filling a box with translates of two bricks.pdf

set Z(χC ) consists of all points ξ with at least one coordinate ξ...Tiling the integers wi... 暂无评价 12页 免费 Liquid-Solid Phase Tra.....

### FILLING A BOX WITH TRANSLATES OF TWO BRICKS.pdf

FILLING A BOX WITH TRANSLATES OF TWO BRICKS_专业...rst brick only and the other one with the ...On the other hand, by the assumed tiling of Q...

### a finite set V called the set of nodes,and_图文.ppt

A graph is a finite set of nodes with edges between nodes ? Formally, ...of nodes (i,j) is an edge: one would have to search the linked list...

### Universal spectra, universal tiling sets and the sp....pdf

Universal spectra, universal tiling sets and the ...: : g be the set of non-negative integers. ...Wang, Tiling the line with translates of one ...

### Article No. AI981748 The Combinatorics behind Numbe....pdf

of permutations with restricted position, and the ...the weight function equals one for a finite ...tiling of R n there exist two tiles that share...

### Interface effects and termination of finite length ....pdf

Interface effects and termination of finite length ...of graphite by eliminating one of the two ...vectors of graphite, and n, m are integers. For...

### ...ALCOVES AND THE EXPONENTS OF THE FINITE WEYL GROUPS.pdf

referred to any one of the books [1, 3, 5]...nite Coxeter group with set of Coxeter generators...ection representation, then the integers m1 , ....

### The Meaning of Infinity.pdf

because the set of all (finite) natural numbers which it is ascribed to,...one or an actual one, but also with respect to the rules to be ...

### ON THE FINITE SAMPLE BEHAVIOR OF THE CONSTANT MODUL....pdf

ON THE FINITE SAMPLE BEHAVIOR OF THE CONSTANT ...One such algorithm is the ACMA [13] which ...In our case we are given a set of antennas ...

### Combining the Expressivity of UCPOP with the Effici....pdf

1 Introduction One of the important issues in ...In Graphplan, a domain is represented by a set...translates domains from an expressive representation ...

### ...negative. Thenumberofverticesisfinite. Thesource....pdf

Thenumberofverticesisfinite. Thesourceisasinglevertex,butth_专业资料。Apath...p and for every set x holds x ∈ / rng p and p is one-to-one i...

### AC transport with reservoirs of finite width.pdf

AC transport with reservoirs of finite width_专业...The S-matrix in turn appears because one ...a complete set l of which is given by the scattering...

### THE ALGORITHM FOR REDUCING THE NUMBER OF THE NONTER....pdf

of integers, then the system is system with ...one derivation step only the productions from the...Each Pi is a finite set of productions of the...

### The construction of single wavelets in D-dimensions.pdf

single because only one function is required to ...A set K , with the property that as the ...of tiling and of the relationship between Fourier...

### The moduli space of n points on the line is cut out....pdf

This question translates to determining the ...This note deals with one of the most classical ...-independent, and indeed work over the integers....

### ...field of a random polynomial over a finite field....pdf

a random polynomial over a finite field_专业资料...the set Pn (q) of monic polynomials of degree...with ?nite ?elds and there is only one ?eld...

### m takes values in a finite set f1 2 mg, and that.pdf

m takes values in a finite set f1 2 mg, and...In information theory one usually assumes the ...Condition (2) and concavity of em imply that ...

### On the design of finite wordlength IIR filters for ....pdf

This paper investigates the problem of designing finite precision one-...with random s wordlength lters designed by the above method are set. We...

### ...the positive rationals on the group of finite ad....pdf

the group of finite adeles and the Bo_专业资料...So let P be the set of prime numbers, Af .... Then ([L1]) there is a one-to-one ...