# Prime number theorem

In number theory, the **prime number theorem** (**PNT**) describes the approximate, asymptotic distribution of the prime numbers. Roughly, the prime number theorem states that the density of primes numbers around *n* is approximately 1 / ln(*n*), where ln(*n*) denotes the natural logarithm of *n*.

## Contents

## 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)\sim\frac{x}{\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 1798 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

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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Li}(x) = \int_2^x \frac1{\ln t} \,\mbox{d}t. }**

This function is related to the logarithm by

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Li}(x) = \frac{x}{\ln x} \sum_{k=0}^\infty \frac{k!}{(\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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)={\rm Li} (x) + O \left(x \mathrm{e}^{-a\sqrt{\ln x}}\right) \quad\mbox{as } x \to \infty}**

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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)={\rm Li} (x) + O \left(x \, \exp \left( -\frac{A(\ln x)^{3/5}}{(\ln \ln x)^{1/5}} \right) \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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x) = {\rm Li} (x) + O\left(\sqrt x \ln x\right). }**

The constant involved in the remainder term is unknown.

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^{316}; 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 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.

## 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

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{x}{\ln x} < \pi(x) < 1.25506 \, \frac{x}{\ln x}. }**

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

Another useful bound is

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac {x}{\ln x + 2} < \pi(x) < \frac {x}{\ln x - 4} \quad\mbox{for } x \ge 55. }**

## Approximations for the *n*th prime number

An approximation for the *n*^{th} prime number is

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_n = n \ln n + n \ln \ln n - n + \frac {n \ln \ln n - 2n} {\ln n} + O\left( \frac {n (\ln \ln n)^2} {(\ln n)^2}\right) }**

As a consequence of the prime number theorem, one gets an asymptotic expression for the *n*^{th} number *p*_{n}

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_n \sim n \ln n.}**

This can be stated more precisely as a pair of bounds:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\ \ln n + n\ln\ln n - n < p_n < n \ln n + n \ln \ln n }**for*n*≥ 6.

The left inequality is due to Pierre Dusart (1999) 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:

x |
π(x) |
π(x) − x/ln(x) |
Li(x) − π(x) |
x/π(x) |
---|---|---|---|---|

10^{1} |
4 | 0 | 2 | 2.500 |

10^{2} |
25 | 3 | 5 | 4.000 |

10^{3} |
168 | 23 | 10 | 5.952 |

10^{4} |
1,229 | 143 | 17 | 8.137 |

10^{5} |
9,592 | 906 | 38 | 10.430 |

10^{6} |
78,498 | 6,116 | 130 | 12.740 |

10^{7} |
664,579 | 44,159 | 339 | 15.050 |

10^{8} |
5,761,455 | 332,774 | 754 | 17.360 |

10^{9} |
50,847,534 | 2,592,592 | 1,701 | 19.670 |

10^{10} |
455,052,511 | 20,758,029 | 3,104 | 21.980 |

10^{11} |
4,118,054,813 | 169,923,159 | 11,588 | 24.280 |

10^{12} |
37,607,912,018 | 1,416,705,193 | 38,263 | 26.590 |

10^{13} |
346,065,536,839 | 11,992,858,452 | 108,971 | 28.900 |

10^{14} |
3,204,941,750,802 | 102,838,308,636 | 314,890 | 31.200 |

10^{15} |
29,844,570,422,669 | 891,604,962,452 | 1,052,619 | 33.510 |

10^{16} |
279,238,341,033,925 | 7,804,289,844,392 | 3,214,632 | 35.810 |

10^{17} |
2,623,557,157,654,233 | |||

10^{18} |
24,739,954,287,740,860 | |||

10^{19} |
234,057,667,276,344,607 | |||

10^{20} |
2,220,819,602,560,918,840 | |||

10^{21} |
21,127,269,486,018,731,928 | |||

10^{22} |
201,467,286,689,315,906,290 | |||

10^{23} |
1,925,320,391,606,818,006,727 |

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

## Poussin's result

Poussin proved that

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_{a,b}(x) \sim \frac{1}{\phi(a)}\mathrm{Li}(x) }**

holds where **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_{a,b}(x)}**
is the number of primes in the progression an+b ,and φ(n) is the Euler's totient function.
This was conjectured by Dirichlet and Legendre.

## See also

## References

- 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. - Donald Knuth,
*The Art of Computer Programming*, volume 2, section 4.5.4, exercise 36, ISBN 0-201-89684-2.

## External links

- Table of Primes by Anton Felkel.
- Prime formulas and Prime number theorem at MathWorld.
- Prime number theorem on PlanetMath.
- How Many Primes Are There? by Chris Caldwell, University of Tennessee at Martin.

de:Primzahlsatz es:Teorema de los números primos fr:Théorème des nombres premiers it:Teorema dei numeri primi he:משפט המספרים הראשוניים hu:Prímszámtétel ja:素数定理 scn:Tiurema dî nummura primi sl:Praštevilski izrek sv:Primtalssatsen zh:素數定理