The spectral set conjecture and multiplicative properties of roots of polynomials

I. Łaba ^{∗}

               Revised version, September 2001

Abstract Fuglede’s conjecture [2] states that a set Ω ⊂ R^{n} tiles R by translations if and only if L^{2}(Ω) has an orthogonal basis of exponentials. We obtain new partial results supporting the conjecture in dimension 1.

2000 Mathematics Subject Classification: 42A99, 20K01, 11B75.

1 The results

A measurable set Ω ⊂ R^{n} of positive measure is said to tile R^{n} by translations if there is a discrete set T ⊂ R^{n} such that, up to sets of measure 0, the sets Ω+t, t ∈ T, are disjoint and ⋃_{t∈T} (Ω + t) = R^{n}. We will refer to T as the translation set, and write R = Ω ⊕ T. We also say that Λ = {λ_{k}}_{k∈Z} ⊂ R^{n} is a spectrum for Ω if

{e^{2πiλ_{k}·x}}_{k∈Z} is an orthogonal basis for L^{2}(Ω).  (1.1)

A spectral set is a domain Ω ⊂ R^{n} such that (1.1) holds for some Λ.

The following conjecture is due to Fuglede [2].

Conjecture 1.1 (The spectral set conjecture [2].) A domain Ω ⊂ R^{n} is a spectral set if and only if it tiles R^{n} by translations.

Conjecture 1.1 has a functional-analytic origin: it was motivated by a question of I. Segal concerning the “extension property”, i.e., the existence of commuting self-adjoint extensions of the operators −i\frac{∂}{∂x_{j}}, j = 1, …, n, defined on C_{0}^{∞}(Ω), to a dense subspace of L^{2}(Ω). It turns out that any spectral set Ω has the extension property; moreover, if Ω is assumed to be connected, it must be a spectral set in order for the extension property to hold ([2], [7], [23]).

∗Supported in part by NSERC

The conjecture is true under the additional assumption that either Λ or T is a group [2]. It has also been verified in several other special cases, including convex regions in R^{2} ([12], [3], [4], [5]), unions of two intervals in R ([17]), and polytopes with “unbalanced face areas” [15]. Attempts to resolve the general case have revealed a wealth of connections to functional analysis, representation theory, combinatorics, commutative algebra, and Fourier analysis. Fuglede’s conjecture has also led to other questions of independent interest concerning the relations between the tiling and spectral properties of sets, see e.g. [6], [8], [11], [9], [13], [18], [19], [20], [21], [25].

The purpose of this paper is to relate the spectral set conjecture for domains Ω of the form A+[0, 1], where A is a finite subset of R, to purely algebraic questions concerning the multiplicative properties of roots of certain types of polynomials, and to provide partial answers to these questions.

We briefly summarize some of the relevant previous research. Lagarias and Wang [20] proved that if Ω ⊂ R is a bounded compact set with boundary of measure zero which tiles R by translations, then the corresponding translation set T is periodic and T − T ⊂ rQ, where r is the period of the tiling. (Here and below, we denote by T − T the set of differences {t − t′ : t, t′ ∈ T }.) The periodicity result was subsequently extended to all bounded measurable sets by Kolountzakis and Lagarias [14]. Furthermore, the results of [20] (Theorem 3) and [21] (Theorem 1.1) have the following consequence: in order to prove that any bounded compact set with boundary of measure 0 which tiles R by translations is spectral, it suffices to prove this for all sets of the form A + [0, 1), where A is a finite subset of Z, with the additional condition that the spectrum is rational, periodic, and can be chosen the same for all such sets which tile R with the same translation set.

The case of sets A + [0, 1], with A as above, was considered in [21], [24]. In particular, it is known [21] that if a set Ω of this form tiles R by translations and if #A is a prime power, then Ω is a spectral set. (See also [19].) Our Corollary 1.6 uses the recent results of [1] to extend Theorem 1.3 of [21] to the case when #A has 2 prime factors.

Clearly, if Ω is a spectral set, then so is any affine image of it; furthermore, if Λ is a spectrum for Ω, then so is any translate of it. Thus we may always assume that the Lebesgue measure of Ω is rational and that 0 ∈ Λ. Under these additional assumptions, all known examples of spectra of subsets of R are rational and periodic. We do not know whether it must be so for all spectral sets in dimension 1. For domains of the form A + [0, 1), where A is a finite subset of Z, the results of [10] (see Proposition 1.3 below) imply that Λ must indeed be periodic. The rationality of Λ seems to be a more difficult question; Theorem 1.9 below is a modest partial result in this direction.

Let

Ω = ⋃_{j=0}^{N−1}[a_{j}, a_{j} + 1) ⊂ R,  (1.2)

where a_{j} ∈ R, a_{j} + 1 ≤ a_{j+1}, and

Λ = {λ_{k}}_{k∈Z} ⊂ R.  (1.3)

