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 $\le 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 $\le z$. The object of the sieve is to estimate

:$S(A,P,z) = \left\vert A \setminus \bigcup_ A_p \right\vert .$

We assume that , ''A''_''d'', may be estimated by

:$\left\vert A_d \right\vert = \frac 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_ \mu(d) f(n/d)$
:$f(n) = \sum_ g(d)$

where μ is the Möbius function.
Put

:$V(z) = \sum_ \frac.$

Then

:$S(A,P,z) \le \frac + O\left( \right)$

where _1,d_2/math> denotes the least common multiple of $d_1$ and $d_2$. It is often useful to estimate $V(z)$ by the bound

:$V(z) \ge \sum_ \frac . \,$

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'') .

References

*
*
*
*
*
* {{cite journal , first=Atle , last=Selberg , authorlink=Atle Selberg , title=On an elementary method in the theory of primes , journal=Norske Vid. Selsk. Forh. Trondheim , volume=19 , year=1947 , pages=64–67 , zbl=0041.01903 , issn=0368-6302

Sieve theory