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
 |  | ![Li(x)+O[xe^(-(lnx)^(1/2)/15)]](/images/equations/PrimeNumberTheorem/Inline46.svg) |
(23)
|
 |  | ![Li(x)+O[xe^(-0.009(lnx)^(3/5)/(lnlnx)^(1/5))].](/images/equations/PrimeNumberTheorem/Inline49.svg) |
(24)
|
et ses conséquences arithmétiques (')."
Bull. Soc. math. France 24, 199-220, 1896.Hardy, G. H.
"The Proof of the Prime Number Theorem" and "Second Approximation
of the Proof." §2.5 and 2.6 in 
-Function
and Dirichlet's 
-Functions."
J. London Math. Soc. 5, 107-112, 1930.Ingham, A. E.
." Acta Arith. 11, 397-410, 1966.Littlewood,
J. E. "Sur les distribution des nombres premiers." Comptes Rendus
Acad. Sci. Paris 158, 1869-1872, 1914.Lu, W. C. "On
the Elementary Proof of the Prime Number Theorem with a Remainder Term." Rocky
Mountain J. Math. 29, 979, 1999.Nagell, T. "The Prime
Number Theorem." Ch. 8 in