We will say that Λ is a spectrum for Ω if (1.1) holds. Clearly, we may assume that a_{0} = 0, λ_{0} = 0. Furthermore, it suffices to consider the case when all a_{j} are integers. Indeed, if Ω as above tiles R by translations, then all intervals (a_{j}, a_{k}) must have integer length; since we assume that a_{0} = 0, it follows that a_{j} ∈ Z for all j. If on the other hand Ω is a spectral set, the same conclusion follows from Proposition 1.3 below.

Definition 1.2 Let A(z) be a polynomial of the form A(z) = ∑_{k=0}^{N−1} z^{a_{k}}, where a_{k} are distinct non-negative integers. Denote θ_{0} = 0. We will say that {0, θ_{1}, …, θ_{N−1}} ⊂ (0, 1) is a spectrum for A(z) if θ_{i} ≠ θ_{j} for all i ≠ j and if

A(ϵ_{ij}) = 0 for all i, j ∈ {0, 1, …, N − 1}, i ≠ j,  (1.4)

where

ϵ_{ij} = e^{2πi(θ_{i}−θ_{j})}.  (1.5)

The reason for this terminology is the following result, due to Jorgensen and Pedersen [10] (see also [24]).

Proposition 1.3 (Jorgensen - Pedersen [10]) Let Ω and Λ be as in (1.2) and (1.3), and assume that a_{0} = 0, 0 ∈ Λ. Then Λ is a spectrum for Ω if and only if all of the following are satisfied:

(i) a_{0}, a_{1}, …, a_{N−1} ∈ Z;

(ii) the polynomial A(z) = ∑_{k=0}^{N−1} z^{a_{k}} has a spectrum {0, θ_{j} : j = 1, …, N −1} ⊂ (0, 1); (iii) Λ = ⋃_{j=0}^{N−1}(θ_{j} + Z), where θ_{0} = 0 and θ_{j}, j = 1, …, N − 1, are as in (ii).

This result was stated in [10] in terms of Hadamard matrices: it is easy to see that the condition (ii) above is satisfied if and only if the columns of the matrix (e^{2πia_{j}θ_{k}})_{j,k} are mutually orthogonal, which was the condition given in [10]. Our reformulation of it in terms of polynomials was motivated by the recent work of Coven and Meyerowitz [1] on finite sets which tile Z by translations. Clearly, a set of integers A tiles Z if and only if A + [0, 1) tiles R, hence the relevance of this work to the problem under consideration.

The main result of [1] is as follows. Recall that, for s ∈ N, the s-th cyclotomic polynomial Φ_{s}(z) is defined inductively by the identity

z^{s} − 1 = ∏_{k|s} Φ_{k}(z);

equivalently, Φ_{s}(z) = ∏(z − ϵ_{i}), where ϵ_{i} are the s-th primitive roots of 1. Define A(z) = ∑_{a∈A} z^{a}, and let S_{A} be the set of prime powers s such that Φ_{s}(z) divides A(z). Consider the following conditions on A(z):

(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}}(z) divides A(z).

Theorem 1.4 (Coven - Meyerowitz [1])

(i) if (T1), (T2) hold, then A tiles Z by translations;

(ii) if A tiles Z by translations, then (T1) holds;

(iii) if A tiles Z by translations and N = #A has at most two prime factors, then (T2) holds.

It is not known whether (T2) is satisfied for all sets A which tile Z by translations; it does hold in all cases known to the author.

Our first result is that (T1), (T2) also guarantee the existence of a spectrum, and that a weak partial converse holds. Here and throughout the rest of this article, A will always be a finite subset of {0, 1, 2, dots} of cardinality N such that 0 ∈ A, N ≥ 2, A(z) and S_{A} are defined as above, and Ω = A + [0, 1).

Theorem 1.5 (i) If A(z) satisfies (T1), (T2), it has a spectrum.

(ii) If A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}} ⊂ p^{−α}Z, where p is a prime and α ∈ N, then N is a power of p and (T1) holds.

We do not know whether an analogue of (ii) above holds if a spectrum is contained in m^{−1}Z and m is not a prime power. Note also that if N = p^{α} is a prime power, then (T2) holds trivially.

Combining Theorem 1.5 with Proposition 1.3 and Theorem 1.4, we obtain the following immediate corollary, which improves on Theorem 1.3 of [21].

Corollary 1.6 (i) If Ω tiles R and N has at most 2 prime factors, then Ω is a spectral set.

(ii) If Ω is a spectral set with a spectrum Λ ⊂ s^{−1}Z, where s = p^{α} is a prime power, then Ω tiles R by translations.

The following corollary is an easy consequence of Corollary 1.6; it may also be deduced directly from the results of [24].

Corollary 1.7 Assume that N = 3, then Ω is a spectral set if and only if it tiles R by translations.

