- Selberg sieve
In
mathematics , in the field ofnumber theory , the Selberg sieve is a technique for estimating the size of "sifted sets" ofpositive integer s which satisfy a set of conditions which are expressed by congruences. It was developed byAtle 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 theinclusion-exclusion principle . Selberg replaced the values of theMö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 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) = leftvert A setminus igcup_{p in P(z)} A_p ightvert .
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:V(z) = sum_{egin{smallmatrix}d < z \ d mid P(z)end{smallmatrix frac{mu^2(d)}{g(d)} .
Then
:S(A,P,z) le frac{X}{V(z)} + Oleft({sum_{egin{smallmatrix} d_1,d_2 < z \ d_1,d_2 mid P(z)end{smallmatrix leftvert R_{ [d_1,d_2] } ightvert} ight) .
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
*
*
*
*
*
Wikimedia Foundation. 2010.