# Sieve method

2010 Mathematics Subject Classification: Primary: 11N35 [MSN][ZBL]

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.

How to Cite This Entry:
Sieve method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sieve_method&oldid=42276
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article