Computational Strategies for the Riemann Zeta Func

JournalofComputationalandAppliedMathematics121(2000)247–296∗,DavidM.Bradleyb,RichardE.CrandallcaCentreforExperimentalandConstructiveMathematics,SimonFraserUniversity,Burnaby,BC,CanadaV5A1S6bDepartmentofMathematicsandStatistics,UniversityofMaine,5752NevilleHall,Orono,ME04469-5752,USAcCenterforAdvancedComputation,ReedCollege,Portland,OR,97202,USAReceived30December1999;receivedinrevisedform14January2000AbstractWeprovideacompendiumofevaluationmethodsfortheRiemannzetafunction,presentingformulaerangingfromhistoricalattemptstorecentlyfoundconvergentseriestocuriousodditiesoldandnew.Weconcentrateprimarilyonpracticalcomputationalissues,suchissuesdependingonthedomainoftheargument,thedesiredspeedofcomputation,andtheincidenceofwhatwecall“valuerecycling”.c2000ElsevierScienceB.V.Allrightsreserved.1.MotivationforecientevaluationschemesItwas,ofcourse,aprofounddiscoveryofRiemannthatafunctionsosuperblyexploitedbyEuler,namely(s)=∞Xn=11ns=Ypprime(1−p−s)−1(1)couldbeinterpreted–togreatadvantage–forgeneralcomplexs-values.Sum(1)denestheRiemannzetafunctioninthehalf-planeofabsoluteconvergenceR(s)¿1,andintheentirecomplexplane(exceptforthepoleats=1)byanalyticcontinuation.Thepurposeofthepresenttreatiseistoprovideanoverviewofbotholdandnewmethodsforevaluating(s).StartingwithRiemannhimself,algorithmsforevaluating(s)havebeendiscoveredovertheensuingcenturyandahalf,andarestillbeingdevelopedinearnest.Butwhyconcentrateatalloncomputationalschemes?Onereason,ofcourse,istheintrinsicbeautyofthesubject;abeautywhichcannotbedenied.ButanotherreasonisthattheRiemannzetafunctionappears–perhapssurprisingly–inmanydisparatedomainsofmathematicsandscience,wellbeyonditscanonical∗Correspondingauthor.E-mailaddresses:[e-mail](J.M.Borwein),[e-mail](D.M.Bradley),[e-mail](R.E.Crandall).0377-0427/00/$-seefrontmatterc2000ElsevierScienceB.V.Allrightsreserved.PII:S0377-0427(00)00336-8248J.M.Borweinetal./JournalofComputationalandAppliedMathematics121(2000)247–296domainofanalyticnumbertheory.Accordingly,weshallprovidenextanoverviewofsomesuchconnections,withtheintenttounderscoretheimportanceofecientcomputationalmethods.Typically,aparticularmethodisgearedtoaspecicdomain,suchasthecriticalstrip0¡R(s)¡1,orthepositiveintegers,orargumentslyinginarithmeticprogression,andsoon.Weshallhonorthisvarietyofpurposeinpresentingbotholdandnewevaluationmethodswithaviewtothespecicdomaininquestion.Justasthemethodofchoiceforevaluationtendstodependonthedomain,thedomaininturntypicallydependsonthetheoreticalorcomputationalproblemathand.Thoughmuchofthepresenttreatmentinvolvesnewresultsfors-valuesinintegerarithmeticprogression,weshalldigresspresentlytomentiontheprimaryhistoricalmotivationforevaluation:analyticnumbertheoryapplications.Therearewell-knownandutterlybeautifulconnectionsbetweennumber-theoreticalfactsandthebehavioroftheRiemannzetafunctionincertaincomplexregions.Weshallsummarizesomebasicconnectionswithabrevitythatbeliesthedepthofthesubject.Firstwestatethatevaluationsincertaincomplexregionsofthes-planehavebeenusedtoestablishtheoreticalbounds.Observefromdenition(1)that,insomeappropriatesense,fullknowledgeofbehaviorshouldleadtofullknowl-edgeoftheprimenumbers.ThereisEuler’srigorousdeductionoftheinnitudeofprimesfromtheappearanceofthepoleats=1;infact,hededucedthestrongerresultthatthesumofthereciprocalsoftheprimesdiverges.Thereistheknown[60]equivalenceoftheprimenumbertheorem[55]:(x)∼li(x):=Zx0dulogu∼xlogx(2)withthenonvanishingof(s)onthelineR(s)=1.Here,theliintegralassumesitsCauchyprincipalvalue.(Notethatsomeauthorsdeneliintermsofanintegralstartingatu=2anddieringfromourpresentintegralbyanabsoluteconstant.)AnotherwaytowitnessaconnectionbetweenprimenumbersandtheRiemannzetafunctionisthefollowing.Weobservethatbehaviorof(s)onalinesuchasR(s)=2inprincipledetermines(x).Infact,foranynonintegerx¿1,∗(x):=(x)+12(x1=2)+13(x1=3)+···=12iZc+i∞c−i∞xsslog(s)ds;(3)foranyrealc¿1.Ifonecanperformthecontourintegraltosucientprecision,thenonehasavaluefor∗andmaypeelothetermsinvolving(x1=n)successively,forexamplebyrecursiveappealtothesameintegralformulawithreducedx.ThisnotionunderliestheLagarias–Odlyzkomethodforevaluationof(x)[76].Thoseauthorssuggestclevermodication,basedonMellintransforms,ofthecontourintegrand.Theideaistotransformxs=stoamoreconvergentfunctionofI(s),witharelativelysmallpenaltyinnecessarycorrectionstothe∗function.Experimentalcalculationsusingstandard64-bitoatingpointarithmeticfortheevaluationsforquadratureofthecontourintegral–with,say,Gaussiandecayspeciedfortheintegrand–canevidentlyreachuptox∼1014butnotmuchfurther[58,48].Still,itshouldeventuallybepossibleviasuchanalyticmeanstoexceedcurrentrecordssuchas:(1020)=2220819602560918840obtainedbyM.Deleglise,J.Rivat,andP.Zimmermanvianonanalytic(i.e.combinatorial)means.Infact,theLagarias–Odlyzkoremainsthe(asymptotically)fastestknown(x)countingmethod,requir-ingonlyO(x1=2+)bitcomplexityandO(x1=4+)memo