Chapter 6
An ``elementary" proof of the prime number theorem

Both proofs of the prime number theorem given in chapter 3 are ``analytic" in the sense that they rely fundamentally on theorems of complex analysis, following the design set out by Riemann. As we have seen, these methods ultimately prove the theorem very satisfactorily, exhibiting it as one case of a wider family of theorems. However, one would surely expect to be able to prove a theorem about integers without resorting to concepts like holomorphic complex functions, seemingly far removed from pure number theory. Such a proof, reverting to the legacy of Chebyshev, would be called ``elementary". Ideas from real analysis, such as integral estimation for series, would be allowed (the theorem is, after all, a statement about a limit), but not those from complex analysis. Defined in this way, the term ``elementary" is not to be confused with ``simple"!

This question attracted a great deal of interest after the original proof had become known. G.H. Hardy, a leading analytic number theorist of the time, predicted in 1921 that such a proof was ``extraordinarily unlikely", but that if one were to be found, it would involve such basic new ideas that it would ``cause the whole theory to be rewritten".

An ``elementary" proof was finally discovered by A. Selberg and P. Erdös in 1948. They worked in cooperation, but eventually published different versions separately, both based on a formula discovered by Selberg. The history of their on-off collaboration is somewhat tangled (for one account, see [Nath]). Many alternative versions and refinements of the proof have appeared since then. Nearly all make use of Selberg's formula in one way or another. For a survey of these various methods, see [Dia]. A method of Daboussi, not based on Selberg's formula, is described in [Ten&MF]. Even after fifty years of tidying up, one would not describe any of these methods as ``simple". Furthermore, they have not really transformed the theory in the way that Hardy predicted. They do not present the prime number theorem as part of a wider scheme of theorems, and have not, as yet, been developed to give error estimates as strong as that of de la Vallée Poussin. So it may be said that both parts of Hardy's prediction have proved to be wrong!

In this chapter, we give an account of one of these versions. With minor simplifications, it follows a method set out by N. Levinson in 1969. The work can be divided into two parts, with quite distinct characters, which we present in two separate sections. The goal is to prove the prime number theorem in the form $\psi (x)/x \to 1$. The main prerequisites, all to be found in our chapters 1 and 2, are Chebyshev's upper estimate, Möbius inversion, the identity  $\Lambda *u = \ell$ and the boundedness of  $\sum_{n \leq x} \Lambda (n)/n - \log x$.