The prime number theorem gives an asymptotic form for the prime counting function , which counts the number of primes less than some integer . Legendre (1808) suggested that for large ,
(1)
|
with (where is sometimes called Legendre's constant), a formula which is correct in the leading term only,
(2)
|
(Nagell 1951, p. 54; Wagon 1991, pp. 28-29; Havil 2003, p. 177).
In 1792, when only 15 years old, Gauss proposed that
(3)
|
Gauss later refined his estimate to
(4)
|
where
(5)
|
is the logarithmic integral. Gauss did not publish this result, which he first mentioned in an 1849 letter to Encke. It was subsequently posthumously published in 1863 (Gauss 1863; Havil 2003, pp. 174-176).
Note that has the asymptotic series about of
(6)
| |||
(7)
|
and taking the first three terms has been shown to be a better estimate than alone (Derbyshire 2004, pp. 116-117).
The statement (4) is often known as "the" prime number theorem and was proved independently by Hadamard (1896) and de la Vallée Poussin (1896). A plot of (lower curve) and is shown above for .
For small , it had been checked and always found that . As a result, many prominent mathematicians, including no less than both Gauss and Riemann, conjectured that the inequality was strict. To everyone's surprise, this conjecture was refuted when Littlewood (1914) proved that the inequality reverses infinitely often for sufficiently large (Ball and Coxeter 1987; Havil 2003, p. 199). Skewes then showed that the first crossing of occurs before , a number now known as the Skewes number (Havil 2003, p. 199). The upper bound for the crossing has subsequently been reduced to . Lehman (1966) proved that at least reversals occur for numbers with 1166 or 1167 decimal digits.
Chebyshev put limits on the ratio
(8)
|
(Landau 1927; Nagell 1951, p. 55; Landau 1974; Hardy and Wright 1979, Ch. 22; Ingham 1990; Rubinstein and Sarnak 1994; Hardy 1999, p. 27; Derbyshire 2004, pp. 124 and 154). For large , he showed that
(9)
|
where is the logarithmic integral (Edwards 2001, p. 4), and
(10)
|
(Havil 2003, p. 186). He also showed that if the limit
(11)
|
exists, then it is 1 (Havil 2003, p. 186). Derbyshire's (2004, p. 124) statement that in 1850, Chebyshev also showed that cannot differ from by more than approximately 10% is therefore correct only for sufficiently large .
Hadamard and de la Vallée Poussin independently proved the prime number theorem in 1896 by showing that the Riemann zeta function has no zeros of the form , in the sense that no deeper properties of are required for the proof (Smith 1994, p. 128; Hardy 1999, pp. 58-60). Wiener (1951) allowed this somewhat vague statement to be interpreted literally (Hardy 1999, pp. 34 and 46), and this proof was simplified by Landau (1932) and Bochner (1933).
An elementary proof was found by Erdős (1949) and Selberg (1950) (Ball and Coxeter 1987, p. 63; Havil 2003, p. 188), although an unfortunate priority dispute over the joint work marred the otherwise beautiful proof (Hoffman 1998, pp. 39-41; Derbyshire 2004, p. 125). Versions of elementary proofs of the prime number theorem appear in final section of Nagell (1951) and in Hardy and Wright (1979, pp. 359-367). As noted by Hardy and Wright (1979, p. 9), although this proof is 'elementary,' "this proof is not easy."
Hadamard's proof depends on the simple trigonometric inequality
(12)
|
(Hardy 1999, p. 58; Havil 2003, p. 187). de la Vallée Poussin (1899) showed that
(13)
|
for some constant (Knuth 1998, p. 381), where is asymptotic notation. In 1901, Koch showed that if the Riemann hypothesis is true, then
(14)
|
(Havil 2003, p. 205), which can be written in the slightly weaker form
(15)
|
(Derbyshire 2004, pp. 237 and 242-244).
The error term in (15) has subsequently been improved to
(16)
|
(Walfisz 1963; Riesel 1994, p. 56; Knuth 1998, p. 382; Derbyshire 2004, p. 244). Ingham (1930) proved the prime number theorem using the identity of Ramanujan
(17)
|
where is the divisor function (Hardy 1999, pp. 59-60).
Riemann estimated the prime counting function with
(18)
|
which is a better approximation than for . Riemann (1859) also suggested the Riemann function
(19)
|
where is the Möbius function (Wagon 1991, p. 29). An even better approximation for small (by a factor of 10 for ) is the Gram series.
The prime number theorem is equivalent to either
(20)
|
or
(21)
|
where and are the Chebyshev functions. Chebyshev showed that the only possible limit of these expressions was 1, but was not able to prove existence of the limit (Hardy 1999, p. 28).
The Riemann hypothesis is equivalent to the assertion that
(22)
|
for some value of (Ingham 1990, p. 83; Landau 1974, pp. 378-388; Ball and Coxeter 1987; Hardy 1999, p. 26), as shown by Koch in 1901 (Havil 2003, p. 205). Some limits obtained without assuming the Riemann hypothesis are
(23)
| |||
(24)
|