A constant that holds the primes

When Euclid’s number is itself prime ended with a list that thins out and may stop: the products of primes plus one that happen to be prime. That is the usual fate of a formula that produces primes by luck. Euler’s $n^2 + n + 41$ is prime forty times and then fails, and the reason it lasts as long as it does is a fact about the integers of one particular number field rather than about primes.

This essay is about a formula that never fails. In 1947 W. H. Mills proved that there is a real number $A$ for which

$$\lfloor A^{3} \rfloor,\ \lfloor A^{9} \rfloor,\ \lfloor A^{27} \rfloor,\ \dots,\ \lfloor A^{3^k} \rfloor,\ \dots$$

are all prime. The smallest such $A$ is $1.3063778838630806904686144926\ldots$, and the primes it gives start 2, 11, 1361, 2521008887.

It is a real theorem with a short proof, and it is the clearest example there is of the difference between a formula and a procedure. Every figure below is a measurement of that difference.

A chain of primes, each just above a cube #

Mills’s proof does not find $A$ first and then check the primes. It builds the primes first, as a chain, and lets $A$ be what the chain converges to.

Start with a prime $p_1$. Find a prime $p_2$ between $p_1^3$ and $(p_1 + 1)^3$, then a prime $p_3$ between $p_2^3$ and $(p_2 + 1)^3$, and so on. Each step needs one fact: between the cubes of two consecutive whole numbers there is a prime. If that holds, the chain goes on for ever.

The chain then squeezes a single number. Since $p_{k+1} \ge p_k^3$, the numbers $p_k^{3^{-k}}$ never decrease as $k$ grows; since $p_{k+1} + 1 \le (p_k + 1)^3$, the numbers $(p_k + 1)^{3^{-k}}$ never increase. The first sequence sits below the second throughout, so they meet at a limit $A$, and for every $k$

$$p_k^{3^{-k}} \le A < (p_k + 1)^{3^{-k}}, \qquad\text{that is,}\qquad p_k \le A^{3^k} < p_k + 1.$$

Rounding $A^{3^k}$ down gives $p_k$, and every $p_k$ is prime by construction.

The smallest $A$ comes from starting at 2 and always taking the least prime available. The cube of 2 is 8, and the first prime from 8 on is 11. The cube of 11 is 1,331, and the first prime is 1,361. The cube of 1,361 is 2,521,008,881, and the first prime is six further on. The figure carries the chain to its seventh member, which has 254 digits, and checks the first five against the published list.

The chain is a machine in the same sense as Euclid’s proof run as a machine: a rule that takes the primes produced so far and makes the next. Euclid’s rule multiplies the list, adds one and takes the least prime factor, and nobody can say where its outputs will fall. Mills’s rule cubes the last prime and takes the next prime up, and its outputs fall exactly where the rule says, just above a cube. That predictability is what lets the whole chain be compressed into one real number, and it is bought by giving up everything Euclid’s rule was for: Mills’s chain proves nothing about the primes being endless, since it assumes a prime in every window from the start.

Each prime lies only a few steps above its cube — 3, 30, 6, 80, 12 and 450 — while the room it had before the next cube is enormous: the cubes of $n$ and $n + 1$ differ by $3n^2 + 3n + 1$, a number two-thirds as long as the prime itself. Primes near a number $N$ come about every $\ln N$, which for the 254-digit member is about 580. The chain never comes close to needing its room.

Computing the constant from its primes #

$A$ is computed the only way it can be: from the chain. Since the seventh prime is $\lfloor A^{3^7} \rfloor$, $A$ is its seventh iterated cube root, give or take the rounding. The figures take integer cube roots in fixed-point arithmetic, two hundred digits wide, and the answer begins

$$A = 1.30637788386308069046861449260260571291678\ldots,$$

which matches the published value. The lower end of the interval, from $p_7$, and the upper end, from $p_7 + 1$, agree to about 257 places, and that agreement is what the hero figure draws for each prime in turn.

Each prime fixes about three times as many digits as the last, because it has three times as many digits and fixes about as many digits of $A$ as it has. The interval around $A$ has width roughly $A / (3^k p_k)$, so the precision of the early steps — one digit from 11, four from 1,361 — becomes eleven, thirty, eighty-seven and two hundred and fifty-seven as the chain climbs.

This is the first half of the difference between a formula and a procedure. To know $A$ to a hundred places, one must already know a prime of about a hundred digits that lies just above a cube. Nothing else determines it: no series, integral or continued fraction is known to produce $A$ independently, and there is no reason to expect one, since $A$ depends on which prime happened to be first above each cube.

