Selberg sieve

From Encyclopedia of Mathematics
Jump to: navigation, search

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}\label{e: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 \ref{e: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.


[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:
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article