Large sieve

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 $\tau \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)

References

[a1]	E. Bombieri, "Le grand crible dans la théorie analytique des nombres" Astérisque , 18 (1974)