The patterns primes are allowed to make

Which infinitudes are proved listed families of primes that are conjectured to be infinite and are not known to be, twin primes first among them, and noted that each comes with a conjectured count that agrees with the measurements “to a percent or two”. It described the model those counts come from — treat each number as prime with probability $1/\log n$, then correct for the obvious dependencies — and left the corrections themselves undrawn.

This essay draws them. The corrections turn out to be the whole of the interesting content: they decide which patterns of primes can occur infinitely often at all, and they predict, with a single constant for each pattern, how often each one does. The constants come from nothing but remainders, and they match the counts with no adjustable parameter.

Pairs at every distance #

Count the pairs of primes that are exactly $d$ apart, for every even $d$. The naive model — each number independently prime with probability $1/\log n$ — gives every gap the same answer, about $x/(\log x)^2$ pairs up to $x$. The counts in the opening figure are nothing like level. Pairs six apart are almost exactly twice as common as pairs two apart: 29,419 against 14,871 up to two million. Pairs thirty apart are more common still.

The reason is divisibility by small primes. Take gap 2. Of the numbers $n$ and $n + 2$, if $n$ is not divisible by 3, then either $n + 2$ is, or neither is: $n$ can have remainder 1 or 2 mod 3, and if it has remainder 1 then $n + 2$ has remainder 0 and is a multiple of 3. So for a prime $n > 3$, only one of its two possible remainders mod 3 leaves $n + 2$ free to be prime. Now take gap 6: $n + 6$ has the same remainder mod 3 as $n$, so whenever $n$ is not a multiple of 3, neither is $n + 6$. Both remainders work. That factor of two between the bars is the arithmetic of the prime 3, visible in a count of millions of primes.

The same argument applies prime by prime. A gap divisible by 5 gets a boost from 5, one divisible by 7 from 7, and the boosts multiply. That is why the tallest bars in the figure sit at 30 and 60, which are divisible by 2, 3 and 5 at once.

The consecutive gaps show the same bias in a different way. Among primes up to a few million, the commonest gap between neighbours is 6, not 2 — because a gap of 6 is favoured by the prime 3 exactly as the pair counts show — and the gap of 30 overtakes 6 as the commonest only far beyond anything a table can reach, when the primes have thinned out enough that the boost from 5 outweighs the rarity of long gaps. These “jumping champions” are predicted by the same constants, and have been checked as far as they can be.

A pattern must leave a remainder free #

Generalise from pairs to patterns: a prime constellation is a set of offsets $(0, h_2, \ldots, h_k)$, and the question is whether $n, n + h_2, \ldots, n + h_k$ can all be prime for infinitely many $n$.

Some patterns plainly cannot. Take $(0, 2, 4)$. Among $n$, $n + 2$ and $n + 4$ the remainders mod 3 are $n$, $n + 2$ and $n + 1$ — all three remainders, in some order — so one of the three numbers is always a multiple of 3. The only way all three can be prime is if that multiple of 3 is 3, which happens once: $3, 5, 7$. The pattern $(0, 2, 4)$ can occur at most once, and it does.

A pattern is admissible when, for every prime $p$, its offsets miss at least one remainder mod $p$. Only primes up to the number of offsets need checking, since a pattern of $k$ numbers cannot fill all $p$ remainders when $p > k$. An inadmissible pattern contains a multiple of some prime every time, and so holds primes at most finitely often. An admissible one faces no such obstruction — and the prime $k$-tuples conjecture, due to G. H. Hardy and J. E. Littlewood in 1923, says that is the only obstruction: every admissible pattern occurs infinitely often.

It is worth dwelling on how much that conjecture claims. The twin prime conjecture is its simplest case, the pattern $(0, 2)$. The triplets $(0, 2, 6)$ and $(0, 4, 6)$ are both admissible, and both are conjectured infinite. Not a single admissible pattern of two or more numbers has been proved to occur infinitely often. The conjecture is supported by every count ever made and by a heuristic nobody seriously doubts, and it is proved for no pattern at all.

The constant, from remainders alone #

Hardy and Littlewood did more than conjecture infinitude. They predicted the count. For an admissible pattern with $k$ offsets, let $\nu(p)$ be the number of remainders mod $p$ that its offsets occupy. For a random $n$, the chance that none of the $k$ numbers is divisible by $p$ is $1 - \nu(p)/p$; if the $k$ numbers were independent, it would be $(1 - 1/p)^k$. The ratio

