18.785: Analytic Number Theory, MIT, spring 2007 (K.S. Kedlaya)
The prime number theorem
Most of my handouts will come with exercises attached; see the web site for the due
dates. (For example, these are due February 14.)
There are likely to be typos in all of my handouts; it would be helpful if you could reportthese by email (including ones I point out in class).
Thanks to Ben Brubaker for filling in for me; I will be back February 12.

1

Euler’s idea: revisiting the infinitude of primes

To begin our story, we turn to Euler’s viewpoint on the fact, originally due to Euclid, that
there are infinitely many prime numbers. Euclid’s original proof was quite simple, andentirely algebraic: assume there are only finitely many primes, multiply them together, add
1, then factor the result.
Euler realized instead that a basic fact from analysis also leads to the infinitude of primes.
This fact is the divergence of the harmonic series
1+

1 1 1+ + +··· ,2 3 4which follows for instance from the fact thatNX
1n=1n≥

NXn=1

12dlog2 ne1≥ blog2 N c
2and the right side tends to ∞ as N → ∞. (We will usually want a more precise estimate;
see the exercises.) On the other hand, if there were only finitely many primes, then uniquefactorization of positive integers into prime powers would imply that
−1
 Y
∞X
1
1
11 Y
=
1+ + 2 +··· =,1−np pppn=1pwhich would give the equality between a divergent series and a finite quantity. Contradiction.
Euler’s idea turns out to be quite fruitful: the introduction of analysis into the studyof prime numbers allows us to prove distribution statements about primes in a much more
flexible fashion than is allowed by algebraic techniques. For instance, we will see in an
upcoming unit how Dirichlet adapted this idea to prove that every arithmetic progression
whose terms do not all share a common factor contains infinitely many primes.

2

Riemann’s zeta function

For the moment, however, let us turn to Riemann’s one paper in number theory, in which
he fleshes out Euler’s idea and fits it into the theory of complex functions of one variable.
1He considered the series
ζ(s) =∞
Xn−sn=1

for all s ∈ C with Re(s) > 1. Note that for Re(s) > 1, the series is absolutely convergent;moreover, it converges uniformly in any region of the form Re(s) ≥ 1 +  for  > 0. Consequently, it gives rise to an analytic function in the half-plane Re(s) > 1. The boundaryRe(s) = 1 is sometimes called the critical line.
In the domain of absolute convergence, we can also writeY
−11 − p−s,ζ(s) =pand this productconverges absolutely and uniformly forPRe(s) ≥ 1 +  for  > 0. (Reminder:Qa product i (1+ai ) converges absolutely if and only if i ai converges absolutely.) It follows
that ζ(s) 6= 0 for Re(s) > 1.
For future reference, we note that the product representation is sometimes more usefulin the form
Xlog ζ(s) =− log(1 − p−s )p=∞XXp−nspn=1n.

We now show that ζ extends somewhat beyond the domain of absolute convergence ofthe original series.
sTheorem 1. The function f (s) = ζ(s) − s−1on the domain Re(s) > 1 extends (uniquely)
to a holomorphic function on the domain Re(s) > 0. Consequently, ζ(s) is meromorphic onRe(s) > 0, with a simple pole at s = 1 of residue 1 and no other poles.

Proof. This is an easy application of one of the basic tools in this subject, Abel’s method ofpartial summation (or summation by parts, as in integration by parts). Namely,NX
n=1

an bn = aN +1 BN −NX(an+1 − an )Bn ,n=1

Bn =nXbi .

i=1We apply partial summation to ζ(s) by taking an = P
n−s and bn = 1, so that Bn = n. Rather,−s
we apply partial summation to the truncated sum N
n=1 n , and note that the error termaN +1 BN = (N + 1)−s N tends to 0 for Re(s) > 1. (Warning: in general, I am not going tobe nearly so verbose when applying partial summation. So make sure you understand thisexample!)2

With that said, we haveζ(s) =∞Xn(n−s − (n + 1)−s )n=1∞
X=s=sn

n=1Z∞

Z n+1

x−s−1 dxnbxcx−s−1 dx.

1We can thus write
f (s) = −sZ ∞{x}x−s−1 dx,

i=1

for {x} the fractional part of x; the integral converges absolutely for Re(s) > 0, and uniformlyfor Re(s) ≥  for any  > 0. This proves the claim.
We already know that ζ(s) cannot vanish for Re(s) > 1; to prove the prime number
theorem, we need to also exclude zeroes on the boundary of that half-plane.
Theorem 2 (Hadamard, de la Vallée-Poussin). The function ζ(s) has no zero on the lineRe(s) = 1.
Proof (Mertens). See exercises.
We will return to Riemann’s memoir, establishing more detailed properties of ζ, in a
subsequent unit.

3Towards the prime number theorem

Using the aforementioned properties of the zeta function, Hadamard and de la Vallée-Poussin
independently established the prime number theorem in 1897. We’ll follow here an argument
due to D.J. Newman; our presentation is liberally plagiarized from D. Zagier, Newman’s shortproof of the Prime Number Theorem, American Mathematical Monthly 104 (1997), 705–708.
For x ∈ R, writeXπ(x) =1p≤xϑ(x) =Xlog p.

