# Selberg sieve

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 Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap 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) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert .$

We assume that |Ad| may be estimated by

$\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) = \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_{\begin{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)} + O\left({\sum_{\begin{smallmatrix} d_1,d_2 < z \\ d_1,d_2 \mid P(z)\end{smallmatrix}} \left\vert R_{[d_1,d_2]} \right\vert} \right) .$

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 nx such that n is coprime to φ(n) is asymptotic to e x / log log log (x) .
How to Cite This Entry:
Richard Pinch/sandbox-CZ. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-CZ&oldid=45660