Chapter 1

Foundations

In this chapter, we assemble a number of ideas and techniques that will eventually be fitted together to achieve our aim. Their only common feature is that they are needed to prove the prime number theorem, so the chapter has no single unifying theme. However, each section of the chapter is devoted to a very clearly defined topic. Some of these ideas are analytic, others number-theoretic, but there would be no advantage in trying to keep the two strands apart: they reinforce each other in a fruitful partnership.

Our objective is to find a formula that approximates $\pi (x)$, the number of primes not greater than x. We start, in section 1.1, by identifying some candidates as suggested by numerical evidence. We also give a brief account of the long history leading to the successful proof of the prime number theorem.

The term ``arithmetic function" is used for a sequence defined using number-theoretic properties in some way. A great deal of number theory consists of the study of such functions. Now we can express $\pi (x)$ as the partial sum  $\sum_{n \leq x} u_P(n)$, where $u_P$ is the arithmetic function defined as follows:

$$u_P(n) = \left\{ \begin{array}{ll} 1 & \mbox{if $n$\ is prime,} \\ 0 & \mbox{otherwise}. \end{array} \right.$$

Typically, arithmetic functions appear to be very irregular, but this is smoothed out by addition and one can hope to find an estimate for their partial sums. This identifies our problem as one of a certain type.

We go on to describe two essential techniques for rewriting and estimating discrete sums, Abel summation and integral estimation. Both are used constantly in all that follows.

After this, we are in a position to describe the first real progress towards the prime number theorem, achieved by Chebyshev in 1850. Chebyshev recognized that an estimation of $\pi (x)$ can be deduced from an estimation of $\theta (x) = \sum_{p \in P[x]}\log p$, (where P[x] denotes the set of primes not greater than x), and showed that the latter sum can be estimated by a comparatively short (but ingenious) argument. In this way, he demonstrated that $\pi (x)$ lies between $cx/\log x$ and $Cx/\log x$ for two constants c and C.

Finally, we introduce a concept that will permeate the rest of our study to the extent that it could serve as a subtitle for this book. A Dirichlet series is a series of the form $\sum_{n=1}^\infty a(n)/n^s$, in which s is a complex variable. The case a(n) = 1 defines the Riemann zeta function. Every arithmetic function has a corresponding Dirichlet series; multiplication of the series corresponds to ``convolution" of the arithmetic functions. Our ``fundamental theorems" in chapter 3 will derive information about the partial sums of a(n) from the nature of the function defined by the series, with the prime number theorem appearing as a special case.