Two halves a sieve cannot tell apart

The sieve that cannot finish described, in words, the obstruction that stops every sieve method short of the twin prime conjecture: a sieve works from counts of how many numbers each small divisor divides, and those counts cannot tell a number with an odd number of prime factors from one with an even number. It named the example that proves this as a debt — Atle Selberg’s, from the 1940s — to be built rather than described.

This essay builds it. The construction is short and completely explicit, and it has the unusual property of being an impossibility result that can be checked by counting. Nothing about it is conjectural; what it shows is that a certain kind of argument, however refined, cannot reach a certain kind of conclusion.

Splitting the numbers by the parity of their factors #

Every whole number above 1 is a product of primes, and the number of primes in the product — counting repeats, so that $12 = 2 \cdot 2 \cdot 3$ has three — is written $\Omega(n)$. Sort the numbers by whether $\Omega(n)$ is odd or even. The primes are all in the odd half, since each has exactly one prime factor. The products of two primes, like $6$, $15$ and $49$, are all in the even half. Products of three are odd again, and so on.

The sorting has a compact form. Let $\lambda(n) = (-1)^{\Omega(n)}$, which is $-1$ on the odd half and $+1$ on the even half. This is the Liouville function, and it multiplies: $\lambda(mn) = \lambda(m)\lambda(n)$, since the prime factors of a product are the factors of each.

How big are the two halves? Up to $100{,}000$, the odd half has $50{,}144$ members and the even half $49{,}855$: almost exactly half each, with a small excess on the odd side. That near-equality is not an accident, and its precise size is one of the deepest questions in the subject, but first the question that matters for sieves. For now it is enough that the halves are nearly equal in every sense a sieve can measure. Each half contains about half the multiples of 2, half the multiples of 3, half the multiples of every small number, and half of every residue class — so that any statistic built from divisibility alone comes out the same for both, up to small errors. The primes, meanwhile, all sit in one half: the odd one. It is hard to imagine a starker difference between two sets that a counting method treats as identical.

What a sieve is allowed to see #

A sieve estimates how many members of a set survive when every multiple of every small prime is removed. The truncated inclusion–exclusion that every sieve refines works like this: start with the size of the set, subtract how many are divisible by each small prime, add back how many are divisible by each product of two, and so on. The only information about the set it ever uses is, for each small $d$, how many members are divisible by $d$.

So a sieve cannot tell apart two sets that have the same counts of multiples of every small $d$ — or nearly the same, relative to their sizes. And that is exactly the situation with the two halves.

Every ratio sits close to 1. The deviations that exist have a pattern worth noticing: the ratio falls slightly below 1 for divisors $d$ with an odd number of prime factors — 2, 3, 5, 7, 8 — and slightly above for those with an even number — 4, 6, 9, 10. That is the multiplicativity of $\lambda$ at work: a multiple $dm$ of $d$ lands in the odd half exactly when $d$ and $m$ have opposite parities, so the multiples of $d$ split between the halves in a way that mirrors the small overall excess of the odd half, flipped when $d$ itself is odd. The deviations are tiny and, crucially, they carry no information about which half contains the primes; they are a property of the divisor, not of the numbers being sifted.

Sifting both halves #

Now sift. Remove from each half every number that has a prime factor below $\sqrt{x}$, with $x = 100{,}000$, so below $316$. What remains?

In the odd half, a survivor has all its prime factors above $316$. If it had three or more of them, it would be larger than $316^3$, far beyond $x$. So it has exactly one: it is a prime. Every prime between $316$ and $100{,}000$ survives — there are $9{,}527$ of them — and nothing else does.

In the even half, a survivor would have at least two prime factors, both above $316$, and so would be larger than $316^2 > 100{,}000$. There are no survivors at all.

That is Selberg’s example, and the opening figure draws it. Two sets that look the same to a sieve — the ratios above are all close to 1 — produce completely different sifted sets: one holds every large prime below $x$, and the other is empty. A sieve method, which sees only the divisor counts, has no way of knowing whether it is looking at the first set or the second. So whatever lower bound it proves for the number of survivors must also be a lower bound for the second set’s survivors, which is zero.

The same thing at a hundred, by hand #

