Selberg sieve
# Selberg sieve

In number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s.

## 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 $A$ be a set of positive integers $\leq x$ and let $P$ be a set of primes. Let $A_{d}$ denote the set of elements of $A$ divisible by $d$ when $d$ is a product of distinct primes from $P$. Further let $A_{1}$ denote $A$ itself. Let $z$ be a positive real number and $P(z)$ denote the product of the primes in $P$ which are $\leq z$. The object of the sieve is to estimate

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

We assume that $|A_d|$ may be estimated by

    $\left\vert A_{d}\right\vert ={\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

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

where μ is the Möbius function.

Put

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

Then

    $S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right)$

where $[d_{1},d_{2}]$ denotes the least common multiple of $d_{1}$ and $d_{2}$. It is often useful to estimate $V(z)$ by the bound

    $V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,$

## Applications

* The Brun–Titchmarsh theorem on the number of primes in arithmetic progression;
* The number of n ≤ x such that n is coprime to φ(n) is asymptotic to $e^{−γ}$ x / log log log (x) .
