Which infinitudes are proved

Euclid’s argument gives infinitely many primes. Aiming it, or handing the question to Dirichlet, gives infinitely many in any residue class that can hold them. Both results are settled and old.

Now ask for infinitely many primes that are one more than a square: $2$, $5$, $17$, $37$, $101$, $197$, $257$, and so on. Fifty-one of them sit below a hundred thousand, they arrive at a rate matching a precise prediction, and nobody has ever proved there are infinitely many. The same is true of the twin pairs, and of the Mersenne primes, and of several other families that look equally inexhaustible.

The five end counts, at a hundred thousand: 9,592 primes; 4,783 of them 1 mod 4; 1,224 twin pairs; 51 primes one more than a square; and 5 Mersenne primes. The first two are theorems, the last three are not, and the ordering by size is no guide — the family with 1,224 members is open and the family with 4,783 is settled, while a family with 5 members would be settled if anybody could prove it.

This rung is about that gap. What makes a proof of infinitude possible is a specific mechanism, and every family for which the mechanism is unavailable is open — regardless of how convincing its numbers look.

A word on what open means here, since it is stronger than unproved. Each of these statements has been attacked by every method the subject has, for a century or more, by people who understood exactly what was missing. The conjectures are believed, the numerical evidence is overwhelming, and the obstruction in each case is identified and named. Open, in this rung, means that the obstruction is understood well enough to say why the available proofs stop, and not well enough to get past it.

The mechanisms that work #

Three proofs of infinitude have appeared on this ladder, and it is worth naming what each one actually uses, because their requirements are what the open cases fail.

Construction. Euclid’s argument builds a number and observes it has a new prime factor. It needs the family to be closed under an operation that produces new members from old — multiply and add one — and it needs the arithmetic to force the result outside the list. Aiming the construction at a residue class works because classes multiply predictably.

Divergence. Euler’s argument shows the sum of reciprocals of primes is infinite, which forces infinitely many terms. It needs a lower bound on how dense the family is, strong enough that the reciprocals cannot converge.

The demand in that word closed is stricter than it sounds. Euclid’s construction works because a product of primes is a number whose prime factors are known — the listed ones and nothing else — so adding one produces a number provably outside the list. There is no analogous operation taking two twin pairs to a third, or two Mersenne primes to another. The family has to be generated by arithmetic before an arithmetic construction can extend it.

Analysis of a counting function. Dirichlet’s proof, and the prime number theorem behind the count’s true rate, work by turning the family into a sum with analytic structure and extracting the count from it. This is the most powerful of the three and the least portable: it needs the family to be describable by something like an Euler product, which is a strong demand.

Every proved infinitude below is one of those three. Every open one is a family that fits none of them.

Why the reciprocals decide so much #

The divergence method has a sharp converse that is easy to state and worth taking seriously.

Brun’s theorem, 1919. The sum of the reciprocals of the twin primes converges.

$$\frac{1}{3} + \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + \cdots \approx 1.902$$

That number is finite whether the twin primes are infinite or not, and it is finite because the twins are sparse — their count below $x$ is about $x/(\ln x)^2$ rather than $x/\ln x$. So the argument that settles the primes is unavailable here, permanently, and not because nobody has arranged it properly. A convergent sum of reciprocals is consistent with a finite family and with an infinite one, so it can never distinguish them.

The same applies to every family this rung is about. The primes one more than a square number about $\sqrt{x}/\ln x$ below $x$, and their reciprocals converge even faster. The Mersenne primes are sparser still.

There is a converse worth stating alongside it, since it is what makes the divergence method a genuine instrument rather than a lucky trick. A family whose reciprocals diverge is infinite, and the divergence also puts a floor under how the family is distributed — it cannot be crowded into a thin stretch and stop. So Euler’s argument proves more than Euclid’s not by being cleverer about infinitude but by measuring something Euclid’s construction never touches, which is how many members the family has below each bound.

That is the cleanest available statement of why these problems are hard: the tool that works has a density requirement, and these families sit below it. It is not a claim that they are unprovable — only that one route is closed and the closure is a theorem rather than a shortage of effort.

