The distribution of spacings between quadratic residues
更新时间:2023-08-11 19:36:01 阅读量: 资格考试认证 文档下载
- the推荐度:
- 相关推荐
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+ ).
正在阅读:
The distribution of spacings between quadratic residues08-11
会计1在线作业答案04-24
八年级上学期第一阶段测试数学试103-14
B07报验申请表12-14
南林考研真题09-25
湖南信息学院开校时间02-15
mpu6050和6000中文 - 图文11-08
三好学生表彰决定10-15
农村牧区改革发展路径的研究05-28
- 1the relationship between language and culture
- 2The+Relationship+between+Men+and+Nature+Reflected+by+the+Conflict+between+Captain+Ahab+and+Moby+Dick
- 3The similarities and differences between Chinese and Western
- 4The differences between Chinese family and American family
- 5Evolution of Cosmological Density Distribution Function from the Local Collapse Model
- 6Comparison between Chinese and American traditional values
- 7The Differences Between Chinese Culture And Western Culture
- 8The difference between American political system and British
- 9On the Cultural Differences Between English and Chinese from
- 10The Differences between Chinese and Western Food Cultures
- 梳理《史记》素材,为作文添彩
- 2012呼和浩特驾照模拟考试B2车型试题
- 关于全面推进施工现场标准化管理实施的通知(红头文件)
- 江西省房屋建筑和市政基础设施工程施工招标文件范本
- 律师与公证制度第2阶段练习题
- 2019-2020年最新人教版PEP初三英语九年级上册精编单元练习unit6训练测试卷内含听力文件及听力原文
- 小升初数学模拟试卷(十四) 北京版 Word版,含答案
- 认识创新思维特点 探讨创新教育方法-精选教育文档
- 00266 自考 社会心理学一(复习题大全)
- 多媒体在语文教学中的运用效果
- 派出所派出所教导员述职报告
- 低压电工作业考试B
- 18秋福建师范大学《管理心理学》在线作业一4
- 中国铝业公司职工违规违纪处分暂行规定
- 13建筑力学复习题(答案)
- 2008年新密市师德征文获奖名单 - 图文
- 保安员培训考试题库(附答案)
- 银川市贺兰一中一模试卷
- 2011—2017年新课标全国卷2文科数学试题分类汇编 - 1.集合
- 湖北省襄阳市第五中学届高三生物五月模拟考试试题一
- distribution
- quadratic
- spacings
- residues
- between
- 基于GIS及RS天津滨海新区城市空间增长格局研究
- (完整版)高一经济生活第三单元测试卷
- 医院信息科个人总结
- 成都七中2012届高三数学入学考试试题(理科)
- 基于CPLD的高分辨率AD转换电路设计
- 一年级下册数学期末复习应用题100道 (2)
- 职业病培训教材
- 《中国档案分类法》适用性试探
- 第七册文明礼仪社团备课
- 传媒产业新型发展之路
- SAP FI-SL-IS 信息系统常用事物码清单
- 吉的堡阳光威尼斯幼儿园发展规划
- 柴油、润滑油物性参数
- 桥梁博士实例
- 第五章 外汇换汇交易
- 政治经济学知识点复习(厦门大学版政治经济学)
- 中空纤维膜技术及其应用
- 劳动法的调整对象
- 9-1甲午战争后民族危机的加深
- 银行中层助理干部竞聘上岗考试面试题汇总之难度题及解答思路