There are uncountably many such constants #

The least prime above each cube is a choice, and nothing in the construction requires it. Any prime in the window will do, and the windows are crowded: the one above $2^3$ holds 11, 13, 17, 19 and 23, the one above $11^3$ holds dozens, and the window above a 29-digit cube holds roughly $10^{54}$ primes. Every sequence of choices gives a chain, every chain gives a constant, and different chains give different constants, since a constant determines its chain by rounding down.

So the Mills constants are uncountable: even allowing only two choices at each step gives a binary branching that never ends, and the branches form a set as large as the real numbers, with the same argument that makes a set with almost nothing left in it still uncountable. Each is at least $1.3063\ldots$, since choosing a larger prime anywhere in the chain only makes the constant larger, and between any two of them lie gaps where no chain lands, because a constant whose first few powers round down to composites is not one.

The number $1.3063778838\ldots$ is distinguished among them only by being the least, which is what makes it the one worth naming. It is also the only one anybody computes, because every other choice would need its own primes to be stated.

The formula gives back exactly what it holds #

The second half runs the formula the other way. Take $A$ to $D$ decimal places, raise it to the powers 3, 9, 27 and on, round down, and count how many of the primes come out right.

They come out in steps, and each step is paid for. Two digits give the first prime, 2. Twelve digits give the third, 1,361; thirty give the fourth, 2,521,008,887; ninety give the fifth, the 29-digit prime. The price of each prime turns out to be the length of the prime after it, and the reason is visible in the construction. $A^{3^k}$ exceeds $p_k$ by very little — about the next prime’s distance above its cube divided by $3p_k^2$ — so a constant truncated from below has to be accurate to that tiny excess or it rounds down to $p_k - 1$.

So the constant is a storage scheme. It holds the primes of the chain in its digits, packed so that each prime’s digits are mostly the previous prime’s cube, and it releases them at almost exactly the rate it was filled. To produce a $d$-digit prime from Mills’ formula one needs about $3d$ digits of a constant that can only be computed from that prime and its successor. A formula that returns what was put into it is a code, not a discovery.

That is not a defect in Mills’s theorem, which never claimed otherwise. It is the reason the theorem is safe: the hard part of a prime-producing formula is producing primes, and the theorem says nothing about how to do that beyond “take the next one”.

Why there is always a prime between two cubes #

The one fact the chain needs is a prime between $n^3$ and $(n + 1)^3$, and it is not elementary. Bertrand’s postulate gives a prime between $N$ and $2N$, which is far too wide: the window between consecutive cubes is about $3N^{2/3}$ long, a vanishing fraction of $N$.

The tools that prove Bertrand’s postulate count primes in long intervals, and the sieve that cannot finish explains why counting by sifting runs out of power long before intervals get short. Short intervals were reached instead through the zeros of the Riemann zeta function: a prime in $[N, N + N^\theta]$ follows from knowing that few zeros lie far from the critical line, and how few determines $\theta$.

What Mills used was a theorem of Albert Ingham’s from 1937: for every large enough $N$ there is a prime between $N$ and $N + N^{\theta}$, with $\theta = 5/8$, or anything slightly larger. The window above $N = n^3$ is about $3N^{2/3}$, and $2/3$ is bigger than $5/8$, so for large $n$ the window is longer than Ingham’s guarantee and contains a prime.

“Large enough” is the catch, and Mills’s argument does not mind it: the chain can begin at any prime, as high as necessary, so it only ever needs the windows beyond some point. Whether every window from $n = 1$ holds a prime is a separate question. The figure checks the first two thousand, where the fullest after the first is at $n = 2$, using three of its nineteen places; by $n = 2{,}000$ the first prime typically uses about a millionth of the window. Adrian Dudek proved in 2016 that every window beyond an explicit but astronomical point holds a prime. Below it, unconditionally, the answer rests on computation, and on the Riemann hypothesis it is true from the start — which is what Chris Caldwell and Yuanyou Cheng used in 2005 to show that the chain from 2, and so the value $1.30637\ldots$, is the least Mills constant there is.

Why the power is three and not two #

The natural first try would have been squares: a constant $B$ with $\lfloor B^{2^k} \rfloor$ prime for every $k$. The same construction works, provided there is a prime between every two consecutive squares.

