Preface

How many prime numbers are there less than a given number $n$? Needless to say, an exact answer, in the form of an expression involving $n$, is not available. However, it is reasonable to ask whether there is a simple formula that approximates (in some sense) to the answer for all $n$. This is a very natural question to ask, but the prime numbers appear to be distributed in a very irregular way, and the reader will be in good company if he or she cannot imagine how to begin to answer it. However, it has been answered: the ``prime number theorem" states that the required approximation is given by  $n/(\log n)$  (and even better by other related formulae). This theorem is without question one of the really great theorems of mathematics. It is the central topic of this book.

Let us place the theorem in the mathematical landscape. It belongs, in principle, to analytic number theory, which is concerned with the estimation of number-theoretic quantities. While it is clearly one of the best theorems in this subject, it occupies a somewhat off-centre position there because of the fact that its most accessible proof requires hardly any number theory, but quite a lot of analysis. For this reason, it does not fit very comfortably in books on analytic number theory, often appearing as an outlying topic. Meanwhile, if it is mentioned at all in a book on analysis, it will be in the role of a far-out application. Neither scenario does justice to such a great theorem! It is important and distinctive enough to be treated as a subject in its own right, rather than a fringe topic of either number theory or analysis. This is the rationale of the following pages. Our objective is to present an account in which the theorem, together with refinements, applications and results of a similar kind, is centre stage.

Mathematical problems are not usually solved by being considered in isolation. The reader may care to reflect on the combination of ideas that are used to evaluate $\pi$ (in the sense of finding an infinite series converging to it). The proof of the Prime Number Theorem is an unrivalled example of the harnessing of a number of seemingly unrelated ideas to achieve the desired result. As the machinery is assembled, it emerges that the original problem can be seen as one example of a more general problem. Strange as it may sound at this stage, our ``fundamental theorem" will take the form of a statement about the coefficients of a ``Dirichlet series", given facts about the function defined by the sum of the series. The prime number theorem will then appear as one case (admittedly the most prominent one) of the general theorem.

The topic is outstandingly suitable for the final year of an undergraduate programme in mathematics. The basic question is understandable from the outset, and clearly worth asking. The solution takes students on a trip through some spectacular (but not excessively difficult) mathematical scenery. They will encounter, perhaps for the first time, such unexpected gems as the Euler product, the various Dirichlet series derived from it, the corresponding convolutions, Möbius inversion, the inversion of Dirichlet series by suitable integrals, and the extension of the zeta function by a clever rewriting of the defining formula. They will also meet the Riemann hypothesis, commonly regarded as the most important unsolved problem in Mathematics.

As already indicated, the main prerequisites lie in analysis rather than number theory. More exactly, we presuppose standard undergraduate courses in both real and complex analysis, including for example Riemann integration and Cauchy's integral theorem. It is hoped that readers will appreciate seeing how the theorems of analysis, which they may have regarded as being very theoretical, can be applied to a ``real" problem - furthermore, to one for which their relevance would hardly have been suspected. Some care is taken to avoid dependence on concepts that are not really needed: in particular, no knowledge of Lebesgue integration is required. A number of topics on the border-line of what might be included in a first course on analysis, such as infinite products and multiplication of series, are treated in appendices.

Certain sections presuppose a very basic knowledge of number theory, but for the core proof of the prime number theorem, even this is not really necessary.

We make no attempt to contrast analysis and number theory, or to keep them separate. Indeed, part of the beauty of this subject is the way in which ideas from the two strands weave together and operate in partnership. A typical benefit is the avoidance of unmotivated definitions: for example, we can allow the Euler product to ``discover" the Möbius and von Mangoldt functions for us, rather than asking the reader to accept strange-seeming definitions out of the blue.

Our basic account of the prime number theorem is contained in the first three chapters. As already remarked, a wide assortment of ideas is encountered on the way. Each topic is accorded enough space to give the reader adequate feeling for them. Also, as stated, our agenda stretches to include ``results of a similar kind". As an example, consider the sum of $1/p$ for all primes $p \leq n$; the original problem is similar, but with 1 instead of $1/p$. It happens that the quantity just stated can be estimated much more easily, so our account includes this estimation although it is not actually needed to prove the prime number theorem. Several other estimations of number-theoretic functions (more exactly, their partial sums) are included in the same spirit. In this way, the book does in fact cover a certain amount of the core material of analytic number theory, without in any way aiming to give a comprehensive treatment of the subject. For the reader wanting a minimal path to the main theorem, all such deviations are identified.

In chapter 3, two alternative methods are given for the final derivation of the fundamental theorem. One is a slight variation of the traditional method based on Mellin inversion of Dirichlet series. The other is Newman's method, which has attracted considerable attention since its appearance in 1980. Readers can judge for themselves the relative merits of the two methods. Either method leads to a prior version of the theorem taking the form of an integral identity. From it one can simultaneously deduce limit results (such as the prime number theorem) and the corresponding series results which are also of considerable interest. This differs from the accounts found in most, if not all, existing books, which require a further stage of work to deduce the series versions from the limit ones (or conversely).

Having at length established the prime number theorem, we describe some applications and extensions, such as the estimation of the number of integers less than $n$ having $k$ prime factors.

The remaining three chapters deal with three mutually independent further topics. Chapter 4 is concerned with Dirichlet's theorem on the equal distribution of prime numbers among residue classes. It is beautiful to see how the notion of ``Dirichlet characters" enables us to adapt the original method for this purpose, with $L$-functions taking the place of the zeta function. This chapter requires a minimal knowledge of group theory.

No statement about approximation is complete without a discussion of accuracy. Chapter 5 addresses the problem of error estimates in the prime number theorem and similar results. The Mellin-inversion method adapts in a straightforward way to provide the classical error estimate (Newman's proof is less suitable for this purpose). Readers need to get this far to appreciate the significance of the Riemann hypothesis, which can now be presented as being equivalent to the much stronger error estimates that seem to be supported by numerical evidence.

Finally, chapter 6 contains an account of one version of the ``elementary" proof of the Prime Number Theorem by essentially number-theoretic methods, avoiding complex analysis.

Proofs and explanations are given at a level of detail suitable for final-year undergraduate students. Results (and only results) have a three-point numbering: $m.n.p$ is result $p$ of section $m.n$. The most important results are labelled ``theorems", and all others ``propositions", unless they are lemmas or corollaries. Exercises serve the usual dual purpose of giving the reader essential practice and of supplementing the information included in the text.

Most of the number-theoretic estimations are accompanied by numerical tables, which some readers may wish to check or supplement by their own computer calculations. These tables serve to put some ``flesh" on the results presented, and to illustrate the enormous variation between the rates of convergence in different cases.

To avert possible disappointment, it would be fair to mention one topic that is not included, the computation of very large prime numbers. This is currently a popular occupation, and it certainly utilises some interesting results of number theory. However, it has little relevance to the prime number theorem, so the reader who wants it must be directed elsewhere.

Acknowledgements. Special acknowledgement is due to my son Timothy Jameson for awakening my interest in this subject in the first place, for numerous comments and suggestions, and for contributing the computational elements, including most of the numerical tables and the sketch of the zeta function in section 3.1. I would also like to thank Gordon Blower, Robin Chapman and Ross Lawther for comments, corrections and suggestions, and Alison Woollatt of Cambridge University Press for her patient help and advice in achieving a very pleasing layout.