In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers.

Roughly speaking, the prime number theorem states that if you randomly select a number nearby some large number N, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. For example, near N = 10,000, about one in nine numbers is prime, whereas near N = 1,000,000,000, only one in every 21 numbers is prime.

In other words, the prime numbers "thin out" as one looks at larger and larger numbers, and the prime number theorem gives a precise description of exactly how much they thin out.

Statement of the theorem

---

Let π(x) be the prime counting function that gives the number of primes less than or equal to x, for any real number x. For example, π(10) = 4 because there are four prime numbers (2, 3, 5 and 7) less than or equal to 10. The prime number theorem then states that the limit of the quotient of the two functions π(x) and x / ln(x) as x approaches infinity is 1. Using Landau notation this result can be written as

$\backslash pi(x)\backslash sim\backslash frac\{x\}\{\backslash ln\; x\}$.

This does not mean that the limit of the difference of the two functions as x approaches infinity is zero.

Based on the tables by Anton Felkel and Jurij Vega, the theorem was conjectured by Adrien-Marie Legendre in 1796 and proved independently by Hadamard and de la Vallée Poussin in 1896. The proof used methods from complex analysis, specifically the Riemann zeta function.

The prime counting function in terms of the logarithmic integral

---

Carl Friedrich Gauss conjectured that an even better approximation to π(x) is given by the offset logarithmic integral function Li(x), defined by

$\backslash mbox\{Li\}(x)\; =\; \backslash int\_2^x\; \backslash frac1\{\backslash ln\; t\}\; \backslash ,\backslash mbox\{d\}t\; =\; \backslash mbox\{li\}(x)\; -\; \backslash mbox\{li\}(2).$

Indeed, this integral is strongly suggestive of the notion that the 'density' of primes around t should be 1/lnt. This function is related to the logarithm by the asymptotic expansion

$\backslash mbox\{Li\}(x)\; =\; \backslash frac\{x\}\{\backslash ln\; x\}\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{k!\}\{(\backslash ln\; x)^k\}$

= \frac{x}{\ln x} + \frac{x}{(\ln x)^2} + \frac{2x}{(\ln x)^3} + \cdots

So, the prime number theorem can also be written as π(x) ~ Li(x). The advantage of this formulation is that the error term is less. In fact, it follows from the proof of Hadamard and de la Vallée Poussin that

$\backslash pi(x)=\{\backslash rm\; Li\}\; (x)\; +\; O\; \backslash left(x\; \backslash mathrm\{e\}^\{-a\backslash sqrt\{\backslash ln\; x\}\}\backslash right)\; \backslash quad\backslash mbox\{as\; \}\; x\; \backslash to\; \backslash infty$

for some positive constant a, where O(…) is the big O notation. This has been improved to

$\backslash pi(x)=\{\backslash rm\; Li\}\; (x)\; +\; O\; \backslash left(x\; \backslash ,\; \backslash exp\; \backslash left(\; -\backslash frac\{A(\backslash ln\; x)^\{3/5\}\}\{(\backslash ln\; \backslash ln\; x)^\{1/5\}\}\; \backslash right)\; \backslash right).$

Because of the connection between the Riemann zeta function and π(x), the Riemann hypothesis has considerable importance in number theory: if established, it would yield a far better estimate of the error involved in the prime number theorem than is available today. More specifically, Helge von Koch showed in 1901 that, if and only if the Riemann hypothesis is true, the error term in the above relation can be improved to

$\backslash pi(x)\; =\; \{\backslash rm\; Li\}\; (x)\; +\; O\backslash left(\backslash sqrt\; x\; \backslash ln\; x\backslash right).$

The constant involved in the big O notation was estimated in 1976 by Lowell Schoenfeld: assuming the Riemann hypothesis,

for all x ≥ 2657. He also derived a similar bound for the Chebyshev prime counting function ψ:

for all x ≥ 73.2.

The logarithmic integral Li(x) is larger than π(x) for "small" values of x. However, in 1914, J. E. Littlewood proved that this is not always the case. The first value of x where π(x) exceeds Li(x) is around x = 10³¹⁶; see the article on Skewes' number for more details.

The issue of "depth"

---