Note, however, that a spectrum need not always satisfy Λ ⊂ p^{−α}Z, even if N is a power of p. For instance, Ω = \{0, 1, 6, 7\} + [0, 1) has a spectrum Λ = \{0, \frac{1}{12}, \frac{1}{2}, \frac{7}{12}\} + Z.

In light of the next theorem, the case when the degree of A(z) is relatively small (equivalently, the set Ω is contained in a relatively short interval) seems to be a natural starting point for further investigation. The author expects that a more general result should hold: if Ω ⊂ R^{n} “almost fills up” a convex set, and if it is a spectral set or tiles R^{n} by translations, it must be a fundamental domain for a group.

Theorem 1.8 Suppose that A ⊂ [0, M − 1], M < 3N/2, and let Ω = A + [0, 1). Then the following are equivalent:

(i) A tiles Z by translations;

(ii) Ω is a spectral set;

(iii) Ω is a fundamental domain for the group NZ, i.e., A = {0, 1, …, N −1}(mod N); (iv) NZ ⊕ A = Z, i.e., NZ ⊕ Ω = R;

(v) Λ = N^{−1}Z is a spectrum for Ω.

The equivalence of (iii), (iv), and (v) (for more general Ω) was proved by Fuglede [2], and the implications (iv) ⇒ (i), (v) ⇒ (ii) are trivial. Our new result is that the implications (i) ⇒ (iii) and (ii) ⇒ (iii) hold for A as in the theorem. Note that the set [0, n] ∪ [2n, 3n] tiles R and is a spectral set (see e.g. [17] for an explicit calculation of the spectra), but is not a fundamental domain for any group; this shows that the inequality M < 3N/2 cannot be weakened.

We do not know whether a spectrum of a set Ω as above must always be rational, or whether any such spectral set must have a rational spectrum. However, we have the following partial result.

Theorem 1.9 Suppose that Ω = A + [0, 1) has a spectrum Λ, and that Ω ⊂ [0, M] for some M < 5N/2. Then Λ ⊂ Q.

If m, n are integers, we will use (m, n) to denote the greatest common divisor of m, n. The cardinality of a finite set B is denoted by #B.

The author is grateful to Peter Borwein, David Boyd, and Richard Froese for helpful conversations.

2 Proof of Theorem 1.5

We first prove (i). Assume that (T1), (T2) hold, and define S_{A} as in the introduction. Consider the set B of all numbers of the form

∑_{s∈S_{A}} \frac{k_{s}}{s} ,

where k_{s} ∈ {0, 1, …, p − 1} if s ∈ S_{A} and s = p^{α}, p is prime. We claim that B is a spectrum for A(z).

Let N = p_{1}^{α_{1}} … p_{m}^{α_{m}}, where p_{i} are distinct primes. We have

Φ_{s}(1) = \{ \begin{matrix}0 & if s = 1, \\ p & if s = p^{α}, p is prime, α ≥ 1, \\ 1 & otherwise \end{matrix}  (2.1)

(see [1], Lemma 1.1). Thus (T1) implies that for each i there are exactly α_{i} powers of p_{i} in S_{A}. It follows that

#B = p_{1}^{α_{1}} … p_{m}^{α_{m}} = N.

Furthermore, taking k_{s} = 0 for all s we see that 0 ∈ B.

It remains to check that

A(e^{2πi(b−b′)}) = 0 for all b, b′ ∈ B.  (2.2)

Fix b, b′ ∈ B. Then b − b′ is a number of the form ∑_{s∈S_{A}} \frac{k_{s}}{s} , where k_{s} ∈ \{−p_{i} + 1, −p_{i} + 2, …, p_{i} − 1} if s is a power of p_{i}. We rewrite this as b − b′ = ∑_{i=1}^{m} b_{i}, where

b_{i} = ∑_{β:p_{i}^{β}∈S_{A}} \frac{k_{p_{i}^{β}}}{p_{i}^{β}} ,

and k_{p_{i}^{β}} ∈ {−p_{i} + 1, …, p_{i} − 1}. If b_{i} ≠ 0, we may further write:

b_{i} = \frac{k_{i}}{p_{i}^{β_{i}}} ,

where β_{i} is the largest exponent such that p_{i}^{β_{i}} ∈ S_{A}, k_{p_{i}^{β_{i}}} ≠ 0, and k_{i} is a non-zero integer not divisible by p_{i}. By Lemma 2.1 below,

Φ_{s}(e^{2πi(b−b′)}) = 0 for s = ∏_{i:b_{i}≠0} p_{i}^{β_{i}}.

This immediately implies (2.2): since p_{i}^{β_{i}} ∈ S_{A} for each i, by (T2) Φ_{s}(z) divides A(z), hence e^{2πi(b−b′)} is also a root of A(z).

Lemma 2.1 Let b = ∑_{i=1}^{n} \frac{k_{i}}{s_{i}}, where (k_{i}, s_{i}) = 1 for all i and (s_{i}, s_{j}) = 1 for all i ≠ j. Then Φ_{s}(e^{2πib}) = 0 for s = s_{1} … s_{n}.

Proof. The roots of Φ_{s}(z) are the primitive s-th roots of unity, i.e., the numbers e^{2πik/s} for (k, s) = 1. We write:

b = \frac{k}{s} , s = s_{1} … s_{n}, k = k_{1} \frac{s}{s_{1}} + … + k_{n} \frac{s}{s_{n}} .

It suffices to check that k and s are relatively prime. Indeed, suppose to the contrary that there is a prime p such that p|k and p|s. Then p divides one of the s_{i}, say s_{1}. Since s_{1} divides s/s_{i} for all i ≠ 1, it follows that p divides k_{2} \frac{s}{s_{2}} + … + k_{n} \frac{s}{s_{n}}. Since we also assumed that p|k, it follows that p divides k_{1}s/s_{1}, hence it divides either k_{1} or s/s_{1}. This, however, contradicts the assumptions of the lemma. Indeed, p cannot divide k_{1}, since (k_{1}, s_{1}) = 1. But we also have (s_{1}, s_{i}) = 1 for i ≠ 1, hence (s_{1}, s/s_{1}) = 1 and p cannot divide s/s_{1}.

Next, we turn to part (ii) of the theorem. Let p be a prime, s = p^{α}, and suppose that A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}} contained in s^{−1}Z. Let θ_{0} = 0 and θ_{ij} = θ_{i} − θ_{j}. Then e^{2πiθ_{ij}} is a root of (z − 1)A(z) for all i, j ∈ {0, 1, …, N − 1}. If i ≠ j, we may write

