• Ingen resultater fundet

UNIVERSAL SPECTRA, UNIVERSAL TILING SETS AND THE SPECTRAL SET CONJECTURE

N/A
N/A
Info
Hent
Protected

Academic year: 2022

Del "UNIVERSAL SPECTRA, UNIVERSAL TILING SETS AND THE SPECTRAL SET CONJECTURE"

Copied!
11
0
0

Indlæser.... (se fuldtekst nu)

Hele teksten

(1)

UNIVERSAL SPECTRA, UNIVERSAL TILING SETS AND THE SPECTRAL SET CONJECTURE

STEEN PEDERSEN and YANG WANG

Abstract

A subsetofRdwith finite positive Lebesgue measure is called aspectral setif there exists a subsetRsuch thatE:=

ei2πλ,x:λ

form an orthogonal basis ofL2(). The set is called aspectrumof the set. The Spectral Set Conjecture states thatis a spectral set if and only iftilesRdby translation. In this paper we prove the Spectral Set Conjecture for a class of setsR. Specifically we show that a spectral set possessing a spectrum that is a strongly periodic set must tileRby translates of a strongly periodic set depending only on the spectrum, and vice versa.

1. Introduction

Let be a (Lebesgue) measurable subset ofRwith finite positive measure.

For tR let +t := {x + t : x} denote the translate of by t. We say that tilesRby translation if there exists a subset TRso that R\

t∈T (+t) is a set of measure zero and (+t)+t

is a set of measure zero whenevert, tT are distinct. In the affirmative caseT is called atiling setfor, and(,T)is called atiling pair. Similarly, we say that tiles the non-negative half lineR+=[0,∞)if there exists a subsetTR such thatR+\

t∈T (+t)is a set of measure zero and(+t)+t is a set of measure zero whenevert, tT are distinct. Sets that tile the real line by translation have been studied recently, e.g., [9], [8], [7].

ForλRwe introduce the functions

eλ(x):=ei2πλx, xR.

We say thatis aspectral setif there exists a subsetRso that the functions E := {eλ :λ}form an orthogonal basis forL2(), the Hilbert space of complex valued square integrable functions onwith the inner product

f, g:=

f (x)g(x) dx.

Received August 25, 1998.

(2)

If the functions inEform an orthogonal basis forL2(), then we call(, ) aspectral pairandaspectrumfor. Spectral sets have recently been studied in various contexts, e.g., [3], [4], [5], [10], [8], [6].

One of the main open questions concerning spectral sets is the following conjecture, first proposed by Fuglede [3]:

Spectral Set Conjecture. Let be a measurable subset of Rd with finite positive Lebesgue measure. Thenis a spectral set if and only iftiles Rdby translation.

In this paper we study the one dimensional case of the Spectral Set Conjec- ture. A special class of sets we study consists of tiles that tile the non-negative half lineR+by translation. We prove:

Theorem1.1. Letbe a subset ofRwith finite positive Lebesgue measure.

Suppose thattilesR+by translation. ThentilesRby translation and is a spectral set.

LetN:= {1,2,3, . . .}be the set of natural numbers andZ+:= {0,1,2, . . .}

be the set of non-negative integers. For anynNletZ+n := {0,1, . . . , n−1}. For anyA,BZwe write

A+B:= {a+b:aA, bB}

for the Minkowski sum ofAandB. We will writeABif each element in A+Bhas auniquedecomposition of the forma+bwithaAandbB. Definition1.2. We callAZ+adirect summand of Z+n if there exists a BZ+such thatAB = Z+n. We call a subsetT ofRastrongly periodic set if there exist annN and a direct summandAZ+ of Z+n such that T =α(AnZ)for some non-zeroαR.

In [8] it was shown that certain tiles that tileRby translation are spectral sets that possess the so-calleduniversal spectra, in the sense that the spectra depend only on the tiling sets, not the tiles. Our main theorem below strengthens this notion by providing a large new class of tiles that possess universal spectra. It shows that a tile that tilesRby the translates of a strongly periodic set must have a universal spectrum that is also a strongly periodic set. More importantly, the theorem also gives rise to the notion ofuniversal tiling set, which can be viewed as the dual of universal spectrum. We show that a spectral set that possesses a spectrum that is a strongly periodic set must have a universal tiling set depending only on the spectrum.

