View source for Sieve method

{{TEX|done}}{{MSC|11N35}}

A general method in number theory which generalizes the principle of sifting [[composite number]]s from the [[natural number]]s (see [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). The problem of the sieve method consists in evaluating for a finite set $A$ of integers the quantity of those elements that are not divisible by any prime number $p$ from some set $P$ of prime numbers. The  "sifting"  function $S(A;P,x)$, which denotes the number of such elements from $A$ under the additional condition $p < x$, is often estimated by using information about the number $N(A_q)$ of elements of a set $A_q$. This set $A_q$ consists of the elements of $A$ that are divisible by a square-free number $q$. When $q=1$, $A_q = A$. Therefore the more general sifting function $S(A_q;P,x)$ is usually estimated.

The choice of an expected value for $N(A_q)$ in the form $(\omega(q)/q)X$, where $X$ is the expected value for $N(A)$ and $\omega(\cdot)$ is a [[Multiplicative arithmetic function|multiplicative function]], is governed by the fact that the magnitude of the error
$$
R(X,q) = N(A_q) - \frac{\omega(q)}{q} X
$$
should be relatively small. If, moreover, $\omega(p) = k$ (at least  "on the average" ), then $k$ is called the dimension of the sieve.

The most advanced branch of the general theory of the sieve method and its applications is that of the linear sieve (when $k=1$). There are various specializations, the most important of which are the [[Brun sieve|Brun sieve]] and the [[Selberg sieve|Selberg sieve]].

When the sieve method is applied to additive problems (see [[Additive number theory|Additive number theory]]), the sifting function must be estimated from below as well as from above. Estimates from below may be based on the logical combinatorial identity (cf [[Inclusion-exclusion formula]])
$$
S(A_q;P;z) = N(A_q) - \sum_{p<z,\,p\in P} S(A_{qp};P,p) \ .
$$

The most precise estimates from below are obtained by invoking combinatorial considerations associated with the use of weight functions. A strong result in the applications of the sieve method with weight functions is that each sufficiently large even number $N$ is representable in the form $N = p+P_2$, where $p$ is a prime number and $P_2$ contains at most two prime factors.

====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">  A.O. Gel'fond,   Yu.V. Linnik,   "Elementary methods in the analytic theory of numbers" , M.I.T.  (1966)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  H. Halberstam,   H.-E. Richert,   "Sieve methods" , Acad. Press  (1974)</TD></TR>
</table>



====Comments====
The first sieve method was known as Brun's sieve, after V. Brun, who proved in 1919 that $\sum
_p \frac{1}{p}$, where the sum is taken over all twin primes, converges. Using the sieve idea and some additional analytic tools, J. Chen proved in 1973 that there exist infinitely many primes $p$ such that $p+2$ is a $P_2$-number. (A $P_2$-number is a number which is either prime or the product of two primes.) By the same technique Chen proved that every sufficiently large even number is the sum of a prime and a $P_2$-number, thus coming very close to the solution of the [[Goldbach problem|Goldbach problem]].

Based on totally different ideas is the [[Large sieve|large sieve]] invented by Yu.V. Linnik in 1941.

====References====
<table>
<TR><TD  valign="top">[a1]</TD> <TD valign="top">Chen Jing-run. "On the representation of a larger even integer as the sum of a prime and the product of at most two primes" ''Scientia Sinica'' '''16''' (1973) 157-176. {{ZBL|0319.10056}}
</TD></TR>
</table>

[[Category:Number theory]]