Namespaces
Variants
Actions

Difference between revisions of "Selberg sieve"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
''Selberg method''
+
{{TEX|done}}
  
A special, and at the same time fairly universal, [[Sieve method|sieve method]] created by A. Selberg [[#References|[1]]]. The Selberg sieve enables one to obtain a good upper bound of the shifting function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838501.png" />, which denotes the number of elements of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838502.png" /> of integers that are not divisible by prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838503.png" /> and that belong to a certain set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838504.png" /> of prime numbers.
+
{{MSC|11N35}}
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838505.png" />. The Selberg method is based on the obvious inequality
+
''Selberg method''
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838506.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
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.
  
which holds when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838507.png" /> for arbitrary real numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838508.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s0838509.png" />). Selberg's idea consists of the following: Set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s08385010.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s08385011.png" />, and minimize the right-hand side of (*) by a suitable choice of the remaining numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s08385012.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s083/s083850/s08385013.png" />).
+
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.
 
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====
 
====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>
+
<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>

Revision as of 19:52, 21 November 2014


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

References

[1] A. Selberg, "On an elementary method in the theory of primes" Norsk. Vid. Selsk. Forh. , 19 : 18 (1947) pp. 64–67
[2] K. Prachar, "Primzahlverteilung" , Springer (1957)
[3] H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974)
How to Cite This Entry:
Selberg sieve. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Selberg_sieve&oldid=34720
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article