θ_{ij} = \frac{k_{ij}}{p^{α_{ij}}}  (2.3)

for some integers α_{ij} and k_{ij} such that α_{ij} ≥ 1, (p, k_{ij}) = 1. Let r_{1}, …, r_{m} be the distinct values of α_{ij} in (2.3). Since Φ_{p^{α_{ij}}} (x) is the minimal polynomial of e^{2πiθ_{ij}}, we must have

Φ_{p^{r_{1}}}(z) … Φ_{p^{rm}}(z) | A(z),

and in particular Φ_{p^{r_{1}}}(1) … Φ_{p^{rm}}(1) | A(1). Since A(1) = N and, by (2.1), Φ_{p^{r_{j}}} (1) = p, it follows that N ≥ p^{m}. Thus (ii) will follow if we prove that N ≤ p^{m}. To do this, it suffices to verify that the polynomial

F_{0,r_{1},...,r_{m}}(z) = (z − 1)Φ_{p^{r_{1}}}(z) … Φ_{p^{rm}}(z)

has at most p^{m} roots ϵ_{i} such that

F_{0,r_{1},...,r_{m}}(ϵ_{i}/ϵ_{j}) = 0 for all i, j.  (2.4)

The proof is by induction on m. If m = 1, all roots of F_{0,r_{1}}(z) = (z − 1)Φ_{p^{r_{1}}}(z) are of the form e^{2πik/p^{r_{1}}}, k ∈ Z. If k and k′ belong to the same residue class modulo p^{r_{1}−1}, then k − k′ and p^{r_{1}} are not relatively prime, hence either the corresponding roots e^{2πik/p^{r_{1}}} and e^{2πik′/p^{r_{1}}} are equal or else e^{2πi(k−k′)/p^{r_{1}}} is not a root of F_{0,r_{1}}(z). Since there are only p distinct residue classes modulo p, the claim follows if m = 1.

Assume now that the claim is true with m replaced by m−1. Let ϵ_{j} = e^{2πik_{j}/r_{m}} be roots of F_{0,r_{1},...,r_{m}}(z) satisfying (2.4). We divide them into p equivalence classes Θ_{0}, Θ_{1}, …, Θ_{p−1} as follows: ϵ_{j} ∈ Θ_{l} if and only if k_{j} = l(mod p^{r_{m}−1}). By the same argument as above, if ϵ_{i} and ϵ_{j} belong to the same Θ_{l}, then ϵ_{i}/ϵ_{j} cannot be a root of Φ_{p^{rm}}(z), hence it must be a root of F_{0,r_{1},...,r_{m−1}}(z). By the inductive hypothesis, #Θ_{l} ≤ p^{m−1}. Since the number of the equivalence classes Θ_{l} is p, the claim follows.

Proof of Corollary 1.7. Let A = {0, a_{1}, a_{2}}. We first claim that it suffices to consider the case when (a_{1}, a_{2}) = 1. Indeed, let k ∈ N. By Lemma 1.4(1) of [1], A tiles Z if and only if kA tiles Z ([1], Lemma 1.4(1)). On the other hand, e^{2πiθ} is a root of A(z) if and only if e^{2πiθ/k} is a root of A(z^{k}), and (kA)(z) = A(z^{k}), hence {0, θ_{1}, θ_{2}} is a spectrum for A(z) if and only if {0, θ_{1}/k, θ_{2}/k} is a spectrum for (kA)(z).

