The sieve that cannot finish

The rung about which infinitudes are proved sorts the candidate families into the settled and the open, and the sorting has a pattern the rung notices and does not explain. The primes are infinite; the primes in any coprime class are infinite; the twin primes are not known to be, nor the primes one more than a square, nor the Mersenne primes.

This rung is about why, and the answer is in two parts. The first is a measurement: the twins are thin, in a sense that can be computed, and thinness kills every argument of the shape that settles the others. The second is structural: the machinery that handles thin sets is the sieve, and the sieve has a ceiling.

Thinness, measured #

Euler’s proof that the reciprocals of the primes diverge is a proof of infinitude that also measures. A sum over a finite set is finite, so divergence gives infinitude — and it gives more, because the rate of divergence says how thick the set is.

Brun proved in 1919 that the same sum over the twin primes converges. The limit is about 1.9022 and is called Brun’s constant, and it is one of the few constants in the subject whose value nobody can compute to more than about ten digits, because the convergence is so slow.

A convergent sum cannot prove its terms are infinite in number. If there were finitely many twins the sum would be finite; the sum is finite; nothing follows. So Brun’s theorem, which is a real theorem about a real quantity, is compatible with the twin primes stopping tomorrow, and it forecloses the one line of attack that works for every family the rung below calls settled.

That is a rare thing to be able to say. Usually the absence of a proof means nobody has found one. Here a specific method has been measured and found to be inapplicable, and the measurement is a figure.

Why the twins are thin #

The convergence is not an accident of the twins and is predictable from a count, which makes the whole situation legible before any theorem is quoted.

Hardy and Littlewood’s conjecture puts the number of twin pairs below $x$ at about $2C_2 \, x/(\log x)^2$, with $C_2$ about 0.6602. The prediction is 1250 pairs below a hundred thousand against 1224 actual, and 8250 below a million against 8169 — accurate to within three per cent at both scales, which is the sort of agreement that makes a conjecture believed.

Now sum the reciprocals. If the $n$-th twin is around $n(\log n)^2$ in size, then the sum of reciprocals behaves like $\sum 1/(n(\log n)^2)$, and that converges — the extra logarithm being exactly enough. The primes have density $1/\log x$ and their reciprocals diverge; the twins have density $1/(\log x)^2$ and theirs converge, and the whole difference is one factor of a logarithm.

Compare with the harmonic series, where the terms vanish and the total does not. The primes are thin enough that the sum climbs like $\log\log x$ rather than $\log x$, which is why the figure’s curve looks nearly flat and is not. The twins are one logarithm thinner still, and that is the difference between nearly flat and actually flat.

So the thinness is not mysterious: it is what the expected count implies. What is remarkable is that the thinness could be proved — by Brun, in 1919, without any of the conjectured count being available — and the proof is the first modern sieve.

Brun’s constant, and the computation it broke #

The constant has an unusual claim to fame and it is worth recording, because it is a genuine instance of a pure computation mattering.

Thomas Nicely set out in 1993 to compute Brun’s constant to more decimal places than anybody had, which needs the twins enumerated far into the range where the partial sums are still moving. In 1994 his results stopped agreeing with themselves between machines, and the discrepancy traced to a division instruction on the Pentium processor that returned wrong answers for a small set of inputs.

The bug was real, it affected every such chip, and the recall cost several hundred million dollars. It was found because somebody was adding up the reciprocals of the twin primes, which is as pure a computation as the subject offers.

The mathematical content of the story is small and the methodological content is not. A computation that runs for months over an enormous range, whose answer is known to converge and whose partial sums are compared against themselves at many scales, is an unusually good test of an arithmetic unit — better than most deliberately written test suites, because it uses the hardware in a pattern nobody designed for.

The sieve, and what a truncation costs #

Brun’s proof of the convergence is itself a sieve, and understanding what a sieve is explains where the ceiling comes from.

