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?

somethingirregular about the function $\zeta_3^{\omega(n)}$ that blocks it from being as uniformly distributed as we expect the Liouville function to be - its Dirichlet series looks roughly like $\zeta(s)^{\zeta_3}$, which has no analytic continuation beyond $s=1$ and so cannot obey anything remotely resembling the Riemann hypothesis. But I don't currently see a more elementary reason why $\zeta_3^{\omega(n)}$ has to be irregularly distributed. $\endgroup$ – Terry Tao Mar 10 '16 at 0:08