The prime number theorem gives an asymptotic form for the prime counting function 
,
(1808) suggested that for large n,
 |
(1) |
with 
(where B 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).
This function has 
as the asymptotic expansion
 |
 |
 |
(6) |
|
 |
(7) |
where 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 n, it had been checked and always found that 
. 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 n (Ball and Coxeter 1987; Havil 2003, p. 199). Skewes then showed that the first crossing of 
occurs before 
,
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 x, he showed that
 |
(9) |
(Havil 2003, p. 186). He also showed that if the limit
 |
(10) |
exists, then it is 1 (Havil 2003, p. 186).
Hadamard and Vallée Poussin independently proved the prime number theorem in 1896 by showing that the Riemann zeta function 
has no zeros of the form 
,
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 Erdos (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
 |
(11) |
(Hardy 1999, p. 58; Havil 2003, p. 187). Vallée Poussin (1899) showed that
 |
(12) |
for some constant a (Knuth 1997, p. 381), where O(x) is asymptotic notation. In 1901, Koch showed that if the Riemann hypothesis is true, then
 |
(13) |
(Havil 2003, p. 205), which can be written in the slightly weaker form
 |
(14) |
(Derbyshire 2004, pp. 237 and 242-244).
The error term in (14) has subsequently been improved to
 |
(15) |
(Walfisz 1963; Riesel 1994, p. 56; Knuth 1997, p. 382; Derbyshire 2004, p. 244). Ingham (1930) proved the prime number theorem using the identity of Ramanujan
 |
(16) |
where 
is the divisor function (Hardy 1999, pp. 59-60).
Riemann estimated the prime counting function with
 |
(17) |
which is a better approximation than for 
.
 |
(18) |
where 
is the Möbius function (Wagon 1991, p. 29). An even better approximation for small n (by a factor of 10 for 
) is the Gram series.
The prime number theorem is equivalent to either
 |
(19) |
or
 |
(20) |
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
 |
(21) |
for some value of c (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
 |
|
 |
(22) |
|
|
 |
(23) |
Bertrand's Postulate, Chebyshev Functions, Chebyshev's Theorem, Dirichlet's Theorem, Gram Series, Prime Counting Function, Riemann Function, Selberg's Formula, Skewes Number
Apostol, T. M. Introduction to Analytic Number Theory. New York: Springer-Verlag, 1976.
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 62-64, 1987.
Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, 1994.
Bochner. Math. Z. 37, 1-9, 1933.
Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Natick, MA: A. K. Peters, p. 64, 2003.
Courant, R. and Robbins, H. "The Prime Number Theorem." §1.2c in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 27-30, 1996.
Crandall, R. and Pomerance, C. Prime Numbers: A Computational Perspective. New York: Springer-Verlag, 2001.
Davenport, H. "Prime Number Theorem." Ch. 18 in Multiplicative Number Theory, 2nd ed. New York: Springer-Verlag, pp. 111-114, 1980.
de la Vallée Poussin, C.-J. "Recherches analytiques la théorie des nombres premiers." Ann. Soc. scient. Bruxelles 20, 183-256, 1896.
Derbyshire, J. "The Prime Number Theorem." Ch. 3 in Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, pp. 32-47, 2004.
Erdos, P. "Démonstration élémentaire du théorème sur la distribution des nombres premiers." Scriptum 1, Centre Mathématique, Amsterdam, 1949.
Gauss, C. F. Werke, Band 10, Teil I. p. 10, 1863.
Hadamard, J. "Sur la distribution des zéros de la fonction 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 Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, pp. 16, 27, and 28-33, 1999.
Hardy, G. H. and Wright, E. M. "Statement of the Prime Number Theorem." §1.8 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 9-10, 1979.
Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.
Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth. New York: Hyperion, 1998.
Ingham, A. E. "Note on Riemann's 
-Function and Dirichlet's L-Functions." J. London Math. Soc. 5, 107-112, 1930.
Ingham, A. E. The Distribution of Prime Numbers. London: Cambridge University Press, p. 83, 1990.
Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.
Landau, E. Vorlesungen über Zahlentheorie, Vol. 1. New York: Chelsea, pp. 79-96, 1970.
Landau, E. Berliner Sitzungsber., 514-521, 1932.
Landau, E. Handbuch der Lehre von der Verteilung der Primzahlen, 3rd ed. New York: Chelsea, 1974.
Legendre, A. M. Essai sur la Théorie des Nombres. Paris: Duprat, 1808.
Lehman, R. S. "On the Difference 
.
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 Introduction to Number Theory. New York: Wiley, pp. 275-299, 1951.
Riemann, G. F. B. "Über die Anzahl der Primzahlen unter einer gegebenen Grösse." Monatsber. Königl. Preuss. Akad. Wiss. Berlin, 671-680, Nov. 1859.
Reprinted in Das Kontinuum und Andere Monographen (Ed. H. Weyl). New York: Chelsea, 1972.
Riesel, H. "The Remainder Term in the Prime Number Theorem." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 6, 1994.
Rubinstein, M. and Sarnak, P. "Chebyshev's Bias." Experimental Math. 3, 173-197, 1994.
Selberg, A. "An Elementary Proof of the Prime Number Theorem." Ann. Math. 50, 305-313, 1949.
Shanks, D. "The Prime Number Theorem." §1.6 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 15-17, 1993.
Smith, D. E. A Source Book in Mathematics. New York: Dover, 1994.
Vallée Poussin, C. Mém. Couronnés Acad. Roy. Belgique 59, 1-74, 1899.
Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 25-35, 1991.
Walfisz, A. Ch. 5 in Weyl'sche Exponentialsummen in der neueren Zahlentheorie. Berlin: Deutscher Verlag der Wissenschaften, 1963.
Wiener, N. §19 et seq. in The Fourier Integral and Certain of Its Applications. New York: Dover, 1951.