A History of the Prime Number Theorem

A History of the Prime Number Theorem Author(s): L. J. Goldstein Reviewed work(s): Source: The American Mathematical Monthly, Vol. 80, No. 6 (Jun. - Jul., 1973), pp. 599-615 Published by: Mathematical Association of America Stable URL: . Accessed: 09/02/2013 20:07 Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at . . JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact support@. .

Mathematical Association of America is collaborating with JSTOR to digitize, preserve and extend access to The American Mathematical Monthly.



This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

A HISTORY OF THE PRIME NUMBER THEOREM

L. J. GOLDSTEIN, Universitoyf Maryland

The sequenceofprimenumbersw, hichbegins

2, 3,5,7, 11,13,17,19,23,29,31,37,

has held untoldfascinationfor mathematiciansb,oth professionalsand amateurs alike. The basic theoremwhichwe shalldiscussin thislectureis knownas theprime numbertheoremand allowsone to predict,at leastin grosstermst, he way in which theprimesaredistributedL.et x be a positiverealnumbera,nd let7r(x)= thenumber of primes 4,

fX dy J2 y l2y

'u' dy

x dy

J2

+ J2_xl-og2 y

(5)

<

-I 1

1/x log2

1 l (1)

[June-July

-

x

0 Vlogx '

wherewe have used the factthat 1/log2xis monotonedecreasingforx > 1. It is clearthat(4) and (5) showthat(2) and (3) are equivalentto one another.The advantage of theversion(3) is thatthefunction

5 ' Li(x) = fx

calledthe logarithmiicntegralp, rovidesa muchclosernumericalapproximationto ir(x)thandoes x /logx. This is a ratherdeep factand we shallreturnto it.

In thislectureI, shouldliketo explorethehistoryoftheideaswhichled up to the primenumbertheoremand to itsproof,whichwas notsupplieduntilsome 100years afterthefirsctonjecturewasmade.The historyoftheprimenumbertheoremprovides a beautifulexampleofthewayin whichgreatideas developand interrelatef,eeding upon one anotherultimatelyto yield a coherenttheorywhichrathercompletely explainsobservedphenomena.

The veryconceptionofa primenumbergoes back to antiquitya,lthoughitis not possibleto say preciselywhentheconceptfirstwas clearlyformulatedH. owever,a numberofelementaryfactsconcerningtheprimeswereknownto theGreeks.Let us citethreeexamples,all ofwhichappearin Euclid:

(i) (Fundamental Theorem of Arithmetic):Every positiveintegern can be writtenas a productof primes.Moreover,thisexpressionof n is unique up to a rearrangemenotf the factors.

(ii) Thereexistinfinitelmy anyprimes. (iii) The primes may be effectivelylisted using the so-called "sieve of Eratosthenes". We willnotcommenton (i), (iii) anyfurthers,incetheyarepartofthecurriculum of mostundergraduatceoursesin numbertheory,and henceare probablyfamiliar to mostofyou. However,thereis a proofof(ii) whichisquitedifferenftromEuclid's well-knownproofand whichis verysignificantto thehistoryof theprimenumber theorem.This proofis due to the Swiss mathematicianLeonhardEuler and dates fromthemiddleof the 18thcenturyI.t runsas follows: AssumethatPI, , PN is a completelistof all primes,and considertheproduct

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

1973]

A HISTORY OF THE PRIME NUMBER THEOREM

601

(6)

