The prime number theorem states that the number of primes less than is approximately . Proofs of the PNT tend to be easy to follow step by step, but I can never remember them once I step away from the page. I think I finally got the outline of the standard analytic proof to stick, so I’m going to record it here before I lose it:

**1. Play around with .**

Define the zeta function by

.

Notice that as . We have Euler’s factorization:

so

.

Here is the Von Mangoldt function: if and otherwise. Since has a first order pole at , we have . So

.

With a little care, we can see that the is an analytic function of . So

exists.

**2. Take the limit as goes to **

Use the limit above to deduce that

converges.

This is in red because it is really hard. Maybe I’ll say something about it later. But, intuitively, it makes sense.

**Added in response to a comment of E. Kowalski** As I discuss a little below, the fear is that might behave like , for some . In this case, we could not take the limit. If this exact problem occurred, then would have a pole at . A very clever trick shows that this function has no poles with real part . The challenge is to show that the absence of poles means that the limit is permissible.

**3. Add up the partial sums**

Fix . So there is an such that, for , we have . Also, there must be some absolute bound for any sum of the form .

So

.

Since is arbitrary, this shows that . You are more likely to see this quoted as .

**4. Clean up**

Standard techniques turn into . In other words,

.

The terms are negligible for .

A few notes below the fold:

**Getting stronger bounds: **

Take the equation , where is analytic near , and differentiate it times. We get that exists; that converges; that ; and that .

**UPDATE** I should probably add a warning that I have neither seen this done nor checked the hardest part myself. It seems like the obvious way to proceed.

Even without the difficult step 2, the fact that exists is already powerful. In shows that, if any result of the form

holds, then the must all be .

**Converting sums to integrals: **

Instead of using as our example of a function with the correct pole at , we could use . So we would say, for example, that

exists. This make a few things a little nicer, and a few things a little uglier.

A more dramatic change is to use measures to make all sums into integrals. Let be the atomic measure which is times a delta function at . So we can write statements like “ converges”. This is very helpful in writing the proof of step 2 cleanly. The reader who is scared by measures can use the Riemann-Stieltjes integral , where .

If even that is too scary, one can integrate by parts and talk about . This is how Newman’s proof is usually written, but I think it obscures more than it reveals.

**The oscillatory fear**

The key step is going from the fact that exists (for a certain measure ) to the conclusion that converges.

The fear here is that could be something like for some constant . Then , where . The limit as exists, but does not converge. **ADDED** Notice that, in this case, would have a pole at .

A professional analytic number theorist would say that the “really hard” step 2 is in fact the proof of the PNT (on the other hand, the post is titled “The easy parts of the proof…”, so it’s fair).

More seriously, there isn’t that much complex analysis in those steps, so the effect of (potential) zeros of zeta(s) on the line with real part 1 is invisible, although any such zero (however far away) would imply that the PNT is false.

I did want to write about the easy steps :). For one thing, until I started thinking this through, I didn’t understand why it was considered hard to go from to , but easy to go from to the “” statement that . Now I see that the value of is hiding not just in the summand, but also in the error bound.

However, I’ve added some edits to try to get a little deeper.

what are other theorems with “elementary” proofs that are worth memorizing? perhaps, the Wigner Semi-Circle theorem.

Small typo: in the end of Step 1, the lower-case lambda should be upper case.

The way I think of this is that there is a hierarchy of averages that one can perform on a quantity f(n) (such as the von Mangoldt function), from rough (and sharply localised) averages to smooth (and slowly decaying) averages. The rougher averages convey more information than the smoother ones, but by the same token are harder to control. (Note that one can typically write a smooth average efficiently as an average of rough averages, but not vice versa, since averaging only makes things smoother, not rougher. There are _inefficient_ tricks to express rough averages in terms of smooth averages, such as Polya-Vinogradov completion of sums or analytic continuation, but these tend to not be terribly good for the goal of obtaining good bounds.)

Various oscillations in the primes (notes in the “music of the primes”, if you will), are picked up by sufficiently rough averages but are damped out to insignificance in sufficiently smooth averages. So as one gets to rougher and rougher averages, one needs to deal with more and more oscillatory scenarios. The first one, as pointed out above, is that resonates with , which would destroy the prime number theorem; then there are weaker resonances such as for some , which would leave the prime number theorem intact but destroy the Riemann hypothesis.

Where complex analysis comes in is in showing that these sinusoidal conspiracies are the

onlythings that cause the primes to behave non-uniformly, so that once one eliminates those, one has good control on the distribution of the primes. Other types of oscillation are not compatible with the meromorphic nature of the zeta function. One can pick up an echo of this important complex-analytic fact in the elementary approaches to the prime number theorem via the Selberg symmetry formula as discussed in a recent blog post of mine, but the complex method (with its well-developed theory of zeroes, factorisation, etc.) is far slicker in doing this.David – Thank you for writing this helpful post. I have had the same experience that you have (where the outline of the proof doesn’t stick despite having been through proof several times) and I appreciate you taking the time to write it down for reference.