The distribution of spacings between quadratic residues

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEEN

QUADRATICRESIDUES

¨KURLBERGANDZEEV´RUDNICKPAR

Abstract.Westudythedistributionofspacingsbetweensquaresmoduloq,whereqissquare-freeandhighlycomposite,inthelimit

asthenumberofprimefactorsofqgoestoin nity.Weshowthat

allcorrelationfunctionsarePoissonian,whichamongotherthings,

impliesthatthespacingsbetweennearestneighbors,normalizedto

haveunitmean,haveanexponentialdistribution.

Date:Dec14,1998.

SupportedinpartbyagrantfromtheIsraelScienceFoundation.Inaddition,the rstauthorwaspartiallysupportedbytheECTMRnetwork”AlgebraicLieRepresentations”,EC-contractnoERBFMRX-CT97-0100.

1

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

2

1.Introduction

Ourgoalinthispaperistostudythedistributionofspacings(orgaps)betweensquaresinZ/qZ,asq→∞.Inthecasethatqisprime,atheoremofDavenport[3,4,11,18]showsthattheprobabilityoftwoconsecutivequadraticresiduesmoduloaprimeqbeingspacedhunitsapartis2 h,asq→∞.Forourpurposes,wemayinterpretthisresultassayingthatwhenwenormalizethespacingstohaveunitmean,thenthedistributionofspacingasq→∞alongprimesisgivenby

∞ hP(s)=2 hδ(s )2h=1

thatis,asumofpointmassesathalf-integerswithexponentiallyde-creasingweights.

Inthispaperwestudythespacingdistributionofsquaresmoduloqwhenqissquare-freeandhighlycomposite,thatisthelimitingdistribu-tionofspacingsbetweenthesquaresmoduloqasthenumberofprimedivisors,ω(q),tendstoin nity.Foroddsquare-freeqthenumberNqofsquaresmoduloqequals

p+1Nq=2p|q

Thisisbecauseifpisanoddprime,thenumberofsquaresmodulopis(p+1)/2andforqsquare-free,xisasquaremoduloqifandonlyifxisasquaremodulopforallprimespdividingq.Thusforoddq,themeanspacingsq=q/Nequals

2ω(q)2ω(q)

sq==σ 1(q)p|q(1+1/p)

Forq=2q evenandsquare-free,itiseasilyseenthatsq=sq .Itfollowsthatsq→∞asω(q)→∞,unlikethecaseofprimeqwherethemeanspacingisessentiallyconstant.Thus,unlikeintheprimecasewherethelevelspacingdistributionwasforcedtobesupportedonalattice,inthehighlycompositecasethereisana-priorichanceofgettingacontinuousdistribution.

ArelevantstatisticalmodelforthedistributionofspacingsisgivenbylookingatrandompointsintheunitintervalR/Z.Forindependent,uniformlydistributednumbersinR/Z,thespacingstatisticsaresaidtobePoissonian.ThedistributionP(s)ofspacingsbetweenconsecutivepointswillbethatofaPoissonarrivalprocess,i.e.P(s)=e s(see

[6]).Moreover,thejointdistributionofkconsecutivespacingsistheproductofkindependentexponentialrandomvariables.

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES3Itiswellknown[15]thatthespacingstatisticsofthesuperpositionofseveralindependentspectraconvergestothePoissoncase-thespac-ingsstatisticsofuncorrelatedlevels.Thustheheuristicthat“primesareindependent”togetherwithDavenport’sresultindicatesthatthespac-ingstatisticsofthesquaresmoduloqshouldinthelimitasω(q)→∞bePoissonian,i.e.,thatinsomesensesquaresmoduloqbehavesasrandomnumbers.Itisourpurposetocon rmthisexpectation.

Inordertostudythelevelspacings,weproceedbystudyingther-levelcorrelationfunctions.ThesemeasureclusteringpropertiesofasequenceinR/Zonascaleofthemeanspacing.Theirde nitionandtheirapplicationtocomputingvariouslocalspacingsstatisticsarerecalledinappendixA.Inourcase,theseturnouttobegivenbybythefollowing:Forr≥2andaboundedconvexsetC Rr 1,letRr(C,q)=1#{xidistinctsquaresmodq:(x1 x2,...xr 1 xr)∈sC}.Nq

Thisisimmediatelytransformedinto

1(1.1)Rr(C,q)=N(h,q)Nqr 1h∈sC∩Z