p≤x

The prime number theorem then asserts thatπ(x) ∼3x.
log x

This is equivalent toϑ(x) ∼ x,because for any  > 0,
ϑ(x) ≤Xlog x = π(x) log xp≤xXϑ(x) ≥log x1− = (1 − )(π(x) + O(x1− )) log x.

x1− ≤p≤x

What we will prove is that the improper integral
Z ∞ϑ(x) − xdx(1)x2
1
converges; remember that this means that for every  > 0, there exists N such that fory, z ≥ N ,Z z
ϑ(x) − xdx < .
x2y(It is much easier to prove that these integrals are bounded; see exercises.) To then deduceϑ(x) ∼ x, suppose that there exists λ > 1 such that ϑ(x) ≥ λx for arbitrarily large x. Sinceϑ is nondecreasing, it then follows that for any such x,Z λx
Z λZ λx
λx − tλ−tϑ(t) − tdt ≥dt =dt > 0,
22ttt2x
1xcontradiction. Likewise, if there exists λ < 1 such that ϑ(x) ≤ λx for arbitrarily large x,then such x satisfyZ x
Z x
Z 1ϑ(t) − tλx − tλ−tdt ≤dt =dt < 0,22ttt2λxλxλcontradiction.

4The Tauberian argument

We have thus reduced the prime number theorem to the convergence of the integral (1);
we turn to this next. Consider the function Φ(s) = −ζ 0 (s)/ζ(s); from the log-productrepresentation for ζ, using partial summation as in Theorem 1, and substituting x = et , wefind∞XXX(log p)p−s +(log p)p−nsΦ(s) =p=sp

Z ∞

n=2

ϑ(x)x−s−1 dx + s1=sZ ∞0Z ∞1e−stt

ϑ(e ) dt + s

Z ∞04ϑ(x)∞
Xnx−ns−1n=2−3st!

2e−2st − eϑ(et ) dt(1 − e−st )2dx

Define the functions
f (t) = ϑ(et )e−t − 1
Φ(z + 1) 1g(z) =− ;z+1
zby the above,g(z) =Z ∞0f (t)e−zt

dt +Z ∞
02e−2(z+1)t − e−3(z+1)tϑ(et ) dt.
(1 − e−(z+1)t )2

Right now, we know that the integral defining g(z) makes sense for Re(z) > 0, but we will
deduce (1) (after substituting x = et ) and hence the prime number theorem if we can obtain
convergence of g(z) in the case z = 0. (Note that the second term converges absolutely forz = 0, so we only have to worry about the first term.)
The idea is to do this by leveraging complex function-theoretic information about Φ; thissort of operation is known as a Tauberian argument. To be precise, by what we know aboutζ, Φ(s) is meromorphic on Re(s) > 0, with a simple pole at s = 1 of residue 1 and no otherpoles in Re(s) ≥ 1. It follows that f and g satisfy the conditions of the following theorem.
Theorem 3 (Newman).
Let f : [0, +∞) → R be a bounded, locally integrable function,
R∞and define g(z) = 0 f (t)e−zt dt; note that this integral converges absolutely uniformly forRe(z) ≥  for any  > 0. Suppose
R ∞ that g(z) extends to a holomorphic function on a neighborhood of Re(z) ≥ 0. Then 0 f (t) dt exists and equals g(0).
RTProof (Zagier, after Newman). For T > 0, put gT (z) = 0 f (t)e−zt dt; each function gT isentire, and we want limT →∞ gT (0) = g(0).
For R large (but fixed until further notice), let C be the boundary of the region{z ∈ C : |z| ≤ R,Re(z) ≥ −δ}

for some δ = δ(R) > 0 chosen small enough that C lies inside the domain on which g isholomorphic. By the Cauchy integral theorem,Zz 2 dz
1zT(g(z) − gT (z))e1+ 2;(2)
g(0) − gT (0) =2πi C
Rz
namely, the only pole of the integrand is a simple pole at z = 0, so we simply pop out theresidue there.
To bound the right side of (2), we separate the contour of integration C into
C+ = C ∩ {z ∈ C : Re(z) ≥ 0}
C− = C ∩ {z ∈ C : Re(z) ≤ 0}.

5Remember that we assumed f is bounded; choose B > 0 so that |f (t)| ≤ B for all t. For
Re(z) > 0 with |z| = R, we have
Z ∞|g(z) − gT (z)| =f (t)e−zt dt
TZ ∞|e−zt | dt
≤BT