If A tiles Z, A(z) has a spectrum by Corollary 1.6(i). Conversely, suppose that A(z) has a spectrum {0, θ_{1}, θ_{2}}, then

1 + e^{2πia_{1}θ_{j}} + e^{2πia_{2}θ_{j}} = 0, j = 1, 2.

Hence e^{2πia_{1}θ_{j}} and e^{2πia_{2}θ_{j}} are cubic roots of 1, and in particular a_{1}θ_{j}, a_{2}θ_{j} ∈ \frac{1}{3}Z. Since (a_{1}, a_{2}) = 1, there are integers k_{1}, k_{2} such that k_{1}a_{1} + k_{2}a_{2} = 1, so that

θ_{j} = k_{1}a_{1}θ_{j} + k_{2}a_{2}θ_{j} ∈ \frac{1}{3}Z.

By Corollary 1.6(ii), A tiles Z.

3 Proof of Theorem 1.8

Let A = {a_{0}, a_{1}, …, a_{N−1}}, where a_{j} ∈ {0, 1, …, M − 1} and M < 3N/2, and let Ω = A + [0, 1). We may assume that

0 = a_{0} < a_{1} < … < a_{N−1} = M − 1.

We must prove that each of the conditions (i), (ii) of Theorem 1.8 implies that Ω is a fundamental domain for NZ, i.e., A = {0, 1, …, N − 1}(mod N).

Part 1: (i) implies (iv). Assume that A tiles Z by translations, i.e., that there is a set of integers B such that A⊕B = Z (hence Ω⊕B = R). We may assume that B = {b_{i}}_{i∈Z}, where b_{i} < b_{i+1} for all i. Denote

c_{i} = b_{i} + M, Ω_{i} = Ω + b_{i}, I_{i} = [b_{i}, c_{i}).

The interval [b_{i}, c_{i+2}) contains three disjoint translates of Ω (Ω_{i}, Ω_{i+1}, Ω_{i+2}), hence we must have c_{i+2} − b_{i} ≥ 3N. Using also that M < 3N/2, we see that

b_{i+2} − c_{i} = (c_{i+2} − M) − (b_{i} + M) ≥ 3N − M > 0.

We also have the trivial inequality c_{i} ≥ b_{i+1} (if it failed, Ω⊕B would have “gaps” (c_{i}, b_{i+1}).) Hence each I_{i} may overlap only with its immediate predecessor I_{i−1} and successor I_{i+1}:

… < b_{i} ≤ c_{i−1} < b_{i+1} ≤ c_{i} < b_{i+2} ≤ ….  (3.1)

For m > 0, define

S_{1}(m) = ∑_{i=1}^{m}(b_{i+1} − c_{i−1}), S_{2}(m) = ∑_{i=1}^{m}(c_{i} − b_{i+1}).

Then:

\begin{matrix}∫_{b_{1}}^{c_{m}} ∑_{i=−∞}^{∞} χ_{Ω_{i}} = S_{1}(m) + S_{2}(m) + O(1), \\ ∫_{b_{1}}^{c_{m}} ∑_{i=−∞}^{∞} χ_{I_{i}} = S_{1}(m) + 2S_{2}(m) + O(1), \end{matrix}  (3.2)

where we used that ∑_{i=−∞}^{∞} χ_{Ω_{i}} ≡ 1 and that, by (3.1),

