29
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 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$
    – Stanley Yao Xiao
    Commented 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$
    – Greg Martin
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 10, 2016 at 1:22

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Denis Chaperon de Lauzières
    Commented 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$
    – Greg Martin
    Commented Mar 24, 2016 at 7:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .