Namespaces
Variants
Actions

Difference between revisions of "Large sieve"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
A method developed by Yu.B. Linnik in 1941 which permits one to sift out in sequences of increasing numbers the residues to be discarded. Its essence may be explained as follows. Consider a given sequence of positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575801.png" /> not larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575802.png" />, a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575803.png" /> and a residue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575804.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575805.png" />. Let
+
A method developed by Yu.B. Linnik in 1941 which permits one to sift out in sequences of increasing numbers the residues to be discarded. Its essence may be explained as follows. Consider a given sequence of positive integers $n_1,\ldots,n_Z$ not larger than $N$, a prime number $p < \sqrt N$ and a residue $\ell$, $0 \le \ell \le p-1$. Let
 
+
$$
<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/l/l057/l057580/l0575806.png" /></td> </tr></table>
+
Q(p,\ell) = \sum_{n_i \equiv \ell \pmod{p} \\ n_i \le N} 1 \ .
 
+
$$
It follows from statistical considerations, which may be rigorously proved with the aid of the fundamental idea of the [[Circle method|circle method]], that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575807.png" /> for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575808.png" />, and hence also for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l0575809.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758010.png" /> be the number of such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758011.png" />'s, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758012.png" /> be the number of corresponding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758013.png" />'s. Linnik showed that
 
 
 
<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/l/l057/l057580/l05758014.png" /></td> </tr></table>
 
  
 +
It follows from statistical considerations, which may be rigorously proved with the aid of the fundamental idea of the [[circle method]], that $Q(p,\ell) > 0$ for almost-all $p$, and hence also for almost-all $\ell$. Let $A$ be the number of such $p$'s, and let $B = B(p)$ be the number of corresponding $\ell$'s. Linnik showed that
 +
$$
 +
A \ge \pi\left({ \sqrt{N}) }\right) - \frac{cN}{\tau^2 Z}
 +
$$
 
and
 
and
 +
$$
 +
B(p) \ge (1-\tau) Z
 +
$$
 +
where $c>0$ is a constant and $t \in (0,1)$, and deduced the theorem: The number of primes in the segment $[N^\epsilon,N]$ to which Vinogradov's hypothesis on the least square non-residue (cf. [[Vinogradov hypotheses]]) does not apply can only be finite (depending on $\epsilon$).
  
<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/l/l057/l057580/l05758015.png" /></td> </tr></table>
+
There exists an improved method of the large sieve in which the average values of $Q(p,\ell)$ are estimated. The best result is due to E. Bombieri (1965):
 +
$$
 +
\sum_{p\le \sqrt N} p \sum_{ \ell=0 }^{p-1} \left[{ Q(p,\ell) - \frac{Z}{p} }\right]^2 \le c N Z \ .
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758016.png" /> is a constant and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758017.png" />, and deduced the theorem: The number of primes on the segment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758018.png" /> to which Vinogradov's hypothesis on the least square non-residue (cf. [[Vinogradov hypotheses|Vinogradov hypotheses]]) does not apply can only be finite (depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758019.png" />).
+
The method of the large sieve made its most important contribution to modern analytic number theory in the context of the [[density method]]; this resulted in a proof of the Vinogradov–Bombieri theorem (1965) — the averaged asymptotic law of prime numbers in progressions. This and other similar theorems about the average found extensive application in the solution of several familiar problems in number theory, replacing the generalized Riemann hypothesis (cf. [[Riemann hypothesis, generalized|Riemann hypothesis, generalized]]) in many cases.
 
 
There exists an improved method of the large sieve in which the average values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057580/l05758020.png" /> are estimated. The best result is due to E. Bombieri (1965):
 
 
 
<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/l/l057/l057580/l05758021.png" /></td> </tr></table>
 
 
 
The method of the large sieve made its most important contribution to modern analytic number theory in the context of the [[Density method|density method]]; this resulted in a proof of the Vinogradov–Bombieri theorem (1965) — the averaged asymptotic law of prime numbers in progressions. This and other similar theorems about the average found extensive application in the solution of several familiar problems in number theory, replacing the generalized Riemann hypothesis (cf. [[Riemann hypothesis, generalized|Riemann hypothesis, generalized]]) in many cases.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  K. Prachar,  "Primzahlverteilung" , Springer  (1957)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</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">  K. Prachar,  "Primzahlverteilung" , Springer  (1957)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  H. Halberstam,  H.-E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR>
 +
</table>
  
  
Line 28: Line 34:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bombieri,  "Le grand crible dans la théorie analytique des nombres"  ''Astérisque'' , '''18'''  (1974)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bombieri,  "Le grand crible dans la théorie analytique des nombres"  ''Astérisque'' , '''18'''  (1974)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 17:34, 11 November 2017

A method developed by Yu.B. Linnik in 1941 which permits one to sift out in sequences of increasing numbers the residues to be discarded. Its essence may be explained as follows. Consider a given sequence of positive integers $n_1,\ldots,n_Z$ not larger than $N$, a prime number $p < \sqrt N$ and a residue $\ell$, $0 \le \ell \le p-1$. Let $$ Q(p,\ell) = \sum_{n_i \equiv \ell \pmod{p} \\ n_i \le N} 1 \ . $$

It follows from statistical considerations, which may be rigorously proved with the aid of the fundamental idea of the circle method, that $Q(p,\ell) > 0$ for almost-all $p$, and hence also for almost-all $\ell$. Let $A$ be the number of such $p$'s, and let $B = B(p)$ be the number of corresponding $\ell$'s. Linnik showed that $$ A \ge \pi\left({ \sqrt{N}) }\right) - \frac{cN}{\tau^2 Z} $$ and $$ B(p) \ge (1-\tau) Z $$ where $c>0$ is a constant and $t \in (0,1)$, and deduced the theorem: The number of primes in the segment $[N^\epsilon,N]$ to which Vinogradov's hypothesis on the least square non-residue (cf. Vinogradov hypotheses) does not apply can only be finite (depending on $\epsilon$).

There exists an improved method of the large sieve in which the average values of $Q(p,\ell)$ are estimated. The best result is due to E. Bombieri (1965): $$ \sum_{p\le \sqrt N} p \sum_{ \ell=0 }^{p-1} \left[{ Q(p,\ell) - \frac{Z}{p} }\right]^2 \le c N Z \ . $$

The method of the large sieve made its most important contribution to modern analytic number theory in the context of the density method; this resulted in a proof of the Vinogradov–Bombieri theorem (1965) — the averaged asymptotic law of prime numbers in progressions. This and other similar theorems about the average found extensive application in the solution of several familiar problems in number theory, replacing the generalized Riemann hypothesis (cf. Riemann hypothesis, generalized) in many cases.

References

[1] K. Prachar, "Primzahlverteilung" , Springer (1957)
[2] H. Davenport, "Multiplicative number theory" , Springer (1980)
[3] H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974)


Comments

References

[a1] E. Bombieri, "Le grand crible dans la théorie analytique des nombres" Astérisque , 18 (1974)
How to Cite This Entry:
Large sieve. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Large_sieve&oldid=42268
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article