en.wikipedia.org

Selberg sieve - Wikipedia

From Wikipedia, the free encyclopedia

Atle Selberg

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

{\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

{\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

{\displaystyle g(n)=\sum _{d\mid n}\mu (d)f(n/d)}
{\displaystyle f(n)=\sum _{d\mid n}g(d)}

where μ is the Möbius function. Put

{\displaystyle V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.}

Then

{\displaystyle S(A,P,z)\leq {\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)}

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

{\displaystyle V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,}