Namespaces
Variants
Actions

Difference between revisions of "Sieve method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (start conversion)
Line 1: Line 1:
A general method in number theory which generalizes the principle of sifting compound numbers from the natural series (see [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). The problem of the sieve method consists in evaluating for a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850301.png" /> of integers the quantity of those elements that are not divisible by any prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850302.png" /> from some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850303.png" /> of prime numbers. The  "sifting"  function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850304.png" />, which denotes the number of such elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850305.png" /> under the additional condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850306.png" />, is often estimated by using information about the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850307.png" /> of elements of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850308.png" />. This set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s0850309.png" /> consists of the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503010.png" /> that are divisible by a square-free number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503011.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503013.png" />. Therefore the more general sifting function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503014.png" /> is usually estimated.
+
A general method in number theory which generalizes the principle of sifting compound numbers from the natural series (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503015.png" /> in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503016.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503017.png" /> is the expected value for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503019.png" /> is a multiplicative function, is governed by the fact that the degree of error
 
The choice of an expected value for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503015.png" /> in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503016.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503017.png" /> is the expected value for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085030/s08503019.png" /> is a multiplicative function, is governed by the fact that the degree of error

Revision as of 17:33, 5 April 2013

A general method in number theory which generalizes the principle of sifting compound numbers from the natural series (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 in the form , where is the expected value for and is a multiplicative function, is governed by the fact that the degree of error

should be relatively low. If, moreover, (at least "on the average" ), then 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 ). 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

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 is representable in the form , where is a prime number and 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 , 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 such that is a -number. (A -number is a number which is either prime or the product of two primes.) By the same technique Chen proved that every number is the sum of a prime and a -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.

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