Why do sieves have the parity problem?

Question

Sieve methods have the "parity problem".

Terry Tao gives a "rough" statement of the problem: If A is a set whose elements are all products of an odd number of primes (or are all products of an even number of primes), then (without injecting additional ingredients), sieve theory is unable to provide non-trivial lower bounds on the size of A. Also, any upper bounds must be off from the truth by a factor of 2 or more.

I understand the above and what the parity problem is, but I still don't understand why sieve methods actually have the parity problem.

Are there are recommended references for trying to further understand why this problem exists / is anyone able to explain further?

Thanks.

Answer 1

In general, sieve theorists are constructing functions $\rho_d^\pm$ such that

$$ \sum_{d|n}\rho_d^-\le\sum_{d|n}\mu(d)\le\sum_{d|n}\rho_d^+\tag1 $$

Although Selberg's $\Lambda^2$-sieve uses a different construction, we can still transform his quadratic form into a certain $\rho_d^+$:

$$ \left(\sum_{d|n}\lambda_d\right)^2=\sum_{d|n}\underbrace{\sum_{[d_1,d_2]=d}\lambda_{d_1}\lambda_{d_2}}_{\rho_d^+} $$

Since Selberg's $\rho_d^+$ vanishes for large $d$, we can assume a more powerful sieve satisfies the following conditions:

1. There exists a fixed $A>0$ such that $|\rho^\pm_d|\le A^{\nu(d)}$, where $\nu(d)$ denotes the number of distinct prime factors of $d$. This is inspired by the fact that Selberg's $\rho_d^+$ satisfies this condition with $A=3$.

2. There exists a fixed $D>0$ such that $\rho^\pm_d=0$ whenever $d$ exceeds $D$. We often regard $D$ as the support level of $\rho^\pm_d$.

With these two assumptions in our head, we can start discussing the parity problem of sieves.

Let $\Omega(n)$ denote the number of prime divisors (counted with multiplicities) of $n$, so we can define the following counting function:

$$ \Phi_v(x,z)=\#\{n\le x:\Omega(n)\equiv v\pmod2,p|n\Rightarrow p>z\} $$

From the definition, we know $\Phi_1(x,z)$ is counting certain numbers with an odd number of prime factors, whereas $\Phi_2(x,z)$ is counting some numbers that possess an even number of prime factors.

By Möbius inversion, we know that if $P$ denotes the product of primes $\le z$, then

$$ \Phi_v(x,z)=\sum_{\substack{n\le x\\\Omega(n)\equiv v(2)}}\sum_{d|(n,P)}\mu(d)\le\sum_{\substack{n\le x\\\Omega(n)\equiv v(2)}}\sum_{d|(n,P)}\rho^+_d:=\Phi_v^+(x,z)\tag2 $$

By an interchange of summation order, we have

$$ \Phi_v^+(x,z)=\sum_{d|P}\rho^+_d\color{red}{\sum_{\substack{n\le x\\\Omega(n)\equiv v(2)\\d|n}}1}\tag3 $$

To estimate the red sum, we introduce Liouville's function $\lambda(n)=(-1)^{\Omega(n)}$, which satisfies the following property:

There exists a constant $c>0$ such that $$\sum_{n\le x}\lambda(n)\ll x\exp\left(-c\sqrt{\log x}\right)$$

Why is this relevant? We can construct the following characteristic function

$$ {1+(-1)^v\lambda(n)\over2}= \begin{cases} 1 & \Omega(n)\equiv v\pmod 2\\ 0 & \text{otherwise} \end{cases} $$

so plugging into (3), we found that if $z\le x$ and $D=x^\theta$ for some $0<\theta<1$, then there exists a $0<c_1<c$ such that

$$ \Phi_v^+(x,z)=\frac x2\sum_{d|P}{\rho_d^+\over d}+O\left\{x\exp\left(-c_1\sqrt{\log x}\right)\right\}\tag4 $$

By definition, we know that the prime number theorem indicates that

$$ \Phi_1(x,\sqrt x)\sim{x\over\log x} $$

and (4) suggests that the asymptotic formula for $\Phi_v(x,z)$ does not depend on the choice of $v$, so from (2) we know

$$ \Phi_v^+(x,\sqrt x)\ge[1+o(1)]{x\over\log x}\tag5 $$

for all $v$. Because prime numbers can only possess an odd number of prime factors, we know $\Phi_2(x,\sqrt x)=O(1)$, and (5) indicates that $\rho_d^+$ is unable to give nontrivial upper bounds in this situation. This is why we say that sieves have parity problem.