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?

  • 2
    $\begingroup$ I don't know the answer, but one possibility is that mod 2 is the only case where both roots of unity are real $\endgroup$ Mar 9, 2016 at 19:27
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 9, 2016 at 21:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Xiaoyu He
    Mar 9, 2016 at 23:29
  • 6
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Mar 10, 2016 at 0:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Mar 10, 2016 at 1:22

1 Answer 1


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.

  • $\begingroup$ 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). $\endgroup$ Mar 24, 2016 at 6:22
  • 1
    $\begingroup$ 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). $\endgroup$ Mar 24, 2016 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.