Theorem1.3. Letbe a subset of Rwith finite positive measure. Suppose that there exists a strongly periodic setRsuch that(, )is a spectral

(3)

pair. Then there exists a strongly periodic setTRdepending only on such thattilesRby translates ofT. Conversely, suppose that there exists a strongly periodic setTRsuch thattilesRby translates ofT. Then there exists a strongly periodic setRdepending only onT such that(, )is a spectral pair.

The strongly periodic setsandT in Theorem 1.3 aredualsof each other, and for each given one the other is constructed explicitly in §4. In fact we prove a stronger version of Theorem 1.3 there. For the rest of the paper, in §2 we state a result on the structure of strongly periodic sets, first shown in [2].

In §3 we classify tiles that tileR+by translation. The classification is used to prove Theorem 1.1.

2. Structure of Strongly Periodic Sets

In this section we classify subsetsA,BofZ+satisfyingAB =Z+n for some nN. The classification is based on a theorem of de Bruijn [2] establishing the structure of subsets ofZ+that tileZ+by translation. To formulate the result we first introduce some notation regarding divisibility. Forr, sZwe user |s to mean thatr dividess; forrZandAZ we user | Ato mean thatr divides everyaA.

Proposition2.1 (de Bruijn). LetA, BZ+such thatAB= Z+and A=Z+,B=Z+. Then there exists an integerr >1such thatr |Aorr |B. Furthermore, ifr|BandB =rBthen there exists anAZ+such that

A=Z+rrA, and AB=Z+.

Proof. A proof can be found in de Bruijn [2]. For the sake of self-contain- ment we give a short proof here.

Without loss of generality we assume 1∈A. Letrbe the smallest non-zero member ofB. For eachmNletAmAandBmBbe the minimal subsets so that

Z+mrAm+Bm.

It follows immediately from the minimality and the uniqueness inABthat Am=AZ+mr, Bm=BZ+mr.

Observe thatZ+(m+1)r\Z+mr =Z+r +mr. So

Am+1\AmZ+r +mr, Bm+1\BmZ+r +mr.

(4)

We show by induction onmthat there are subsetsCmandDmofZ+such that Am=Z+r +rCm, Bm=rDm.

Let C1 := {0} andD1 := {0}. Then A1 = Z+r +rC1 and B1 = rD1 as required. Suppose that Cm, DmZ+ have been constructed so thatAm = Z+r +rCm and Bm = rDm. IfZ+(m+1)rAm +Bm, then Am+1 = Am and Bm+1 = Bm, and so it suffices to set Cm+1 := Cm and Dm+1 := Dm to complete the proof.

Now suppose thatZ+(m+1)rAm+Bm. LetjZ+r. Ifj+mrAm+Bm= Z+r +r(Cm+Dm)thenmCm+Dmand thereforeZ+r +mrAm+Bm, contradictingZ+(m+1)rAm+Bm. Hence,

(Z+r +mr)(Am+Bm)= ∅.

It follows thatmrAm+1ormrBm+1.

IfmrBm+1, thenAm+1= AmandBm+1 =Bm∪ {rm}. Hence we may setCm+1:=CmandDm+1:=Dm∪ {m}.

Assume that mrAm+1. Let jZ+r . We have shown above thatj + mr /Am+Bm, so j +mr = a+b foraAm+1\Am, bBm+1 or aAm,bBm+1\Bm. IfbBm+1\Bmthen(m+1)rbZ+r . Thus mr+ r = ((m+ 1)rb)+b constitute two different decompositions of the same element inAB, a contradiction. This yieldsaAm+1\Am. If b = 0 thenBm = rDm andBm+1\BmZr++mr implies thatbr. So j+mr = a+bmr+r > j +mr, again a contradiction. Sob= 0 and thereforej+mr=aAm+1. It follows that

Am+1=Am(Z+r +mr).

The inductions steps are now complete by setting Cm+1 := Cm∪ {m} and Dm+1:=Dm.

