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 {\displaystyle A} be a set of positive integers ≤ x {\displaystyle \leq x} and let P {\displaystyle P} be a set of primes. Let A d {\displaystyle A_{d}} denote the set of elements of A {\displaystyle A} divisible by d {\displaystyle d} when d {\displaystyle d} is a product of distinct primes from P {\displaystyle P} . Further let A 1 {\displaystyle A_{1}} denote A {\displaystyle A} itself. Let z {\displaystyle z} be a positive real number and P ( z ) {\displaystyle P(z)} denote the product of the primes in P {\displaystyle P} which are ≤ z {\displaystyle \leq z} . The object of the sieve is to estimate
S ( A , P , z ) = | A ∖ ⋃ p ∣ P ( z ) A p | . {\displaystyle 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
| A d | = 1 f ( d ) X + R d . {\displaystyle \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 ) = ∑ d ∣ n μ ( d ) f ( n / d ) {\displaystyle g(n)=\sum _{d\mid n}\mu (d)f(n/d)}
f ( n ) = ∑ d ∣ n g ( d ) {\displaystyle f(n)=\sum _{d\mid n}g(d)}
where μ is the Möbius function. Put
V ( z ) = ∑ d < z d ∣ P ( z ) 1 g ( d ) . {\displaystyle V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.}
Then
… excerpt ends here. Continue reading the full article.
