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. 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 be a set of positive integers and let be a set of primes. Let denote the set of elements of divisible by when is a product of distinct primes from . Further let denote itself. Let be a positive real number and denote the product of the primes in which are . The object of the sieve is to estimate We assume that |Ad| may be estimated by where f is a multiplicative function and X = |A|. Let the function g be obtained from f by Möbius inversion, that is where μ is the Möbius function. Put Then where denotes the least common multiple of and . It is often useful to estimate by the bound 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) .