Finally, the proposition follows by lettingA:=

m=1CmandB=

m=1Dm. Proposition 2.1 immediately leads to the following classification of strongly periodic sets.

Corollary2.2. Let A, BZ+such that AB = Z+n andA = Zn+, B =Z+n. Then there exists anr >1such thatr |nand eitherr |Aorr |B. Furthermore, ifr|BandB =rBthen there exists anAZ+so that

A=Z+rrA, and AB=Z+n

r.

Proof. Suppose that 1∈A. Applying Proposition 2.1 toA(BnZ+)= Z+yields anr >1 and a setAso thatA=Z+rrAandr |(BnZ+). Since

(5)

0∈B and 0∈Z+it follows thatr |nandr |B. Finally,Z+rr(A+B) = AB =Z+n impliesAB=Z+nr.

Corollary2.3. LetA,BZ+such thatA⊕B=Z+n. Assume that1∈A. Then there exists a unique finite sequenced0 = 1, d1, . . . , dk−1, dk = ninN withrj :=dj/dj−1Nandrj >1for1≤jksuch that

A=d0Z+r1d2Z+r3⊕ · · ·, (2.1)

B=d1Z+r

2d3Z+r

4⊕ · · ·. (2.2)

Proof. Since 1∈A, the proof of Proposition 2.1 yieldsA=Z+r1⊕r1Aand B =r1Bwherer1=min{b:bB, b=0}, andAB=Z+n

r1

. The proof is completed by applying Corollary 2.2 iteratively toAB=Z+n

r1

. Note that the uniqueness follows from the fact thatr1 = d1/d0 = min{b: bB, b =0}, r2=d2/d1= {a :aA, a =0}, etc.

Corollary2.4. Suppose thatA, BZ+such thatAB =Z+, and that Bis finite. ThenBis a direct summand ofZ+n for somenN.

Proof. By the same argument for Corollary 2.3Bmust have the form (2.1) or (2.2), depending on whether 1∈B. SoBmust be a direct summand ofZn+ for somenN.

Call a polynomial a 0−1polynomialif each of its coefficients is either 0 or 1. We associate each finiteAZ+with the following 0−1 polynomial

A(x):=

a∈A

xa,

called thecharacteristic polynomial of A. Clearly every 0−1 polynomial is the characteristic polynomial of the set of exponents corresponding to its non-zero coefficients. IfA,B,CZ+are finite, thenAB =Cif and only ifA(x)B(x) = C(x). We call a 0−1 polynomial c-irreducibleif A(x) = A1(x)A2(x)for any 0−1 polynomialsA1(x)≡1,A2(x)≡1. The following result was first stated in [1] (simple examples, however, show that Lemma 1 in [1] is false).

Theorem2.5.Letn >1. Then every factorization ofxx−n11into c-irreducible 0−1polynomials has the form

xn−1

x−1 =Fp1(x)Fp2(xp1)Fp3(xp1p2) . . . Fpk(xp1p2...pk−1),

(6)

whereFm(x) := xx−m11, allpj are primes (not necessarily distinct) andn = p1p2. . . pk.

Proof. This is a direct consequence of Corollary 2.3, by observing that Zp+1p2···pk =Zp+1p1Z+p2p1. . . pk−1Zpk.

Note that each term in the factorization is c-irreducible, because it contains a prime number of terms.

3. Tiling the Non-Negative Real Line

LetRbe a tile with finite and positive Lebesgue measure that tilesR+by translates ofT. In this case we will writeT = R+. In this section we derive the structure of tilesRthat tileR+by translation.

Theorem3.1. LetRwith finite positive Lebesgue measure. Suppose thattilesR+by translation. Then there exists an affine mapϕ(x)=ax+b such that

ϕ()=[0,1]+B

for some finite subsetBZ+with0∈B. Furthermore,Bis a direct summand ofZ+n for somenN. HencetilesRby translation.

Proof. In this proof, all set relations involving the tilewill be interpreted as up to measure zero sets.

Let TR such thatT = R+. We first examine the special case T = {0,1, t2, t3, . . .}wheretj >1 for allj ≥2. In this special case we prove that =[0,1]+B for someBZ+and 0∈B. LetTn =T ∩[0, n−1]