The reason a congruence is the boundary is structural rather than accidental. A residue class is exactly the kind of set an Euler product can see: the class is a subgroup coset, the characters detect it, and the analytic machinery applies unchanged. One more than a square is not a coset of anything, so nothing in the machinery picks it out, and the whole apparatus that settles the congruence case has no point of contact with it.

What the counts look like #

The measurements are worth setting out, because the fit between them and their conjectural predictions is one of the striking things about this subject.

Below a hundred thousand there are 51 primes one more than a square. Hardy and Littlewood’s conjecture predicts about $1.37\sqrt{x}/\ln x$, which at that bound is 38. The counted figure exceeds it by a third, and the discrepancy shrinks slowly because the conjecture is asymptotic — the error terms are of size comparable to the main term at these ranges.

Below the same bound there are 1,224 twin pairs, against a predicted 996 by the same authors’ constant. Again a third high, again shrinking.

Both are excellent agreement by the standards of the subject and neither is evidence of infinitude. A family that stopped at a trillion would produce identical curves everywhere the figures reach, and there is no scale at which the picture could start to disagree, since the prediction is about a limit and the picture is about a bound.

The families, sorted #

Proved infinite.

Every prime. Euclid, and four other proofs.

Every coprime residue class. Dirichlet.

Primes that are the sum of two squares — equivalently the primes 1 mod 4, since a prime is a sum of two squares exactly when it is 1 mod 4.

Primes of the form $x^2 + y^4$. Friedlander and Iwaniec, 1997 — a genuinely thin family, thinner than the primes one more than a square, and proved infinite by an argument built for it. This is the case that stops “too sparse for the reciprocals to diverge” being an excuse: sparseness closes one route and does not close the question.

Primes in short intervals of the right length. Between every number and its double there is a prime, proved by Chebyshev in 1852 and by Erdős at nineteen with a counting argument about binomial coefficients. The interval grows with the number, which is what makes it reachable.

Arbitrarily large gaps. Not an infinitude but its opposite, and proved by construction: the $n - 1$ consecutive numbers $n! + 2, \ldots, n! + n$ are each divisible by something, so no prime is among them.

Open.

Twin primes. Infinitely many $p$ with $p + 2$ prime. Conjectured since at least 1849, and the 1,224 pairs below a hundred thousand show no sign of thinning beyond what the prediction expects — the pairs 3 and 5, 5 and 7, 11 and 13 at the start, and 99,989 and 99,991 at the end of the range the figures count.

Primes one more than a square. One of Landau’s four problems of 1912, all four still open.

Mersenne primes, of the form $2^n - 1$. Only a few dozen are known, each found by a computation rather than an argument, and the conjecture that there are infinitely many rests on a heuristic about how often $2^n - 1$ should be prime.

Fermat primes, of the form $2^{2^n} + 1$. Five are known — 3, 5, 17, 257, 65537 — and none has been found since, with the prevailing guess being that there are no more at all. Here the same evidence supports the opposite conclusion, which is the most useful thing this list contains: a sparse family with no proof is a family about which nobody should have an opinion based on counting.

Sparse does not mean hopeless #

It would be tidy if the dividing line were density, and it is not. The Friedlander–Iwaniec theorem is the counterexample that has to be kept in view.

Primes of the form $x^2 + y^4$ number about $x^{3/4}$ below $x$ — fewer than the primes one more than a square in proportional terms, far fewer than the twins, and vastly fewer than the primes themselves. Their reciprocals converge comfortably. And they are proved infinite, by an argument that spends its effort on the specific shape of that polynomial rather than on any general principle.

So the honest statement is not that sparse families are unreachable. It is that each sparse family needs an argument built for it, and that whether such an argument exists is decided case by case, by whether the family’s defining condition has enough arithmetic structure to be exploited. The fourth power in $x^2 + y^4$ is what supplies that structure, and $n^2 + 1$ — with only one variable — supplies less.

Which is why counting the members is worthless as a guide. The families are not ordered by size, or by density, or by how natural they look. They are ordered by how much arithmetic their definition happens to carry, and nothing in a count reveals that.

What partial results look like #

The open problems are not untouched, and the shape of the partial results says what the obstruction is.

Chen’s theorem, 1973. There are infinitely many primes $p$ such that $p + 2$ is prime or a product of two primes. One step from the twin prime conjecture, by a sieve argument pushed to its limit — and the last step has resisted since.

