Transcription
A History of the Prime Number TheoremAuthor(s): L. J. GoldsteinReviewed work(s):Source: The American Mathematical Monthly, Vol. 80, No. 6 (Jun. - Jul., 1973), pp. 599-615Published by: Mathematical Association of AmericaStable URL: http://www.jstor.org/stable/2319162 .Accessed: 09/02/2013 20:07Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at ms.jsp.JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact support@jstor.org.Mathematical Association of America is collaborating with JSTOR to digitize, preserve and extend access toThe American Mathematical Monthly.http://www.jstor.orgThis content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
A HISTORY OF THE PRIME NUMBER THEOREMof MarylandL. J. GOLDSTEIN, UniversityThe sequenceof primenumbers,whichbegins2, 3,5,7, 11,13,17,19,23,29,31,37,both professionalsand amateurshas held untold fascinationfor mathematicians,alike. The basic theoremwhichwe shalldiscussin thislectureis knownas theprimeand allows one to predict,at leastin grossterms,the way in whichnumbertheoremLet x be a positiverealnumber,and let7r(x) thenumbertheprimesare distributed.of primes x. Then the primenumbertheoremassertsthat(X)lim(1)X0x/logx 1,wherelog x denotesthenaturallog of x. In g?((logx)(x-oo),whereo(x/logx) standsfora functionf(x) withthe propertylimf(x)l , x/logx 0Actually,forreasonswhichwill become clear later,it is muchbetterto replace(1)and (2) by the followingequivalentassertion:?O(lox) x)r(x) Jb doyy- 7t(x)loglog(3)to integrateTo provethat(2) and (3) are equivalent,it suffices[x dy12log yonce bypartsto get(4)flogylogxlog2 log2yPh.D. underG. Shimura.Aftera GibbsinstructorshipLarryGoldsteinreceivedhis PrincetonHis researchat Yale, hejoinedtheUniv.of M arylandas AssociateProfessorand nowisProfessor.Functions.He is theauthorofAnalyNumberTheoryandAutomorphicis inAnalyticand Algebraictic Number Theory(Prentice-Hall 1971), and AbstractAlgebra,A First Course (Prentice-Hall, toappear). Editor.599This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
600[June-JulyL. J. GOLDSTEINHowever,for x 4,fXJ2(5)dyJ2y l2y- 1/x-0xdy'u' IdyyJ2 log2x-1log2l1(1)xVlogx 'wherewe have used the fact that 1/log2xis monotonedecreasingfor x 1. It isclearthat(4) and (5) showthat(2) and (3) are equivalentto one another.The advantage of the version(3) is thatthe functionLi(x) fx5'called the logarithmicintegral,providesa muchcloser numericalapproximationtoir(x)thandoes x /logx. This is a ratherdeep factand we shall returnto it.In thislecture,I shouldlike to explorethehistoryof theideas whichled up to theprimenumbertheoremand to itsproof,whichwas notsupplieduntilsome 100 yearsafterthefirstconjecturewas made.The historyoftheprimenumbertheoremprovidesfeedinga beautifulexampleof theway in whichgreatideas developand interrelate,upon one anotherultimatelyto yield a coherenttheorywhich rathercompletelyexplains observedphenomena.The veryconceptionof a primenumbergoes back to antiquity,althoughit is notpossibleto say preciselywhenthe conceptfirstwas swereknownto theGreeks.Let usnumberof elementarycitethreeexamples,all of whichappearin Euclid:(i) (Fundamental Theorem of Arithmetic):Every positive integern can bewrittenas a productof primes.Moreover,this expressionof n is unique up to arearrangementof the factors.manyprimes.(ii) There exist infinitely(iii) The primes may be effectivelylisted using the so-called "sieve ofEratosthenes".We willnotcommenton (i), (iii) anyfurther,sincetheyare partof thecurriculumof most undergraduatecoursesin numbertheory,and hence are probablyfamiliarfromEuclid'sto mostof you. However,thereis a proofof (ii) whichis quitedifferentto the historyof the primenumberwell-knownproofand whichis verysignificantLeonhard Euler and datestheorem.This proofis due to the Swiss mathematicianfromthemiddleof the 18thcentury.It runsas follows:AssumethatPI, , PN is a completelist of all primes,and considerthe productThis content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
A HISTORY OF THE PRIME NUMBER THEOREM1973](6)E(H.1(1 P)601p T2 . 'Since everypositiveintegern can be writtenuniquelyas a productof primepowers,everyunit fraction1/n appears in the formalexpansionof the product(6). Forthe termsthen 1/n occurs frommultiplyingexample,if n p'l .p'N1a/ll1 /pa2,.lpa,Therefore,if R is any positiveinteger,Iru(-'N(7)a-1-11PiR 11 1E,1In.whichHowever,as R - oo, the sum on the righthand side of (7) tendsto infinity,contradicts(7). Thus, P1, *', PN cannotbe a completelist of all primes.We shouldmake two commentsabout Euler's proof: First,it linksthe FundamentalTheoremof primes.Second,it uses an e divergenceof the harmonicseries,to conclude an arithmeticresult.It is thislatterfeaturewhich became the cornerstoneupon which much of 19th centurynumbertheorywas erected.The firstpublishedstatementwhichcame close to the primenumbertheoremwas due to Legendrein 1798[8]. He assertedthat7r(x)is of theformx /(Alog x B)forconstantsA and B. On the basis of numericalwork,Legendrerefinedhis conjecturein 1808 [9] by assertingthat logx A(x)'where A(x) is "approximately1.08366.".Legendremeant thatPresumably,by this latterstatement,lim A(x) 1.08366.x -I 00It is preciselyin regardto A(x), whereLegendrewas in error,as we shall see below.In his memoir[9] of 1808,Legendreformulatedanotherfamousconjecture.Let kprimeto one another.Then Legendreassertedand 1be integerswhichare relativelymanyprimesof theform1 kn(n 0, 1,2, 3, .). In otherthatthereexistinfinitelywords,if 7rk,l(x)denotesthenumberof primesp of theform1 kn forwhichp x,thenLegendreconjecturedthat(8)7tk,l(x)- ooas x - cc.Actually,the proofof (8) by Dirichletin 1837 [2] providedseveralcrucialideas onhow to approachtheprimenumbertheorem.This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
602L. J. GOLDSTEIN[June-JulyAlthoughLegendrewas the firstperson to publish a conjecturalformof theprimenumbertheorem,Gauss had alreadydone extensivework on the theoryofprimesin 1792-3. EvidentlyGauss consideredthetabulationof primesas some sortof pastimeand amused himselfby compilingextensivetables on how the primesin variousintervalsof length1009. We have included some ofdistributethemselvesGauss' tabulationsas an Appendix.The firsttable,excerptedfrom[3, p. 436], coversan intervalof lengththeprimesfrom1 to 50,000.Each entryin the table represents168toarefrom135fortherefrom1001to 2000;11000.Thus, example,primes1000;127 from3001 to 4000; and so forth.Gauss suspectedthatthe densitywithwhichprimesoccuredin theneighborhoodof theintegern was 1/logn, so thatthenumberof primesin the interval[a, b) should be approximatelyequal toTb dxx'JalogIn the second set of tables, samples from[4, pp. 442-3], Gauss investigatesthedistributionof primesup to 3,000,000and comparesthe numberof primesfoundwiththe above integral.The agreementis striking.For example,between2,600,000and 2,700,000,Gauss found6762 primes,whereas2,700.0002,600,000dx-log x 6761.332.on the distributionof primes.NeverGauss neverpublishedhis investigationstheless,thereis littlereasonto doubt Gauss' claim thathe firstundertookhis workin 1792-93, well beforethe memoirof Legendrewas written.Indeed, thereareseveralotherknownexamplesof resultsof the firstrank whichGauss proved,butnevercommunicatedto anyoneuntilyearsafterthe originalworkhad been done.This was the case, for example,withthe ellipticfunctions,whereGauss precededwhereGauss anticipatedRiemann.The onlyJacobi,and withRiemanniangeometry,informationbeyond Gauss' tables concerningGauss' work in the distributionofprimesis containedin an 1849 letterto theastronomerEncke. We have includedatranslationof Gauss' letter.In his letterGauss describeshis numericalexperimentsand his conjectureconcerningi(x). There are a numberof remarkablefeaturesof Gauss' letter.On thesecondpage of theletter,Gauss compareshis approximationto 2r(x),namelyLi(x),with Legendre'sformula.The resultsare tabulatedat the top of the second pageand Gauss' formulayieldsa muchlargernumericalerror.In a veryprescientstatement,Gauss defendshis formulaby notingthat althoughLegendre'sformulayields asmallererror,therateof increaseof Legendre'serrortermis muchgreaterthanhisown. We shall see below thatGauss anticipatedwhat is knownas the "Riemannhypothesis."Anotherfeatureof Gauss' letteris thathe casts doubt on Legendre'sassertionabout A(x). He assertsthatthe numericalevidencedoes not supportanyconjectureabout the limitingvalue of A(x).This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
1973]A HISTORY OF THE PRIME NUMBER THEOREM603Gauss' calculations are awesome to contemplate,since they were done longbeforethe days of high-speedcomputers.Gauss' persistenceis most impressive.My student,Edward Korn, has checkedHowever,Gauss' tablesare not error-free.Gauss' tables usingan electroniccomputerand has founda numberof errors.Weinclude the correctedentriesin an appendix. In spite of these (remarkablyfew)evidencein favorof theprimeerrors,Gauss' Modern studentsof mathematicsshould take note of the greatcare withwhichdata was compiledby such giantsas Gauss. Conjecturesin thosedays were rarelyidle guesses.They were usuallysupportedby piles of laboriouslygatheredevidence.The next step toward a proof of the prime numbertheoremwas a step in adifferentcompletelydirection,and was takenby Dirichletin 1837 [2]. In a beautifulmemoir,Dirichletproved Legendre's conjecture(8) concerningthe infinitudeofprimesin an arithmeticprogression.Dirichlet'sworkcontainedtwo radicallynewideas, whichwe should discuss in some detail.denotethe ringof residueclasses modulo n, and let En denotethe groupLetof unitsof 7n. Then En is theso-called"group of reducedresidueclassesmodulo n"and consistsof thoseresidueclassescontainingan elementrelativelyprimeto n. If kis an integer,let us denoteby k its residueclass modulo n. Dirichlet'sfirstbrilliantof the groupEn; thatis, thehomomorphismsidea was to introducethecharactersofEn into the multiplicativegroup Cx of non-zerocomplexnumbers.If x is such acharacter,thenwe may associate withx a function(also denotedx) fromthe semigroup Z* of non-zerointegersas follows: Set@,,y(a) Z(d) if (a, n) 10 otherwise.Then it is clear thatx: Z*C' and has the followingproperties:(i)Z(a n) (ii),(aa') &)%(a),(iii) Z(a) 0 if (a, n) # 1,(iv) x(i) 1.charactermodulo n.A functionx: E* ?x satisfying(i)-(iv) is called a edorthogonalDirichlet'smain resultityrelations,which assertthe following:(A)E Z(a) 0(n) if xis identically1,a0otherwise,wherea runsover a completesystemof residuesmodulo n;This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
604[June-JulyL. J. GOLDSTEIN(B)xX(a) 4(n) if a -1 (mod n),0otherwise,whereX runsoverall numericalcharactersmodulo n. Dirichlet'sideas gave birthtothe moderntheoryof dualityon locallycompactabelian groups.Dirichiet'ssecondgreatidea wasto associateto each numericalcharactermodulo nand each real numbers 1, the followinginfiniteseriesL(s,X) -(9)x(nsn 1a continuousfunctionIt is clear thatthe seriesconvergesabsolutelyand representsfor s 1. However,a more delicate analysisshows that the series(9) convergesa continuousfunctionof s in this(althoughnot absolutely)fors 0 and entically1. The functionL(s,x) hasXcome to be called a DirichletL-function.Note thefollowingfactsabout L(s, X): FirstL(s, X) has a productformulaof theformL(s, X) (10)(1-pp(s 1),F) )wheretheproductis takenoverall primesp. The proofof (10) is verysimilarto theof primenumbers.Therefore,argumentgivenabove in Euler's proofof theinfinityby (10),logL(s,X)(11) -Elog(1 -pm 1 mp pIps)MsDirichlet'sidea in provingthe infinitudeof primesin the arithmeticprogressiona, a n, a 2n,*, (a, n) 1, was to imitate,somehow,Euler's proof of the infinitudeof primes,by studyingthefunctionL(s, X)fors near 1. The basic quantitytoconsideris(12)XE (a)-'logL(s,X)X -Ep -m 1Ed Y.pm 1XX(a) X(Pm)mmmsX(a)mpjXaX(pm),wherewe have used (11). Let a* be an integersuch that aa* 1 (mod n). ThenX(a*) X(a)' l by (i)-(iv). Moreover,This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
1973]605A HISTORY OF THE PRIME NUMBER THEOREMX Z(a) 'x(pm) x(13) z X(a*ptm)x (n) if a*pm 1 (modn)O otherwise.However,a*pm(13), we have(14)by (12) and1 (mod n) is equivalentto pm a (mod n). Therefore,Z x(a)llogL(s,Z)-40(n)xzm-mPMsm im pn)pnma(modThus, finally,we have-(15)4 (n)x(n S Z(a)logL(s,Z)-pMmpMPmm 2pm a(modnt)(s ).p5-p a(mod n)manysee thatin orderto prove thatthereare infinitelyFrom (15), we immediatelyprimesp a (mod n), it is enoughto showthatthefunctionp a(mod n)PS1tendsto co as s approaches1 fromtheright.But it is fairlyeasy to see thatass- 1 , the sum1pp m-amodIn)m-2MsItPto show thatremainsbounded.Thus, it suffices010(n) ,Z (a)-log L(s, Z) - oo(s )However,if Xodenotesthecharacterwhichis identically1, thenit is easy to see thatZn)o(a) 1L(s,Zo)-- so ass 1 .it is enoughto show thatif x#Zo, thenlog L(s, x) remainsbounded asTherefore,s 1 1. We have alreadymentionedthatL(s, X) is continuousfors 0 if X# Xo.Therefore,it sufficesto show that L(1, X)# 0. And this is preciselywhat Dirichletshowed.This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
606L. J. GOLDSTEIN[June-JulyDirichlet'stheoremon primesin arithmeticprogressionswas one of the majorachievementsof 19thcenturymathematics,because it introduceda fertilenew ideainto numbertheory-that analyticmethods(in thiscase the studyof the DirichletL-series)could be fruitfullyapplied to arithmeticproblems(in thiscase theproblemof primesin arithmeticprogressions).To thenovice,such an applicationof analysisto numbertheorywould seemto be a wasteof time.Afterall, numbertheoryis thestudyof the discrete,whereasanalysisis the studyof the continuous;and whatshould one have to do with the other! However,Dirichlet's 1837 paper was thebeginningof a revolutionin number-theoreticthought,thesubstanceof whichwas toapply analysisto numbertheory.At first,undoubtedly,mathematicianswere veryuncomfortablewith Dirichlet'sideas. They regardedthemas verycleverdevices,whichwould eventuallybe supplantedby completelyarithmeticideas. For althoughanalysismightbe usefulin provingresultsabout the integers,surelythe etheoryoftheintegersin an inessentialwayand could be eliminatedbytheuse of of numbertheoryin the 19thcenturyshowsthatthisidea was eventuallyconnectionbetweenanalysisand numbertheorycame torepudiatedand therightfulbe recognized.The firstmajor progresstoward a proof of the prime numbertheoremafterDirichletwas due to theRussianmathematicianin two memoirs[12,13]Tchebycheffwrittenin 1851 and 1852. Tchebycheffintroducedthe followingtwo functionsof areal variable x:0(x) V(x) Xlogp,?logp,p xpen Xwherep runsoverprimesand m numbertheorem(1) is equivalentto eitherof the two statementslim 0(x) l(16)x-00(17)lim (xo x)1.Moreover,Tchebycheffprovedthatiflimx 0.(0(x) /x)exists,thenitsvalue mustbe 1.Furthermore,Tchebycheffproved that(18).92129 1 lim sup? lim inf x/log-() x (x)x 1.10555.x /logmethodswere of an elementary,Tchebycheff'scombinatorialnature,and as suchwerenot powerfulenoughto provetheprimenumbertheorem.This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
1973]A HISTORY OF THE PRIME NUMBER THEOREM607The firstgiantstridestowarda proofof theprimenumbertheoryweretakenbyB. Riemannin a memoir[10] writtenin 1860. RiemannfollowedDirichletin connectingproblemsof an arithmeticnaturewith the propertiesof a functionof acontinuousvariable.However,whereDirichlet consideredthe functionsL(s, X) asfunctionsofa realvariables, Riemanntook thedecisivestepin connectingarithmeticof a hetheoryoffunctionsfunction:1(19)c(n)n 1It is reasonablyeasy towhichhas come to be known as the Riemannzeta function.fors in a compactsubsetsee thatthe series(19) convergesabsolutelyand uniformlyof thehalf-planeRe (s) 1. Thus, C(s) is analyticforRe (s) 1. Moreover,by usingof primes,it is easythesame sortof argumentused in Euler's proofof theinfinitudeto provethat(20)C(s) 171(1pIp )(Re (s) 1),ofwherethe productis extendedover all primesp. Euler's proofof the infinitudeprimessuggeststhatthe behaviorof C(s) for s 1 is somehowconnectedwiththeof primes.And, indeed,thisis the case.distributionRiemannprovedthat C(s) can be analyticallycontinuedto a functionwhichisin the whole s-plane.The onlysingularityof C(s) occursat s 1 andmeromorphicthe Laurentseriesabout s 1 looks like(21)sa a1(s-1)C(s) Moreover,if we set(22)R(s) s(s- 1)7sI2r(S /2)4(s),thenR(s) is an entirefunctionof s and satisfiesthefunctionalequation(23)R(s) R(1 - s).To see the immediateconnectionbetweenthe Riemannzeta functionand thedistributionof primes,let us returnto Euler's proof of the infinitudeof primes.A variationon theidea of Euler's proofis as follows: Suppose thattherewereonlyfinitelymanyprimesPl, ', PN. Then by (20), 4(s) would be boundedas s tendsto 1,whichcontradictsequation (21). Thus, the presenceof a pole of C(s) at s 1 immediatelyimpliesthatthereare infinitelymanyprimes.But the connectionbetweenthe zeta functionand the distributionof primesrunseven deeper.This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
608[June-JulyL. J. GOLDSTEINLet us considerthe followingheuristicargument:From equation(20), it is easyto deduce that(24)C() Epm 1(Re (s) 1).(logp)pmSMoreover,by residuecalculus,it is easy to verifythat1-lrn(25)T-o22 TasJ2-iT-ds- s1, x 10,x 1.we see thatof limitand summationis x not equal to an integer,welimT o2m h-iTX C'()SC(O)ds (26)Epm 1pm;iX(logp) limT1 J2o27ri pmJ-iT-dslogp (by equation (25)) x).Thus, we see thatthereis an intimateconnectionbetweenthefunctionf(x) and C(s).This connectionwas firstexploitedby Riemann,in his 1860 paper.Note that the functionxs C'()s cs(27)has poles at s 0 and at all zeroesp of C(s). Moreover,note thatby equation (20),we see that C(s) : 0 forRe (s) 1. Therefore,all zeroes of C(s) lie in thehalf-planeRe (s) 1. Further,since R(s) is entireand C(s) : 0 for Re(s) 1, the functionalequation (23) implies that the only zeroes of C(s) for which Re (s) 0 are ats -2, -4, -6, -8, ., and theseare all simplezeroes and are called the trivialzeroes of C(s) lie in the stripzeroesof C(s).Thus, we have shownthatall non-trivial0 ? Re (s) 1. This stripis called the criticalstrip.The residue of (27) at a nontrivialzero p isxPpThug,if ai is a largenegativenumber,and if CG,T denotesthe rectanglewithverticesa iT, 2 iT, thenCauchy's theoremimpliesthat(28)1I2 iT-s-c2 2riJ2iTSxs1(s)ds --I(X)2Fic ITiT-T 2 iT.iT2 ff iTj XsIs-iTC'(s)-dsC(S) R(u, T),whereR(u, T) denotesthesumof theresiduesof thefunction(27) at thepoles insideThis content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
1973]A HISTORY OF THE PRIME NUMBER THEOREM609CG,T. By lettinga and T tend to infinityand by applyingequations (26) and (28),Riemannarrivedat thefollowingremarkableformula,known as Riemann'sexplicitformula(29)/X) x -X,,p -?4'i22)- 1og(1 pCM0 2x-2),wherep runs over all non-trivialzeroes of the Riemannzeta function.Riemann'sformulais surprisingfor at least two reasons.First,it connectsthe function*(x),which is connectedwith the distributionof primes,with the distributionof thezeroes of the Riemannzeta function.That thereshould be any connectionat all isamazing. But, secondly,the formula(29) explicitlyputs in evidencea formof theprimenumbertheoremby equating*(x) withx plus an errortermwhichdependson thezeroesof thezeta function.If we denotethiserrortermby E(x), thenwe seethatthe primenumbertheoremis equivalentto theassertion(30)limx 00x0, which,in turn,is equivalentto the assertion(31)limX-cxEpp 0.Riemannwas unableto prove(31), but he made a numberof conjecturesconcerningof thezeroesp fromwhichthestatementthedistributions(31) followsimmediately.The most famous of Riemann's conjecturesis the so-called Riemannhypothesis,whichassertsthatall non-trivialzeroesof C(s) lie on theline Re (s) i, whichis theline of symmetryof the functionalequation (23). This conjecturehas resistedallattemptsto proveit formorethana centuryand is one of themostcelebratedopenproblemsin all of mathematics.However,if the Riemannhypothesisis true,then'XPI1- II Iand fromthisfactand equation (29), it is possibleto provethat(32)t(x) x O(xJ )foreverye 0, whereO(xi ?) denotesa functionf(x)suchthatf(x)/xi? is boundedforall largex. Thus,theRiemannhypothesisimplies(31) in a trivialway,and hencethe primenumbertheoremfollowsfromthe Riemannhypothesis.What is perhapsis thefactthatif(32) holdsthentheRiemannhypothesismorestrikingis true.Thus,the primenumbertheoremin the sharp form(32) is equivalentto the Riemannthattheconnectionbetweenthezeta functionand thehypothesis.We see, therefore,This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
610L. J. GOLDSTEIN[June-Julydistributionofprimesis no accidentalaffair,butsomehowis wovenintothefabricofnature.In his memoir,Riemannmade many otherconjectures.For example,if N(T)denotesthe numberof non-trivialzeroesp of C(s) such that - T ? Im(p) T, thenRiemannconjecturedthat(33)N(T) 1-T27tlogT-1 log (27t) TO(log T).27tThe formula(33) was firstprovenby von-Mangoldtin 1895 [14]. An interestinglineof researchhas been involvedin obtainingestimatesforthe numberof non-trivialzeroes p on the line Re(s) -. Let M(T) denotethe numberof p such thatRe(s)j, - T Im(s) ? T. ThenHardy[6] in 1912,provedthatM(T) tendsto infinityasT tendsto infinity.Later,Hardy[7] improvedhisargumentto provethatM(T) AT,whereA is a positiveconstant,not dependingon T. The ultimateresultof thissortwas obtainedby AtleSelbergin 1943[11]. He provedthatM(T) ATlog T forsomepositiveconstantA. In viewofequation(33), Selberg'sresultshowsthata positivepercentage of thezeroesof C(s) actuallylie on theline Re(s) i. This resultrepresentsthebestprogressmade to date in attemptingto prove the Riemannhypothesis.itFortunately, is not necessaryto prove the Riemann hypothesisin order toprovetheprimenumbertheoremin theform(17). However,it is necessaryto obtainabout thedistributionsomeinformationof thezeroesof C(s). Such informationwasobtained independentlyby Hadamard [5] and de la Vallee Poussin [1] in 1896,therebyprovidingthefirstcompleteproofsof theprimenumbertheorem.Althoughin detail,theybothestablishtheexistenceof a zero-freetheirproofsdifferregionforC(s),the existenceof whichservesas a substituteforthe Riemannhypothesesin thereasoningpresentedabove. More specifically,theyprovedthatthereexist constantsa, to such that C(o it) : 0 if ? 1 - 1/a log It , I t to. This zero-freeregionallows one to prove the primenumbertheoremin the form-(34) x O(xe- C(log X) 1/14)tfr(x)Please note,however,thattheerrortermin (34) is muchlargerthantheerrortermpredictedby the Riemannhypothesis.Thus,theprimenumbertheoremwas finallyproved aftera centuryof hardworkby manyof theworld'sbestmathematicians.It is grosslyunfairto attributeproofofsucha theoremto thegeniusof a singleindividual.For, as we have seen,each stepinthe directionof a proof was conditionedhistoricallyby the work of precedinggenerations.On the otherhand, to denythatthereis geniusin th&workwhichledup to the ultimateproofwould be equally unfair.For at each step in the chain ofdiscovery,brilliantand fertileideas werediscovered,and providedthe materialoutof whichto fashionthe nextlink.This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
1973]611A HISTORY OF THE PRIME NUMBER THEOREMAPPENDIX A: Samples from Gauss' Tables. TABLE e,II, p. 490968810110285968690958998The frequencyof primes.TABLE 2 (Werke,II, p. 443) 6857684967876766680467626714This content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and 7056862168741259816744
612[June-JulyL. J. GOLDSTEINAPPENDIXB: Gauss' Letterto Enke.My distinguishedfriend:Your tto mein morewaysthanone.me of myownendeavorsin thisfieldwhichbeganin theverydistantpast,inYou havereminded1792or 1793,afterI had acquiredtheLambertsupplementsto c,one of myfirstprojectswasI had begunmymoredetailedinvestigationsto turnmyattentionto thedecreasingof primes,to whichend I lsof length1000; Trans.)and recordedthe resultson theattachedwhitethatbehindall ofitsfluctuations,thisfrequencypages.I soonrecognizedis on theaverageinverselyto thelogarithm,so thatthenumberofprimesbelowa givenboundn is approximatelyproportionalequal toIdnnJlogis understoodwherethelogarithmto be hyperbolic.Lateron, whenI becameacquaintedwiththelistin Vega,'stables(1796)goingup to 400031,I extendedthatmycomputationfurther,confirmingIn emuchpleasureandI havefrequently(sinceI lack thepatiencefora continuouscount)spentan idlequartr ofan hourto countanotherchiliadhereand there;althoughI eventuallygaveit up withoutquite gettingthrougha million.Onlysometimelaterdid I makeuse of thediligenceof Goldschmidtto fillsomeof theremainingthecomputationgaps in thefirstmillionand tocontinueto Burkhardt'stables.Thus(foraccordingmanyyearsnow) thefirstthreemillionhave beencountedand checkedagainstthe 0001500000200000025000003000000Here llnErrorlog n41606.4 79627.5 114263.1 149054.8 183245.0 216970.6 .9 40.978672.7- 171.7114374.0 264.0149233.0 350.0183495.1 479.1217308.5 563.5I was notawarethatLegendrehad also workedon thissubject;yourlettercausedmeto lookin his Thioriedes Nombres,and in thesecondeditionI founda fewpageson now,forgotten).Legendreusedtheformulanlog n -AwhereA is a constantwhichhe setsequal to 1.08366.Aftera hastycomputation,I findin theabovecases the deviationsThis content downloaded on Sat, 9 Feb 2013 20:07:45 PMAll use subject to JSTOR Terms and Conditions
19731-A HISTORYOF THE PRIME NUMBERTHEOREM613TABLE B23,3 42,2? 68,1-1- 92,8 159,1 167,6buttheyseemto growfasterwithiare esso thatit is quitepossibletheymaysurpassthem.To makethecountand theformulaagree,onenumbers:insteadof A 1.08366,thefollowingwouldhaveto use,respectively,TABLE C1,090401,076821,075821,075291,071791,07297I darenotconjecn,the(average)valueofA decreases;however,It appearsthat,withincreasingfrom1. I cannotsay thatis I or a numberdifferentthelimitas n approachesinfinityturewhetherforexpectinga verysimplelimitingvalue;on theotherhand,theexcessofthereis anyjustificationoftheorderof1/logn.I wouldbe inclinedto believethatthe differwellbe a quantityA over1 mightthanthefuLnctionmustbe simpleritself.entialofthefunctionwould suggestthatthedifferentialforhe function,Legendre'sformulan is postulatedIf dn/logof theformdnl(log n- (A -1)). By theway,forlargen,yourformightbe somethingfunctionmula could be consideredto coincidewithnlog n-(i/2k)if we put A 1/2kformula,thatis,withLegendre'swherek is ountsandmine.Finally,I wanttoremarkthatI noticeda coupleofdisagreementsBetween 59000 and 60000,you have 95, whileI have mthefactthat,in Lambert'sSupplement,The firstdifferencewithis virtuallycrawlingoccurstwice.The chiliadfrom101000- 102000in Lambert'sSupplementerrors;in mycopy,I have indicatedsevennumberswhichare notprimesat all, and suppliedtwomissingones.Woulditnotbe possibleto induceyoungMr.Dase tablesat theAcademywhich,I am afraid,are notintended(few)millions,to myIn thiscase,letme remarkthatin .million.thefirsthaveemployedin countingbased on a specialschemewhichI myselfinstructions,on a singlepage in 10 columns,each columnbelongingThe countsforeach 100000are irndicated10000;Trans.);an additionalcolumnin front(left)and anotherto one myriad(an on theright;forexamplehereisa verticalcolumnfollowingfor
A HISTORY OF THE PRIME NUMBER THEOREM L. J. GOLDSTEIN, University of Maryland The sequence of prime numbers, which begins 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, has held untold fascination for mathematicians, both professionals and amateurs alike. The basic theorem whi
![Algorithms AppendixI:ProofbyInduction[Sp’16]](/img/13/98-induction.jpg)