whereN(h,q)isthenumberofsolutionsofthesystemofcongru-encesyi+1 yi=himodqwithy1,y2,...yrsquaresmoduloqandh=(h1,...hr 1)∈Zr 1.

TocomputethecorrelationsfordistinctxiweconsideronlysetsCwhicha-priorionlycontainvectors(xi xi+1)withdistinctcoordinates. 1Todothis,wede ne“roots”σijonRr 1fori<jbyσij(h)=j

k=ihk.

Thehyper-planes{σij=0} Rr 1arecalled“walls”,and(xi xi+1)doesnotlieinanyofthewallsifandonlyifallcoordinatesxiaredistinct.

OurmainresultshowsthatifCdoesnotintersectanywallthenRr(C,q)→vol(C)foranysequenceofsquare-freeqwithω(q)→∞:Theorem1.Letqbesquare-free,r≥2andC Rr 1aboundedconvexsetwhichdoesnotintersectanyofthewalls.Thenther-levelcorrelationfunctionsatis es

Rr(C,q)=vol(C)+O(s 1/2+ )

forall >0,wheresisthemeanspacing.

ThistheoremimpliesthatallspacingstatisticsarePoissonian(seeAppendixA).Forinstance,ifwedenotebys1,...,sN 1thenormalizeddi erencesbetweenneighboringsquares,thenwehaveass→∞

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

4¨KURLBERGANDZEEV´RUDNICKPAR

Theorem2.Forqsquare-free,thelimitinglevelspacingdistributionofthesquaresmoduloqisgivenbyP(t)=exp( t)asω(q)→∞.Moreover,underthesamecondition,foranyk ≥1thelimitingjointdistributionof(sn,sn+1,...,sn+k)isaproductk

i=0exp( ti)ofk+1

independentexponentialvariables.

Thereareonlyafewknowncaseswherethecompletespacingdis-tributioncanbeprovedtobePoissonianasinourcase.AnotableexampleisHooley’sresults[7,8,9,10]thatthespacingsbetweenele-mentsco-primetoqarePoissonianasthemeanspacingq/φ(q)→∞.AmuchmorerecentresultisduetoCobeliandZaharescu[2]whoshowthatthespacingsbetweenprimitiverootsmoduloaprimeparePoissonianprovidedthemeanspacingp/φ(p 1)→∞.

Theresultsofthispaperarerelatedtoworkonthelevelspacingdistributionofthefractionalparts{αn2}(αirrational)byRudnick,SarnakandZaharescu[16,17].Inparticular,in[17]anattempttostudythatproblemismadebyreplacingαwitharationalapproxi-mationb/q,andthisleadstostudythespacingsofthesequencebn2modq,1≤n≤NforNasmallpowerofq.Theavailablesitesareexactlythesetofsquaresmoduloq,andhenceourinterestintheproblem.

In[17],itisshownthatinorderforallthecorrelationfunctionsofthesequence{αn2}tohavePoissonbehavior,itisnecessarytoassumethattherationalapproximantsb/qhavedenominatorqwhichisclosetosquare-free.Henceourinterestinthesquare-freecase.ForarbitraryqitisstilltruethatallcorrelationsarePoissonian,buttherearesigni canttechnicalcomplicationstoovercomeinprovingthis,see

[13].

Webelievethatthemethodsdevelopedinthispapershouldbeusefulinstudyingsimilarproblems,forinstancethespacingdistributionofcubesmoduloq,asthenumberofprimefactorsofqthatarecongruentto1modulo3tendstoin nity.(Theconditionmodulo3isnecessaryinorderforthemeanspacingtogotoin nity.)

Contentsofthepaper:Webeginwithasectionsketchingtheargu-mentforTheorem1inthecaseofthepaircorrelationfunction.Thissectioncanbeusedasaguidetotherestofthepaper.

Insection3we rstreducetheproblemtothecasethatqisodd.Theninsection4weanalyzethebehaviorofN(h,p)wherepisprime.Squaresthataredistinctmoduloqarenotnecessarilydistinctmodulop;wedenotebyreff(h)inganinclusion-exclusionargumentwe

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES5writereff(h)asalinearcombinationofcharacteristicfunctionsofcer-tainhyper-planesoverZ/pZ.Next,insection5weusethemultiplica-tivepropertiesofthecountingfunctionsN(h,q)toderiveanexpressionforRr(C,q)asasumoverdivisorscofqandlatticesLarisingfromintersectionsofhyper-planesmodulopfordi erentp’s(proposition6).Insection6weshowthatthemaintermofthesumconsistsofthosetermsforwhichtheproductofcandthediscriminantofLaresmallwithrespecttos,andanerrortermcorrespondingtotermswheretheproductislarge.Insection7weevaluatethemaintermandshowthatitgivesusexactlyvol(C),thusgivingusourmainresult.

