Prime number theorem
In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. For any positive real number x, define
The prime number theorem then states that
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
for x → ∞ (see big O notation). Here Li(x) is the offset logarithmic integral function.
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 |
4 ·1016 | 1,075,292,778,753,150 | 28,929,900,579,949 | 5,538,861 | 37.200 |
As a consequence of the prime number theorem, one get an asymptotic expression for the nth prime number p(n):
One can also derive the probability that a random number n is prime: 1/ln(n).
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.
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, if the Riemann hypothesis is true, the error term in the above relation can be improved to
The constant involved in the O-notation is unknown.
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 put paid 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.