$$\mathfrak{S} = \prod_{p} \frac{1 - \nu(p)/p}{(1 - 1/p)^k}$$

corrects the naive model prime by prime, and the conjecture says the pattern occurs about $\mathfrak{S} \int_2^x dt/(\log t)^k$ times up to $x$.

The table is the essay’s central exhibit. Every constant is a product over primes, computed here up to 100,000, and every count is a direct sieve of the numbers up to two million. The predictions track the counts to within a few per cent for patterns whose frequencies differ by a factor of fifty. The twin prime constant, $2C_2 \approx 1.3203$, gives 14,798 predicted pairs against 14,871 found. The triplet constant, about $2.858$, predicts 2,445 triplets of each shape, against 2,380 and 2,508. The quadruplet $(0, 2, 6, 8)$ — the tightest four primes can crowd, as in $11, 13, 17, 19$ — has constant about $4.151$ and predicted count 286, against 295.

Two patterns related by reflection, like $(0, 2, 6)$ and $(0, 4, 6)$, occupy the same number of remainders mod every prime, so they share a constant exactly. Their counts differ by about five per cent up to two million, one above and one below the prediction — the kind of fluctuation that the essay on primes in residue classes found between classes that are equally shared in the limit.

The ingredients of the prediction are worth separating, because only one of them is conjectural. The integral $\int_2^x dt/(\log t)^k$ is the naive count — what $k$ independent events of probability $1/\log t$ would give — and its $k = 1$ case is the prime number theorem’s count, which is proved. The constant $\mathfrak{S}$ is an exact computation: for each prime $p$ it compares the true chance that the pattern avoids multiples of $p$ with the chance independence would give, and the comparison is pure arithmetic of remainders, the same arithmetic the sieve of Eratosthenes performs one prime at a time. What is conjectured is only that multiplying the two is correct — that after every prime’s effect on divisibility has been accounted for, nothing else correlates the numbers in the pattern.

For the patterns with one number, that conjecture is a theorem: it is the prime number theorem itself, and for one number in a residue class it is Dirichlet’s. The moment a pattern has two numbers, it becomes one of the most famous open problems in mathematics.

Why the model works, and what it cannot prove #

The constant is a statement about independence. It says that, once the divisibility by each small prime is accounted for exactly, what is left behaves as though the numbers were independent random events. That is a strong claim about the primes and it is not proved for any pattern. Its success is evidence of a very specific kind: not that the primes are random, but that their correlations are entirely explained by remainders.

The model also knows its limits. It predicts the count up to a ratio tending to one, and the fluctuations around that ratio — the five per cent separating the two triplet shapes at two million — are not predicted, and are expected to shrink only slowly. And it says nothing about why the conjecture should be true; it takes the pattern’s admissibility as the only obstruction and assumes that no other conspiracy among the primes exists.

That assumption has one surprising consequence. Hardy and Littlewood also conjectured that $\pi(x + y) \le \pi(x) + \pi(y)$ — that no interval of length $y$ holds more primes than the first $y$ numbers do. Douglas Hensley and Ian Richards showed in 1973 that the two conjectures cannot both be true: there are admissible patterns denser than the primes near the start of the number line, and if every admissible pattern occurs, some interval far out holds more primes than the first interval of its length. Most number theorists believe the $k$-tuples conjecture and have abandoned the other — but the interval where it would fail is so far out that no computation has come close.

The same test for polynomials #

Fixed offsets are one kind of pattern. Another asks whether a polynomial takes prime values infinitely often: is $n^2 + 1$ prime for infinitely many $n$? The essay on primes of one kind took up the linear case — primes of the form $an + b$ — and the quadratic case is open, one of the four problems Edmund Landau listed in 1912 as unattackable.

The admissibility test carries over exactly. A polynomial can take prime values infinitely often only if no single prime divides all its values: $n^2 + n + 2$ is always even, so it cannot, while $n^2 + 1$ is never divisible by 3 (its values mod 3 are 1 and 2) and passes the test for every prime. Andrzej Schinzel’s Hypothesis H is the conjecture that this necessary condition is also sufficient, for any finite collection of irreducible polynomials at once — and the $k$-tuples conjecture is the special case where every polynomial is $n + h_i$.

