ConceptComplete

Classical Sieve Methods

Sieve methods estimate the size of sets defined by divisibility conditions. Starting from Eratosthenes' sieve, the modern theory develops upper and lower bounds that approach the truth for many prime-counting problems.


Eratosthenes and Legendre

Definition7.1Sieve Setup

The sieve problem: estimate S(A,P,z)={aA:(a,P(z))=1}S(\mathcal{A}, \mathcal{P}, z) = |\{a \in \mathcal{A} : (a, P(z)) = 1\}| where A\mathcal{A} is a finite set of integers, P\mathcal{P} is a set of primes, and P(z)=pP,p<zpP(z) = \prod_{p \in \mathcal{P}, p < z} p. The sifted set consists of elements of A\mathcal{A} not divisible by any pPp \in \mathcal{P} with p<zp < z. By inclusion-exclusion: S(A,P,z)=dP(z)μ(d)AdS(\mathcal{A}, \mathcal{P}, z) = \sum_{d | P(z)} \mu(d) |\mathcal{A}_d| where Ad={aA:da}\mathcal{A}_d = \{a \in \mathcal{A} : d | a\}.

Definition7.2Sieve Dimension and Density

Write Ad=ω(d)dX+rd|\mathcal{A}_d| = \frac{\omega(d)}{d} X + r_d where X=AX = |\mathcal{A}|, ω\omega is a multiplicative function (the sieve density), and rdr_d is the remainder term. The sieve dimension κ\kappa is defined by p<zω(p)pκloglogz\sum_{p < z} \frac{\omega(p)}{p} \approx \kappa \log\log z. For primes: κ=1\kappa = 1 (linear sieve). For twin primes: κ=2\kappa = 2 (2-dimensional sieve). The dimension governs the difficulty: κ=1\kappa = 1 is the easiest, higher κ\kappa gives weaker results.


Brun's Sieve

ExampleBrun's Theorem on Twin Primes

Brun's combinatorial sieve truncates the inclusion-exclusion at level DD, bounding SS by alternating sums. Brun proved: {px:p+2 is prime}x(logx)2|\{p \leq x : p+2 \text{ is prime}\}| \ll \frac{x}{(\log x)^2}, and the sum twin p1/p<\sum_{\text{twin } p} 1/p < \infty (Brun's constant B1.902B \approx 1.902). While this does not prove infinitely many twin primes, it shows they are rare enough for the reciprocal sum to converge.

RemarkSieve Limitations: The Parity Problem

A fundamental limitation: no sieve of dimension 1 can detect whether nn has an even or odd number of prime factors. This means sieves alone cannot prove the twin prime conjecture or Goldbach's conjecture -- they can only show the count is of the right order of magnitude. Breaking the parity barrier requires additional input: bilinear forms (Friedlander-Iwaniec), algebraic structure (Green-Tao), or L-function non-vanishing.