The Prime Number Theorem

God may not play dice with the Universe, but something strange is going on with the prime numbers [Paul Erdös, paraphrasing Albert Einstein]

The prime numbers are the atoms of the natural number system. We recall that a prime number is a natural number greater than one that cannot be broken into smaller factors. Every natural number greater than one can be expressed in a unique way as a product of primes.

The primes have fascinated mathematicians for millennia. Euclid gave a remarkably simple proof that there are infinitely many primes. Yet, many questions about primes remain to be answered. A simple example is the set of prime pairs ${(p, p+2)}$ . All the evidence suggests that this set is infinite, but this has never been proved.

Primes occur with decreasing frequency as their magnitude grows. Since there are more potential divisors with increasing magnitude, it is unsurprising that the density of primes becomes less with increasing size. There are 25 primes below 100 (or 25%), 168 below 1000 (16.8%) and 78,498 below one million (or 7.8%). For one billion and one trillion, the corresponding perentages are 5.1% and 3.8%.

The Prime Number Theorem

The Prime Number Theorem (PNT) describes the asymptotic distribution of the prime numbers. We define the prime counting function ${\pi(n)}$ to be the number of primes less than or equal to ${n}$ . Thus, ${\pi(2)=1}$ , ${\pi(10)=4}$ and ${\pi(100)=25}$ . Then the proportion of primes less than ${n}$ is given by ${\pi(n)/n}$ . The PNT states that this is asymptotic to ${1/\log n}$ . So we can write the PNT as

$\displaystyle \lim_{n\rightarrow\infty}\left[ \frac{\pi(n)}{n/\log n} \right] = 1 \,.$

We also write ${\pi(n) \sim n/\log n}$ . The PNT is equivalent to saying that the ${n}$ -th prime number ${p_n}$ is given approximately by ${p_n\sim n\log n}$ . The relative error of this approaches zero as ${n}$ increases. However, the primes are not distributed evenly, as suggested by this formula, but appear to have an element of randomness. The pattern of primes is one of the most intriguing issues in all of mathematics.

Prime counting function for n <= 100.

In 1792 Carl Friedrich Gauss, then only 15 years old, found that the proportion of primes less that ${n}$ decreased apprximately as ${1/\log n}$ . Around 1795 Legendre noticed a similar logarithmic pattern of the primes, but it was to take another century before a proof emerged.

In a letter written in 1823 the Norwegian mathematician N H Abel described the distribution of primes as the most remarkable result in all of mathematics. In 1838, Dirichlet discovered an improved approximation to ${\pi(n)}$ using the (offset) logarithmic integral

$\displaystyle \pi(n) \approx\mathrm{Li}(n) = \int_2^n \frac{{\rm d}x}{\log x}$

This gives a significantly better estimate of ${\pi(n)}$ than the simple ratio ${n/\log n}$ .

Chebyshev and Riemann

The first person to prove that ${\pi(n)}$ has order of magnitude ${n/\log n}$ was the Russian, Pafnuty Chebyshev, in 1852. This enabled him to prove Bertrand’s Conjecture, that for any n>1, there is a prime number p such that n<p<2n.

In 1859, Bernhardt Riemann published a paper on the distribution of the primes. This was his only publication on this topic and was, like all his other contributions to mathematics, a result of singular importance. His major discovery was the link between the primes and the zeros of a complex function now called the Riemann zeta function

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

This is the main reason why the zeta function has such importance in number theory. Euler had earlier discovered the connection between the zeta function and prime numbers:

$\displaystyle \zeta(z) =\prod_{p\ {\rm prime}} \frac{1}{1-p^{-z}}$

Riemann’s work inspired two proofs of the PNT, by Frenchman Jacques Hadamard and Belgian Charles de la Vallée Poussin, discovered independently and published in the same year, 1896.

Elementary proof of the PNT

The early proofs depended essentially on the theory of complex variables. Elementary proofs, using only real numbers, were found later, but not before some fifty years had elapsed. The leading British mathematician G H Hardy speculated in 1921 that if an elementary proof of the PNT were ever found, it would be “time for the books to be cast aside and for the theory to be rewritten”.

The mathematical world was amazed when, in 1948, elementary (but difficult) proofs were announced by the Norwegian mathematician Atle Selberg and the Hungarian Paul Erdös. This was regarded as a sensation at the time. Unfortunately, a bitter dispute between the two mathematicians over priority followed the announcement.

Numerical Results

The function ${n/\log n}$ is asymptotic to the prime counting function ${\pi(n)}$ . In the figure below the function ${\pi(n)}$ is recognisable as it has a jump discontinuity at each prime number. The blue curve below it is ${n/\log n}$ , which gives a reasonable approximation to ${\pi(n)}$ . While the ratio tends to 1, the difference increases with ${n}$ .

$The thick black curve is the prime counting function {\pi(n)} for {2\le n\le 4000}. The blue curve below it is {n/\log n} and the red curve above is the logarithmic integral {\mathrm{Li}\,n}$

The thick black curve is the prime counting function \pi(n) for 2<n<4000. The blue curve below it is n/log n and the red curve above is the logarithmic integral Li n.

The upper curve (red) is the logarithmic integral Li n. Actually, we plot the asymptotic expansion

$\displaystyle \mathrm{li}(n) \approx \left(\frac{n}{\log n}\right)\sum_{k=0}^\infty \frac{k!}{(\log x)^k}$

and ${\mathrm{Li}\,(n)=\mathrm{li}(n)-\mathrm{li}(2)}$ , with ${\mathrm{li}(2)=1.045164}$ , which yields a significantly more accurate estimate of ${\pi(n)}$ . In fact, there are much more precise formulae, involving the Riemann zeta function, but they are relatively complicated to compute.

We note from the graph that ${\mathrm{Li}\,n > \pi(n)}$ . John Edensor Littlewood proved in 1914 that the expression ${\mathrm{Li}\,n -\pi(n)}$ changes sign infinitely often, but the first value of ${n}$ for which ${\pi(n) > \mathrm{Li}}$ is huge. Stanley Skewes,a student of Littlewood, found an upper limit for this:

$\displaystyle S = 10^{10^{10^{34}}}$

a truly enormous number. Since that time, the limit has been drastically reduced, to ${10^{316}}$ . This is still large and the actual value remains to be found.

ThatsMaths