∑_{i=−∞}^{∞} χ_{I_{i}}(x) = \{ \begin{matrix}2, & x ∈ (b_{i+1}, c_{i}), \\ 1, & x ∈ (c_{i−1}, b_{i+1}). \end{matrix}

(Here and in the sequel, O(1) denotes a quantity which, for any fixed N and M, is bounded uniformly in m as m → ∞.) On the other hand, counting the sets Ω_{i} contained in [b_{1}, c_{m}] and the intervals I_{i} having non-empty intersection with it, we obtain that:

\begin{matrix}∫_{b_{1}}^{c_{m}} ∑_{i=−∞}^{∞} χ_{Ω_{i}} ≥ mN + O(1), \\ ∫_{b_{1}}^{c_{m}} ∑_{i=−∞}^{∞} χ_{I_{i}} ≤ mM + O(1) ≤ αmN + O(1), \end{matrix}  (3.3)

for some α < 3/2 independent of m. From (3.2) and (3.3) we have

\begin{matrix}S_{1}(m) + 2S_{2}(m) ≤ αmN + O(1), \\ S_{1}(m) + S_{2}(m) ≥ mN + O(1), \end{matrix}

which yields that

S_{2}(m) ≤ (α − 1)mN + O(1), S_{1}(m) ≥ (1 − α)mN + O(1).

In particular, lim_{m→∞} \frac{S_{1}(m)}{m} ≥ (1 − α)N > N/2, hence there is an i ∈ Z such that b_{i+1} − c_{i−1} > N/2. But, by (3.1), (c_{i−1}, b_{i+1}) ⊂ Ω_{i} \ ⋃_{j≠i} Ω_{j}, hence Ω contains at least one complete interval of length greater than N/2.

Assume therefore that [m, n] ⊂ Ω, n − m > N/2, and that [m, n] is maximal in the sense that m − \frac{1}{2}, n + \frac{1}{2} ∉ Ω. Let m_{i} = m + b_{i} and n_{i} = n + b_{i}. By (3.1),

([m_{i} − 1, m_{i}) ∪ [n_{i}, n_{i} + 1)) ⊂ (I_{i−1} ∪ I_{i+1}).

Suppose that [m′ − 1, m′) ⊂ I_{i+1} for some m′ such that b_{i} ≤ m′ ≤ m_{i}. Since b_{i+1} > 1, I_{i+1} contains at least one unit interval to the right of I_{i}, and, in particular, [m_{i}, n_{i}) ⊂ I_{i+1}. But [m_{i}, n_{i}) ∩ Ω_{i+1} = ∅. Thus |I_{i+1}| ≥ |Ω_{i+1}| + (n_{i} − m_{i}) > 3N/2, which contradicts the assumption that M = |I_{i+1}| < 3N/2. We must therefore have [m′ − 1, m′) ⊂ I_{i−1}. Similarly, [n′, n′ + 1) ⊂ I_{i+1} whenever n_{i} ≤ n′ ≤ c_{i} − 1. It follows that

c_{i−1} = m_{i}, b_{i+1} = n_{i}, [b_{i+1}, c_{i}) ⊂ Ω_{i} ∪ Ω_{i+1}.

Hence

b_{i+1} − c_{i−1} = n_{i} − m_{i} = n − m

and

\begin{matrix}c_{i} − b_{i+1} = |Ω_{i} ∩ [n_{i}, c_{i})| + |Ω_{i+1} ∩ [b_{i+1}, c_{i})| = |Ω ∩ [n, M)| + |Ω ∩ [0, m)| \\ = |Ω \ [m, n)| = N − (n − m), \end{matrix}

so that

c_{i} − c_{i−1} = (c_{i} − b_{i+1}) + (b_{i+1} − c_{i−1}) = (N − (n − m)) + (n − m) = N.

This proves (iv).

Part 2: (ii) implies (v). Suppose that Ω is a spectral set, and let A(z) = ∑_{a∈A} z^{a}. By Proposition 1.3, A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}}. As before, we denote θ_{0} = 0. Then

A(ϵ_{ij}) = 0, i ≠ j,

where ϵ_{ij} = e^{2πi(θ_{i}−θ_{j})}. Here and below, all indices i, j, etc. range from 0 to N − 1. We will first prove that

∀i, j, k, l ∃m, i′, l′ such that ϵ_{ij} = ϵ_{i′m}, ϵ_{kl} = ϵ_{ml′}.  (3.4)

This will imply that G = {ϵ_{ij} : i, j = 0, 1, …, N − 1} is a group. Indeed, since G is finite and contains 1, it suffices to prove that G is closed under multiplication. But if (3.4) holds, then for any ϵ_{ij}, ϵ_{kl} ∈ G we have

ϵ_{ij}ϵ_{kl} = ϵ_{i′m}ϵ_{ml′} = ϵ_{i′l′} ∈ G.

The verification of (3.4) is as follows. Observe that

ϵ_{ij} = ϵ_{i′m} ⇔ ϵ_{ii′} = ϵ_{jm}, ϵ_{kl} = ϵ_{ml′} ⇔ ϵ_{ll′} = ϵ_{km},

hence it suffices to prove the following:

∀i, j, k, l ∃m, i′, l′ such that ϵ_{ii′} = ϵ_{jm}, ϵ_{ll′} = ϵ_{km}.  (3.5)

For each pair (i, j) define

E_{ij} = {m ∈ {0, 1, …, N − 1} : ϵ_{jm} = ϵ_{ii′} for some i′},

then (3.5) is equivalent to

E_{ij} ∩ E_{kl} ≠ ∅.  (3.6)

Since M < 3N/2, A(z) is a polynomial of degree strictly less than \frac{3N}{2} − 1. If i = j, ϵ_{ij} is equal to 1; otherwise, it is a root of A(z). Hence the number of possible values that ϵ_{ij} may take is bounded by deg (A(z)) + 1, which is less than 3N/2. On the other hand, since θ_{0}, …, θ_{N−1} are distinct, so are ϵ_{i0}, ϵ_{i1}, …, ϵ_{i,N−1} for any i. Hence for any i, j the number of values which occur both in {ϵ_{i0}, ϵ_{i1}, …, ϵ_{i,N−1}} and in {ϵ_{j0}, ϵ_{j1}, …, ϵ_{j,N−1}} is strictly greater than N + N − \frac{3N}{2} = N/2. But this means that

