Sieve method

A general method in number theory which generalizes the principle of sifting composite numbers from the natural numbers (see 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 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 and the Selberg sieve.

When the sieve method is applied to additive problems (see 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

[1]	K. Prachar, "Primzahlverteilung" , Springer (1957)
[2]	A.O. Gel'fond, Yu.V. Linnik, "Elementary methods in the analytic theory of numbers" , M.I.T. (1966) (Translated from Russian)
[3]	H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974)

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.

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

References

[a1]	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. ISSN 0250-7870. Zbl 0319.10056