Counting what has no formula

The primes below a hundred are 2, 3, 5, 7, 11 and twenty more, and nothing about that list suggests a pattern. There are gaps of two and gaps of eight, runs that crowd together and runs that thin out, and no expression is known that produces the nth entry. Ask instead how many entries there are below a bound and the subject changes completely.

That figure is the whole rung in one picture. The quantity being estimated is $\pi(x)$, the number of primes not exceeding $x$: 25 below a hundred, 168 below a thousand, 1,229 below ten thousand. It jumps by one at every prime and is flat everywhere else, so it is as irregular as the primes themselves — and it is nevertheless predictable, from a smooth function with no primes in it anywhere.

The staircase, and the first guess #

Drawn against the smooth estimate, the count looks like a straight answer to a question nobody asked.

Gauss made the guess at fifteen, reading tables of primes and noticing that the density near a number $x$ — the proportion of numbers near there that are prime — falls off like $1 / \ln x$. That is a statement about local density, and integrating it gives an estimate of the total count.

The crude version of that integration replaces the density by its value at the top and multiplies: $\pi(x) \approx x / \ln x$. The careful version keeps the integral,

$$\operatorname{li}(x) = \int_2^x \frac{dt}{\ln t},$$

which weights the early stretches by their own higher density. Both are the same guess and they are not equally good, which is what the first figure exists to say: the crude version is out by eleven per cent at twenty thousand and the integral by two hundredths of one per cent.

The prime number theorem, proved in 1896 independently by Hadamard and de la Vallée Poussin, says that the ratio of $\pi(x)$ to either estimate tends to one. That is the weakest statement compatible with the picture, and the interesting mathematics is entirely in the difference between the two.

Where the density comes from, and why the obvious argument is wrong #

The density $1 / \ln x$ can be guessed from the sieve, and the guess is instructive precisely because it comes out wrong.

A number near $x$ is prime when no prime up to $\sqrt{x}$ divides it. Treating divisibility by different primes as independent, the chance of surviving is

$$\prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p}\right),$$

and Mertens’ theorem says that product is asymptotic to $e^{-\gamma} / \ln(\sqrt{x})$, where $\gamma$ is the constant relating the harmonic sum to the logarithm. That evaluates to $2e^{-\gamma} / \ln x$, or about $1.12 / \ln x$ — twelve per cent too large.

The heuristic is therefore wrong, and it is worth being precise about why, because it is the same failure that makes many sieve arguments delicate. Divisibility by different primes is very nearly independent, but the errors do not cancel; they accumulate over the whole range of primes being sieved by, and the accumulated discrepancy is exactly the factor $2e^{-\gamma}$. Getting the constant right needs the analytic proof, and no amount of care with the elementary argument produces it.

That is a good reason to distrust a density argument that gives the right shape. The shape here is right and the constant is not, and only the shape is what the elementary reasoning is entitled to.

The two estimates are not close to each other #

If both estimates have ratio tending to one, why prefer the integral? Because ratio tending to one is a weak statement, and the difference between the two is enormous.

$$\operatorname{li}(x) - \frac{x}{\ln x} \approx \frac{x}{(\ln x)^2},$$

which grows without bound. At $x = 10^{6}$ the two estimates differ by about five thousand, and the count is within a hundred and thirty of the integral. So the crude estimate is wrong by an amount that grows, while its ratio to the truth still tends to one — the two statements are compatible, and confusing them is the standard error in reading an asymptotic result.

The general lesson is worth carrying out of number theory: an asymptotic statement about a ratio controls relative error and says nothing at all about absolute error. The same trap appears wherever a rate is quoted — a bound that shrinks in proportion to the quantity being measured can still be growing.

The error, and the one question nobody can answer #

Everything above concerns the leading behaviour. The remaining question is the size of $\pi(x) - \operatorname{li}(x)$, and it is the deepest open problem in the subject.

The error is known to be at most about $x / e^{c\sqrt{\ln x}}$, which is smaller than $x$ divided by any fixed power of the logarithm and larger than any power of $x$ below one. The Riemann hypothesis is exactly the assertion that the error is at most about $\sqrt{x}\,\ln x$ — square-root size, which is what a random fluctuation of this kind would give. It is unproved, and no figure here or anywhere assumes it.

What can be said without it is that the error changes sign infinitely often. This is the surprise of the subject, and it is invisible in every drawable picture.

The count runs below the integral for every $x$ anybody has ever checked, which is into the range of $10^{19}$. Littlewood proved in 1914 that it must exceed it infinitely often. Nobody has produced a single value of $x$ where it does: the best known bounds place a crossing somewhere below $10^{316}$, and the earliest such bound, Skewes’ number, was for a long time the largest number to appear in a serious proof.

That is the sharpest available illustration of the limits of numerical evidence. The pattern holds for every number that will ever be examined and is false, and no amount of computing was ever going to settle it.

Counting by weight instead #

The estimate becomes much cleaner if the question is changed slightly, and the change is the one every proof of the theorem actually makes.

Instead of counting each prime once, count each prime power $p^k$ with weight $\ln p$. The resulting total, written $\psi(x)$, is asymptotic not to $x/\ln x$ or to an integral but to $x$ itself — the estimate loses its logarithm entirely. Weighting by $\ln p$ is not a trick to tidy the answer; it is the natural weight, because it is the one under which the multiplicative structure of the integers turns into an additive statement, and a logarithm is the only function that does that.