InappendixAweexplainhowtouseTheorem1toderiveresultssuchasTheorem2,thatthelevelspacingsarePoissonianaswell.Appen-dixBexplainssomebackgroundoncountinglatticepointsinconvexsets.InappendixCweestimatethenumberofdivisorsofqthataresmallerthana xedpowerofthemeanspacings.

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

6¨KURLBERGANDZEEV´RUDNICKPAR

2.Thepaircorrelation-asketch

Inordertoexplaintheproofofourmaintheorem1,wegiveanoverviewoftheargumentinthespecialcaseofthepaircorrelationfunction.

Letqbeanodd,square-freenumberwithω(q)primefactors,andIaninterval,notcontainingtheorigin.De neasintheintroductionthepaircorrelationfunction

1 R2(I,q)=N(h,q)Nh∈sI∩Z

ω(q)whereNisthenumberofsquaresmoduloq,s=q/N=2/σ 1(q) 1istheirmeanspacing,σ 1(q)=p|q(1+),andN(h,q)isthenumber

ofsolutionsinsquaresmoduloqoftheequation

y1 y2=hmodq

WewillsketchaproofthatR2(I,q)→|I|asω(q)→∞(|I|beingthelengthoftheinterval).InfactwehavethemorepreciseresultTheorem3.Forqodd,square-freewehaveforall >0

R2(I,q)=|I|+O(s 1+ )

Herearethemainstepsintheargument:

Step1: BytheChineseRemainderTheorem,N(h,q)=p|qN(h,p)isaproductoverprimesdividingq.Byelementaryconsiderations,oneseesthat

p+a(h,p)(2.1)N(h,p)= (h,p)4

witha(h,p)=O(1)and 0p|h (h,p)=1+δ(h,p),δ(h,p)=1p|h

q (h,q) a(h,c)(2.2)N(h,q)=4ω(q)cc|q witha(h,c):=p|ca(h,p) c and (h,q)=p|q (h,p).

Step2:

Wedecompose (h,q)= (h,c) (h,q)andrewrite (h,q)ascc q (h,)=(1+δ(h,p))=δ(h,g)cqqp|g|Fromthisweseethat

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES7with 0g|hδ(h,g)=1g|h

Substitutingthisintotheexpression(2.2)forN(h,q)andinsertingtheresultintotheformulaforR2(I,q),weget

1 1(2.3)R2(I,q)=a(h,c) (h,c)σ 1(q)2ω(q)cqh∈sI∩gZc|qg|Step3:

Wepartitionthesumintotwoparts,oneoverthepairsg,cwithgc<sandtheleftoverpartoverpairswithgc≥s.Wewillshowthisleftoverpartisnegligible(infactO(s 1+ )):We rstusea(h,c) (h,c) c andthefactthatinorderfortheinnersumoverhtobenonempty,weneedg s(recallthatIdoesnotcontaintheorigin!)togetthatthesumoverpairswithcg>sisboundedby

s 1+ 1+ 1+ 1+ sc#(sI∩gZ) sc

qqgc|qg|g scg>sc|q

s

d|q

d>sd 1+ g|dg sg|g scg>s1

NowweuseLemma18whichshowsthatthenumberofdivisorsg<sofqisamostO(s )andLemma19toboundtheaboveby

sd 1+ s 1+

d|q

d>s

aspromised.

Step4:

Foreachpairofc,gwithcg<s,we rsttreattheinnersumover

|I|+O(1)subintervalsh∈sI∩gZ.Webreakitupintosumsovers

[y,y+cg)∩gZplusaleftovertermofsizeatmostc1+ .Foreachsubinterval,weuseperiodicityofa(h,c) (h,c)underh→h+cto nd

h∈[y,y+cg)∩gZa(h,c) (h,c)=c h1=1a(gh1,c) (gh1,c)

Becauseqissquare-free,andgdividesq/c,wehavethatg,carecoprime.Thereforewecanchangevariablesh=gh1togetthatthis

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

