“Analytic Number Theory: The Prime Number Theorem.”
This is the most beautiful thing in mathematics to me
--------------------------------------------------------------------------------
The search for the order of magnitude of two arithmetical functions related to primes led to one of the most profound theorems in number theory, the prime number theorem. If pn denotes the nth prime number and (n) denotes the number of primes in the interval from 1 to n, Euclid's theorem on the infinitude of primes guarantees that (n) as n . It is natural to ask how pn and (n) grow as functions of n for large n. Irregularities in the distribution of primes and the lack of a simple formula for determining primes suggest that precise answers to these questions might be difficult or impossible to obtain. It seems astonishing to learn that answers can be obtained, and they are remarkably simple: For large n, the nth prime pn grows as n log n, whereas (n) grows as n/log n. Each of these statements implies the other, and each is known as the prime number theorem. More precisely, the prime number theorem can be stated in two equivalent forms:
and
These relations are written more simply as (n) n/log n and pn n log n and are expressed verbally by saying that (n) is asymptotic to n/log n and that pn is asymptotic to n log n, respectively.
The first form was conjectured independently by Gauss and by Legendre around 1800, but neither provided proof. Gauss was led to his conjecture by examining a table of primes 106. He calculated (n) simply by counting the number of primes in the interval from 1 to n. This is similar to the exercise done in an earlier section, in which primes were counted in blocks of 1,000 consecutive integers. However, if the blocks are not of equal length but are allowed to grow by a factor of 100, the following values of (n) and of the ratio n/ (n) are obtained:
The table shows that the ratio n/ (n) grows very slowly compared to n. As the exponents on the powers of 10 increase by 2, the ratio n /(n) seems to increase by about 4.6, or 2.3 times the exponent of 10. The exponent of 10 is the logarithm of n to the base 10, so the table indicates that n/ (n) grows at about 2.3 times this logarithm. But 2.3 times the logarithm of a number to base 10 is approximately equal to the natural logarithm of that number. Comparison of the natural logarithm log n with the ratio n/ (n) reveals the following values:
This remarkable agreement between log n and n/ (n) suggests that their ratio approaches 1 as n . Gauss, Legendre, and many other eminent mathematicians of the early 19th century tried unsuccessfully to prove this conjecture. The first step toward a proof was made in 1851 by Chebyshev, who showed that if (n)log n/n has a limit as n , then this limit must equal 1.
In 1859 Bernhard Riemann attacked the problem with a new method, using a formula of Euler relating the sum of the reciprocals of the powers of the positive integers with an infinite product extended over the primes. Euler's product formula, devised in 1737, states that, for every real s > 1,
where the product runs through all the primes. Euler derived this formula by writing each factor on the right as an infinite geometric series
with x = pn-s. When all these series are multiplied together and the denominators are arranged in increasing order, the result is the series on the left (because of the fundamental theorem of arithmetic).
Riemann replaced the real variable s in Euler's product formula with a complex number and showed that the distribution of prime numbers is intimately related to properties of the function (s) defined by the series (now called the Riemann zeta function). Riemann came close to proving the prime number theorem, but not enough was known during his lifetime about the theory of functions of a complex variable to complete the proof successfully.
Thirty years later the necessary analytic tools were at hand, and in 1896 Jacques-Salomon Hadamard and Charles Jean de la Vallee-Poussin independently proved the first form of the prime number theorem. The proof was one of the great achievements of analytic number theory. Subsequently, new proofs were discovered, including an elementary proof found in 1949 by Paul Erdos and Atle Selberg that makes no use of complex function theory.
The second form of the prime number theorem is easily deduced from the first form by taking logarithms of both members of equation (1) and then removing a factor log n to obtain
Because log n , the factor multiplying log n must tend to zero. The quotient log log n/log n also tends to zero, hence
This relation, multiplied by equation (1), yields
Now replace n by the nth prime, pn, in this equation. Then (pn) = n, and the equation becomes
which implies equation (2). Equation (1) can also be deduced from (2), so the two statements are equivalent.
Each of the following statements involving the Mobius function is also equivalent to the prime number theorem:
The prime number theorem is important not only because it makes an elegant and simple statement about primes and has many applications but also because much new mathematics was created in the attempts to find a proof. This is typical in number theory. Some problems, very simple to state, are often extremely difficult to solve, and mathematicians working on these problems often create new areas of mathematics of independent interest. Another example is the creation of algebraic number theory as a result of work on the Fermat conjecture.