Bounded gaps, 2013 onwards. There are infinitely many pairs of primes differing by at most a fixed amount. Zhang’s first bound was seventy million; work since has brought it to 246. Getting to 2 needs something the method does not have.

Iwaniec, 1978. There are infinitely many $n$ for which $n^2 + 1$ has at most two prime factors. Again one step short.

Every one of these stops in the same place. Sieve methods bound the number of prime factors and cannot force it down to one, because of a barrier — the parity problem — that is intrinsic rather than technical: the sieve cannot distinguish numbers with an odd number of prime factors from those with an even number, and prime is an odd-count condition.

Reading those two side by side is the clearest statement of where the difficulty sits. It is not that the primes near a given point are mysterious; it is that every available method measures them in bulk, and the open questions all ask about a fixed, tiny window.

The parity barrier is worth one more sentence, because it explains the shape of every result in that list. A sieve counts numbers surviving the removal of multiples, and the count it produces is insensitive to a certain symmetry — swapping the roles of numbers with an odd and an even number of prime factors leaves its estimates unchanged. So it can prove there are infinitely many $n$ with $n$ and $n + 2$ both having few prime factors, and it cannot cut few down to one, because that is precisely the distinction its estimates are blind to. Every one of Chen’s, Zhang’s and Iwaniec’s results sits exactly at that wall.

The heuristics, and what they are worth #

Every open family above has a conjectured count, and the conjectures agree with the measurements to a percent or two over the ranges anybody can compute.

They come from a model, and the model is worth stating because it is the thing everybody’s intuition is actually running on. Treat a number near $x$ as prime with probability $1/\ln x$, independently, then correct for the obvious dependencies — a number and its neighbour are not independent about divisibility by two, which is where the constants in Hardy and Littlewood’s predictions come from.

The model is not a theorem and cannot become one, since it assumes exactly the independence that the question is about. But it is right about everything it can be checked against, including the density of the primes themselves and the intervals that are never empty, which is why nobody doubts the answers even while nobody can prove them.

The gap between confidence and proof is what this rung measures, and the figures make it concrete: five curves, three of which are conjectures dressed exactly like the two that are theorems.

What a proof would have to do #

It is worth asking what is actually missing, since “nobody has proved it” is not a description of anything.

For the twin primes, the missing ingredient is a lower bound on how often two events happen together, where each event is being prime and the two are two apart. Every method available gives upper bounds of the right order and lower bounds that collapse to nothing, because the terms that would give a lower bound arrive with signs nobody can control. That is a technical statement, and it is the technical statement — the difficulty is in a sign, not in a mystery about the primes.

For the Mersenne primes the missing ingredient is different in kind. Nothing forbids proving them infinite; there is simply no known handle on the primality of $2^n - 1$ beyond the special test that makes them computable, and a test that decides one case at a time can never settle infinitely many. Each new Mersenne prime is found by running that test on exponents in turn, which is search rather than mathematics — successful search, and it produces the largest numbers anybody has proved prime, but it moves no closer to the general statement with each success.

And that is the sharpest contrast in the whole rung. The largest known prime is a Mersenne prime with tens of millions of digits, found by a computation of enormous scale. The proof that there is no largest prime at all takes three lines and was written down twenty-three centuries ago. Neither has anything to say to the other.

What this rung settles #

That the difficulty of proving an infinitude is a property of the method’s requirements rather than of the family’s plausibility.

Euclid’s construction needs closure under an arithmetic operation. Euler’s needs density. Dirichlet’s needs an Euler product. Take a family that has none of the three — the twin pairs, the primes one more than a square, the Mersenne primes — and there is nothing left to try, however abundant the family looks.

And the corollary, which is the reason to be careful when reading any of the figures here: a count that matches a conjecture is a check on the conjecture, not evidence for the theorem. Both are worth having and only one of them is a proof, and the whole distinction is visible in a picture where three curves are dashed and two are not, and everything else about them is the same.

Sideways, the same distinction runs through the rest of the subject: the sieve written as a product is the mechanism that settles the primes, always one before the double is a statement about intervals that a density argument can reach, and the primes drawn on a spiral is the shape of the evidence that has convinced everybody of things nobody can prove.