In the first half of the twentieth century, some mathematicians felt that there exists a hierarchy of techniques in mathematics, and that the prime number theorem is a "deep" theorem, whose proof requires complex analysis. Methods with only real variables were supposed to be inadequate. G. H. Hardy was one notable member of this group.

The formulation of this belief was somewhat shaken by a proof of the prime number theorem based on Wiener's tauberian theorem, though this could be circumvented by awarding Wiener's theorem "depth" itself equivalent to the complex methods. However, Paul Erdős and Atle Selberg found a so-called "elementary" proof of the prime number theorem in 1949, which uses only number-theoretic means. The Selberg-Erdős work effectively laid rest to the whole concept of "depth", showing that technically "elementary" methods (in other words combinatorics) were sharper than previously expected. Subsequent development of sieve methods showed they had a definite role in prime number theory.

Avigad et al. (2005) contains a computer verified version of this elementary proof in the Isabelle theorem prover.

The prime number theorem for arithmetic progressions

---

Let $\backslash pi\_\{n,a\}(x)$ denote the number of primes in the arithmetic progression a, a + n, a + 2n, a + 3n, … less than x. Dirichlet and Legendre conjectured, and Vallée Poussin proved, that, if a and n are coprime, then

$$

\pi_{n,a}(x) \sim \frac{1}{\phi(n)}\mathrm{Li}(x), where φ(·) is the Euler's totient function. In other words, the primes are distributed evenly among the residue classes ^* modulo n with gcd (a, n) = 1.

Bounds on the prime counting function

---

The prime number theorem is an asymptotic result. Hence, it cannot be used to bound π(x).

However, some bounds on π(x) are known, for instance

The first inequality holds for all x ≥ 17 and the second one for x > 1.

Another useful bound is

$$

\frac {x}{\ln x + 2} < \pi(x) < \frac {x}{\ln x - 4} \quad\mbox{for } x \ge 55.

Approximations for the nth prime number

---

As a consequence of the prime number theorem, one gets an asymptotic expression for the nth prime number, denoted by p_n:

$p\_n\; \backslash sim\; n\; \backslash ln\; n.$

A better approximation is

$p\_n\; =\; n\; \backslash ln\; n\; +\; n\; \backslash ln\; \backslash ln\; n\; +\; \backslash frac\{n\}\{\backslash ln\; n\}\; \backslash big(\; \backslash ln\; \backslash ln\; n\; -\; \backslash ln\; n-\; 2\; \backslash big)$

+ O\left( \frac {n (\ln \ln n)^2} {(\ln n)^2}\right).

Rosser's theorem states that p_n is larger than n ln n. This can be improved by the following pair of bounds:

The left inequality is due to Pierre Dusart Pierre Dusart. "The kth prime is greater than k(ln k + ln ln k-1) for k>=2". Mathematics of Computation 68 (1999), pp. 411–415. and is valid for n ≥ 2.

Table of π(x), x / ln x, and Li(x)

---

Here is a table that shows how the three functions π(x), x / ln x and Li(x) compare:

{| class="wikitable" style="text-align: right"

! x π(x) π(x) − x / ln x Li(x) − π(x) x / π(x) 10 4 −0.3 2.2 2.500 102 25 3.3 5.1 4.000 10³ 168 23 10 5.952 10⁴ 1,229 143 17 8.137 10⁵ 9,592 906 38 10.425 10⁶ 78,498 6,116 130 12.740 10⁷ 664,579 44,158 339 15.047 10⁸ 5,761,455 332,774 754 17.357 10⁹ 50,847,534 2,592,592 1,701 19.667 10¹⁰ 455,052,511 20,758,029 3,104 21.975 10¹¹ 4,118,054,813 169,923,159 11,588 24.283 10¹² 37,607,912,018 1,416,705,193 38,263 26.590 10¹³ 346,065,536,839 11,992,858,452 108,971 28.896 10¹⁴ 3,204,941,750,802 102,838,308,636 314,890 31.202 10¹⁵ 29,844,570,422,669 891,604,962,452 1,052,619 33.507 10¹⁶ 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812 10¹⁷ 2,623,557,157,654,233 68,883,734,693,281 7,956,589 38.116 10¹⁸ 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420 10¹⁹ 234,057,667,276,344,607 5,481,624,169,369,960 99,877,775 42.725 10²⁰ 2,220,819,602,560,918,840 49,347,193,044,659,701 222,744,644 45.028 10²¹ 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332 10²² 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1,932,355,208 49.636 10²³ 1,925,320,391,606,818,006,727 37,083,513,766,592,669,113 7,236,148,412 51.939

The first column is sequence A006880 in OEIS; the second column is sequence A057835; and the third column is sequence A057752.

Analogue for irreducible polynomials over a finite field

---

There is an analogue of the prime number theorem that describes the "distribution" of irreducible polynomials over a finite field; the form it takes is strikingly similar to the case of the classical prime number theorem.

To state it precisely, let F = GF(q) be the finite field with q elements, for some fixed q, and let N_n be the number of monic irreducible polynomials over F whose degree is equal to n. That is, we are looking at polynomials with coefficients chosen from F, which cannot be written as products of polynomials of smaller degree. In this setting, these polynomials play the role of the prime numbers, since all other monic polynomials are built up of products of them. One can then prove that

$N\_n\; \backslash sim\; \backslash frac\{q^n\}\{n\}.$

If we make the substitution x = qⁿ, then the right hand side is just

$\backslash frac\{x\}\{\backslash log\_q\; x\},$

which makes the analogy clearer. Since there are precisely qⁿ monic polynomials of degree n (including the reducible ones), this can be rephrased as follows: if you select a monic polynomial of degree n randomly, then the probability of it being irreducible is about 1/n.

One can even prove an analogue of the Riemann hypothesis, namely that

$N\_n\; =\; \backslash frac\{q^n\}n\; +\; O\backslash left(\backslash frac\{q^\{n/2\}\}\{n\}\backslash right).$

The proofs of these statements are far simpler than in the classical case. It involves a short combinatorial argument, summarised as follows. Every element of the degree n extension of F is a root of some irreducible polynomial whose degree d divides n; by counting these roots in two different ways one establishes that

$q^n\; =\; \backslash sum\_\{d\backslash mid\; n\}\; d\; N\_d,$

where the sum is over all divisors d of n. Möbius inversion then yields

$N\_n\; =\; \backslash frac1n\; \backslash sum\_\{d\backslash mid\; n\}\; \backslash mu(n/d)\; q^d,$

where μ(k) is the Möbius function. (This formula was known to Gauss.) The main term occurs for d = n, and it is not difficult to bound the remaining terms. The "Riemann hypothesis" statement depends on the fact that the largest proper divisor of n can be no larger than n/2.

See also

---

• Abstract analytic number theory for information about generalizations of the theorem.
• Gaps between prime numbers
• Landau prime ideal theorem for a generalization to prime ideals in algebraic number fields.

References

---

• G.H. Hardy and J.E. Littlewood, "Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes", Acta Mathematica, 41(1916) pp.119-196.

• Jeremy Avigad, Kevin Donnelly, David Gray, and Paul Raff, A formally verified proof of the prime number theorem, e-print cs. AI/0509025 in the ArXiv, 2005.
• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 233 in section 8.8.
• Andrew Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial Journal, vol. 1, pages 12–28, 1995.
• Donald Knuth, The Art of Computer Programming, volume 2, section 4.5.4, exercise 36, ISBN 0-201-89684-2.
• Lowell Schoenfeld, Sharper bounds for the Chebyshev functions θ(x) and ψ(x), II, Mathematics of Computation, vol. 30, no. 134, pp. 337–360, 1976.
• Ivan Soprounov, A Short Proof of the Prime Number Theorem for Arithmetic Progressions, 1998.

External links

---

• Table of Primes by Anton Felkel.
• Prime formulas and Prime number theorem at MathWorld.
• How Many Primes Are There? and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.
• Tables of prime counting functions by Tomás Oliveira e Silva

Analytic number theory | Prime numbers | Mathematical theorems

مبرهنة الأعداد الأولية | Primzahlsatz | Teorema de los números primos | Théorème des nombres premiers | 소수 정리 | Teorema dei numeri primi | משפט המספרים הראשוניים | Prímszámtétel | 素数定理 | Tiurema dî nùmmura primi | Praštevilski izrek | Primtalssatsen | 素數定理