Always one before the double

The count of primes below a bound is predictable to a fraction of a per cent, and that fact permits something it does not rule out: a long stretch of numbers with no primes at all, compensated for by a crowd somewhere else. Such stretches do exist — arbitrarily long ones. The question of whether a particular interval can be empty is a different question, and it has an answer.

Written out: for every whole number $n$ greater than one there is a prime $p$ with $n < p \le 2n$. Bertrand conjectured it in 1845 after checking it up to three million, Chebyshev proved it in 1852, and it has been called Bertrand’s postulate ever since — a name that has outlived its accuracy by a hundred and seventy years.

What a density cannot promise #

The distinction between this and the counting estimate is the point of the rung, and it is worth stating twice.

The estimate says that the primes below $x$ number about $x/\ln x$. Suppose all the primes between a million and two million were bunched into the first ten thousand of those numbers. The count would be unaffected — the estimate is about a total, and totals do not see arrangement — and the interval from a million and ten thousand to two million would be empty. Nothing in the counting theorem forbids it.

And the arrangement really is uneven. The numbers $n! + 2,\, n! + 3,\, \dots,\, n! + n$ are divisible by $2, 3, \dots, n$ respectively, so there is a run of $n - 1$ consecutive composites somewhere, for every $n$. Gaps of any prescribed length occur. The postulate says that no such gap can straddle a doubling: however long the empty run, it fits inside an interval whose right-hand end is less than twice its left.

The proof, by a binomial coefficient #

The argument everybody uses is Erdős’s, found in 1932 when he was nineteen and still the shortest complete proof. It is a squeeze on one number.

The number in question is $\binom{2n}{n}$. Two facts about it fight each other.

It is large. The $2n$-th row of Pascal’s triangle sums to $4^n$ and has $2n+1$ entries, of which the middle one is the largest; so $\binom{2n}{n} \ge 4^n / (2n+1)$.

Its prime factorisation is constrained. Every prime power dividing $\binom{2n}{n}$ is at most $2n$; primes between $n$ and $2n$ divide it exactly once; and — the fact that does the work — no prime strictly between $2n/3$ and $n$ divides it at all, because such a prime appears twice in the factorial below and twice in the one above, and cancels.

Now suppose no prime lies between $n$ and $2n$. Then every prime factor of $\binom{2n}{n}$ is at most $2n/3$, and the size of the coefficient must be accounted for entirely by those. Bounding the product of the primes up to $2n/3$ by $4^{2n/3}$ — a separate lemma, proved by induction on the same kind of coefficient — and bounding the contribution of prime powers by $(2n)^{\sqrt{2n}}$, the whole coefficient is at most about $4^{2n/3} (2n)^{\sqrt{2n}}$. Set that against $4^n / (2n+1)$ and the two are incompatible once $n$ is past a few hundred. The remaining cases are checked by exhibiting a short list of primes, each less than twice the one before: 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631.

That last step is worth admiring rather than skipping. The general argument fails for small $n$ and the small cases are settled by a list — a list chosen so that each entry is under twice its predecessor, so that any $n$ below the largest of them has one of the list in its interval. Eleven numbers dispose of every case the inequality cannot reach.

What is being used #

Three things carry the proof, and none of them is a fact about primes.

A count is large. The central binomial coefficient is big because it counts the largest class of subsets, and that is combinatorics.

Factorisation is unique. The bookkeeping of which primes divide which factorial needs each number to have exactly one factorisation, and Legendre’s formula for the exponent of $p$ in $n!$ is where that enters.

Two bounds cannot both hold. The conclusion arrives as a contradiction between a lower bound and an upper bound on the same number, which is the shape of most impossibility arguments turned around to prove existence.

The result is an existence proof that exhibits nothing. It shows that the interval cannot be empty by showing that an empty one makes a certain integer too small to be itself, and it gives no way to find the prime it promises other than looking.

What came first: two bounds with a fixed ratio #

Chebyshev’s proof of the postulate was a by-product of something more general, and the general thing is worth stating because it is the first quantitative fact ever proved about how the primes are spread.

Those bounds are enough for the postulate and not enough for the counting theorem, and the gap between the two is instructive. To show that the interval from $n$ to $2n$ is non-empty it suffices to know that $\pi(2n)$ exceeds $\pi(n)$, and the two Chebyshev bounds do that as soon as the lower constant times $2n/\ln 2n$ beats the upper constant times $n/\ln n$ — which is arithmetic with two explicit numbers in it, and which holds for large $n$ because the factor of two beats the change in the logarithm. Showing that the ratio tends to one is an entirely different problem, and it took Hadamard and de la Vallée Poussin another forty-six years.

The methods differ in the same way. Chebyshev’s is elementary and gives constants; the 1896 proofs are analytic and give a limit. It is one of the cleaner illustrations of a general pattern in the subject: elementary methods produce inequalities with explicit constants and a floor they cannot get below, and analytic methods produce exact asymptotics and are usually silent about the range in which they take effect.

Where the name comes from #

Bertrand did not conjecture it out of curiosity about primes. He needed it in 1845 for a question about permutations — how many distinct values a function of $n$ variables can take when its arguments are permuted — and the step he was missing was exactly the existence of a prime between $n/2$ and $n$.

That is a common way for such statements to arise and it explains the awkward name. What Bertrand had was a lemma required by an argument elsewhere, verified numerically far enough to be usable, and published as an assumption he could not discharge. Seven years later Chebyshev discharged it, and the name stayed with the person who needed it rather than the person who proved it.

