Sieves are extraordinary machines. Starting from the Selberg sieve and Brun's sieve, they let us count integers with no small prime factors, bound the number of twin primes, and prove that "almost-primes" are plentiful. So it is natural to hope that a clever enough sieve, pushed hard enough, could finally corner the primes themselves — settle the twin-prime conjecture, or Goldbach's.

It cannot. There is a precise, structural reason, discovered by Atle Selberg in the 1940s and named the parity problem. In one sentence: a sieve cannot tell an integer with an even number of prime factors from one with an odd number. Since a prime has exactly one prime factor (odd) and a product of two primes has exactly two (even), any sieve that tries to catch primes catches their even-factored cousins just as well — and that ambiguity, provably, costs it a factor of two and forbids it from ever proving a positive lower bound for the primes alone. This lesson is about why the wall is there, and how the great breakthroughs climb over it.

Counting prime factors: Ω and the Liouville function

Everything hinges on one bookkeeping device. For an integer n \ge 1, let \Omega(n) be the number of prime factors of n counted with multiplicity. So \Omega(12) = \Omega(2^2\cdot 3) = 3, \Omega(p) = 1 for any prime, and \Omega(pq) = 2 for a product of two (not necessarily distinct) primes.

The Liouville function \lambda is the hero (and villain) of this story. The parity problem is the statement that \lambda is, in a precise sense, invisible to sieves — they cannot see the sign, so they cannot separate the +1 integers from the -1 integers.

Seeing the two colours a sieve blends together

Picture the integers n \le 60 split into two colours by the sign of \lambda(n): the "odd" integers (an odd number of prime factors — including every prime) sit below the axis at -1, and the "even" integers (two prime factors, four prime factors, or a perfect square like 36 = 2^2 3^2) sit above at +1. Both colours are woven densely and irregularly through the number line.

A sieve works by assigning smooth, slowly-varying weights to residue classes modulo small primes and adding them up. Such weights are essentially blind to how the two colours are interleaved: as far as the sieve's arithmetic is concerned, the +1 integers and the -1 integers look statistically identical. It sees the union of the two colours perfectly well — but never the boundary between them.

The parity phenomenon, precisely

Here is Selberg's observation in the form used in practice. A (combinatorial) sieve estimates a sum \sum_{n} a_n over a sequence by comparing it against congruence data: how many terms fall in each residue class modulo d, for d below some level of distribution. The barrier is that this data is exactly the same whether you weight each term by 1 or by 1 + \lambda(n).

The key algebraic fact is that \lambda has small partial sums — \sum_{n\le x}\lambda(n) = o(x), and conjecturally as small as O(x^{1/2+\varepsilon}) — yet it correlates with none of the linear (Type-I) congruence data a sieve is built from. It slips between the sieve's fingers.

Worked example: why a sieve lower bound for primes must collapse to zero

Suppose, for contradiction, a purely combinatorial sieve could prove a bound of the form

using only Type-I congruence information about the sifted set. Consider the weight w(n) = \tfrac12\bigl(1 - \lambda(n)\bigr). Since \lambda(n) = -1 exactly when \Omega(n) is odd,

The primes (\Omega = 1) all have w = 1, so they survive the weight. But so does every \Omega = 3 number (8 = 2^3, 12, 18, 20, 27, 28, \dots), every \Omega = 5 number, and so on. The parity principle says the sieve's estimate for \sum w(n) is indistinguishable from its estimate for the complementary weight \tfrac12(1 + \lambda(n)), which keeps only the \Omega-even numbers — and contains no primes at all (bar the empty edge case).

So the very same congruence data must simultaneously support a "there are many primes" reading and a "there are no primes" reading. A sieve, having no way to break the tie, is forced to certify only the weaker of the two — which is the empty one. Its guaranteed lower bound for the primes drops to 0. That collapse is the parity barrier: not a failure to compute, but a genuine ambiguity the input data cannot resolve.

Selberg's two indistinguishable sequences

Selberg made the obstruction vivid with an explicit pair. Consider, up to x,

These two sets have the same count in every residue class modulo every small d, up to an error too small for a sieve to exploit — because their difference is governed entirely by \lambda, whose sums over arithmetic progressions are tiny. A sieve fed the congruence data of A and the congruence data of B literally cannot tell which is which. Yet B contains all the primes and A contains none. Any argument that could give a nonzero lower bound for the primes inside B would give the same bound inside A — where it is false. Contradiction; so no such sieve argument exists.

What sieves can deliver: almost-primes and Chen's theorem

The parity barrier forbids primes, but it does not forbid almost-primes — integers with a bounded number of prime factors. There the factor-of-two ambiguity is affordable, because you are already allowing both an odd and an even factor count. This is exactly the regime where sieves are spectacular.

Chen Jingrun's result is, in a sense, exactly one factor away from Goldbach and the twin-prime conjecture — and that one factor is the parity barrier. Sieve technology (Chen used a weighted sieve of remarkable ingenuity) gets you to P_2 and then stops dead. Turning the P_2 into a genuine prime P_1 is precisely the even-vs-odd distinction that \lambda makes impossible for a sieve alone.

How the breakthroughs beat parity

Every modern advance that does reach primes shares a common move: it smuggles in an arithmetic input the sieve cannot manufacture for itself — something that correlates with \lambda and so breaks the tie. A field guide:

The pattern is unmistakable. A sieve supplies the "Type-I" scaffolding; a separate, harder-won Type-II (bilinear) estimate — often a level-of-distribution statement about how evenly primes spread across arithmetic progressions — supplies the arithmetic muscle that finally distinguishes odd from even. Neither half alone reaches the primes; together they clear the wall.