Be− Re(z)T=Re(z)andezTz21+ 2R2 Re(z)1= eRe(z)T.
z
R2Since the length of the contour is at most 2πR, the contribution over C+ to (2) is boundedin absolute value by
Be− Re(z)T Re(z)T 2 Re(z)2B1(2πR)e=.
22πRe(z)RROver C− , we separate the integral into integrals involving g and gT . Since gT is entire,
its integral over C− can instead be calculated over the semicircle C−0 = {z ∈ C : |z| =R, Re(z) ≤ 0}. Since for Re(z) < 0 we haveZ Tf (t)e−zt dt|gT (z)| =0Z T≤B|e−zt | dt−∞− Re(z)T=Be,| Re(z)|as above we bound this contribution to (2) by 2B/R.
Finally, we consider the contribution to (2) from g over C− ; we are going to show that
this contribution tends to 0 as T → ∞. By parametrizing the contour, we can writeZZ 1z 2 dz
1zT
1+ 2a(u)eb(u)T du,g(z)e=
2πi C−Rz0
where a(u) and b(u) are continuous, and Re(b(u)) < 0 for 0 < u < 1; the key point is thata does not depend on T , so as T → ∞ the integrand tends to 0 pointwise except at theendpoints. Since the integrands are all bounded, Lebesgue’s dominated convergence theorem
implies that the integral tends to 0 as T → ∞. (Again, I’m being more explicit with theanalysis than I will be in general.)
We conclude that4B;
lim sup |g(0) − gT (0)| ≤RT →∞since R can be chosen arbitrarily large, this yields the desired result.
6

You might be thinking at this point that if one knew g extended to a holomorphic functionon a region a bit larger than Re(s) R≥ 0, then maybe one could prove something about the∞rate of convergence of the integral 0 f (t) dt. In particular, if one can exclude zeroes of ζin some region beyond the line Re(s) = 1, one should correspondingly get a prime number
theorem with an improved error term. We will see that this is correct in a subsequent
unit, at least if we replace the approximation π(x) ∼ x/(log x) with Gauss’s approximation
π(x) ∼ li(x) (see exercises).

Historical aside: the Erdős-Selberg method
About 40 years after the original proof, Erdős and Selberg gave so-called elementary proofsof the prime number theorem, which do not use any complex analysis. The key step inSelberg’s proof is to give an elementary proof of the boundZ x
log log x
1|R(x/t)| dt + O x,(3)|R(x)| ≤log x 1log xwhere R(x) = ϑ(x) − x; I will probably say something about this result in the section onsieving.
Using (3) and the fact thatZ x
R(t)dt = O(1)(4)
t21(much easier than the convergence of the integral; see exercises), one then produces 0 < c < 1such that if there exists α > 0 such that |R(x)| < αx for x large, then also |R(x)| < αcxfor x large. I find this step somewhat unenlightening; if you must know the details, see A.
Selberg, An elementary proof of the prime number theorem, Annals of Math. 50 (1949),
305–313. Or see Chapter XXII of Hardy-Wright, or Nathanson’s Elementary Methods inNumber Theory.

Exercises
1. Prove that there exists a positive constant γ such thatnX
1i=1i− log n = γ + O(n−1 ),Rnby comparing the sum to a Riemann sum for 1 x1 dx. The number γ is called Euler’sconstant, and it is one of the most basic constants in analytic number theory. However,since it is defined purely analytically, we remain astonishingly ignorant about it; forinstance, γ is most likely irrational (even transcendental) but no proof is known.

7

2. Let d(n) denote the number of divisors of n ∈ N. Prove thatnXd(i) = n log n + (2γ − 1)n + O(n1/2 ),i=1

by estimating the number of lattice points in the first quadrant under the curve xy = n.
3. (Mertens) Fix t ∈ R nonzero. Prove that the function
Z(s) = ζ(s)3 ζ(s + it)4 ζ(s + 2it)
extends to a meromorphic function on Re(s) > 0. Then show that if s ∈ R and s > 1,
then log |Z(s)| = Re(log Z(s)) can be written as a series of nonnegative terms, so|Z(s)| ≥ 1.
4. Use the previous exercise to prove that ζ(s) has no zeroes on the line Re(s) = 1.
5. (Chebyshev) Prove thatYp ≤ 22nn<p≤2nby considering the central binomial coefficient

2n. Then deduce that ϑ(x) = O(x).
n

6. Let k be a positive integer. Prove that for any c > 0, if we write CR for the straightcontour from c − iR to c + iR, then(kZ
1xs ds1
1 − x1x≥1k!
=lim
R→∞ 2πi C s(s + 1) · · · (s + k)
00 ≤ x ≤ 1.
R(Hint: use a contour-shifting argument.)
7. (Gauss) Define the logarithmic integral function
Z xdtli(x) =.
2 log t(Warning: there is some disagreement in the literature about what lower limit ofintegration to use.) Prove that li(x) ∼ x/(log x), so that the prime number theorem isequivalent to π(x) ∼ li(x). In fact, Gauss noticed empirically, and we will prove later,that li(x) gives a somewhat better approximation to π(x) than x/(log x).

8. Using the identity
Xlog n =i=1 p:pi ≤xn≤x

prove that∞ X  Xx

X log pp≤xppi

log p,= log x + O(1),then deduce (4) by partial summation.

8