8¨KURLBERGANDZEEV´RUDNICKPAR

lastsumequals

hmodca(h,c) (h,c)= p|chmodpa(h,p) (h,p)

Weevaluatethesumhmodpa(h,p) (h,p)bynotingthatsum-ming(2.1)overhmodp,thesumoftheLHSissimplythenumberofallpairsofsquaresmodulop,namely(p+1)2/4.Thisgives a(h,p) (h,p)=p+1

hmodp

Thustheinnersumoverh∈sI∩gZequals s|I|+O(1)(p+1)+O(c1+ )a(h,c) (h,c)=gch∈sI∩gZp|c

=s|I|σ 1(c)+O(c1+ )g

Step5:

Insertingthisintotheexpression(2.3)forR2(I,q)gives

1 s|I|1R2(I,q)=ω(q)σ 1(c)+O(s 1+ )2σ 1(q)cqgc|qg|:gc<s

Nowweextendthesumtoallpairsg,c,to ndthatuptoanerrorofO(s 1+ )wehave

σ 1(c) 11R2(I,q)～|I|σ 1(q)2cqgc|q

σ 1(c)q1σ()=|I| 12σ 1(q)ccc|qg|1 1=|I|=|I|σ 1(q)cc|qwhichiswhatweneedtoproveourtheorem .Inthefollowingsections,wewillrepeatthesestepswithfulldetailsforthehighercorrelationfunctions,whereseveraltechnicalcomplica-tionsarise.

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES9

3.Reductiontooddq

We rstshowthatinTheorem1itsu cestoconsideronlythecaseofqodd:Supposethatq=2q withq oddandsquare-free.Werecallthat 1(3.1)Rr(C,q)=N(h,q)Nqr 1h∈sC∩Z

whereN(h,q)isthenumberofsolutionsofthesystemyi+1 yi=hiwherey1,y2,...yraresquaresmoduloqandh=(h1,...hr 1)∈(Z/qZ)r 1.

BytheChineseRemainderTheorem,thenumberNqofsquaresmod-uloqistheproduct

Nq=N2Nq =2Nq

Thereforethemeanspacingsq:=q/Nqisgivenby

2q q

(3.2)sq===sq 2Nq Nq

Moreover,againbytheChineseRemainderTheorem,

N(h,q)=N(h,2)N(h,q )

andsinceallresiduesmodulo2aresquares,wehaveN(h,2)=2.Thuswe nd

N(h,q)2N(h,q )N(h,q )(3.3)==Nq2Nq Nq

Inserting(3.2),(3.3)into(3.1),we ndthat

Rr(C,q)=Rr(C,q )

Thisshowsthatitsu cestoproveTheorem1forqodd,whichweassumeisthecaseinthesequel.

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

10¨KURLBERGANDZEEV´RUDNICKPAR

4.Theprimecase

Letp>2beaprime.Forh=(h1,...hr 1)∈(Z/pZ)r 1,wede neNr(h,p)tobethenumberofsolutionsinsquaresyimodp(includingyi=0)ofthesystem

(4.1)yi yi+1=himodp,1≤i≤r 1

Thisnumberdependscruciallyonthenumberofdistinctyj.Foreachh=(h1,...,hr 1),wede nereff(h)tobethenumberofdistinctyj(notnecessarilysquares)satisfyingthesystem(4.1).Sincethesolu-tionsofthehomogeneoussystemyi yi+1=0modparespannedby(1,...,1),reff(h)iswell-de ned(independentoftheparticularsolu-tionyof(4.1)).

Wede nerootsσij(h),1≤i<j≤rby

(4.2)σij(h)=j 1

k=ihk

1sothatσi,i+1(h)=hi,σij=j

k=iσk,k+1.Thesolutionsof(4.1)areall

distinctofandonlyifσij(h)=0,foralli<j,since

yi yj=j 1

k=iyk yk+1=j 1 k=ihk=σij(h)

Proposition4.Letreff(h)bethenumberofdistinctyiinasolutionof(4.1).Then

(4.3)

witha(h,p) rp1/2.

Proof.Thecasereff(h)=1ispreciselywhenh=0andallyiareequal:y1=y2=···=yr.Inthiscasethenumberofsolutionsisthenumberofsquaresmodulop,namely(p+1)/2,whichisofthedesiredform.Wethusassumefromnowthatreff(h)>1.

