# Prime number theorem

In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. It is useful to define the prime counting function π(x) as 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

[itex]\pi(x)\sim\frac{x}{\ln(x)}[itex]

where ln(x) is the natural logarithm of x. This notation means only that the limit of the quotient of the two functions π(x) and x/ln(x) as x approaches infinity is 1; it 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

[itex]\pi(x)={\rm Li} (x) + O \left(\frac{x}{\ln(x)} e^{-\frac{1}{15}\sqrt{\ln(x)}}\right)[itex]

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

Here are some bounds on π(x):

(1)

[itex]

\pi(x)> \frac{x}{\log x} [itex] for x > 16;

(2)

[itex]

\pi(x)< 1.25506 \frac{x}{\log x} [itex] for x > 1;

(3)

[itex]

\frac {x}{\log x + 2} < \pi(x) < \frac {x}{\log x - 4} [itex] for x > 54.

As a consequence of the prime number theorem, one gets an asymptotic expression for the nth prime number p(n):

[itex]p(n)\sim n\ln(n).[itex]

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

[itex]

n\ \log n < p(n) < n \log n + n \log \log n [itex] for n > 5.

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

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 Valle Poussin in 1896. The proof used methods from complex analysis, specifically the 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.

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

[itex] \pi(x) = {\rm Li} (x) + O\left(\sqrt x \ln (x)\right)[itex]

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.

 Contents

## The issue of "depth"

So-called "elementary proofs" of PNT are available that only use number-theoretic means. The first of these was provided partly independently by Paul Erdős and Atle Selberg in 1949. It was previously believed by some experts in the field that such proofs could not be found. That is, it was asserted, notably by G. H. Hardy, that complex analysis was essentially involved in PNT, leading to a conception of depth of theorems. Methods with only real variables were supposed to be inadequate. This was not a rigorous, logical concept (and indeed could not be), but was rather based on the feeling that such a hierarchy of techniques should exist (for reasons of aesthetics, presumably, in Hardy's case). The formulation of this belief was somewhat shaken by a proof of PNT based on Wiener's tauberian theorem, though this could be circumvented by awarding Wiener's theorem "depth" itself equivalent to the complex methods.

The Selberg-Erdős work effectively laid rest to the whole concept, 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.

## 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)
101 4 0  2 2.500
102 25 3  5 4.000
103 168 23  10 5.952
104 1,229 143  17 8.137
105 9,592 906  38 10.430
106 78,498 6,116  130 12.740
107 664,579 44,159  339 15.050
108 5,761,455 332,774  754 17.360
109 50,847,534 2,592,592  1,701 19.670
1010 455,052,511 20,758,029  3,104 21.980
1011 4,118,054,813 169,923,159  11,588 24.280
1012 37,607,912,018 1,416,705,193  38,263 26.590
1013 346,065,536,839 11,992,858,452  108,971 28.900
1014 3,204,941,750,802 102,838,308,636  314,890 31.200
1015 29,844,570,422,669 891,604,962,452  1,052,619 33.510
1016 279,238,341,033,925 7,804,289,844,392  3,214,632 35.810
1017 2,623,557,157,654,233
1018 24,739,954,287,740,860
1019 234,057,667,276,344,607
1020 2,220,819,602,560,918,840
1021 21,127,269,486,018,731,928
1022 201,467,286,689,315,906,290
1023 1,925,320,391,606,818,006,727

The first column is sequence A006880 (http://www.research.att.com/projects/OEIS?Anum=A006880) in OEIS; the second column is sequence A057835 (http://www.research.att.com/projects/OEIS?Anum=A057835); and the third column is sequence A057752 (http://www.research.att.com/projects/OEIS?Anum=A057752).

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

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy