Image: Christian Albrecht Jensen, 1840 (public domain)The prime number theorem in plain words
There are 4 primes below 10, 25 below 100, 168 below 1000, 1229 below 10,000, 9592 below 100,000, and 78,498 below a million. Write π(x) for the number of primes up to x; the function has nothing to do with the circle constant, and the notation is Landau's from 1909. The primes get rarer, that much is visible in the list, and the question is at what rate. The prime number theorem is the answer: π(x) is close to x divided by the natural logarithm of x, and the ratio of the two tends to 1 as x grows.
What "close to" means
For x = 1,000,000 the formula gives 10⁶ / ln 10⁶ = 10⁶ / 13.8155 = 72,382, against the true 78,498, an error of 8 percent. For x = 10⁹ it gives 48,254,942 against 50,847,534, an error of 5 percent. The error shrinks slowly, and never to zero; the theorem says only that the ratio π(x) / (x / ln x) tends to 1, which allows a difference that grows, as long as it grows slower than x / ln x. Gauss's own version of the guess is better. He proposed the logarithmic integral li(x), the integral of 1 / ln t from 2 to x, which is what you get by assuming that a number near t is prime with probability 1 / ln t and adding up. For a million it gives 78,628, off by 130; for a billion it gives 50,849,235, off by 1,701. The relative error of li(x) at a billion is 0.003 percent.
The theorem is usually stated with x / ln x because that is the simplest form; li(x) is the form that matters, and the size of the difference π(x) - li(x) is the subject of the Riemann hypothesis.
Gauss at fifteen
In a letter of 24 December 1849 to the astronomer Encke, Gauss recalled that in 1792 or 1793, as a boy, he had been given a table of logarithms with a list of primes at the back, and had amused himself by counting the primes in blocks of a thousand. He noticed that the density near x behaved like 1 / ln x and wrote the integral down. He went on counting for the rest of his life: in the same letter he reports having counted the primes up to three million, in his spare quarter-hours, and compares the count with the integral to the last digit. He published none of it. Legendre, independently, published in 1798 the formula x / (A ln x - B) with constants fitted to tables, and in 1808 gave A = 1 and B = 1.08366. The famous constant is a fit, and the true second-order correction is 1, not 1.08366; Legendre's tables did not reach far enough to see the difference.
Chebyshev, halfway
Pafnuty Chebyshev in St Petersburg proved in 1852 that if the ratio π(x) / (x / ln x) has a limit at all, the limit is 1, and that in any case the ratio stays between about 0.92 and 1.11 for all large x. His proof is elementary in the technical sense: it uses no complex numbers and no limits beyond the ones in the definition. The key is the central binomial coefficient, the middle entry of row 2n of Pascal's triangle, which is at most 4ⁿ and is divisible by every prime between n and 2n. Comparing the size of the coefficient with the size of the product of those primes gives bounds on how many there can be. As a by-product he proved Bertrand's postulate, that there is always a prime between n and 2n, which Bertrand had checked up to three million in 1845 and could not prove. Unit 12 of the masterclass gives Chebyshev's proof in full and Erdős's short version of the Bertrand argument.
1896
The theorem itself was proved in 1896, twice, by Jacques Hadamard in France and Charles de la Vallée Poussin in Belgium, working independently and using the same tool: the Riemann zeta function, extended into the complex plane as Riemann had done in 1859. The decisive step in both proofs is that the zeta function has no zeros on the line where the real part of s equals 1. From that fact the theorem follows, and in 1899 de la Vallée Poussin showed that the error term is less than x times a decaying function, which is more than the theorem says and less than the Riemann hypothesis would give. The connection between zeros of a function of a complex variable and the count of primes is the subject of Unit 13 of the masterclass, and it is the reason the analytic tier of the program exists.
For half a century it was believed that no proof could avoid complex analysis. In 1949 Atle Selberg and Paul Erdős found an elementary proof, starting from an identity of Selberg's about sums over primes, and the question of who deserved the credit led to a quarrel that is still written about. The elementary proof is longer and harder to follow than the analytic one, and most courses teach the analytic one, but its existence settled a question about the nature of the theorem.
What it means in practice
The theorem says that a number of size N, chosen at random, is prime with probability about 1 / ln N. For a 100-digit number, ln N is about 230, so about one in 230 such numbers is prime, and one in 115 of the odd ones. For a 300-digit number it is one in 690. That is why generating an RSA key, which needs two 300-digit primes, takes well under a second: pick random odd numbers, run a fast primality test, and expect a prime after a few hundred tries. The article on primality tests covers the testing side.
The theorem also says how big the n-th prime is: about n ln n. The millionth prime is 15,485,863, and 10⁶ × ln 10⁶ = 13,815,511, a fair estimate; the billionth prime is 22,801,763,489, against 20,723,265,837 from the formula. Andrew Booker's Nth Prime Page, in the resources of Unit 12, computes exact values of both π(x) and the n-th prime up to a trillion, and the formula can be checked against them at any scale.
What it does not say
The theorem is a statement about averages. It says nothing about where the next prime is, or about gaps, or about primes of special forms. The average gap between primes near x is ln x, about 230 near 10¹⁰⁰, but individual gaps can be far larger (there are stretches of a million consecutive composite numbers, as the factorial construction of Unit 16 shows) and as small as 2, which is the twin prime question. The theorem is the baseline against which every finer question about the primes is measured, and the finer questions, from the Riemann hypothesis to bounded gaps, are what the last four units of the masterclass are about.
Unit 12 of the masterclass presents the data, Gauss's and Legendre's guesses, Chebyshev's theorem with its proof, Mertens' theorems on sums over primes, and the statement of the prime number theorem with its history; the proof, through the zeta function, is Unit 13.