That statement is Legendre’s conjecture, and it is unproved. The window between $n^2$ and $(n + 1)^2$ is $2n + 1$ long, which is $2\sqrt N$ for $N = n^2$, and no theorem about gaps between primes reaches down to a square root. Even the Riemann hypothesis only gives a prime within about $\sqrt N \ln N$ of $N$, a logarithm too wide.

The figure shows what the conjecture is up against. For cubes the share of the window used falls steadily, because the window grows like $n^2$ while the gap before the first prime grows only like $\ln n$. For squares the window grows only like $n$, and the shares do not fall away: they scatter between a hundredth and a tenth across the whole range, with the fullest at $n = 5$, where the first prime after 25 is 29, four places into a window of eleven. No window in the range comes close to failing, and Legendre’s conjecture has been checked far beyond it, but the margin is not growing the way it does for cubes, and a proof would need to control the gaps between primes at a scale nobody can.

What each gap theorem buys #

Mills’s construction works for any power $c$, as long as there is a prime between $n^c$ and $(n + 1)^c$ for every large $n$. That window is about $c\,n^{c-1} = c\,N^{1 - 1/c}$ long, so any gap theorem with exponent $\theta < 1 - 1/c$ will do. Every improvement in the gap exponent therefore lowers the power, and the history of the subject is a curve:

• Guido Hoheisel showed in 1930 that $\theta$ can be taken just below 1 — the first theorem of its kind — with $\theta = 1 - 1/33{,}000$, which would allow a power of 33,000;
• Ingham’s $5/8$ of 1937 allows any power above $8/3$, which is why Mills could use 3;
• Martin Huxley’s $7/12$ of 1972 allows any power above $2.4$;
• Roger Baker, Glyn Harman and János Pintz’s $0.525$ of 2001 allows any power above $2.105$.

The power 2 is out of reach of every method. Getting there would need $\theta = 1/2$ exactly, with no logarithm to spare, and that is Legendre again. So the exponent in Mills’s formula is not a choice but a measurement: it records how short an interval the theory of primes can currently guarantee a prime in, and it has fallen from 33,000 to 2.105 in seventy years while the last step, to 2, remains as far off as ever.

A formula is not a procedure #

The useful question to ask of a formula for primes is what it costs to evaluate. Mills’s costs a prime to get a prime. The same is true of the others that look like it. E. M. Wright found in 1951 a constant $\omega \approx 1.9287800$ for which the towers $2^{\omega}$, $2^{2^{\omega}}$, $2^{2^{2^{\omega}}}$, rounded down, are prime — 3, 13, 16,381, and then a prime of nearly five thousand digits — and $\omega$ is computed from those primes exactly as $A$ is.

Formulas built from Wilson’s theorem, which test every number up to $n$ for primality inside a single expression, are honest in a different way: they produce the $n$-th prime by trying every candidate, which is a sieve written as algebra. And the polynomial in twenty-six variables whose positive values are exactly the primes, which follows from the theorem that every listable set is a shadow of a polynomial, encodes a primality check in its variables — finding a prime with it means solving a Diophantine equation, which is harder than finding the prime.

None of this contradicts what counting what has no formula argues: the primes are predictable in bulk and unpredictable one by one. A formula that delivers them one by one must contain them, and Mills’ constant is the shape that containing takes when it is written as a single real number.

What the computations rest on #

The primes in the chain beyond $10^{24}$ are tested by Miller–Rabin on twelve fixed bases, which is a proof of primality below $3.3 \times 10^{24}$ and a probable-prime test above it. The chain to its fifth member agrees with the published list, and the sixth and seventh are the first probable primes above their cubes, with offsets 12 and 450. The value of $A$ is computed from the seventh member by exact integer cube roots and agrees with the published digits; an error in any member of the chain would have changed it beyond the first few places.

The windows between consecutive squares and cubes are checked for every $n$ up to 2,000, with the first prime found exactly. That range says nothing about larger $n$ by itself; the statement about all cubes past a point is Ingham’s theorem, and the one about squares is a conjecture.

Still open: a prime-producing constant for squares #

Is there a constant $B$ such that $\lfloor B^{2^k} \rfloor$ is prime for every $k$? Legendre’s conjecture would give one at once, by the same chain, and it is open. A weaker form is open too: it would be enough to have a prime between $n^2$ and $(n+1)^2$ for every $n$ in some sparse sequence the chain could follow, since the chain only visits the squares of its own primes, and nobody has found a way to exploit that freedom.

The computations suggest what the answer should be, and the figure for squares shows why proving it is hard: the windows never come close to failing, but they do not empty out either, and every known way of finding primes in short intervals loses a factor that the square window cannot spare.