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.

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 $\leq x$ and let $P$ be a set of primes. Let $A_{d}$ denote the set of elements of $A$ divisible by $d$ when $d$ is a product of distinct primes from $P$ . Further let $A_{1}$ denote $A$ itself. Let $z$ be a positive real number and $P (z)$ denote the product of the primes in $P$ which are $\leq z$ . The object of the sieve is to estimate

S (A, P, z) = | A ∖ ⋃_{p ∣ P (z)} A_{p} | .

We assume that |A_d| may be estimated by

| A_{d} | = \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 ∣ n} μ (d) f (n / d)

f (n) = \sum_{d ∣ n} g (d)

where μ is the Möbius function. Put

V (z) = \sum_{\begin{matrix} d < z \\ d ∣ P (z) \end{matrix}} \frac{1}{g (d)} .

Then

S (A, P, z) \leq \frac{X}{V (z)} + O (\sum_{\begin{matrix} d_{1}, d_{2} < z \\ d_{1}, d_{2} ∣ P (z) \end{matrix}} | R_{[d_{1}, d_{2}]} |)

where $[d_{1}, d_{2}]$ denotes the least common multiple of $d_{1}$ and $d_{2}$ . It is often useful to estimate $V (z)$ by the bound

V (z) \geq \sum_{d \leq z} \frac{1}{f (d)} .

Applications

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) .

References

Selberg sieve

Description

Applications

References

Navigation menu

Search