The count has a constant too. Paul Bateman and Roger Horn gave the analogue of Hardy and Littlewood’s product in 1962, with $\nu(p)$ replaced by the number of roots the polynomials have mod $p$, and it predicts the values of $n^2 + 1$ as well as the twin prime constant predicts twins. Which infinitudes are proved quoted it: 38 predicted primes of the form $n^2 + 1$ below a hundred thousand, against 51 found — a worse match than the table above, because the relevant range of $n$ is only up to 316, far too small for the asymptotics to have settled. The constant is right; the scale is not large enough yet to show it.

Patterns that were proved: progressions #

There is one kind of prime pattern for which infinitely many examples are known, and the reason it escapes the difficulty is instructive. An arithmetic progression of primes, like $5, 11, 17, 23, 29$, has a common difference — but the difference is not fixed in advance. The question is whether, for each length $k$, some progression of $k$ primes exists, with whatever difference it needs.

Ben Green and Terence Tao proved in 2004 that it does, for every $k$. Their proof shows the primes are dense enough, in a suitable sense, inside a larger set that behaves randomly, and that any dense subset of such a set contains long progressions — a statement about the primes’ size, not about their fine arrangement. That is why it succeeds where the $k$-tuples conjecture does not: allowing the difference to grow lets the pattern be found in the bulk of the primes, where density arguments reach, rather than at a fixed small scale, where the parity problem and its relatives stand in the way. The longest progression of primes actually found has more than two dozen terms; the theorem promises arbitrarily long ones and gives no practical way to find them.

Narrow patterns and bounded gaps #

The patterns matter even without the full conjecture, because of what has been proved.

In 2013 Yitang Zhang proved that some admissible pattern of numbers contains at least two primes infinitely often, and deduced that infinitely many pairs of consecutive primes lie within 70 million of each other — the first proof that gaps between primes do not grow without bound. James Maynard and Terence Tao then found a simpler and stronger method: for every $m$, any admissible pattern of enough numbers contains at least $m$ primes infinitely often. For $m = 2$, fifty numbers are enough.

So take the narrowest admissible pattern of fifty numbers. Infinitely often, at least two of its fifty numbers are prime, and so two primes lie within its width of each other. The figure computes the narrowest widths up to ten numbers by exhaustive search, reproducing the known values; for fifty, the answer is 246, found by the Polymath collaboration’s searches — and that is the current bound: infinitely many pairs of primes differ by at most 246.

What stands between 246 and 2 is the parity problem. Maynard’s method proves “at least two of fifty are prime”, which holds in both parity classes and so is within a sieve’s reach. Proving that both members of a specific pair are prime is the parity-sensitive statement, and no sieve can make it.

What the counts cannot show #

The figures count up to two million, and every agreement between prediction and count is an agreement at that scale. For the twin primes the agreement holds as far as computation has reached, in the trillions, but no finite count can support the claim that the pattern continues for ever, and the conjecture is exactly that claim. The constants themselves are computed from primes up to 100,000; the omitted tail changes them in the fifth decimal place, which is below anything the counts could detect.

The narrowest-pattern figure is an exhaustive search for small widths and says nothing about the value 246, which comes from a much larger search the figure does not reproduce. And no figure shows the actual theorem — Maynard’s — which is a statement about weighted sums over all $n$ up to $x$, and has no picture. What the table can do is make the claim concrete: seven patterns, seven constants, seven predictions, and seven counts that fall within a few per cent. A conjecture that fits that well with no free parameter is not proved by fitting, but it is hard to believe it is merely lucky.

Still open: every admissible pattern #

The Hardy–Littlewood conjecture is open in every case. No admissible pattern with two or more numbers is known to occur infinitely often; the twin primes are the simplest instance and the best studied. The bounded-gaps theorems prove that some pattern among many does, without saying which.

Between the current bound of 246 and the conjectured truth, the obstacle is well understood: the methods prove statements that are insensitive to the parity of prime factors, and “these two specific numbers are both prime” is not such a statement. Assuming the strongest conjecture about how evenly primes spread over residue classes — the Elliott–Halberstam conjecture — Maynard’s method brings the bound down to 12, and a generalised form brings it to 6. Getting from 6 to 2 is exactly the parity barrier, and nothing currently known is expected to cross it. Even the most modest statement of the conjecture — that the pair $(0, 2)$ occurs infinitely often, the twin primes — is out of reach, while the most ancient infinitude of all, Euclid’s, is a proof of a few lines. The distance between those two statements, one about primes and one about primes two apart, is the measure of what is not yet understood about how the primes are arranged.