Prime number theorem

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

Related Topics:
Number theory - Asymptotic - Prime number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 four prime numbers (2, 3, 5 and 7) are 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. Here ln(x) is the natural logarithm of x. Using Landau notation this result can be written as

Related Topics:
Prime counting function - Limit - Natural logarithm - Landau notation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:pi(x)simrac{x}{ln x}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An even better approximation, and an estimate of the error term, is given by the formula

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:pi(x)={ m Li} (x) + O left(rac{x}{ln(x)} e^{-rac{1}{15}sqrt{ln(x)}} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for x → ∞ (see big O notation). Here Li(x) is the offset logarithmic integral function. (See the table below.)

Related Topics:
Big O notation - Offset logarithmic integral

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An approximation for the nth prime number is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: p_n = n ln n + n ln ln n - n + rac {n ln ln n - 2n} {ln n} +

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Oleft( rac {n (ln ln n)^2} {(ln n)^2} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Here are some useful bounds on π(x):

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

pi(x)> rac{x}{ln x}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for x ≥ 17;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

pi(x)< 1.25506 rac{x}{ln x}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for x > 1;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac {x}{ln x + 2} < pi(x) < rac {x}{ln x - 4}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for x ≥ 55.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

As a consequence of the prime number theorem, one gets an asymptotic expression for the nth number pn

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:p_n sim n ln n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

n ln n + nlnln 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

One can also derive the probability that a random positive integer n is prime: 1/ln(n).

Related Topics:
Random - Positive integer

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Anton Felkel - Jurij Vega - Adrien-Marie Legendre - 1798 - Hadamard - De la Vallée Poussin - 1896 - Proof - Complex analysis - Riemann zeta function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Riemann zeta function - Riemann hypothesis - Number theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Helge von Koch in 1901 showed that more specifically, if and only if the Riemann hypothesis is true, the error term in the above relation can be improved to

Related Topics:
Helge von Koch - 1901 - If and only if

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: pi(x) = { m Li} (x) + Oleft(sqrt x ln (x) ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The constant involved in the O-notation is unknown.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In 1914 J. E. Littlewood proved that Li(x) is not always larger than π(x), see Skewes' number.

Related Topics:
J. E. Littlewood - Skewes' number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~