# Selberg sieve

In mathematics, in the field of 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 ≤ x and let P be a set of primes. Let Ad denote the set of elements of A divisible by d when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ 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 |Ad| 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 Then

$S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2} where [d1,d2] denotes the least common multiple of d1 and d2. It is often useful to estimate V(z) by the bound

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