The "parity problem" in sieve theory, so far as I understand it, is the fact that sieves can't distinguish between primes and $2$-almost primes, numbers with exactly two prime factors, and will always be off by a factor of two. Of course as stated this is false: there are way more $2$-almost primes ($\frac{N\log \log N}{\log N}$) than primes ($\frac{N}{\log N}$) – what we really mean is either (a) $2$-almost primes weighted by the second von Mangoldt function, or (b) $2$-almost primes with no small prime factors.
Terry Tao gives an explanation for this phenomenon: look at the sequence $a_n = 1+\lambda(n)$ where $\lambda(n)$ is the parity of the number of prime factors of $n$, counting multiplicity. This sequence is the indicator (x2) of the numbers with an even number of prime factors. Assuming Riemann Hypothesis this sequence looks almost exactly like the constant function along arithmetic progressions, so sieves should not be able to distinguish $\sum_{prime} a_p= 0$ and the prime counting function.
My question is why this problem doesn't happen for any other moduli. If we picked $a_n = 1+\zeta_3 ^{\Omega(n)}$ instead, where $\Omega(n)$ is the number of prime factors and $\zeta_3$ is a cube root of unity, why doesn't this force a "mod 3" problem? Why can sieves distinguish between numbers with $0$, $1$, or $2$ mod $3$ prime factors?
Best Answer
I found the answer from Zeb Brady. The relevant method is the Selberg-Delange method, see for example this paper. In particular Selberg proved that the average order of $z^{\Omega(n)}$, where $|z| < 2$ is not $-1$ (when it would be a pole of $\Gamma(z)$) is estimated by
$$ \sum_{n\le x} z^{\Omega(n)} = (\frac{f(1,z)}{\Gamma(z)}+o(1)) x (\log x)^{z-1} $$
where $f$ is some convergent Euler product.
So for $z$ any root of unity other than $-1$ we get a comparatively huge main term (as Terry's comments predict). Maybe other people can comment on where the $1/\Gamma(z)$ comes from and how it allows Mobius to cancel unlike everything else.