完全奇哥德巴赫猜想的證明

1、ELECTRONICRESEARCHANNOUNCEMENTSOFTHEAMERICANMATHEMATICALSOCIETYVolume3,Pages99104(September17,1997)S1079-6762(97)00031-0ACOMPLETEVINOGRADOV3-PRIMESTHEOREMUNDERTHERIEMANNHYPOTHESISJ.-M.DESHOUILLERS,G.EFFINGER,H.TERIELE,ANDD.ZINOVIEV(CommunicatedbyHughMontgomery)Abstract.WeoutlineaproofthatiftheGenera

2、lizedRiemannHypothesisholds,theneveryoddnumberabove5isasumofthreeprimenumbers.Theproofinvolvesanasymptotictheoremcoveringallbutanitenumberofcases,anintermediatelemma,andanextensivecomputation.1.IntroductionBy“The3-PrimesProblem,”wemean:caneveryoddnumbergreaterthan5bewrittenasasumofthreeprimenumbers?

3、ThisproblemwasrstsuccessfullyattackedbyHardyandLittlewoodintheirseminal1923paper6;usingtheirCircleMethodandassuminga“WeakGeneralizedRiemannHypothesis,”theyprovedthateverysucientlylargeoddnumbercouldbesowritten.Thesecondauthorhascalculated4directlyfromthatpaperthat“sucientlylarge,”assumingthe“full”Ge

4、neralizedRiemannHypothesis(GRHbelow,i.e.,thatallnon-trivialzerosofallDirichletL-functionshaverealpartequalto1/2),isapproximately1050.In1926Lucke11,inanunpublisheddoctoralthesisunderEdmundLandau,hadalreadyshownthatwithsomerenementsthegurecouldbetakenas1032.In1937Vinogradov15usedhisingeniousmethodsfor

5、estimatingexponentialsumstoestablishthedesiredasymptoticresultwhileavoidingtheGRHentirely.However,thenumericalimplicationsofavoidingtheGRHaresubstantial:in1956Borodzkin1showedthatsucientlylargeinVinogradovsproofmeantnumbers15greaterthan33107000000.Thisgurehassincebeenimprovedsignicantly,mostrecently

6、byChenandWang2,whohaveestablishedaboundof1043000,butinanycasethisgureisfarbeyondhopeof“checkingtheremainingcasesbycomputer.”If,however,wereturntotheoriginalstanceofHardyandLittlewoodbyassumingthetruthoftheGRHwhileatthesametimeusingsomeoftherenedtechniquesofprimarilyVinogradovandLinnik10,andusinganex

7、tensivecomputersearch,wedoindeedarriveatthefollowing:Theorem.AssumingtheGRH,everyoddnumbergreaterthan5canbeexpressedasasumofthreeprimenumbers.ReceivedbytheeditorsFebruary26,1997.1991MathematicsSubjectClassication.Primary11P32.Keywordsandphrases.Goldbach,Vinogradov,3-primesproblem,Riemannhypothesis.c

8、1997AmericanMathematicalSociety99100J.-M.DESHOUILLERS,G.EFFINGER,H.TERIELE,ANDD.ZINOVIEVTheproofofthisresultfallsnaturallyintothreeparts:anasymptotictheo-remhandlingallbutanitenumberofcases,alemmaassuringtheexistenceofprimesrelativelynearuncheckedoddnumbers,andacomputersearchfor2-primesrepresentatio

9、nsoftheremainingdierences.Wenowoutlineeachoftheseparts.2.TheasymptotictheoremTheorem(Zinoviev).AssumingtheGRH,everyoddnumbergreaterthan1020isasumofthreeprimenumbers.Wediscussherebrieythemainideasbehindthisresult;forcompletedetailssee16.FixN9.Weareinterestedinthenumberoftriples(p1,p2,p3)ofprimenumber

10、swhichsatisfytheequation(1)N=p1+p2+p3.Following10weintroducethefunction log(p1)log(p2)log(p3),J(N)=p1+p2+p3=Nwherethesumrangesoveralltriplesofprimes(2).IfJ(N)>0thenthereisatleastonesolutionof(1).Hereby(n)(nisalwaysanaturalnumber)wedenotevonMangoldtsfunction:(n)=log(p)ifn=pk(pisprime),and(n)=0othe

11、rwise.Foranyrealnumberset (n)e2inen/N.S()=n>1ThenwehaveS()=p>1log(p)e2ipep/N+N0.5log2(N),where|1.Clearly,foranyintegerm 11e2imd=00ifm=0,ifm=0.Changingtheorderofsummationandintegration(see10),forsomenewreal(|1)weobtain 1wS3()e2iNd+N1.5log3(N),J(N)=ewwherew=w(N)isasmallnumberdenedlater.Wewillexp

12、ressJ(N)asasumoftheleadingtermandtheremainder.Estimatingtheremainderfromabove,wewillshowthatitislessthantheleadingtermwhenN1020.WethenconcludethatJ(N)>0.FollowingLinnikandVinogradov,wesubdividetheintervalw,1wintothe ,E1,E2.Ourmainideaistorenethissubdivision.disjointunionofsubsetsE1 Inparticularwe

