This course develops the main sieve methods of analytic number theory, with an emphasis on how one estimates the size of sets of integers after removing those divisible by many small primes. The central problem is to turn arithmetic information about congruences and divisibility into upper and lower bounds for primes, almost primes, and other sparse sets. Along the way, the course builds a working vocabulary for sifting problems, inclusion-exclusion, and the balance between combinatorial structure and analytic estimates.

The first chapters set up the basic framework by formulating sifting problems and comparing naive inclusion-exclusion with Brun’s pure sieve and related combinatorial ideas. From there, the course moves to Selberg’s upper bound sieve and the linear sieve, which refine the method and make it effective for almost-prime results. The large sieve then introduces a different but complementary analytic tool, leading to results on distribution in arithmetic progressions and culminating in the [Bombieri-Vinogradov theorem](/theorems/7189). The final chapters apply these methods to classical problems such as twin primes, Goldbach-type questions, and almost-prime representations, showing how sieve theory provides both a flexible method and a deep set of consequences in prime number theory.

# Introduction

Sieve methods begin with a simple obstruction: primes are rare, but exact primality is too rigid to detect directly by inclusion-exclusion. The central move of the course is to replace the question "is $n$ prime?" by the more flexible question "has $n$ avoided all small prime divisors?" This chapter fixes the language for that move, explains the scale of the main terms and errors, and gives the first identities that later chapters will sharpen.

The course sits between elementary number theory and analytic estimates for arithmetic progressions. We use Dirichlet convolution, the Mobius function, asymptotic notation, and distribution results for primes as inputs; the new material is the systematic design of weights that count sifted integers from above or below.

## The Problem Sieve Methods Address

How can we count elements of a finite arithmetic set after removing all elements divisible by small primes? If $A$ is a finite set of integers and $P(z)$ is the product of primes below $z$, the rough count is governed by divisibility conditions modulo many primes at once. The difficulty is that exact inclusion-exclusion has too many terms once $z$ is large.

[definition: Sifting Product] The sifting product is the function \begin{align*} P : [2,\infty) \to \mathbb N, \qquad z \mapsto P(z) := \prod_{p < z} p, \end{align*} where the product is over primes $p$. [/definition]

The product $P(z)$ records the primes by which we intend to sift. To turn this product into a counting problem, we need notation for the elements of $A$ that survive all divisibility tests by primes below $z$.

[definition: Sifting Function] Let $A \subset \mathbb Z$ be finite. The sifting function attached to $A$ is the function \begin{align*} S(A,P,\cdot) : [2,\infty) \to \mathbb N \cup \{0\}, \qquad z \mapsto S(A, P, z) := |\{a \in A : \gcd(a, P(z)) = 1\}|. \end{align*} [/definition]

This definition includes the classical example $A = \{1,2,\dots,x\}$, where $S(A,P,z)$ counts integers up to $x$ with no prime factor below $z$. It also includes arithmetic sequences such as $A = \{n(n+2) : n \le x\}$, which appear when studying twin-prime-type questions.

[example: Rough Integers Up To x] Let $A=\{1,2,\dots,x\}$ with $z\le x$. By the definition of $S(A,P,z)$, an integer $n\le x$ is counted exactly when $\gcd(n,P(z))=1$, which means that no prime $p<z$ divides $n$; equivalently, every prime factor of $n$ is at least $z$. For a fixed prime $p<z$, the multiples of $p$ in $\{1,\dots,x\}$ are \begin{align*} p,2p,3p,\dots,\left\lfloor \frac{x}{p}\right\rfloor p, \end{align*} so their number is $\lfloor x/p\rfloor$ and their proportion is $\lfloor x/p\rfloor/x$. Since \begin{align*} \frac{x}{p}-1 < \left\lfloor \frac{x}{p}\right\rfloor \le \frac{x}{p}, \end{align*} we get \begin{align*} \frac{1}{p}-\frac{1}{x} < \frac{1}{x}\left\lfloor \frac{x}{p}\right\rfloor \le \frac{1}{p}. \end{align*} Thus the proportion divisible by $p$ is $1/p+O(1/x)$, and the proportion not divisible by $p$ is $1-1/p+O(1/x)$. The independence heuristic discards the small endpoint errors and multiplies these local survival proportions over the primes $p<z$, giving \begin{align*} S(A,P,z) \approx x\prod_{p<z}\left(1-\frac{1}{p}\right). \end{align*} By *Mertens' theorem*, \begin{align*} \prod_{p<z}\left(1-\frac{1}{p}\right) \sim \frac{e^{-\gamma}}{\log z}, \end{align*} so the predicted main scale is \begin{align*} x\prod_{p<z}\left(1-\frac{1}{p}\right) \sim \frac{e^{-\gamma}x}{\log z}. \end{align*} This is the basic local-product prediction: sieving by primes below $z$ should leave about a constant multiple of $x/\log z$ integers. [/example]

This heuristic explains why a sieve should produce a product of local factors. It does not explain how to control the accumulated error from many residue classes; that is the main technical issue behind the course.

## Inclusion-Exclusion as the Starting Point

What happens if we try to count the sifted set exactly? The condition $\gcd(a,P(z))=1$ can be written using the Mobius function, so the first formula is an exact identity rather than an estimate.

[quotetheorem:7160]

[citeproof:7160]

The identity reduces sifting to the task of estimating the divisibility counts $|A_d|$, but it does not by itself give a usable estimate. The hypothesis $d \mid P(z)$ is doing real work: it restricts the sum to squarefree moduli built from the primes being sieved, so the Mobius coefficient is exactly the inclusion-exclusion sign for the chosen local conditions. If one summed over unrelated divisors, for instance over moduli involving a prime $q \ge z$, the divisibility condition $q \mid a$ would impose a test that is not part of the event $\gcd(a,P(z))=1$, and the resulting expression would no longer be the sifted-set indicator. Thus the theorem is exact bookkeeping for a fixed set of forbidden primes, not an estimate for how often the corresponding residue classes occur.

To turn the identity into an asymptotic statement, each divisibility count must be split into a predicted density and an error. The obstruction is that inclusion-exclusion asks for $|A_d|$ simultaneously for many squarefree $d$, so a single estimate for $|A|$ or for divisibility by one prime is not enough. The page therefore needs a bookkeeping device that records the expected local density for every relevant squarefree modulus and separates it from the part that must later be bounded.

[definition: Local Density Model] Let $A \subset \mathbb Z$ be finite and let $X \in \mathbb R_{+}$. A local density model for $A$ consists of a multiplicative function \begin{align*} g : \{d \in \mathbb N : d \text{ squarefree}\} \to \mathbb R \end{align*} and a remainder function \begin{align*} r : \{d \in \mathbb N : d \text{ squarefree}\} \to \mathbb R, \qquad d \mapsto r_d, \end{align*} such that \begin{align*} |A_d| = g(d)X + r_d \end{align*} for every squarefree $d$. [/definition]