1.1 Counting prime numbers

As the reader surely knows, prime numbers are those that have no positive divisors except 1 and the number itself. The special significance of prime numbers is due to the following fact, which we will assume known:

Every positive integer is expressible as a product of primes. The expression is unique if the primes are listed in increasing order.

Effectively, this means that the primes are the basic ``atoms" in the multipicative system of integers. (If $n$ is itself prime, we are regarding it as a ``product" of one prime, itself.)

The first result on the number of primes was already known to Euclid. Here it is, with Euclid's beautiful proof.

Proposition 1.1.1. There are infinitely many prime numbers.

Proof. Choose finitely many primes $p_1, p_2, \ldots , p_n$. We will show that they cannot constitute the total set of primes. Consider the number

$$N = p_1 p_2 \ldots p_n +1.$$

Then $N$ is not a multiple of any $p_j$, since it clearly leaves remainder 1 when divided by $p_j$. However, by the above statement, $N$ is expressible as a product of primes. Let $q$ be any one of these. Then $q$ is a further prime, different from all the $p_j$, which therefore indeed fail to constitute the total set of primes. $\Box$

(Note: This reasoning actually shows a bit more: if the primes are listed as $p_1, p_2, \ldots$ in increasing order, then  $p_{n+1} \leq p_1 p_2 \ldots p_n +1$.)

With this settled, it is natural to ask how many prime numbers there are up to any given number. This is the topic of our study. Let us give it some notation:

$$\pi (x) = \mbox{the number of primes not greater than $x$}.$$

This notation is standard in number theory; there is no real danger of confusion with the number $\pi$. It will suit our purposes to regard $\pi (x)$ as a function of a real variable $x$. As such a function, it is, of course, constant between primes and jumps by 1 at each prime.

The first impression given by the sequence of primes

$$2, 3, 5, 7, 11, \ldots , 101, 103, 107, 109, 113, 127, \ldots , 163, 167, 173, 179, \ldots$$

is one of extreme irregularity. There are bunches, gaps and relatively uniform stretches. It would appear to be a daunting task to find a simple expression that approximates to $\pi (x)$ for all large enough $x$. The only simple observation is that the primes tend to become more sparse as one goes on. However, an examination of the numerical values of $\pi (x)$ suggests that a reasonable approximation is given by  $x/(\log x)$, a considerably better one by

$$\frac {x}{\log x -1},$$

and a still better one by the ``logarithmic integral", defined as follows:

$$\mbox{li}(x) = \int_2^x \frac{1}{\log t}\; dt.$$

Some of these numerical values are as follows (given to the nearest integer).