E ( P ) .H1(1+ p+T2+.. '

Sinceeverypositiveintegern can be writtenuniquelyas a productofprimepowers, everyunitfraction1/n appears in the formalexpansionof the product(6). For example,if n = p'l ... p'N then 1/n occursfrommultiplyingthe terms

1a/ll 1 /pa2, ..

lpa,

Thereforei,f R is any positiveinteger,

(7)

ru(I-' N

a-1

> E, 1 -1

Pi

R

1 In.

11=1

However,as R -+oo, thesum on therighthand side of (7) tendsto infinityw,hich contradicts(7). Thus, P1, *', PN cannotbe a completelistof all primes.We should maketwo commentsabout Euler's proof:First,it linkstheFundamentalTheorem ofArithmetiwc iththeinfinitudoef primes.Second,it uses an analyticfact,namely the divergenceof the harmonicseries,to concludean arithmeticresult.It is this latterfeaturewhich became the cornerstoneupon which much of 19th century numbertheorywas erected.

The firstpublishedstatementwhichcame close to the primenumbertheorem wasdue to Legendrein 1798[8]. He assertedthat7r(x)is oftheformx /(Alog x + B) forconstantsA and B. On thebasis of numericalwork,Legendrerefinedhis conjecturein 1808[9] byassertingthat

= logx + A(x)'

where A(x) is "approximately1.08366...". Presumablyb, y thislatterstatement, Legendremeantthat

lim A(x) = 1.08366.

x -I 00

It is preciselyin regardto A(x), whereLegendrewas in error,as we shallsee below. In his memoir[9] of 1808,LegendreformulatedanotherfamousconjectureL. et k and 1be integerswhichare relativelyprimeto one another.Then Legendreasserted thatthereexistinfinitelmy anyprimesof theform1+ kn(n = 0,1,2,3,...). In other words,if7rk,l(x)denotesthenumberofprimesp oftheform1+ knforwhichp < x, thenLegendreconjecturedthat

(8)

7tk,l(x) -+ oo as x -+ cc.

Actually,theproofof (8) by Dirichletin 1837 [2] providedseveralcrucialideas on how to approachtheprimenumbertheorem.

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

602

L. J. GOLDSTEIN

[June-July

AlthoughLegendrewas the firstpersonto publisha conjecturalformof the primenumbertheorem,Gauss had alreadydone extensiveworkon the theoryof primesin 1792-3.EvidentlyGauss consideredthetabulationofprimesas somesort of pastimeand amused himselfby compilingextensivetables on how the primes distributtehemselveisn variousintervalsof length1009.We have includedsome of Gauss' tabulationsas anAppendix.The firstable,excerptedfrom[3, p. 436], covers theprimesfrom1 to 50,000.Each entryin thetablerepresentasn intervalof length 1000.Thus,forexample,thereare 168primesfrom1 to 1000; 135from1001to 2000; 127 from3001 to 4000; and so forth.Gauss suspectedthatthedensitywithwhich primesoccuredin theneighborhoodoftheintegern was 1/logn,so thatthenumber of primesin theinterval[a, b) should be approximatelyequal to

Tb dx

Jalogx'

In the second set of tables,samplesfrom[4, pp. 442-3], Gauss investigatetshe distributionof primesup to 3,000,000and comparesthe numberof primesfound withtheabove integralT. he agreementis strikingF. or example,between2,600,000 and 2,700,000,Gauss found6762 primes,whereas

2,700.000

dx

-_

= 6761.332.

2,600,000 log x

Gauss neverpublishedhis investigationosn the distributionof primes.Nevertheless,thereis littlereasonto doubtGauss' claimthathe firstundertookhis work in 1792-93, well beforethe memoirof Legendrewas written.Indeed, thereare severalotherknownexamplesof resultsof thefirstrankwhichGauss proved,but nevercommunicatedto anyoneuntilyearsafterthe originalworkhad been done. This was the case, forexample,withthe ellipticfunctionsw, hereGauss preceded Jacobi,and withRiemanniangeometryw,hereGauss anticipatedRiemann.The only informationbeyondGauss' tablesconcerningGauss' workin the distributionof primesis containedin an 1849letterto theastronomerEncke. We have includeda translationof Gauss' letter.

In his letterGauss describeshis numericalexperimentasnd his conjectureconcerningi(x). Thereare a numberof remarkablefeaturesof Gauss' letter.On the secondpage of theletterG, auss compareshis approximationto 2r(x),namelyLi(x), withLegendre'sformula.The resultsare tabulatedat the top of the second page andGauss' formulayieldsa muchlargernumericaelrrorI.n a verypresciensttatement, Gauss defendshis formulaby notingthat althoughLegendre'sformulayieldsa smallererror,therateofincreaseof Legendre'serrortermis muchgreaterthanhis own. We shallsee below thatGauss anticipatedwhatis knownas the "Riemann hypothesis."Anotherfeatureof Gauss' letteris thathe castsdoubt on Legendre's assertionabout A(x). He assertsthatthenumericalevidencedoes not supportany conjectureabout the limitingvalue of A(x).

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

1973]

A HISTORY OF THE PRIME NUMBER THEOREM

603

Gauss' calculationsare awesome to contemplate,since theywere done long beforethe days of high-speedcomputers.Gauss' persistenceis most impressive. However,Gauss' tablesare not error-freeM. y student,EdwardKorn,has checked Gauss' tablesusingan electroniccomputerand has founda numberof errors.We includethe correctedentriesin an appendix. In spite of these (remarkablyfew) errors,Gauss' calculationsstillprovideoverwhelminegvidencein favoroftheprime numbertheorem.Modern studentsof mathematicshould take note of the great care withwhichdata was compiledby such giantsas Gauss. Conjecturesin those days wererarelyidle guesses.They wereusuallysupportedby piles of laboriously gatheredevidence.

The nextstep towarda proofof the primenumbertheoremwas a step in a completelydifferendtirectiona,nd was takenbyDirichletin 1837[2]. In a beautiful memoir,Dirichletproved Legendre'sconjecture(8) concerningthe infinitudeof primesin an arithmeticprogressionD. irichlet'sworkcontainedtwo radicallynew ideas, whichwe should discussin some detail.

Let @,, denotetheringof residueclassesmodulo n, and let En denotethegroup ofunitsof 7n. Then En is theso-called"group ofreducedresidueclassesmodulon" and consistsofthoseresidueclassescontainingan elementrelativelyprimeto n. If k is an integerl,et us denotebyk itsresidueclass modulo n. Dirichlet'sfirstbrilliant idea was to introducethecharacterosf the groupEn; thatis, thehomomorphismosf

En into the multiplicativgeroup Cx of non-zerocomplexnumbers.If xis such a charactert,henwe mayassociatewithxa function(also denotedx) fromthesemi-

group Z* of non-zerointegersas follows:Set

y(a) = Z(d) if (a, n) = 1

0 otherwise.

Then it is clearthatx: Z* C' and has thefollowingproperties:

(i) Z(a + n) = (a),

(ii) ,(aa') =&)%

(iii) Z(a) = 0 if (a, n) # 1,

(iv) x(i)

= 1.

A functionx: E* ?x satisfyin(gi)-(iv) is called a numericaclharactermodulo n.

Dirichlet'smainresultaboutsuchnumericacl haracterswas the so-calledorthogonalityrelationsw, hichassertthe following:

(A)

E Z(a) = 0(n) if xis identically1,

a

0 otherwise,

wherea runsovera completesystemofresiduesmodulon;

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

604

L. J. GOLDSTEIN

[June-July

(B)

X(a) = 4(n) ifa -1 (mod n),

x

0 otherwise,

whereXrunsoverall numericalcharactersmodulon. Dirichlet'sideas gave birthto themoderntheoryof dualityon locallycompactabelian groups.

Dirichiet'ssecondgreatidea wasto associateto eachnumericaclharactermodulo n and each real numbers > 1, thefollowinginfiniteseries

(9)

L(s,X)=- xn( s

n=1

It is clearthattheseriesconvergesabsolutelyand representas continuousfunction fors > 1. However,a more delicateanalysisshows thatthe series(9) converges (althoughnotabsolutelyf) ors > 0 and representas continuousfunctionof s in this semi-infinitinetervalprovidedthatX is not identically1. The functionL(s,x) has come to be called a DirichletL-function.

Note thefollowingfactsabout L(s,X): FirstL(s,X)has a productformulaofthe form

(10)

L(s, X) =

(1- F) )

(s > 1),

p

p

wheretheproductis takenoverall primesp. The proofof(10) is verysimilarto the argumentgivenabove in Euler's proofof theinfinityof primenumbers.Therefore, by (10),

(11)

logL(s,X) = - E log(1 - ps) ~~~~~~~~p

p m=1ImpMs

Dirichlet'sidea in provingthe infinitudeof primesin the arithmeticprogression a, a + n, a + 2n,*, (a, n) = 1, was to imitate,somehow,Euler's proofof the infinitudoefprimes,bystudyingthefunctionL(s,X)fors near1. The basic quantityto consideris

XE (a)-'logL(s,X) = - E

X(a) X(Pm)

(12)

X

p m=1 X

mm

= -

Ed Y. ms X(a) X(pm),

p m=1 mpjXa

wherewe have used (11). Let a* be an integersuch thataa* =_1 (mod n). Then X(a*) = X(a)' l by (i)-(iv). Moreover,

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

1973]

A HISTORY OF THE PRIME NUMBER THEOREM

605

(13)

However,a*pm (13), we have

X Z(a) 'x(pm)= z X(a*ptm)

x

x

= +(n) if a*pm = 1 (modn)

O otherwise.

1 (mod n) is equivalentto pm_ a (mod n). Thereforeb,y(12) and

(14)

Z x(a)llogL(s,Z)-40(n)

x

Thus, finally,we have

~z~~~~~~mm~-p=immPMs

pnma(mod n)

- 4>(xn()n S Z(a)logL(s,Z)-

p

m=2 MmP Mp

(15)

pm = a(modnt)

-

p5

(s >).

p _a(mod n)

From(15), we immediatelysee thatin orderto provethatthereare infinitelmy any primesp _ a (mod n),itis enoughto showthatthefunction

S1

p_a(mod n) P

tendsto + co as s approaches1 fromtheright.But it is fairlyeasyto see thatas s-+1+, the sum

1

p p m-amod

I

Ms

m-2 ItP

n)

remainsbounded.Thus,it sufficetso showthat

01

Z (a)-

0(n) ,

log L(s, Z) - + oo

(s

+ )

However,ifXodenotesthecharacterwhichis identically1, thenit is easyto see that

Zn)o(a) 1L(s,Zo)-- + so as s> 1+ .

Thereforei,t is enoughto showthatif x#Zo, thenlog L(s,x) remainsboundedas

s 1+1. We have alreadymentionedthatL(s, X)is continuousfors > 0 if X#Xo. Thereforei,t sufficetso show thatL(1, X)#0. And thisis preciselywhatDirichlet

showed.

This content downloaded on Sat, 9 Feb 2013 20:07:45 PM All use subject to JSTOR Terms and Conditions

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download