Counting the numbers up to $N$ with no prime factor below $z$ is an inclusion–exclusion. Subtract the multiples of each small prime, add back the multiples of each product of two, subtract the products of three, and so on. The formula is exact and it has $2^k$ terms for $k$ small primes, so it is unusable as written.

Every sieve is a way of stopping that sum early, and stopping it early is dangerous.

The truncations alternate: an even number of layers gives an upper bound, an odd number a lower bound. That is Bonferroni’s inequality and it is exact. What the figure shows is that the bounds are useless until nearly all the layers are in — the running total swings by a factor of six past the answer, and the lower bounds spend part of their time below zero.

Every sieve method is a scheme for making that swing smaller, by weighting the terms rather than including or excluding them outright, and the whole technical apparatus of the subject is devoted to it.

Brun’s own scheme is the simplest and it is worth stating. Instead of stopping at a fixed number of layers, stop at a number that grows with the sifting limit, and choose it so that the terms left out are provably smaller than the terms kept. That is enough to get an upper bound of the right order for the twins, which is what proves the convergence of their reciprocals. Selberg’s scheme, twenty years later, replaces the alternating signs with a quadratic form and chooses its weights by minimising — which is why it is optimal among schemes of its shape and why it is still the standard tool.

Both are answers to the same question: which linear combination of the divisor counts is closest to the indicator of the sifted set. A sieve is a linear algebra problem in disguise, and the reason it has a ceiling is that the target it is approximating is not in the span of the data.

The parity problem #

The weighting schemes are good enough to give upper bounds of the right order. They are not good enough to give a positive lower bound for the twins, and the obstruction has been understood since Selberg pointed it out in the 1940s.

A sieve works from counting data: how many members of a set are divisible by each small number. It never sees anything else. And there are two sets with identical counting data of that kind — one consisting of numbers with an even number of prime factors, the other with an odd number — which a sieve cannot tell apart.

Since a prime has one prime factor and a product of two primes has two, a sieve that cannot distinguish even from odd cannot distinguish a prime from a product of two primes. Any lower bound it proves for the twins is equally a lower bound for products of two primes, and the second is much easier to satisfy — so the argument stops before it can conclude anything about primes.

That is the parity problem, and it is not a gap in anybody’s cleverness. It is a statement about what the input to a sieve determines.

The word parity is literal. Assign each number the sign $(-1)$ raised to the number of its prime factors — the Liouville function — and the obstruction is that a sieve’s data does not control the sum of that sign over the sifted set. Control it and the twin prime conjecture would follow; nobody can, and the sum’s behaviour is closely tied to the same question the prime counting function raises, which is why the two difficulties are usually described as one.

It is worth noticing that this is an obstruction of exactly the kind an impossibility theorem lists rather than a difficulty of degree. Sieve theory has been developed for a century since Brun and the ceiling has not moved; what has moved is the set of questions people ask of it.

What a sieve does deliver #

The ceiling is not the whole story, and the results below it are substantial.

Chen’s theorem, 1966: there are infinitely many primes $p$ such that $p + 2$ is either a prime or a product of two primes. That is exactly what a sieve can prove, and the shape of the statement — prime or nearly prime — is the parity problem written into the conclusion.

Brun’s own bound: the number of twin primes below $x$ is at most a constant times $x/(\log x)^2$. That is the right order of magnitude, matching the conjectured count, and it is an upper bound only.

Chen’s theorem deserves a second look because its statement is so nearly the conjecture. It says infinitely many primes $p$ have $p+2$ prime or a product of two primes, and the second alternative is what the parity problem forces into it. If anybody could delete those four words the twin prime conjecture would follow immediately — and the whole content of the obstruction is that deleting them requires information a sieve does not have.

And Zhang’s theorem, 2013: there are infinitely many pairs of primes differing by at most a bounded amount, now known to be at most 246. That is a genuine escape from the ceiling, and it works by proving something about gaps rather than about a fixed difference — which is a question the parity problem does not obstruct, because it does not require deciding whether a specific number is prime.

