Selberg sieve

Description

In terms of sieve theory the Selberg sieve is of combinatorial type: that is, derives from a careful use of the inclusion–exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an upper bound for the size of the sifted set.

Let ${\displaystyle A}$ be a set of positive integers ${\displaystyle \le x}$ and let ${\displaystyle P}$ be a set of primes. Let ${\displaystyle A_d}$ denote the set of elements of ${\displaystyle A}$ divisible by ${\displaystyle d}$ when ${\displaystyle d}$ is a product of distinct primes from ${\displaystyle P}$. Further let ${\displaystyle A_1}$ denote ${\displaystyle A}$ itself. Let ${\displaystyle z}$ be a positive real number and ${\displaystyle P(z)}$ denote the product of the primes in ${\displaystyle P}$ which are ${\displaystyle \le z}$. The object of the sieve is to estimate

${\displaystyle S(A,P,z)=\left|A\setminus \bigcup _{p\mid P(z)}{A}_p\right|.}$

We assume that |A_d| may be estimated by

${\displaystyle \left|A_d\right|=\frac{1}{f(d)}X+R_d.}$

where f is a multiplicative function and X = |A|. Let the function g be obtained from f by Möbius inversion, that is

${\displaystyle g(n)=\sum _{d\mid n}\mu (d)f(n/d)}$

${\displaystyle f(n)=\sum _{d\mid n}g(d)}$

where μ is the Möbius function. Put

${\displaystyle V(z)=\sum _{\begin{array}{c}d<z\\ d\mid P(z)\end{array}}\frac{1}{g(d)}.}$

Then

${\displaystyle S(A,P,z)\le \frac{X}{V(z)}+O\left(\sum _{\begin{array}{c}{d}_1,d_2<z\\ d_1,d_2\mid P(z)\end{array}}\left|R_{[d_1,d_2]}\right|\right)}$

where ${\displaystyle [d_1,d_2]}$ denotes the least common multiple of ${\displaystyle d_1}$ and ${\displaystyle d_2}$. It is often useful to estimate ${\displaystyle V(z)}$ by the bound

${\displaystyle V(z)\ge \sum _{d\le z}\frac{1}{f(d)}.}$