andn =∩[0, n]. We claim thatTnZ+andn=[0,1]+Bnfor some BnZ+, by induction onn.

Sincetj >1, we must have [0,1]⊆. So the claim is clearly true forn=1.

Assume that the claim is true for alln < k. We show that the claim is also true forn = k. We divide the proof into two cases:k−1k andk−1 = k. Suppose thatk−1k. Then(k−1, k] = ∅. Ifk = [0,1]+Bk for anyBkZ+, then (k−1, k](k−1, k]. Hence there exists atT such that(+t)(k−1, k]= ∅. Note thattTk−1, sotZ+. It follows that ∅(k−1−t, kt](k−1−t, kt],

contradicting the inductive hypothesis. Sok=[0,1]+Bkfor someBkZ+. The assumption thatk−1k now implies that Bk = Bk−1∪ {k−1}, so Tk = Tk−1. This proves the claim forn = k in the first case. Suppose that k−1 = k. Then k = [0,1] +Bk with Bk = Bk−1. Therefore Tk =

(7)

Tk−1∪ {k−1}. This completes the induction steps and proves the claim. So we have shown thatB,TZ+, and clearly 0∈B.

It remains to show thatBis a direct summand ofZ+n for somenN. Observe thatBT =Z+. ThereforeBis a direct summand ofZ+n for somenNby Corollary 2.4.

In general, suppose thattilesR+by translates ofT where the elements inT aret0< t1< t2<· · ·. Letϕ(x)= t1−t10(xt0)andtj =ϕ(tj). Then

ϕ()⊕ {0,1, t2, t3, . . .} =R+. Henceϕ()=[0,1]+Bfor someBZ+with 0∈B. 4. Proofs of Main Theorems

To prove our main theorems we first introduce some notation. For any finite setAZ we denote fA(ξ) := A

ei2πξ

where A(z) is the characteristic (Laurent) polynomial ofA. We will useZA to denote the set of zeros offA. For a subsetRwith positive and finite measure we will useZto denote the set of zeros ofχ(ξ).

Observe that for any finiteAZ, ξZA impliesξ +mZA for all mZ. SoZA = ZX for some finiteXR. If in additionAis a direct summand ofZ+n for somenN, thennZAZ.

Lemma4.1. LetAZ+be a direct summand of Z+n for somenN. Then there exists a direct summandAof Z+n with the same cardinality such that (4.1) AAnZA ∪ {0}, AAnZA∪ {0}.

Proof. We procced by induction onn. Forn=1,2 it is easy to check that the lemma holds. Assume that the lemma holds for alln < k, wherek ≥ 3.

We show that it holds forn=k.

Case 1.1∈A. ThenA=rA1for somer >1,r |kand direct summand A1ofZ+k

r. By the hypothesis there exists a direct summandA1ofZ+k

r such that (4.1) holds forA1,A1andn=k/r. NowfA(ξ)=fA1(rξ)yieldsZA= 1rZA1. Set A = A1. ClearlyA is a direct summand of Z+k because it is a direct summand ofZ+k

r, and we have

AA=r(A1A1)r· k

rZA1 ∪ {0} =kZA∪ {0}, and

AA=A1A1k

rZA1∪ {0} =kZA∪ {0}.

(8)

Case 2.1 ∈ A. Then A = Z+rrA1 for some r > 1, r | k and direct summandA1ofZ+k

r. By the hypothesis there exists a direct summandA1ofZ+k

r

such that (4.1) holds forA1,A1andn = k/r. SetA = A1krZ+r .Ais a direct summand ofZ+k becauseAB1=Z+k whereA1B1=Zkr. We have

fA(ξ)=fZ+r(ξ)fA1(rξ), fA(ξ)=fA1(ξ)fZ+r

k

rξ .

It follows fromZZ+r = 1rZ\Zthat (4.2) ZA= 1

r(ZZA1)\Z, ZA =ZA1r k

1

rZ\Z .

Letm=a+ krj andm=a+ krjbe two distinct elements inA, where a, aA1andj, jZ+r. Ifa=athen