13、changethesetof“majorarcs”,whichinourcaseisE1,makingtheintervalsfromthissetsmaller.Wedoitasfollows.LetQ=1.1log2(N),=4900log4(N),w=1/.ACOMPLETEVINOGRADOV3-PRIMESTHEOREM101DenotebyE(a,q)(whereifq>1,then(a,q)=1,0<a<q,andifq=1,thena=0)theinterval 1a1a,+.qqqqThen a1a1w,1w=,+.qqqq0<q0a<q(q,a

14、)=1LetE1=E(a,q),qQandE2=w,1wE1. Finally,denotebyE1thesetofintervalsE1withsmallerlength a2log(N)a2log(N),+,q(q)Nq(q)NandsetE1=E1E1. WesplittheintegralJ(N)intotwointegrals:overE1(theleadingterm)and E1E2(theremainder).Thefollowinglemmaisusedtoestimatetheremainderterm.Lemma.ForanyE1E2,andforanyN>1020

15、(notnecessarilyodd),GRHimpliesthatN.|S()|<0.18log(N)TheproofofthislemmausestheRiemann-HadamardmethodwhichinvolvessummationoverthezeroesofL-functions.TheleadingtermistreatedusingthecirclemethodofHardyandLittlewood,asusedbyVinogradovandLinnik.3.AnintermediatelemmaNow,bytheasymptotictheorem,ourprobl

16、emisreducedtoconsideringoddnumberswhichare1020.Forthese,weneedthefollowing:Lemma.IftheGRHholdsandif6n1020,thenthereexistsaprimenumberpsuchthat4np1.615×1012.Proof.Theconclusionofthelemmaobviouslyholdsforn <1012,say.Forlargern,weapplySchoenfeld13,equation(6.1).Let(n)=pnlogp;iftheGRHholds,andif

17、n23×108,wehave1n2)logn.|(n)n|<8Justsupposethatthereisnoprimeintheinterval(nh,nexceptpossiblyfortwoofthesixconsecutivenumbersfromn5throughn;thenwehave2logn>(n)(nh)=(n)n)(nh)(nh)+h,whencebytheabove,1n2)logn+2logn.4Sincen1020,wegeth<1.615×1012.Weconcludethenthattheremustbeaprimepsuch

18、that4np1.615×1012.h<102J.-M.DESHOUILLERS,G.EFFINGER,H.TERIELE,ANDD.ZINOVIEVWenoteherethattheGRHactuallyimpliesanestimateon|(n)n|whichhasasinglelogfactor;seeIvic7forexample.However,thesecondauthor,inworkingthroughthedetailsofsuchanestimate,foundthattheconstantobtainedwaslargeenoughsothat,atth

19、eleveln=1020,Schoenfeldsestimategivesaslightlybetternumericalresult.4.Thecomputersearchfor2-primesrepresentationsFinally,then,ifnisanoddnumber1020andpisasinthepreviouslemma,thenm=npisevenand1.615×1012.Butformwehavethefollowing:Theorem(DeshouillersandteRiele).Everyevennumber4m1013isasumoftwoprim

20、enumbers.Foracompleteexpositionofthisandrelatedresults,see3.Letpibetheithoddprimenumber.Theusualapproach5,14toverifytheGoldbachconjectureonagivenintervala,bistond,foreveryevenea,b,thesmallestoddprimepisuchthatepiisaprime.AnecientwaytodothisistogeneratethesetofprimesQ(a,b)=q|qprimeanda aqb,where aisc

21、hoseninasuitableway,andtogeneratethesetsofevennumbersE0E1E2···,denedbyE0=,Ei+1=Ei(Q(a,b)+pi+1),i=0,1,.,1untilEjcoversalltheevennumbersintheintervala,bforsomej.ThesetQ(a,b)isgeneratedwiththesieveofEratosthenes:thisisthemosttime-consumingpartofthecomputation.Forthechoiceof aitissucientt

22、hat aexceedsthelargestoddprimeusedinthegenerationofthesetsEj.InthecomputationscheckingtheGoldbachconjectureupto4×101114,thelargestsmalloddprimeneededwasp446=3163(thisisthesmallestprimepforwhich244885595672pisprime).Amoreecientidea,whichwehaveimplemented,istond,foreveryevenea,b,aprimeq,closetoa,

23、forwhicheqisaprime.Todothateciently,asetofkconsecutiveprimesq1,q2,.,qkclosetoaisgenerated,forsuitablychosenk,andalargesetPofalltheoddprimesuptoaboutbaisprecomputed(withthesieveofEratosthenes)inordertocheckthenumberseqforprimality.Fortheactualcheckoftheintervala,b,wegeneratethesetsofevennumbersF0F1F2

