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. For each "p" in "P", let "A"_"p" denote the set of elements of "A" divisible by "p" and extend this to let "A"_"d" the intersection of the "A"_"p" for "p" dividing "d", when "d" is a product of distinct primes from "P". Further let A₁ 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

:

We assume that |"A"_"d"| may be estimated by

:$leftvert\; A\_d\; ightvert\; =\; 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

:

Then

:

It is often useful to estimate "V"("z") by the bound

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

Applications

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

References

*
*
*
*
*