We rstreducethesystem(4.1)toasystemofreff 1equationsinreffvariables:Ifreff(h)isthenumberofdistinctyiinasolutionof(4.1)(independentofy!),thenwecaneliminatesomeoftheequations.Renumberthevariablessothaty1,...yreffarethedistinctcoordinatesofasolution,andforallj≥1,yreff+jequalsoneofthese,thenthesystem(4.1)isequivalenttothereducedsystem

(4.4)yi yi+1=h imodp,1≤i≤reff 1Nr(h,p)=p+a(h,p)2eff

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES11(wheretheh iarerenumberedhjtogivethatthe rstreffcoordinatesaredistinct).Soweneedto ndthenumberofsolutionofthereducedsystem(4.4).

We rsteliminatethosesolutionswhereatleastoneoftheyjiszero.Inthiscase,sincethesystem(4.4)(consideredasalinearsystem)hasrankreff 1inreffvariables,specifyinganyoneofthevariablesdeterminesalltheothers,hencethenumberofsolutionswithsomecoordinatezeroisatmostreff.Thusweneedonlycountsolutionswhereallcoordinatesyiarenonzero.

Toeverysuchsolutioninsquaresyi=0modp,writeyi=x2imodpwithxi=0modp.Therearepreciselytwosuchsolutions,namely±ximodp.Thusthenumberofpossiblexicorrespondingtoagivensolutionyof(4.4)isprecisely2reff,andthenumberofnonzerosolutionsofthereducedsystem(4.4)withyisquaresmodulopisexactly1/2refftimesthenumberofsolutionsofthesystem

(4.5)2 x2i xi+1=himodp,1≤i≤reff 1

withxi=0modp.Byaddingbackatmostrsolutionswecanremovetheconditionxi=0,andthenwe ndthat

1(4.6)Nr(h,p)=effn(h ,p)+Or(1)2

wheren(h ,p)isthenumberofsolutionsof

2 x2i xi+1=himodp1≤i≤reff(h) 1

Thisisjustthenumberofsolutions(t,x1,...,xreff)ofthesystem

(4.7)x21=t b1,2x22=t b2,...,xreff=t breff

withb1=0,b2=h 1,b3=h 1+h 2,...,breff(h)=h 1+h 2+···+h reff 1andingeneralbk=σ1k(h ).Notethatthebiaredistinct-thisisequivalenttotherequirementthatthesolutionsofthereducedsystem(4.4)bedistinct.Onecannowusethe“RiemannHypothesisforcurves”[21](seeSchmidt’sbook[19],ChapterII,Theorem5AandCorollary5Bforthecaseb1= 1,b2= 2,...br= r),to nd√(4.8)|n(h ,p) p| reff2reffInaddition,|N(h,p) n(h ,p)/2reff|≤randso

N(h,p)=

withp+a(h,p)2reff

√√a(h,p) 2reff(reff+r) rThisprovesProposition4.

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

12¨KURLBERGANDZEEV´RUDNICKPAR

4.1.Aformulaforreff(h).Ournextorderofbusinessistogiveaformulaforreff(h).Webeginwithsomecombinatorialbackground:Asetpartitionoftheset{1,2,...,r}isacollectionofdisjointsubsets=[F1,...,Ft],Fi {1,2,...,r},whoseunionisallof{1,2,...,r}.Weset||=t,thenumberofsubsetsin.

ToeachsetpartitionweassociateasubsetVFofa ner-spaceV=Arbysetting

(4.9)VF={s∈Ar:si=sjifi,jareinsomeFk}

HF={h∈Ar 1:σij(h)=0ifi,jareinsomeFk}Correspondingly,inH=Ar 1wehaveasubspace(4.10)

Underthemapπ:V→Htakings=(si)→(si si+1),wehaveVF=π 1HF.

Thereisapartialorderingonthecollectionofallset-partitionsof{1,...,r}withF GifandonlyifeveryFiiscontainedinsomeGj.Forexample,=[{1,2,...,r}]isthemaximalelementofthispar-tialordering,with|=1andHO=(0).Theminimalelementis=[{1},{2},...,{r}]with|=rHr=Ar 1.

Thepartialorderingonset-partitionsinclusion-reversingonsub-spaces: V V H H.

TheregularpartofVis

×V={s∈VF:si=sjifi,jarenotinsomeFk}

××andlikewisewede neH.ThenH=HO=(0),andeveryhbelongs

×toauniqueHFforsome.Wethushave

×H=Handlikewise

HF= F G×HG

