Proof of the Fundamental Lemma of Sieve Theory

The fundamental lemma provides both upper and lower sieve bounds that approach the "expected" answer as the sifting parameter increases. It quantifies how well the sieve approximates the inclusion-exclusion sum.

Statement

Theorem7.3Fundamental Lemma of Sieve Theory

In the sieve setting with dimension $\kappa$ and sifting level $D = z^s$ , there exist functions $F_\kappa(s)$ and $f_\kappa(s)$ such that: $f_\kappa(s) X V(z) + O(R^-) \leq S(\mathcal{A}, z) \leq F_\kappa(s) X V(z) + O(R^+)$ where $V(z) = \prod_{p < z}(1 - \omega(p)/p)$ , and $R^\pm$ are remainder terms depending on $|r_d|$ for $d \leq D$ . The functions satisfy $F_\kappa(s) \to 1$ and $f_\kappa(s) \to 1$ as $s \to \infty$ , with $F_\kappa(s) - 1 = O(e^{-s})$ and $1 - f_\kappa(s) = O(e^{-s})$ . For the linear sieve ( $\kappa = 1$ ): $f_1(s) > 0$ for all $s > 2$ .

Proof (for the linear sieve, $\kappa = 1$ )

Proof

Step 1: Buchstab identity. The Buchstab identity decomposes the sifting function recursively: $S(\mathcal{A}, z) = S(\mathcal{A}, w) - \sum_{w \leq p < z} S(\mathcal{A}_p, p)$ for any $2 \leq w < z$ , where $\mathcal{A}_p = \{a \in \mathcal{A} : p | a\}$ . This follows from inclusion: an element sifted out between $w$ and $z$ is divisible by exactly one "new" prime $p$ (its smallest factor in $[w, z)$ ).

Step 2: Iterating Buchstab. Apply the identity recursively, alternating upper and lower bounds:

Upper: $S(\mathcal{A}, z) = S(\mathcal{A}, w) - \sum_p S(\mathcal{A}_p, p) \leq S(\mathcal{A}, w)$ (dropping negative terms).
Lower: Keep the first sum and apply an upper bound to $S(\mathcal{A}_p, p)$ : $S(\mathcal{A}, z) \geq S(\mathcal{A}, w) - \sum_p U(\mathcal{A}_p, p)$ where $U$ is an upper bound.

Step 3: Continuous approximation. Replace discrete sums by integrals using the approximation $S(\mathcal{A}_d, z) \approx \frac{\omega(d)}{d}X V(z)/V(p)$ . This leads to integral equations for $F$ and $f$ : $sF_1(s) = \begin{cases} 2e^\gamma & 1 \leq s \leq 3 \\ 2e^\gamma - \int_2^{s-1} f_1(t-1)\frac{dt}{t} & s > 3\end{cases}$ $sf_1(s) = \begin{cases} 0 & 0 < s \leq 2 \\ 2e^\gamma \log(s-1) & 2 < s \leq 4 \end{cases}$ with $F$ and $f$ satisfying the differential-delay equations: $(sF_1(s))' = -f_1(s-1)$ and $(sf_1(s))' = -F_1(s-1)$ for $s > 3$ (resp. $s > 4$ ).

Step 4: Convergence. The alternating Buchstab iterations produce $F_1(s) \downarrow 1$ and $f_1(s) \uparrow 1$ as $s \to \infty$ . The rate is exponential: $|F_1(s) - 1| + |f_1(s) - 1| \ll e^{-s}$ . The error from the continuous approximation is absorbed into the remainder terms $R^\pm$ .

Step 5: Positivity of $f_1$ for $s > 2$ . From the explicit formula $f_1(s) = 2e^\gamma \log(s-1)/s > 0$ for $2 < s \leq 4$ . For $s > 4$ , the positivity follows from the integral equation and induction, since $F_1 > 0$ for all $s$ . This positivity for $s > 2$ is crucial: it means the linear sieve gives a nontrivial lower bound whenever $D > z^2$ . $\square$

■

RemarkHigher-Dimensional Sieves

For $\kappa > 1$ , the functions $f_\kappa$ and $F_\kappa$ satisfy analogous differential-delay equations with different initial conditions. The critical threshold (where $f_\kappa$ becomes positive) is $s > \beta_\kappa$ where $\beta_1 = 2$ , $\beta_2 \approx 4$ , and $\beta_\kappa \to 2e^\gamma \kappa$ as $\kappa \to \infty$ . Higher dimension makes it harder to obtain positive lower bounds.

Proof of the Fundamental Lemma of Sieve Theory

Statement

Proof (for the linear sieve, κ=1\kappa = 1κ=1)

Proof (for the linear sieve, $\kappa = 1$ )