mm = k

r(jj)k1

rZ\Z

kZA.

Ifa =athenaakrZA1. Henceaa+ krlkrZA1for alllZ. Since mmkZ, we have

mmkrZA1\kZkZA. HenceAAkZA∪ {0}.

Now letm =j+ra,m= j+rabe two distinct elements inA, where a, aA1 andj, jZ+r. If j = j thena = a, and by the hypothesis aakrZA1. Somm=r(aa)kZA1. Ifj =jthenjjrZ, so

mm=jj+r(aa)Z\rZ= r k

1

rZ\Z

ZA. HenceAAZA.

We have now completed the induction steps and proven the lemma.

We will call two direct summandA andA satisfying (4.1) a conjugate pair, andA aconjugateofA. The proof of Lemma 4.1 leads to an explicit construction of conjugate pairs. LetAZ+be a direct summand ofZ+n. Then by Corollary 2.3 there exists a unique sequence r0, r1, . . . , r2k+1 in N with 2k+1

j=0 rj =n,rj >1 for 0< j <2k+1 andr0, r2k+1≥1, such that (4.3) A=k

j=0

d2jZ+r

2j+1, where dm:=m

j=0

rj.

(9)

Define the mapϑnon the set of direct summand ofZ+n by (4.4) ϑn(A)=k

j=0

n d2j+1

Z+r

2j+1.

Thenϑn(A)is exactly the conjugate setAconstructed inductively in the proof of Lemma 4.1.

Lemma4.2. Suppose thatAZ+is a direct summand of Z+n. ThenAand ϑn(A)form a conjugate pair, andϑnn(A))=A. Furthermore, ifA, BZ+ such thatAB =Z+n, thenϑn(A)ϑn(B)=Z+n

Proof. The proof of Lemma 4.1 already implies thatA, ϑn(A)form an conjugate pair. It is easy to see that ϑnn(A)) = A by directly applying (4.3) and (4.4). Now, suppose thatAis given by (4.3) andBZ+satisfies AB =Z+n. Then there are several cases:r0=1 orr0>1, andr2k+1=1 or r2k+1>1. Ifr0=1,r2k+1>1 then

(4.5) B =

k+1

j=1

d2j−1Z+r2j, where r2k+2:=1.

So

(4.6) ϑn(B)=

k+1

j=1

n d2jZ+r

2j.

It is now straightforward to check from (4.4) and (4.6) thatϑn(A)ϑn(B)= Z+n. Other cases can be checked similarly.

Definition4.3. Let,TRbe strongly periodic sets. We say thatT is adualofif there exist a non-zeroαRandA, BZ+withAB=Zn+ for somenNsuch that

=α(AnZ), T = 1

ϑn(B)nZ .

By Lemma 4.2 ifT is a dual ofthenis a dual ofT.

Lemma4.4. LetRsatisfyµ() = nN. Suppose that= LZ whereLis a finite subset ofRsuch thatZ∪ {0}. Then(, )is a spectral pair if and only if|L| =n.

Proof. See [10], Theorem 1, or [8], Theorem 2.1.

(10)

We shall establish the following result, which is a stronger version of our main theorem.

Theorem4.5. Suppose thatRhas positive and finite Lebesgue meas- ure. Let,TRbe strongly periodic sets such thatT is a dual of. Then (, )is a spectral pair if and only iftilesRby translates ofT.

Proof. Without loss of generality we may assume that = 1n(AnZ) andT =ϑn(B)nZfor somenNandA, BZ+withAB=Z+n. (⇐) The set=⊕ϑn(B)tilesRby translates ofnZ, so it is a fundamental domain of the latticenZ. Hence

Z =ZZϑn(B)⊇ 1 nZ\ {0}.

Sinceϑn(A)ϑn(B)=Z+n we have

Zϑn(A)Zϑn(B)=ZZ+n = 1 nZ\Z.

Furthermore,Zϑn(A)Zϑn(B)= ∅becausefϑn(A)(ξ)fϑn(B)(ξ)has no multiple roots. Hence

ZZϑn(A)Z\ {0}.