The pattern is that a sieve can find primes in a set it cannot pin down. Every result above says a prime exists somewhere in a range or in a family; none says a specific arithmetic form is infinitely often prime.

How the counting data runs out #

It is worth being concrete about the information a sieve has, because the phrase “counting data” hides the whole issue.

To sift the numbers up to $N$ for those coprime to every prime below $z$, a sieve is told, for each such prime $p$, how many numbers in its set are divisible by $p$ — and similarly for products. That is a list of counts, one per divisor, and everything the sieve concludes is a function of that list.

The sifting limit $z$ cannot be taken as large as $\sqrt{N}$, which is what would be needed to leave only primes, because the number of terms explodes and the error terms swamp the main one. In practice $z$ reaches about $N^{1/4}$ for a lower bound, and the survivors of sifting up to $N^{1/4}$ include every product of two primes both larger than $N^{1/4}$.

So the survivors are not primes, and the sieve has no way of asking which of them are. The parity problem is that limitation stated as a theorem rather than as an inconvenience.

The upper bound, checked against the count #

Brun’s upper bound and the conjectured count are the same order of magnitude, and putting numbers on the gap says exactly how much a sieve loses.

The conjecture says about $8250$ twin pairs below a million. Brun’s method, run carefully, gives an upper bound of about four times that — the constant a sieve can prove is a small multiple of the constant the count predicts, and improving it has been a minor industry.

A factor of four is a good result for a sieve and it is on the wrong side. An upper bound of four times the truth says the twins are not more common than expected; it says nothing about their being common at all, and multiplying it by anything leaves it an upper bound.

That asymmetry is the parity problem in its practical form. Sieve upper bounds are within a constant of the truth for essentially every problem of this kind. Sieve lower bounds are zero, for the twins and for every problem where the answer would have to be a prime rather than a nearly-prime. One direction is a technical exercise and the other is impossible, and both come from the same counting data.

What the pictures cannot show #

Brun’s constant is measured to a million, where the partial sum is 1.711 against a limit of about 1.9022. The convergence is roughly like one over the logarithm, so reaching two decimal places of the limit by direct summation would need a range far beyond anything drawn.

The inclusion–exclusion figure sifts by ten primes, where the exact sum has a thousand terms and can be accumulated in full. A real sieve sifts by millions of primes and never computes the exact sum, so the figure shows the phenomenon at a size where the answer is available and the danger is visible.

And the parity problem is stated and not demonstrated. Selberg’s example — two sets with identical divisor counts and different numbers of primes in them — is a construction, and constructing one small enough to draw has not been done here.

Where the ladder goes next #

This rung closes the ladder: Euclid, the aimed constructions, the sorted families, the theorem covering every class, and the ceiling on the elementary methods.

Named here as debts. Selberg’s parity example, built rather than described, which would turn the obstruction from a statement into a picture. And the bounded gaps machinery, which is the one genuine escape and which works by a route none of these figures touches.

Sideways, the families this cannot settle are the rung below, the theorem that does settle the residue classes is Dirichlet’s, the sieve in its original form is Eratosthenes’, and the count everything here is measured against is the prime number theorem’s.

What is worth carrying away #

A method that has been measured and found inapplicable is worth more than a method that has merely failed.

Nobody has proved the twin primes infinite, and the usual reading of that is that the problem is hard. The sharper reading is that the standard proof of infinitude — show a sum of reciprocals diverges — provably cannot work, because the sum converges; and that the standard machinery for thin sets provably stops one step short, because its input does not determine the answer.

The habit worth taking is to ask what a method’s input determines. A sieve is given divisor counts and nothing else, and two sets with the same counts must receive the same verdict — so any question distinguishing such sets is outside the method, whatever is done with the counts.

The corollary is about where progress comes from. Zhang’s theorem escaped the ceiling not by improving a sieve but by asking a question the ceiling does not obstruct: bounded gaps rather than a fixed gap. When a method has a proved limit, the productive move is to change the question until it falls outside the limit, and finding which questions do is what knowing the limit is for.