The example is small enough to check without a machine. Among the numbers from 2 to 100, fifty-one have an odd number of prime factors and forty-eight an even number. Of the odd half, twenty-two are even numbers and fourteen are multiples of three; of the even half, twenty-eight and nineteen. Those are the kinds of counts a sieve works from, and on this small scale they are visibly noisy, but they are of the same order in both halves, and nothing in them singles out one half as special.

Now sift by the primes up to $\sqrt{100} = 10$: remove everything divisible by 2, 3, 5 or 7. In the odd half the survivors are $11, 13, 17, 19, 23, \ldots, 89, 97$ — the twenty-one primes between 10 and 100, and nothing else. In the even half there are no survivors, because the smallest number with two prime factors both above 10 is $11^2 = 121$.

Twenty-one against none. Any argument that looks at the four divisor counts for each half, and at the counts for their products, sees two collections of numbers of similar size with similar divisibility; it must give the same answer for both, and the true answers are twenty-one and zero. The larger figure above is the same computation at a hundred thousand, where the divisor counts agree to within a few per cent and the survivors are 9,527 and none.

Why this blocks the twin primes #

The twin prime problem asks for infinitely many $p$ with $p$ and $p + 2$ both prime. A sieve attacks it by taking the numbers $n(n + 2)$ and sifting out those with small prime factors, hoping to show that the survivors — where both $n$ and $n + 2$ have no small factors — are numerous. The essay on which infinitudes are proved recorded how far that goes: the upper bounds come out of the right size, and the lower bounds do not.

Selberg’s example says why. Among the products $n(n + 2)$ the sieve keeps, the ones where $n$ and $n + 2$ are both prime have exactly two prime factors in total — an even count, so $\lambda(n(n+2)) = +1$. The point is not about that one case, though, but about what the sieve can see.

A sieve’s estimates would be unchanged if the set being sifted were replaced by a version weighted by $1 + \lambda(n)$ or $1 - \lambda(n)$, keeping only one parity class, because the divisor counts barely change. One of those versions contains the twin primes and the other contains none of them, and the sieve cannot tell which it has. Any lower bound a sieve proves for the survivors holds for both versions, and one of them has no twin primes at all — so the lower bound for twin primes it can prove is zero.

What a sieve can do is prove results that are true in both parity classes. That is the shape of every result it has produced. Brun’s upper bound for twin primes, the bounds on primes in short intervals, the almost-primes of every kind — each is a statement that would remain true if the primes were swapped for the numbers with two prime factors, and each was proved by a sieve precisely because it does not need to know the difference.

Chen Jingrun’s theorem of 1973 is the sharpest example. There are infinitely many primes $p$ such that $p + 2$ is either a prime or a product of two primes. The two cases have opposite parity, the sieve cannot tell them apart, and so it proves the disjunction — which includes both — and stops. To remove “or a product of two primes” would be to resolve exactly the distinction Selberg’s example shows a sieve cannot see. The figure shows how much larger Chen’s set is: about three and a half times the twin primes, up to a million.

The difference between the halves, summed #

The two halves’ sizes differ by a small amount, and the difference as $x$ grows is the running sum of the Liouville function, $L(x) = \sum_{n \le x} \lambda(n)$.

The sum stays small, and it stays negative. George Pólya conjectured in 1919 that it is never positive past $n = 1$ — that among the numbers up to any bound, those with an odd number of prime factors are never outnumbered. The figure supports him as far as it goes. He was wrong: C. Brian Haselgrove proved in 1958 that the sum eventually becomes positive, without finding where, and Minoru Tanaka found the first crossing in 1980, at $n = 906{,}150{,}257$. It is one of the standard warnings that small cases lie: a pattern holding for the first nine hundred million numbers can fail.

How large the sum can get is tied to the deepest open problem in the subject. The statement that $|L(x)|$ grows no faster than $x^{1/2 + \varepsilon}$, for every $\varepsilon > 0$, is equivalent to the Riemann hypothesis — the same statement that controls how accurately the primes can be counted. The sieve’s blindness to parity and the size of the prime-counting error are two faces of one question: how evenly $\lambda$ takes its two values.

How the barrier has been broken, and how not #

The parity obstruction is a statement about sieves that use divisor counts alone. It is not a statement about the primes, and it can be circumvented by bringing in information of another kind.