#E_{ij} > N/2.

Thus E_{ij}, E_{kl} are two subsets of {0, 1, …, N − 1} of cardinality strictly greater than N/2, whereupon (3.6) follows.

We have proved that G is a group, hence G must be the set of all n-th roots of 1 for some n ∈ Z. But A(ϵ_{ij}) = 0 for all ϵ_{ij} ∈ G, hence the polynomial P_{n}(z) = 1 + z + … + z^{n−1} divides A(z). In particular, P_{n}(1)|A(1), i.e., n|N. On the other hand, since ϵ_{i} are all distinct, n ≥ N. Hence n = N, and the ϵ_{i} are N-th roots of 1, i.e., Λ = \frac{1}{N} Z.

Observe that the proof of the implication (ii) ⇒ (v) did not actually use that the degree of A(z) was less than \frac{3N}{2} − 1, but only that A(z) has less than \frac{3N}{2} − 1 roots of modulus 1. Hence we have also proved the following result, which will be used in the proof of Theorem 1.9.

Lemma 3.1 Suppose that A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}}, and that #{z : A(z) = 0, |z| = 1\} < \frac{3N}{2} − 1. Let θ_{0} = 0. Then the set

G = {e^{2πi(θ_{j}−θ_{k})} : j, k = 0, 1, …, N − 1}

is a group.

4 Proof of Theorem 1.9.

Suppose that Ω has a spectrum Λ. By Proposition 1.3, the polynomial A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}}. It suffices to prove that if Ω ⊂ [0, M] and if θ_{1} is irrational, then

M ≥ \frac{5N}{2} .  (4.1)

Suppose that θ_{1} ∉ Q. By Lemma 3.1, A(z) has at least \frac{3N}{2} − 1 roots of modulus 1. By Lemma 4.1 below, A(z) has at least N roots off the unit circle. Hence

M ≥ deg (A(z)) + 1 ≥ (N) + (\frac{3N}{2} − 1) + 1 = \frac{5N}{2} ,

which is (4.1).

Lemma 4.1 Suppose that A(z) has a spectrum {0, θ_{1}, …, θ_{N−1}}, and that θ_{1} ∉ Q. Then A(z) has at least N roots of modulus not equal to 1.

Proof. We will need some basic results of Galois theory. Let A(z) be a polynomial with integer coefficients, and let L be its splitting field extension over Z, i.e., the smallest subfield of C containing Z and all roots of A. The Galois group of A is the group G of all automorphisms of L preserving Q. It follows from the definition that if A(ξ) = 0, then also A(σ(ξ)) = 0 for all σ ∈ G. A fundamental result of Galois theory is that G acts transitively on the roots of each irreducible factor of A(z).

Let ϵ_{j} = e^{2πiθ_{j}}, ϵ_{0} = 1, and ϵ_{jk} = ϵ_{j}/ϵ_{k}. Then A(ϵ_{j}) = 0 for all j ≠ 0, and A(ϵ_{jk}) = 0 for all j ≠ k. Since ϵ_{1} is not a root of 1, by Kronecker’s theorem [16] the minimal polynomial A_{1}(z) of ϵ_{1} has at least one root ξ_{1} such that |ξ_{1}| ≠ 1.

The Galois group G of A(z) acts transitively on the roots of A_{1}(z), hence there is a σ ∈ G such that σ(ϵ_{1}) = ξ_{1}. Let ξ_{i} = σ(ϵ_{i}) and ξ_{ij} = σ(ϵ_{ij}). Then A(ξ_{j}) = 0 for all j ≠ 0 and A(ξ_{jk}) = 0 for all j ≠ k. Note also that ξ_{ij} = ξ_{i}/ξ_{j}, and that ξ_{ij} ≠ 1 if i ≠ j. Let

I = {i : 1 ≤ i ≤ N − 1, |ξ_{i}| = 1},

and let k = #I. Observe that 1 ∉ I.

Let r_{1} = |ξ_{1}|, and consider the roots

ξ_{1i}, i ∈ I.  (4.2)

All of them have modulus r_{1}, since |ξ_{1i}| = |ξ_{1}|/|ξ_{i}| = r_{1}. Furthermore, ξ_{1i} ≠ ξ_{1j} for i ≠ j, and ξ_{1i} ≠ ξ_{1} since ξ_{i} ≠ 1. Thus there are at least k + 1 distinct roots of modulus r_{1}: the k roots in (4.2), and ξ_{1}.

We now consider two cases.

Case 1. If |ξ_{i}| ≥ 1 for all i, consider the roots

ξ_{0i} : i ≠ 0, i ∉ I.

