View source for Selberg sieve

{{TEX|done}}

{{MSC|11N35}}

''Selberg method''

A special, and at the same time fairly universal, [[sieve method]] created by A. Selberg [[#References|[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.

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  A. Selberg,   "On an elementary method in the theory of primes"  ''Norsk. Vid. Selsk. Forh.'' , '''19''' :  18  (1947)  pp. 64–67</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  K. Prachar,   "Primzahlverteilung" , Springer  (1957)</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  H. Halberstam,   H.-E. Richert,   "Sieve methods" , Acad. Press  (1974)</TD></TR>
</table>