Wecannowgiveaformulaforreff(h):

(4.11)reff(h)=dimVF=dimHF+1=||

×whereistheuniqueset-partitionsuchthath∈HF.

Wecanwritethisasfollows:De ne ×1h∈HF1h∈HF×(4.12)δF(h)=,δF(h)=0otherwise0otherwise

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES13Then

(4.13)

Similarly

(4.14) (h,p):=2reff(h)= F×dim(VF)δF(h)r reff(h)= F×2codim(VF)δF(h)

Itwillbeconvenienttoexpressthisintermsofthecharacteristicfunc-tionδofthesubspacesH.ForthisweuseM¨obiusinversion.Sincethecollectionofallset-partitionsof{1,...,r}isapartially-orderedset,ithasaM¨obiusfunctionµ(whichistheuniquefunctionsothatforanyfunctionsψ,φonset-partitionssatisfying (4.15)φ(F)=ψ(G)

F G

wehave

(4.16)ψ()= F Gµ(,φAnexplicitformofµ(canbefoundin[14],§25.Wewillnothaveanyuseforit. ×Inourcase,clearlywehaveH=F GHGsothat

×(4.17)δF=δF G

Thuswehave

(4.18)×δF= F Gµ()δG

Thisgivesustheformulafor (h,p)=2r reff(h):From(4.14)and(4.18)we nd

λ(δ(h)(4.19) (h,p)=

G

with

(4.20)λ()= µ(,)2codimVF

ForuseinSection7,weneedtoknowthesumoftheproductof (h,p)withtheerrorterma(h,p)in(4.3)overallvectorsh:

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

14¨KURLBERGANDZEEV´RUDNICKPAR

Lemma5.

hmodpa(h,p) (h,p)=(p+1) prr Gλ()p codimHG

Proof.Wehavebyde nition

N(h,p)=

sothatp+a(h,p) (h,p)2r

a(h,p) (h,p)=2rN(h,p) p (h,p)

Nowsumoverallhmodp:ThesumofN(h,p)isjustthetotalnumber

)r.Tosum (h,p)overofr-tuplesofsquaresmodulop,namely(p+1

h,weuse(4.19):SincethesumoverallhofδG(h)isjustthenumber

ofvectorsinthesubspaceHG,namelypdimHG=pr 1 codimHG,we nd ra(h,p) (h,p)=(p+1) p (h,p)

hmodph

=(p+1)r pr

asrequired. Gmodpλ(G)p codimHG

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES15

5.AformulaforRr(C,q)

InordertoproveTheorem1,wegiveanexpression(5.2)forther-levelcorrelationRr(C,q)whichinvolvessummingovertheintersectionofthedilatedsetsCwithvariouslattices.

Recallthatforeachset-partitionof{1,...,r}weassociatedasubspaceH (Z/pZ)r 1.Nowgivenadivisordmodq,letG= p|dG(p),beatupleofsuchset-partitions,oneforeachprimepdividingd(recall thatq,henced,issquare-free).LetL(G) Zr 1bethepre-imageofp|dH(p)underthereductionmapZr 1→p|d(Z/pZ)r 1 (Z/dZ)r 1.L(G)isalattice,whosediscriminant(thatis,theindexinZr 1)is codim(H)G(p)disc(G)=p

p|d

Thesupportsupp(G)ofL(G)istheproductofallprimespforwhichH(p)=(Z/pZ)r 1:

psupp(G)=

p:G(p)=[{1},...,{r 1}]

Sincecodim(HG(p))≤r 1,weget

supp(G)|disc(G)|supp(G)r 1

Weset

λ(G)=

p|dλ(G(p))

whereλ(isgivenby(4.20).Wealsosetforadivisorc|q

a(h,c):=a(h,p), (h,c):= (h,p)

p|cp|c

NotethatbyProposition4

(5.1)a(h,c) c1/2+ , (h,c) c

forall >0.

OurformulaforRr(C,q)is

Proposition6.Ther-levelcorrelationfunctionisgivenby

s 1 (5.2)Rr(C,q)=rω(q)λ(G)a(h,c) (h,c)2cqc|qsupp(G)|h∈sC∩L(G)

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

16¨KURLBERGANDZEEV´RUDNICKPAR

Proof.Wehavethat

1Rr(C,q)=N h∈sC∩Zr 1N(h,q)

BytheChineseRemainderTheorem,

N(h,q)=N(h,p)

p|q

Werewriteformula(4.3)intheform

N(h,p)=

where

(h,p)=2r reff(h)

Thuswe nd

(5.3)p+a(h,p) (h,p)2r

q q (h,q) a(h,c)qa(h,c) (h,c)=)N(h,q)= (h,2rω(q)c2rω(q)ccc|qc|q

Inserting(5.3)wegetaformulaforRr(C,q):RecallingthatN=q/s,

s 1 q(5.4)Rr(C,q)=rω(q) (h,)a(h,c) (h,c)2ch∈sCcc|qq)=Nextweusetheexpression(4.19)for (h,p)towrite (h, p|q/c (h,p)intheform

q(p)(p)(5.5) (h,)=λ()δ(h,)=λ(G)δ(h,G)cq(p)(p)p|GG= p|qG(p),oneforwherethesumisoveralltuplesofset-partitionsG= p|q

eachprimedividingq,andweputforeachsuchtupleG λ(G):=λ((p))

p|q

and

δ(h,G):=

p|q

1h∈HG(p)(p)δ(h,)=0otherwisemodpforallp|q

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES17ThisisthecharacteristicfunctionofthelatticeL(G)whosesupportsupp(G)dividesq/c.ThuswegetthedesiredexpressionforRr(C,q)

s 1 Rr(C,q)=rω(q)λ(G)a(h,c) (h,c)2cqc|qsupp(G)|h∈sC∩L(G)

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

18¨KURLBERGANDZEEV´RUDNICKPAR

6.Evaluatingther-levelcorrelations

InordertoestimatethecorrelationsusingProposition6,wepartitionthesum(5.2)intotwoparts:the rstconsistingofpairscandGsuchthatcdisc(G)<s,andthesecondofthepairsforwhichcdisc(G)>s.Wewillshowthatthe rstpartgivesthemaintermandthesecondisnegligible.

6.1.Thecasecdisc(G)>s.Weusea(h,c) c1/2+ (5.1),and (h,c) c toseethatthistermisboundedby

s 1 |λ(G)|#{sC∩L(G)}c1/2+ (6.1)rω(q)2cqc|qsupp(G)|cdisc(G)>s

BytheLipschitzprinciple(Lemma16),

#{sC∩L(G)} vol(sC)+sr 2

disc(G)

andsincevol(sC)=sr 1vol(C),we ndthat

(6.2)sr 1

#{sC∩L(G)} +sr 2

disc(G)

Moreover,inorderthatsC∩L(G)= ,wewillseethatweneedsupp(G) sr(r 1)/2,sinceCdoesnotintersectthewalls.Thisisaconsequenceofthefollowingobservation:LetC Rr 1beaboundedconvexset.De ne

r 1 diam1(C)=max{|xk|:x∈C}

k=1

Notethatdiam1scaleslinearly:diam1(sC)=sdiam1(C)foralls>0.Lemma7.Ifsupp(G)>diam1(sC)r(r 1)/2thensC∩L(G)iscontainedinthewalls{h∈Rr 1:σij(h)=0forsomei<j}.

Proof.Letdij(G)betheproductoftheprimespsuchthatσijvanishesonH(p),i.e.sothat

σij(x)=0modpforallx∈L(G)

Thendij(G)|supp(G)andmoreoverweclaimthat:

disc(G)|dij(G)

i<j

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES19Itisenoughtocheckthisoneprimeatatimeandisequivalenttosayingthat

codim(HG(p))≤#{i<j:σij=0onHG(p)}

whichfollowssinceH(p)isgivenbyvanishingofsomeoftheσij.Nownotethatifsupp(G)> dr(r 1)/2thenforsomei<j,dij(G)>dbecausesupp(G)≤disc(G)≤i<jdij(G)andthelastproductconsistsofr(r 1)/2factors.Ifwetaked=diam1(sC)=sdiam1(C),thenonehasdij(G)>diam1(sC)forsomei<j.Howeverσij(h)=0moddij(G)andsoσij(h)=mdij(G)forsomeintegerm.Ifm=0thenhliesinawall.Ifm=0thenbeinganinteger,|m|≥1andso

|σij(h)|≥dij(G)>diam1(sC)

Since

σij(h)=|

we ndthat

r 1

k=ij 1 k=ij 1 k=ir 1 k=ihk|≤|hk|≤|hk||hk|>diam1(sC)

Thush∈sCbyde nitionofdiam1(sC).

ByLemma7,togetherwith|λ(G)| supp(G) ,(6.1)isboundedby

r 1 s 1/2+ s r 2(6.3)csupp(G)+s2rω(q)disc(G)qc|qsupp(G)|cdisc(G)>s

supp(G) sr(r 1)/2

Wesplitthesumintotwopartsanduses<2ω(q)tobound(6.3)bythesumof

s1 1/2+ csupp(G) (6.4)sdisc(G)qc|qsupp(G)|cdisc(G)>s

and

(6.5)1 1/2+ csc|q supp(G)|q

cdisc(G)>s

supp(G) sr(r 1)/2supp(G)

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

20¨KURLBERGANDZEEV´RUDNICKPAR

WebeginbynotingthatthenumberofGwithsupp(G)=gisO(g ),i.e.,

(6.6)1 g ,

supp(G)=g

Sincewesumoversupp(G) sr(r 1)/2in(6.5),wehavesupp(G) s ,andthus(6.5)isboundedby1 1/2+ csc|q

g sr(r 1)/2g|qg s 1+ c|qc 1/2+

g sr(r 1)/2g|q1.

ByLemma18,thenumberofdivisorsofq/cwhicharelessthansr(r 1)/2isatmosts ,sothistermisboundedby

1+ sc 1/2+ .

c|q

Since

c|qc 1/2+ =(1+p|qp ) (1+1) s1/2 1p|q

thecontributionof(6.5)isatmostO(s 1+ ).

Itnowremainstobound(6.4).We rstconsiderthetermsforwhichcsupp(G)>s.Now,disc(G)≥supp(G),soifcsupp(G)>sthencertainlycdisc(G)>s,andsumofthecorrespondingtermsin(6.4)isboundedby1 1/2+ csc|q supp(G)|q

csupp(G)>ssupp(G) ssupp(G)

1,1 gq= c|qc 1/2+ g|cg>s 11 qg supp(G)=g1 c|qc 1/2+ g|cg>sby(6.6).Changingvariabletod=cg,whichisadivisorofqsatisfyingd>s,thisisboundedby

c 1/2+ 1 =c1/2+

1 1 (d/c)dd|qc|d

d>sd|qd>sc|d

Abstract. We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among oth

THEDISTRIBUTIONOFSPACINGSBETWEENQUADRATICRESIDUES21

Nowthesumc|dc1/2+ isboundedbyτ(d)d1/2+ d1/2+ ,sothe

aboveisboundedby d 1/2+ s 1/2+

d|q

d>s

byLemma19.Thisboundsthecontributionofc,Gwithcsupp(G)>s.

sIfcdisc(G)>sthen≤c.This,togetherwith(6.6)impliesthat1 1/2+ ssupp(G) csdisc(G)qc|qsupp(G)|cdisc(G)>s

csupp(G)<s

1 1/2+ 1/2+ cg s1 sqc|qg|cg<sc|qg|qc<sg<s

s

since 1/2+ 1 s 1/2+ , c|qc<s 2

(Notethatweonlyusedsupp(G) sr(r 1)/2tobound(6.5)!)

6.2.Thecasecdisc(G)≤s.Fixc≥1andGandpartitionthelatticepointsinsC∩L(G)intotwosubsetsasfollows:Fixareducedfunda-mentalcell(seeB.1)P=P(G)forthelatticeL=L(G).ThencPisareducedfundamentalcellforthedilatedlatticecL.WecantileRr 1bythetranslateshc+cP,hc∈cL.

De nition6.1.Wesaythatx∈L∩sCisc-interiorifthereissomey∈cLsothatx∈y+cP sC.Wesaythatx∈L∩sCisac-boundarypointotherwise.

NotethatthenotiondependsoncandonthechoiceofafundamentalcellPforL.

Animportantfactisthatifdist(x, (sC)) rcdisc(L)thenxisc-interior.ThisfollowsfromLemma15sincediam(cP) rcdisc(L).Lemma8.LetPbeafundamentalcellforthelatticeL Zr 1,c≥1sothatgcd(c,disc(L))=1.Thenfory∈cL,theintersectionL∩(y+cP)withLofthetranslateofthedilatedcelly+cPconsistsofafullsetofrepresentativesofZr 1/cZr 1.c|qc<s1 s bylemma19.Consequently(6.4)isO(s 1/2+ ).

本文来源：https://www.bwwdw.com/article/1n1j.html