Since there are N − 1 − k indices i such that i ≠ 0 and i ∉ I, the number of such roots is N − 1 − k. They all have modulus less than 1, since |ξ_{0i}| = 1/|ξ_{i}|. In particular, they are distinct from the k + 1 roots of modulus r_{1}, since we are assuming that r_{1} > 1. Hence the total number of roots of modulus different from 1 is at least (k + 1) + (N − 1 − k) = N. The case when |ξ_{i}| ≤ 1 for all i is similar.

Case 2. Suppose now that r_{2} < 1 and r_{3} > 1, where

r_{2} = min{|ξ_{i}| : i = 1, …, N − 1}, r_{3} = max{|ξ_{i}| : i = 1, …, N − 1}.

Then there are ξ_{2}, ξ_{3} such that |ξ_{2}| = r_{2}, |ξ_{3}| = r_{3}. Consider the roots

ξ_{2j} for j such that |ξ_{j}| > 1  (4.3)

and

ξ_{3j} for j such that |ξ_{j}| < 1.  (4.4)

The roots (4.3) have modulus strictly less than r_{2}, since

|ξ_{2j}| = \frac{|ξ_{2}|}{|ξ_{j}|} < |ξ_{2}| = r_{2}.

Similarly, the roots (4.4) have modulus strictly greater than r_{3}. Thus all roots in (4.4) are distinct from those in (4.3). To each j such that |ξ_{j}| ≠ 1 there corresponds either a root in (4.3) (if |ξ_{j}| > 1) or in (4.4) (if |ξ_{j}| < 1). Hence the combined number of the roots in (4.3) and (4.4) is N − 1 − k. Furthermore, since r_{2} ≤ r_{1} ≤ r_{3}, the roots in both (4.3) and (4.4) are distinct from those in (4.2). As in the previous case, we conclude that there are at least N roots with modulus different from 1.

References

[1] E. M. 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] A. Iosevich, N. H. Katz, S. Pedersen: Fourier bases and a distance problem of Erdös, Math. Res. Lett. 6 (1999), 251–255.

[4] A. Iosevich, N. H. Katz, T. Tao: Convex bodies with a point of curvature do not have Fourier bases, Amer. J. Math. 123 (2001), 115–120.

[5] A. Iosevich, N. H. Katz, T. Tao: Fuglede conjecture holds for convex planar domains, preprint, 2001.

[6] A. Iosevich, S. Pedersen: Spectral and tiling properties of the unit cube, Internat. Math. Res. Notices 16 (1998), 819–828.

[7] P. Jorgensen: Spectral theory of finite volume domains in R^{n}, Adv. Math. 44 (1982), 105–120.

[8] P. Jorgensen, S. Pedersen: Spectral theory for Borel sets in R^{n} of finite measure, J. Funct. Anal. 107 (1992), 72–104.

[9] P. Jorgensen, S. Pedersen: Harmonic analysis and fractal limit-measures induced by representations of certain C^{∗}-algebra, J. Funct. Anal. 125 (1994), 90–110.

[10] P. Jorgensen, S. Pedersen: Fractal Geometry and Stochastics, in: Progress in Probability, vol.17, Birkhäuser, Basel, 1995, 191–219.

[11] P. Jorgensen, S. Pedersen: Spectral pairs in Cartesian coordinates, J. Fourier Anal. Appl. 5 (1999), 285–302.

[12] M. Kolountzakis: Non-symmetric convex domains have no basis of exponentials, Illinois J. Math. 44 (2000), 542–550.

[13] M. Kolountzakis: Packing, tiling, orthogonality, and completeness, Bull. London Math. Soc. 32 (2000), 589–599.

[14] M. Kolountzakis, J.C. Lagarias: Structure of tilings of the line by a function, Duke Math. J. 82 (1996), 653–678.

[15] M. Kolountzakis, M. Papadimitrakis: A class of non-convex polytopes that admit no orthogonal basis of exponentials, preprint, 2001.

[16] L. Kronecker: Zwei Sätze über Gleichungen mit ganzzahligen Coefficienten, J. Reine Angew. Math. 53 (1857), 173–175.

[17] I. Łaba: Fuglede’s conjecture for a union of two intervals, Proc. Amer. Math. Soc. 129 (2001), 2965–2972.

[18] J. C. Lagarias, J. A. Reed, Y. Wang: Orthonormal bases of exponentials for the n-cube, Duke Math. J. 103 (2000), 25–37.

[19] J. C. Lagarias, S. Szabó: Universal spectra and Tijdeman’s conjecture on factorization of cyclic groups, J. Fourier Anal. Appl. 7 (2001), 63–70.

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

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

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

[23] S. Pedersen: Spectral theory of commuting self-adjoint partial differential operators, J. Funct. Anal. 73 (1987), 122–134.

[24] S. Pedersen: Spectral sets whose spectrum is a lattice with a base, J. Funct. Anal. 141 (1996), 496–509.

[25] S. Pedersen, Y. Wang: Universal spectra, universal tiling sets and the spectral set conjecture, Math. Scand., to appear.

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

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