Ramanujan returned to it in 1919 with a two-page proof and one addition worth having: he asked how large $n$ must be for the interval to contain at least $k$ primes, and the answers — 2, 11, 17, 29, 41 and onward — are now called the Ramanujan primes. Erdős’s proof came in 1932 and is the one in the textbooks, and he later summarised the whole subject in a couplet whose first line credits Chebyshev with saying it and whose second says it again — a rhyme that has outlasted several of the proofs.

What it is good for #

The postulate is used constantly, usually as a lemma nobody comments on.

Consecutive primes never more than double. Writing $p_1, p_2, \dots$ for the primes in order, $p_{k+1} < 2p_k$. That is the postulate restated, and it is what allows an induction over the primes to control its own step size.

Every number is a sum of distinct primes, past a small bound, and the greedy proof of that uses the postulate to guarantee the next term is available.

The harmonic sum over primes in a doubling interval is bounded below, which converts statements about individual primes into statements about ranges.

And in a slightly different register, it is the standard example of a theorem whose statement a schoolchild can check and whose proof is genuinely non-obvious. Ramanujan’s 1919 paper on it introduced what are now called the Ramanujan primes — the smallest number past which the interval to twice it always contains at least $k$ primes — and that generalisation, unlike the original, was found by asking how much slack the proof had.

The primorial, and a second proof of an old result #

One consequence deserves its own paragraph, because it turns the postulate into a fact about factorisation.

Every whole number $n$ can be written in base two, and the postulate gives the corresponding statement about primes: taking the largest prime below $n$, then the largest below what is left, and so on, terminates in about $\log_2 n$ steps, because each prime is more than half of what remained. That is the greedy argument behind the representation of every sufficiently large number as a sum of distinct primes, and it works only because the interval to the next halving is never empty.

The postulate also gives another proof that there are infinitely many primes, and a quantitative one at that: iterating it from 2 produces a prime below every power of two, so there are at least $\log_2 x$ primes below $x$. That is a poor bound — the truth is $x/\ln x$, which is vastly larger — and it is obtained without any of the machinery the better bound needs, from a statement about a single interval applied over and over.

How much better it can be made #

The postulate is not tight, and the improvements measure how far the subject has come.

Two thirds, not a half. The proof above shows there is a prime between $2n/3$ and $2n$ in the same breath, since it is what makes the cancellation range matter.

Intervals that shrink. For sufficiently large $n$ there is a prime between $n$ and $1.1n$, and between $n$ and $(1 + \varepsilon)n$ for any fixed $\varepsilon$, which follows directly from the counting theorem: the estimate gives about $\varepsilon n / \ln n$ primes in the interval, which exceeds zero once $n$ is large enough. So the density does eventually imply a version of the postulate, with a threshold nobody can write down explicitly.

Gaps below a power. The best unconditional result gives a prime between $x$ and $x + x^{0.525}$ for large $x$, which is a far stronger statement and is proved by machinery of a different order entirely.

And the natural question is open. Whether there is always a prime between consecutive squares — between $n^2$ and $(n+1)^2$ — is Legendre’s conjecture, and it is not known. The interval has length about $2n$ and the density predicts about $2n / \ln(n^2)$ primes in it, which is comfortably positive; but the prediction has an error term nobody can bound tightly enough, and the gap between the estimate says yes and it is proved is exactly the error term the Riemann hypothesis is about. Even assuming that hypothesis, the question stays open.

That last item is the honest measure of the rung. A guarantee for the doubling interval is elementary; a guarantee for an interval of length $2n$ around $n^2$ is beyond everything known, and the difference between the two is not a matter of effort.

What the picture cannot show #

Twenty-six intervals is not evidence for a statement about all of them, and the figure says so by reporting the check that runs behind it to five thousand — which is also not evidence, merely a much larger absence of counterexamples. Bertrand himself checked to three million and was right to call it a conjecture.

The picture also cannot show the mechanism. Nothing in a drawing of intervals and dots suggests a binomial coefficient, and the proof’s key step — that primes in a certain middle range cancel out of the coefficient entirely — is a statement about factorials with no geometric content whatever.

And the drawn range makes the theorem look weaker than it is. At $n = 26$ the interval holds four or five primes and the postulate asks for one, so the picture appears to be about a comfortable margin. It is not: the margin grows, and the theorem’s content is at the bottom end, where the intervals hold exactly one prime and there is nothing to spare.

The ladder from here #

Below: the sieve and the infinitude of primes, whose Euclidean proof is the other elementary existence argument in the subject. Sideways: the counting theorem, which this complements rather than follows from, and the pigeonhole principle, which is the other way of turning a counting bound into an existence claim. Above: the sieve written as a product, where the elementary arguments give out and the analytic ones begin.

What the interval’s length has to be #

The doubling in the statement is not sacred, and asking what it can be replaced by is the natural follow-up.

Any interval whose right-hand end is a fixed multiple of its left works for large enough numbers, by the counting theorem, with the threshold depending on the multiple. What is special about doubling is that the threshold is one: the guarantee holds from the very first case, with no exceptions to check beyond the eleven the proof itself lists.

That is worth a moment. A statement true from the smallest case onward can be used inside an induction with no separate base; a statement true past some unspecified point cannot be used at all until the point is found, and finding it is usually harder than the original theorem. The difference between the two kinds of result is what makes an elementary proof valuable even when a stronger analytic one exists.

A guarantee, and an average #

The lasting point is the difference in kind between the two rungs. An average is a statement about accumulation and is compatible with any amount of local misbehaviour; a guarantee is a statement about every instance and rules the misbehaviour out.

Mathematics is full of pairs like this and they are constantly conflated. A distribution’s mean says nothing about its tail; a walk’s expected position says nothing about where it can be found. The useful habit is to ask, of any quantitative claim, whether it constrains a total or an instance — and to notice that the second is almost always the harder theorem, and almost always the one wanted.