# Why is there a Parity Problem in Sieve Theory and not a Mod p problem for any other p?

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?

• I don't know the answer, but one possibility is that mod 2 is the only case where both roots of unity are real – Stanley Yao Xiao Mar 9 '16 at 19:27
• One probably pertinent detail is that the Möbius function (herald of inclusion-exclusion) takes values that are $\pm1$, as opposed to higher roots of unity. – Greg Martin Mar 9 '16 at 21:12
• Agree, but what if we choose (the less arithmetically natural but essentially equivalent) $a_n = 3$ iff $3 | \omega(n)$? Somehow the Mobius function (and therefore the parity of the number of prime factors) is distinguished in sieve theory because it is the ideal coefficient you put against an arithmetic progression - however, it's not clear to me how this relates to the inability to detect parity of prime factors within any given arithmetic progression. – Xiaoyu He Mar 9 '16 at 23:29
• Interesting question! There is something irregular 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. – Terry Tao Mar 10 '16 at 0:08
• Yes. For instance I think one can show that the series $\sum_n \frac{\zeta_3^{\omega(n)}}{n} \log n$ is not conditionally convergent, basically because the derivative of the Dirichlet series blows up at s=1. This shows that $\zeta_3^{\omega(n)}$ does not oscillate nearly as well as a random sequence. – Terry Tao Mar 10 '16 at 1:22

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.
• For polynomials over finite fields, the analogue of this formula also comes with the $1/\Gamma(z)$, and there is a proof that shows that its origin lies in the distribution of the number of (long) cycles of random permutations (this is explained in "Mod-poisson convergence in probability and number theory", arXiv:0905.0318). – Denis Chaperon de Lauzières Mar 24 '16 at 6:22
• The $1/\Gamma(z)$ factor comes from the related formula $\sum_{n\le x} d_z(n) = (1/\Gamma(z) + o(1)) x(\log x)^{z-1}$. Here $d_z(n)$ is the coefficient of $\zeta(s)^z$, and the $1/\Gamma(z)$ in the main term comes from integrating essentially $\zeta(s)^z x^s$ around the singularity at $s=1$. Indeed, in this alternate version, the main term disappears at every negative integer, not just $-1$; it's the passing from $d_z(n)$ to $z^{\Omega(n)}$ where the restriction $|z|<2$ arises (basically since $2^{\Omega(n)}$ is huge when $n$ is a power of $2$ or nearly so). – Greg Martin Mar 24 '16 at 7:03