$$\begin{array}{rrrrr} n & \pi(n) & \frac{n}{\log n} & \frac{n... ...0,000,000 & 664,579 & 620,421 & 661,459 & 664,918 \end{array}$$

By the year 1800, long before the age of computers, mathematicians had performed the remarkable feat of calculating these figures by hand up to $n = 400,000$. In the age of computers, it has of course become much easier to calculate values of $\pi (x)$. Some readers will be interested in doing so on their own computer: various methods for this are discussed in Appendix F.

Let us formulate precisely the conjecture suggested by these figures. Given two functions $f(x)$, $g(x)$, both tending to infinity as $x \to \infty$, we write

$$f(x) \sim g(x) \qquad \mbox{as } x \to \infty$$

to mean that

$$\frac{f(x)}{g(x)} \to 1 \qquad \mbox{as } x \to \infty .$$

Our conjecture is the statement

$$\pi (x) \sim \mbox{li}(x) \qquad \mbox{as } x \to \infty .$$

In fact, as we will show in section LI,

$$\frac{x}{\log x} \sim \frac{x}{\log x -1} \sim \mbox{li}(x) \qquad \mbox{as } x \to \infty ,$$

so at this level it is equivalent to state the conjecture using any of the three functions.

The conjecture is in fact true. The statement $\pi (x) \sim \mbox{li}(x)$ is called the prime number theorem. It is indisputably one of the most celebrated theorems in mathematics. Ways of proving it, together with related results, more precise versions and generalizations, form the subject of this book. Of course, numerical evidence of the above type can never constitute a proof of the general statement.

An informal interpretation of the theorem is that the ``average density" of primes around a large number $x$ approximates to $1/(\log x)$, or that the ``probability" of $n$ being prime is (in some sense) $1/(\log n)$.

Let us return to the historical trail. Legendre, in 1798, postulated the approximations $x/(\log x)$ and  $x/(\log x -1)$. He suggested (wrongly) that an even better approximation would be given by $x/(\log x - A)$, with $A = 1.0836$. Meanwhile, Gauss proposed li$(x)$. It seems that Gauss recorded his conjecture around 1793 (at the age of 14 !), but did not communicate it to anyone until 1849.

The search for a proof remained one of the main areas of mathematical endeavour during the rest of the 19th century. In 1850, a giant stride was made by Chebyshev, who showed, by essentially number-theoretic methods, that there are constants $c,C$ (not very far from 1) such that

$$c\; \mbox{li}(x) \leq \pi (x) \leq C\; \mbox{li}(x)$$

for all large enough $x$. However, no refinement of his methods seemed to offer any hope of proving the desired limit.

A completely different approach was proposed by Riemann in 1859. His starting point was a remarkable identity already discovered by Euler in 1737, expressing the ``zeta function"

$$\zeta (s) = \sum_{n=1}^\infty \frac{1}{n^s}$$

as an infinite product involving the primes. Riemann considered this as a function of a complex variable $s$, defined by the above formula for Re $s > 1$. He showed how to extend the definition of the function to the rest of the complex plane, and outlined a programme showing how, if certain properties of the extended zeta function could be established, the prime number theorem would follow. His paper was a bold imaginitive leap; it was hardly an obvious idea to use the theorems of complex analysis to count prime numbers! However, Riemann was not able to justify all his steps, and one of them, the ``Riemann hypothesis", has remained unsolved to this day, regarded by many as the most important unsolved problem in mathematics.

It was not until 1896 that Riemann's programme was successfully completed. It was then done so independently by the French mathematician Jacques Hadamard and the Belgian Charles-Jean de la Vallée Poussin. They were able to by-pass the Riemann hypothesis and establish other properties of the zeta function that were sufficient for the purpose. Hadamard lived until 1963 (aged 97) and de la Vallée Poussin until 1962 (aged 95): their mathematical labours cannot have done any harm to their health!

Further variations and modifications of their methods were developed by Mertens, Landau and others, but to this day the simplest, and most powerful, proofs of the prime number theorem rely on the zeta function and complex analysis, as suggested by Riemann. In chapters 1-3, we present a version (and a variant) which benefits from a century of ``tidying up", but which still recognisably owes its existence to Riemann.

After the successful outcome of Riemann's programme, it remained a matter of great interest to ask whether the theorem could after all be proved by number-theoretic methods, without complex analysis. Some leading mathematicians expressed strong doubts that this could be done. However, it was eventually achieved in 1949, again independently by two people, A. Selberg and P. Erdös. Proofs of this sort are called ``elementary" as opposed to ``analytic". However, ``elementary" does not mean ``simple"! Half a century later, known proofs of this sort are still more complicated than analytic ones, and less successful in providing error estimates or in delivering other theorems of the same sort. We present a version of the ``elementary" proof in chapter 6.

Exercises

1. Let $n \geq 1$ and let $E = \{ 30n + r: 0 \leq r \leq 29 \}$. For which values of $r$ is $30n + r$ not a multiple of 2,3 or 5 ? By considering the possible positions of multiples of 7, show that $E$ contains at most seven primes (seven cases, no short cuts!).

2. Show that for any $n \geq 2$, there is eventually a gap of length at least $n$ between successive primes. [Hint: consider $n! + 2$ or $p_1p_2 \ldots p_n +2$.]

3. Let the primes be listed, in order, as $p_1, p_2, \ldots \;$. Use Euclid's proof to show by induction that  $p_n \leq 2^{2^{n-1}}$  for each $n$. Deduce that

$$\pi (x) \geq \frac{\log \log x}{\log 2}.$$