24、···,denedbyF0=,Fi+1=Fi(P+qi+1),i=0,1,.,untilFjcoversalltheevennumbersintheintervala,bforsomej.Inourexperi-ments,wehavechosentheintervalsa,btohaveaxedlengthof108.ThelargestpossibleprimewemayneedinthesetPliesclosetobq1.Bytheprimenumbertheorem,q1akloga,sothatbq1108+kloga.Forthechoiceofkw

25、enoticethatthedensityoftheoddprimesamongtheoddnumbersupto108isabout0.115(thereare5761454oddprimesbelow108).Thismeansthataproportionofabout0.885oftheevennumbersina,bisnotcoveredbythesetF1=P+q1;iftheprimesupto108wereuniformlydistributed,whichtheyarenot,aproportionofabout0.8852oftheevennumberswouldnotb

26、ecoveredbyF2.After151steps,thisproportionisreducedtobelow108.Itturnedoutthatk=360wassucient1ByQ(a,b)+pi+1wemeantheset:q+pi+1|qQ(a,b).ACOMPLETEVINOGRADOV3-PRIMESTHEOREM103forourexperiments.Fora1013thisimpliesthatthelargestprimeinthesetPmusthaveasizecloseto108+104.Intherstapproach,asmallsetofsmallprim

27、esupto5000,say,hastobeavailable,andforeachintervala,btobetreated,alltheprimesina,bhavetobegenerated.Inthesecondapproach,alargesetofsmallprimesuptoabout108+104hastobegenerated(onlyonce),andforeachintervala,btobetreated,onehastondthelargestkprimesa.Ofcourse,thisismuchcheaperthantondalltheprimesinthein

28、tervala,b.Thepricetopayisthatforeachea,bsomeprimepisfoundforwhichepisprime,butingeneralthispisneitherthesmallestnorthelargestsuchprime.FortheactualgenerationofkprimesclosetoawehaveusedJaeschkescompu-tationalresults8,statingthatifapositiveintegern<2152302898747isastrongpseudoprimewithrespecttother

29、stveprimes2,3,5,7,11,thennisprime;correspondingboundsfortherstsixandsevenprimesare3474749660383and341550071728321,respectively.WehaveimplementedthesecondapproachonaCrayC98vectorcomputerandveriedtheGoldbachconjectureforallevennumbers>4×1011and1013.Afterthegenerationofkprimesneara,theactualver

30、icationwascarriedoutbysievingwithalongarrayof64-bitintegerscalledODD,whereeachbitrepresentsanoddnumber<108+104,thebitbeing1ifthecorrespondingoddnumberisprime,and0ifitiscomposite.GeneratingFi+1fromFiamountstodoingan“or”operationbetweenonelongarrayofintegersandashiftedversionofthearrayODD.Thiscanbe

31、carriedoutveryecientlyontheCrayC98.Inonetypicalrun,wehandled5000consecutiveintervalsoflength108.Closeto1013thetimetogenerate5000×360largeprimeswasabout2600CPU-seconds,andthetotalsievingtimewasabout5040seconds.Thetotaltimeusedtocovertheinterval4×1011,1013wasapproximately53(lowpriority)CPU-h

32、ours.Thelargestnumberoflargeprimeswhichweneededwas328:fore=7379095622422andrstprimeq1=7378999992031itturnedoutthateqiiscompositefori=1,.,327,andprimefori=328(q328=7379000002739andeq328=95619683).AcknowledgmentThesecondauthorwishestothankPaulT.BatemanandMarshallAshforhelpfulcorrespondencesonthistopic

33、.References1.K.G.Borodzkin,OnI.M.Vinogradovsconstant,Proc.3rdAll-UnionMath.Conf.,vol.1,Izdat.Akad.NaukSSSR,Moscow,1956.(Russian)MR20:6973a2.JingrunChenandTianzeWang,OntheoddGoldbachproblem,ActaMath.Sinica32(1989),702718.MR91e:111083.Jean-MarcDeshouillers,HermanteRiele,andYannickSaouter,Newexperiment

34、alresultsconcerningtheGoldbachconjecture,toappear.4.GoveEnger,SomenumericalimplicationoftheHardyandLittlewoodanalysisofthe3-primesproblem,submittedforpublication.5.A.Granville,J.vandeLune,andH.teRiele,CheckingtheGoldbachconjectureonavectorcomputer,NumberTheoryandApplications(R.A.Mollin,ed.),KluwerAc

35、ademicPublishers,1989,423433.MR93c:110856.G.H.HardyandL.E.Littlewood,SomeproblemsofPartitioNumerorum.III:Ontheexpressionofanumberasasumofprimes,ActaMathematica44(1922),170.7.A.Ivic,TheRiemannzeta-function,J.WileyandSons,1985.MR87d:11062104J.-M.DESHOUILLERS,G.EFFINGER,H.TERIELE,ANDD.ZINOVIEV8.GerhardJaeschke,Onstrongpseudoprimestoseveralbases,Math.Comp.61(1993),915926.MR94d:110049.A.A.Karatsuba,Basicanalyticnumbertheory,Springer-Verlag,1993.MR94a:1100110.U.V.Linnik,Th