# Selberg sieve

2010 Mathematics Subject Classification: *Primary:* 11N35 [MSN][ZBL]

*Selberg method*

A special, and at the same time fairly universal, sieve method created by A. Selberg [1]. The Selberg sieve enables one to obtain a good upper bound of the sifting function $S(A;P,z)$, which denotes the number of elements of a set $A$ of integers that are not divisible by prime numbers $p < z$ and that belong to a certain set $P$ of prime numbers.

Let $P(z) = \prod_{p<z\,;\,p \in P} p$. The Selberg method is based on the obvious inequality $$ \begin{equation}\tag{1} S(A;P,z) \le \sum_{a \in A} \left({ \sum_{d | a\,;\,d | P(z)} \lambda_d }\right)^2 \end{equation} $$ which holds for $\lambda_1 = 1$ and arbitrary real numbers $\lambda_d$ ($d \ge 2$). Selberg's idea consists of the following: Set $\lambda_d = 0$ for $d \ge z$, and minimize the right-hand side of (1) by a suitable choice of the remaining numbers $\lambda_d$ ($2 \le d < z$).

When combined with other sieve methods, the Selberg sieve enables one to obtain lower bounds that are particularly powerful when used with weight functions.

#### References

[1] | A. Selberg, "On an elementary method in the theory of primes" Norsk. Vid. Selsk. Forh. , 19 : 18 (1947) pp. 64–67 Zbl 0041.01903 |

[2] | K. Prachar, "Primzahlverteilung", Die Grundlehren der Mathematischen Wissenschaften 91, Springer (1957) Zbl 0080.25901 |

[3] | H. Halberstam, H.-E. Richert, "Sieve methods", London Mathematical Society Monographs 4, Academic Press (1974) Zbl 0298.10026 |

**How to Cite This Entry:**

Selberg sieve.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Selberg_sieve&oldid=34721