Brun Sieve

Sieve Methods

Sieve methods are techniques for counting integers that remain after removing residue classes modulo primes.

The basic idea is ancient. To find primes up to $x$ , one removes multiples of small primes:

2,3,5,7,\ldots

The remaining numbers have no small prime factors. This is the idea behind the sieve of Eratosthenes.

Modern sieve theory turns this procedure into a quantitative analytic method. It estimates the size of sets after many congruence restrictions have been imposed.

Sifting a Set

Let

A

be a finite set of integers. Let

P(z)=\prod_{p<z}p.

The sifted set is

S(A,z) = \#\{a\in A:(a,P(z))=1\}.

Thus $S(A,z)$ counts elements of $A$ not divisible by any prime less than $z$ .

For example, if

A=\{1,2,\ldots,x\},

then $S(A,z)$ counts integers up to $x$ with no prime factor below $z$ .

The Basic Heuristic

For a fixed prime $p$ , the probability that a random integer is not divisible by $p$ is

1-\frac1p.

Assuming approximate independence over primes $p<z$ , one expects

S(A,z) \approx |A| \prod_{p<z} \left(1-\frac1p\right).

Mertens’ theorem gives

\prod_{p<z} \left(1-\frac1p\right) \asymp \frac1{\log z}.

Thus sieving by primes less than $z$ should reduce the set by roughly a logarithmic factor.

Brun’s Idea

Brun’s sieve refines inclusion-exclusion.

Exact inclusion-exclusion gives

S(A,z) = \sum_{d\mid P(z)} \mu(d)A_d,

where

A_d=\#\{a\in A:d\mid a\}.

This formula is exact but impractical because it has too many terms and large cancellations.

Brun’s idea is to truncate inclusion-exclusion in a controlled way. Instead of using all divisors $d\mid P(z)$ , one keeps only divisors with restricted prime factor count or bounded size.

This produces upper and lower bounds rather than exact formulas.

Upper and Lower Bounds

Brun’s sieve gives inequalities of the form

S(A,z) \leq X V(z)+\text{error}

and

S(A,z) \geq X V(z)+\text{error},

where $X$ is the expected size of $A$ , and

V(z)=\prod_{p<z}\left(1-\frac{\omega(p)}p\right).

Here $\omega(p)$ measures how many residue classes modulo $p$ are removed.

For ordinary primes, usually $\omega(p)=1$ . For twin-prime-type problems, often $\omega(p)=2$ for odd primes.

Twin Prime Application

To study twin primes, consider

A=\{n(n+2):n\leq x\}.

If both $n$ and $n+2$ are prime, then $n(n+2)$ has very few prime factors.

For each odd prime $p$ , the condition

p\mid n(n+2)

excludes two residue classes:

n\equiv0\pmod p, \qquad n\equiv-2\pmod p.

Thus the local density factor is approximately

1-\frac2p.

Brun’s sieve can estimate how many $n\leq x$ avoid these exclusions for small primes.

Brun’s Theorem

Brun proved that the sum of reciprocals of twin primes converges:

\sum_{\substack{p\text{ prime}\\p+2\text{ prime}}} \frac1p <\infty.

This is now called Brun’s theorem.

It contrasts sharply with Euler’s theorem:

\sum_p\frac1p=\infty.

Thus even if infinitely many twin primes exist, they are much sparser than the full set of primes.

The value of the convergent sum is called Brun’s constant.

Almost Primes

Brun’s sieve is especially effective at proving results about almost primes.

An almost prime is an integer with only a bounded number of prime factors.

For example, Brun’s methods can show that there are infinitely many integers $n$ such that both

n \quad\text{and}\quad n+2

have only a bounded number of prime factors.

This is weaker than the Twin Prime Conjecture but still a deep approximation to it.

The Parity Barrier

Classical sieve methods face a serious limitation called the parity problem.

Roughly, sieves are good at detecting whether an integer has small prime factors, but they have difficulty distinguishing numbers with an odd number of prime factors from numbers with an even number of prime factors.

Since primes have exactly one prime factor, this limitation prevents classical sieves from proving many prime-pattern conjectures directly.

The parity barrier explains why Brun’s sieve can prove results about almost primes but not the Twin Prime Conjecture itself.

Dimension of a Sieve

The quantity $\omega(p)$ determines the sieve dimension.

For ordinary prime detection, one removes one residue class modulo each prime, giving dimension $1$ .

For twin primes, one removes two residue classes modulo each odd prime, giving dimension $2$ .

The dimension affects the expected size of the sifted set. In dimension $2$ , one expects a factor roughly

\frac1{(\log z)^2}.

This matches the heuristic that twin primes up to $x$ should occur with frequency about

\frac{x}{(\log x)^2}.

Importance

Brun’s sieve marks the beginning of modern sieve theory.

It introduced a systematic way to replace exact inclusion-exclusion by controlled upper and lower bounds. It also showed that one can obtain meaningful results about prime patterns even without proving the full conjectures.

The method leads naturally to later developments such as Selberg’s sieve, the large sieve, Chen’s theorem, and modern bounded-gap methods.