John Friedlander and Henryk Iwaniec did exactly that in 1998, proving that there are infinitely many primes of the form $a^2 + b^4$ — a set so thin that no sieve could reach it — by combining a sieve with estimates of a different shape, sums over pairs of numbers called bilinear forms, which carry the parity information a plain sieve discards. Roger Heath-Brown did the same for primes of the form $a^3 + 2b^3$. Those are the known ways across the barrier, and each works for a special problem.

The breakthroughs on bounded gaps between primes, by Yitang Zhang in 2013 and by James Maynard and Terence Tao after him, did not cross it. Maynard’s method shows that among any admissible pattern of enough numbers, at least two are prime infinitely often — and “at least two out of fifty” is a statement that holds in both parity classes, so the barrier does not apply to it. That is why those results give gaps bounded by 246 and cannot give gaps of 2: getting both members of a pair to be prime is exactly the parity-sensitive question.

Parity in other disguises #

The Liouville function is one of a family of signs that encode how a number factors, and the parity problem reappears wherever one of them does. Its close relative, the Möbius function $\mu(n)$, is $\lambda(n)$ for numbers with no repeated prime factor and zero otherwise, and the statement that $\sum_{n \le x} \mu(n)$ grows more slowly than $x$ is equivalent to the prime number theorem. So the fact that the two halves are nearly equal in size is not a curiosity about factorisation: it is, in a precise sense, the same fact as the prime number theorem’s count.

The twin prime problem has a parity version too. Sarvadaman Chowla conjectured that $\lambda(n)$ and $\lambda(n + 2)$ behave like independent random signs — that $\sum_{n \le x} \lambda(n)\lambda(n+2)$ is small compared with $x$. That statement is exactly the kind of information a sieve lacks, and if it were known in a strong enough form the parity obstruction would dissolve for twin primes. Terence Tao proved an averaged version of the two-point case in 2015, and that result was strong enough to settle Paul Erdős’s discrepancy problem; the full conjecture remains open.

The same sign problem sits under the essay on primes in every residue class, in a disguise: there the primes in a class are counted by averaging characters, and the proof works because the characters’ sums over primes are controlled. The Liouville function is the sign that no averaging over residue classes can reach, since it depends on every prime factor rather than on a remainder. Methods that see residues see Dirichlet’s theorem; methods that see only divisor counts, like the sieve that crosses out the composites, see neither the residue classes’ fine structure nor the parity of factors.

What the counts cannot show #

The figures count up to a hundred thousand, a million, two hundred thousand. They show the two halves looking alike to a sieve, the sifted sets diverging, and the Liouville sum staying negative — and the last of those is precisely the kind of pattern that fails at a scale no figure reaches. The parity example itself is exact at every scale, because it is an argument about what survives sifting, not a measurement. The sizes chosen are also far too small to show how slowly the parity information fades. The ratios in the divisor-count figure are a few per cent from 1 at a hundred thousand, and they shrink as the bound grows, but they shrink slowly; a sieve working at larger bounds sees halves that look ever more alike, which is the example’s point, and no figure of finite range can show the limit that makes the argument airtight.

What the pictures cannot show is the theorem the example proves, which is about methods: that every sieve, of any sophistication, using only divisor counts, gives the same bounds for the two halves. That statement is about all possible sieve weights at once, and Selberg’s example establishes it by exhibiting the two sets, not by examining the methods one by one. That is the unusual strength of the argument: it is not a counterexample to one proof but to a whole class of possible proofs, and it needs no knowledge of what those proofs look like beyond the information they are allowed to use.

Still open: primes where the parity has to be seen #

The twin prime conjecture remains open, and so do all the problems that require telling a prime from a product of two primes by counting alone: primes of the form $n^2 + 1$, Goldbach’s conjecture for every even number, and the infinitude of primes $p$ with $(p + 1)/2$ also prime. Each would follow from a method that sees parity, and each is out of reach of the methods that do not.

What is not known is whether there is a general way across the barrier or only special ones. The bilinear-form arguments that proved the $a^2 + b^4$ result depend on the algebra of that particular form, and no one has found an analogue that applies to twin primes. Whether the barrier is a property of sieves alone, or a sign that questions like the twin prime conjecture need an idea of an entirely different kind, is one of the central unknowns of analytic number theory. The recent history is suggestive in both directions: the bounded-gaps breakthroughs showed how much a sieve can still do when the question is shaped to fit inside the barrier, and the Friedlander–Iwaniec theorem showed that the barrier can be crossed when a problem supplies structure of its own. The twin primes have, so far, supplied none.