Recovering $\pi(x)$ from $\psi(x)$ is then a matter of partial summation, and the logarithm and the integral reappear from the conversion rather than from the primes. This is worth knowing because it explains an oddity of the subject: the natural statement has no logarithm in it, and the familiar statement is a corollary that acquires one on the way out.

The same reorganisation is why the prime powers hardly matter. Squares of primes below $x$ number about $\sqrt{x}$ of them, which is negligible beside $x$, so counting prime powers and counting primes differ by an amount far smaller than the error either estimate carries.

How it was proved, and then proved again #

The history is unusually well marked, and each stage corresponds to a different kind of argument.

Chebyshev got the order right in 1850, by an elementary argument about binomial coefficients: he showed that $\pi(x)$ lies between about $0.92$ and $1.11$ times $x/\ln x$ for large $x$, which pins the shape without settling the constant. His method is the one behind the guarantee of a prime between $n$ and $2n$, and it goes no further than a factor.

Riemann changed the subject in a single eight-page memoir in 1859, by connecting the count to a function of a complex variable and writing down a formula for $\pi(x)$ in terms of that function’s zeros. He did not prove the theorem; he laid out the machinery that would, and stated in passing the hypothesis about the zeros that still stands open.

The proof came in 1896, from Hadamard and de la Vallée Poussin independently, and it rests on showing that the relevant function has no zeros on one particular line. That is where the theorem’s difficulty is concentrated: the statement about primes has been converted entirely into a statement about where a function does not vanish.

Then in 1949 Selberg and Erdős found a proof with no complex analysis in it at all, which had been widely believed impossible — the standard view was that the theorem’s depth was its analytic content. The proof is not simple, and its main effect was to correct a belief about what kind of argument a result requires. The two men fell out permanently over the credit, which is the least mathematical fact in this rung and the one most often remembered.

Regular in the large, erratic in the small #

The two halves of the subject sit uncomfortably together, and holding both is most of what understanding the distribution means.

Locally the primes are as irregular as anything in mathematics. There are arbitrarily long runs with no primes at all: the numbers from $n! + 2$ to $n! + n$ are each divisible by something, so a gap of any prescribed length occurs somewhere. There are also, apparently, infinitely many pairs differing by two, which nobody can prove.

Globally the count is smooth to a fraction of a per cent. The reconciliation is that the estimate is an integral — it does not predict any particular prime, it predicts an accumulation, and the erratic behaviour averages out over a range that is short compared to $x$ and long compared to a gap. That is why the density is a good tool and the search for a formula for the nth prime is not.

What a good estimate is worth #

It is fair to ask what having $\operatorname{li}(x)$ actually buys, given that it names no prime.

It settles questions of the form are there enough. The number of primes with exactly a hundred digits is the difference of two values of the estimate, and it is about $3.9 \times 10^{97}$ — a count nobody could obtain by listing, and one that decides immediately whether a search for such a prime by random trial is sensible. Testing whether a candidate is prime is a separate matter and a solved one; knowing that a random hundred-digit odd number is prime with probability about one in a hundred and fifteen is what makes the search worth starting, and that probability is the density $1/\ln x$ with the even numbers removed.

It also converts questions about primes into questions about the estimate’s error. Is there a prime between consecutive squares is not a question about primality at all once the count is available: it asks whether the estimate’s error can exceed the number of primes the estimate predicts in that interval, which is a question about the error term and is open for exactly that reason.

The general point is that a smooth estimate turns an existence question into an inequality between two quantities that can be bounded. That is the only reason to care about the difference between a ratio tending to one and an error term of a stated size — the second answers questions, and the first does not.

What the picture cannot show #

The horizontal axis stops at twenty thousand, and every claim above about the eventual behaviour concerns numbers a picture cannot reach. That is not a mild limitation here: the sign change of the error is the central open behaviour of the object being drawn, and the drawn range is smaller than the known bound on where it happens by a factor beyond any expression in ordinary units.

The ratio panel also flatters the integral in a specific way. Both estimates approach one, and the picture shows one of them arriving and the other visibly not; at $x = 10^{40}$ the crude estimate’s ratio would be about $1.03$, which is much better than at twenty thousand and still much worse than the integral. The difference between them shrinks and never closes, and the drawn range makes it look like a difference in kind rather than in rate.

And the sieve figure is a heuristic, not a proof. It shows where the density guess comes from; the guess is off by twelve per cent, and the correct constant comes from an argument with no picture in it — a contour integral in the complex plane, which is the one piece of machinery this collection cannot draw and the one that settles the theorem.

The ladder from here #

Below: the sieve, which produces the primes this counts, and Euclid’s proof that the list never ends. Above and sideways: the guarantee that a prime lies between every number and its double, which is a statement no density can make, and the sieve written as a product, which is where the analytic machinery starts. Further out: the harmonic series, whose divergence is the first fact in the chain, and the constant that relates it to the logarithm, which is the constant the naive sieve heuristic gets wrong.

A smooth answer to a rough question #

The lasting point is the shape of the result rather than its content. The primes have no formula and their counting function has a good one; what makes that possible is that the question was changed from which to how many, and the second question has an answer whose error is smaller than the objects being counted.

That trade recurs everywhere a subject looks intractable. Individual walks are unpredictable and their distribution is exact; individual permutations are arbitrary and the count of those with no fixed point is a clean formula. Asking about an aggregate rather than an instance is not a retreat from the hard question — it is often the only question with a smooth answer, and the smooth answer is what makes the hard one approachable at all.