Now, for any distinctλ, λwe haveλλ= n1k+jfor somekAA, jZ. Ifk=0 thenknZϑn(A)by (4.1), which implies thatλλ= kn+jZϑn(A)Z. Otherwiseλλ= jZ\ {0} ⊆Z. By Lemma 4.4(, ) is a spectral pair.

(⇒) Suppose that (, )is a spectral pair. For any x ∈ [0,1)let Dx := (Z+x). It follows from [10], Theorem 2, that

(4.7) |Dx| = |A|, DxDxnZA∪ {0}

for almost allx∈[0,1). We show that(Dxx)+ϑn(B)is a complete residue system (modn) for every Dx satisfying (4.7). Note thatϑn(B)ϑn(B)nZB∪ {0}, and observe thatkmmodnfor anyknZA andmnZB. Thus for anyk1, k2Dxx andm1, m2ϑn(B)we must havek1k2m2m1modnunlessk1=k2andm1=m2. Hencek1+m1k2+m2modn. Since|Dxx| · |ϑn(B)| =nit follows that(Dxx)+ϑn(B)=(Dxx)ϑn(B)containsndistinct residue classesmodn, and hence is a complete residue systemmodn. Therefore

Dx+T =DxT =x+Z

for almost allx∈[0,1). This implies thattilesRby translates ofT.

(11)

Theorem 1.1 is a simple consequence of Theorem 3.1 and Theorem 4.5.

Acknowledgement.The first author would like to thank Palle E. T. Jor- gensen for many useful conversations about spectral pairs.

REFERENCES

1. Carlitz and Moser,On some special factorizations of(1xn)/(1x), Canad. Math. Bull.

9 (1966), 421–426.

2. de Bruijn, N. G.,On number systems, Nieuw Arch. Wisk. (4) 4 (1956), 15–17.

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

4. Jorgensen, P. E. T., and Pedersen, S.,Spectral theory for Borel sets inRnof finite measure, J.

Funct. Anal. 107 (1992), 72–104.

5. Jorgensen, P. E. T., and Pedersen, S.,Harmonic analysis and fractal limit-measures induced by representations of a certainC-algebra, J. Funct. Anal. 125 (1994), 90–110.

6. Jorgensen, P. E. T., and Pedersen, S.,Orthogonal harmonic analysis of fractal measures, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 35–42.

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

8. Lagarias, J. C. and Wang, Y.,Spectral sets and factorizations of finite abelian groups, J. Funct.

Anal. 145 (1997), 73–98.

9. Odlyzko, A. M.,Non-negative digit sets in positional number systems, Proc. London Math.

Soc. 37 (1978), 213–229.

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

STEEN PEDERSEN

DEPARTMENT OF MATHEMATICS WRIGHT STATE UNIVERSITY DAYTON OH 45435 USA

E-mail:steen@math.wright.edu

YANG WANG

DEPARTMENT OF MATHEMATICS GEORGIA INSTITUTE OF TECHNOLOGY ATLANTA GA 30332

USA

E-mail:wang@math.gatech.edu

Referencer

RELATEREDE DOKUMENTER

By a specification we shall here (a bit narrowly) mean a narrated and a formal description of a domain, a narrated and a formal prescription of a (set of) requirements, or a

– When the target class of an associations is not shown in the diagram – With datatypes / Value objects.. ∗ Datatypes consists of a set of values and set of operations on

Having observed the outcome and features in a set of objects (a training set of data) we want to build a model that will allow us to predcit the outcome of

“Given a large data set select a subset of its elements that best represent the original set.”..  This reduction is usually driven by the requirements of a particular application

We show that the set of fixed-point combinators forms a recursively- enumerable subset of a larger set of terms that is (A) not recursively enumerable, and (B) the terms of which

In the CCS-setting of Busi and Gorrieri [BG95], choice is replaced by a lower-level notion of conflict that is based on a set of conflict names (and contrasting conames) together

This dissertation presents the design, development and evaluation of the Social Set Visualizer, an innovative Visual Analytics software tool, that expands upon a novel

The analysis draws on historical materialism (HM) understood as a research program based on a set of interlinked concepts and propositions that are open to development and