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:
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
2. Take the limit as goes to
Use the limit above to deduce that
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 .
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 .