Selberg's Sieve

Selberg's sieve obtains sharp upper bounds by optimizing a quadratic form rather than truncating inclusion-exclusion. It is cleaner and often sharper than Brun's combinatorial sieve, and its optimization framework is foundational for modern sieve theory.

The Selberg Upper Bound Sieve

Definition7.3Selberg's Sieve

Selberg's sieve bounds $S(\mathcal{A}, \mathcal{P}, z)$ from above by writing: $S \leq \sum_{a \in \mathcal{A}} \left(\sum_{\substack{d | (a, P(z)) \\ d \leq D}} \lambda_d\right)^2$ where $\lambda_1 = 1$ and the $\lambda_d$ are real weights to be optimized. Expanding and using $|\mathcal{A}_d| = \frac{\omega(d)}{d}X + r_d$ : $S \leq X \cdot \sum_{\substack{d_1, d_2 \leq D}} \frac{\lambda_{d_1}\lambda_{d_2}\omega([d_1,d_2])}{[d_1,d_2]} + \text{remainder}$ The quadratic form in $\lambda$ is minimized by solving a linear system, giving the Selberg main term: $S \leq X/G(z) + \text{error}$ where $G(z) = \sum_{d \leq D} \mu^2(d) \prod_{p|d}\frac{\omega(p)}{p - \omega(p)}$ .

ExampleSelberg Sieve for Primes

For counting primes in $[1, x]$ with $\omega(p) = 1$ , $D = x^{1/2}$ : $\pi(x) \leq \frac{2x}{\log x}(1 + o(1))$ . The constant 2 (vs. the PNT's 1) reflects the sieve's inability to distinguish even/odd number of prime factors. For twin primes $\{n : n, n+2 \text{ both prime}\}$ with $\omega(p) = 2$ for $p > 2$ : $\pi_2(x) \leq \frac{8\mathfrak{S}_2 x}{(\log x)^2}$ where $\mathfrak{S}_2 = \prod_{p>2}\frac{p(p-2)}{(p-1)^2} \approx 0.66$ . The conjectured asymptotic has coefficient $2\mathfrak{S}_2$ , so the sieve overshoots by a factor of 4.

The Lambda-Squared Method

Definition7.4Selberg's Lambda-Squared Sieve

The optimal weights in Selberg's sieve satisfy $\lambda_d = \mu(d) \prod_{p|d}\frac{\omega(p)}{p - \omega(p)} \cdot \frac{G(z, d)}{G(z)}$ where $G(z, d) = \sum_{\substack{e \leq D/d \\ (e, P(z)/d)}} \mu^2(e)\prod_{p|e}\frac{\omega(p)}{p-\omega(p)}$ is a truncated version of $G(z)$ . These weights decay smoothly, making the remainder terms manageable.

RemarkSelberg Sieve vs. Combinatorial Sieves

Selberg's sieve gives the same quality upper bounds as the best combinatorial sieves (Brun's pure sieve) but with a cleaner structure. The beta-sieve (Rosser-Iwaniec) extends Selberg's ideas to provide both upper and lower bounds, with continuous approximations $F(\beta)$ and $f(\beta)$ (sifting limit) satisfying differential-delay equations. For the linear sieve ( $\kappa = 1$ ): $f(s) = 2e^\gamma/s$ for $2 \leq s \leq 4$ , and $f(s) > 0$ for all $s > 2$ .

The Fundamental Lemma

ExampleSieve Fundamental Lemma

The fundamental lemma of sieve theory: for $D = z^s$ with $s > 1$ , $S(\mathcal{A}, \mathcal{P}, z) = X \prod_{p < z}(1 - \omega(p)/p)(1 + O(e^{-s})) + \text{remainder}$ . As $s \to \infty$ , the sieve estimate approaches the "expected" answer $X\prod(1-\omega(p)/p)$ . The error $O(e^{-s})$ is exponentially small in $s = \log D/\log z$ , but the limitation is controlling the remainder terms $\sum|r_d|$ for $d \leq D$ .