V.26 The Prime Number Theorem and the Riemann Hypothesis
How many prime numbers are there between 1 and n? A natural first reaction to this question is to define π(n) to be the number of prime numbers between 1 and n and to search for a formula for π(n). However, the primes do not have any obvious pattern to them and it has become clear that no such formula exists (unless one counts highly artificial formulas that do not actually help one to calculate π(n)).
The standard reaction of mathematicians to this kind of situation is to look instead for good estimates. In other words, we try to find a simply defined function f(n) for which we can prove that f(n) is always a good approximation to π(n). The modern form of the prime number theorem was first conjectured by GAUSS [VI.26] (though a closely related conjecture had been made by LEGENDRE [VI.24] a few years earlier). He looked at the numerical evidence, which suggested to him that the “density” of primes near n was about 1/log n, in the sense that a randomly chosen integer near n would have a probability of roughly 1/log n of being a prime. This leads to the conjectured approximation of n/log n for π(n), or to the slightly more sophisticated approximation
The function defined by the integral on the right-hand side is called li(n) (which stands for the “logarithmic integral” of n). Some care is needed in interpreting the integral because log 1 = 0, but one can avoid this problem by integrating from 2 to n instead, which changes the function by just an additive constant.
The prime number theorem, proved independently by HADAMARD [VI.65] and DE LA VALLÉE POUSSIN [VI.67] in 1896, states that li(n) is indeed a good approximation to π(n), in the sense that the ratio of the two functions tends to 1 as n tends to infinity.
This result is considered one of the great theorems of all time, but it is by no means the end of the story. The proofs of Hadamard and de la Vallée Poussin used the RIEMANN ZETA FUNCTION [IV.2 §3] ζ(s). The Riemann zeta function is defined to be 1-s + 2-s + 1-s + . . . whenever s is a complex number with real part greater than 1; this expression defines a HOLOMORPHIC FUNCTION [I.3 §5.6], which can be extended (by analytic continuation) to a function that is holomorphic on the entire complex plane, except for a pole at 1. This function has zeros, known as “trivial zeros,” at all negative even integers. Riemann proved that the prime number theorem was equivalent to the assertion that the only “nontrivial zeros” were inside the critical strip, which consists of those complex numbers with real part strictly between 0 and 1. He also formulated what is often held to be the most important unsolved problem in mathematics, now known as the Riemann hypothesis: that in fact the nontrivial zeros all have real part equal to 
. This assertion about the zeros of the zeta function has been shown to be equivalent to a stronger form of the prime number theorem, which states not just that π(n)/li(n) tends to 1, but even that |π(n) - li(n)| ≤ 
log n for every n ≤ 3. Since li(n) is around n/log n, which is much bigger than log n, this would mean that the error |π(n) - li(n)| was extremely small compared with π(n) or li(n) themselves.
The importance of the Riemann hypothesis goes far beyond its consequences for the distribution of primes: hundreds of statements in number theory have been shown to follow from it. This is particularly true when one considers generalizations of the Riemann hypothesis that apply to a wider class of L-FUNCTIONS [III.47]. For example, analogues of the Riemann hypothesis for Dirichlet L-functions imply very good estimates for the distribution of primes in arithmetic progressions, from which many further consequences follow.
The prime number theorem and the Riemann hypothesis are discussed in more detail in ANALYTIC NUMBER THEORY [IV.2 §3].