Sieve theory
Encyclopedia
Sieve theory is a set of general techniques in number theory
, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime number
s up to some prescribed limit X. Correspondingly, the primordial example of a sieve is the sieve of Eratosthenes
, or the more general Legendre sieve
. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.
One successful approach is to approximate a specific sifted set of numbers (e.g. the set of
prime number
s) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight function
s on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted
set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze than
the characteristic function of the set.
Modern sieves include the Brun sieve
, the Selberg sieve
, and the large sieve. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the twin prime conjecture. While the original broad aims of sieve theory still are largely unachieved, there have been some partial successes, especially in combination with other number theoretic tools. Highlights include:
The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the parity problem
, which roughly speaking asserts that sieve theory methods have extreme difficulty distinguishing between numbers with an odd number of prime factors, and numbers with an even number of prime factors. This parity problem is still not very well understood.
Compared with other methods in number theory, sieve theory is comparatively elementary, in the sense that it does not necessarily require sophisticated concepts from either algebraic number theory
or analytic number theory
. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is and a more modern text is .
The sieve methods discussed in this article are not closely related to the integer factorization
sieve methods such as the quadratic sieve
and the general number field sieve
. Those factorization methods use the idea of the sieve of Eratosthenes
to determine efficiently which members of a list of numbers can be completely factored into small primes.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s up to some prescribed limit X. Correspondingly, the primordial example of a sieve is the sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
, or the more general Legendre sieve
Legendre sieve
In mathematics, the Legendre sieve, named after Adrien-Marie Legendre, is the simplest method in modern sieve theory. It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers...
. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.
One successful approach is to approximate a specific sifted set of numbers (e.g. the set of
prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight function
Weight function
A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more "weight" or influence on the result than other elements in the same set. They occur frequently in statistics and analysis, and are closely related to the concept of a...
s on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted
set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze than
the characteristic function of the set.
Modern sieves include the Brun sieve
Brun sieve
In the field of number theory, the Brun sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
, the Selberg sieve
Selberg sieve
In mathematics, in the field of number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
, and the large sieve. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the twin prime conjecture. While the original broad aims of sieve theory still are largely unachieved, there have been some partial successes, especially in combination with other number theoretic tools. Highlights include:
- Brun's theoremBrun's theoremIn number theory, Brun's theorem was proved by Viggo Brun in 1919. It states that the sum of the reciprocals of the twin primes is convergent with a finite value known as Brun's constant, usually denoted by B2...
, which asserts that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of the primes themselves diverge); - Chen's theoremChen's theoremright|thumb|Chen JingrunChen's theorem states that every sufficiently large even number can be written as the sum of either two primes, or a prime and a semiprime . The theorem was first stated by Chinese mathematician Chen Jingrun in 1966, with further details of the proof in 1973. His original...
, which shows that there are infinitely many primes p such that p + 2 is either a prime or a semiprimeSemiprimeIn mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....
(the product of two primes); a closely related theorem of Chen JingrunChen JingrunChen Jingrun was a Chinese mathematician who made significant contributions to number theory.- Personal life :Chen was the third son in a large family from Fuzhou, Fujian, China. His father was a postal worker. Chen Jingrun graduated from the Mathematics Department of Xiamen University in 1953...
asserts that every sufficiently large even number is the sum of a prime and another number which is either a prime or a semiprime. These can be considered to be near-misses to the twin prime conjecture and the Goldbach conjecture respectively. - The fundamental lemma of sieve theoryFundamental lemma of sieve theoryIn number theory, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems...
, which (very roughly speaking) asserts that if one is sifting a set of N numbers, then one can accurately estimate the number of elements left in the sieve after
iterations provided that 
is sufficiently small (fractions such as 1/10 are quite typical here). This lemma is usually too weak to sieve out primes (which generally require something like 
iterations), but can be enough to obtain results regarding almost primes. - The Friedlander–Iwaniec theorem, which asserts that there are infinitely many primes of the form
.
The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the parity problem
Parity problem (sieve theory)
In number theory, the parity problem refers to a limitation in sieve theory that prevents sieves from giving good estimates in many kinds of prime-counting problems. The problem was identified and named by Atle Selberg in 1949...
, which roughly speaking asserts that sieve theory methods have extreme difficulty distinguishing between numbers with an odd number of prime factors, and numbers with an even number of prime factors. This parity problem is still not very well understood.
Compared with other methods in number theory, sieve theory is comparatively elementary, in the sense that it does not necessarily require sophisticated concepts from either algebraic number theory
Algebraic number theory
Algebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
or analytic number theory
Analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Dirichlet's introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic...
. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is and a more modern text is .
The sieve methods discussed in this article are not closely related to the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
sieve methods such as the quadratic sieve
Quadratic sieve
The quadratic sieve algorithm is a modern integer factorization algorithm and, in practice, the second fastest method known . It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve...
and the general number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
. Those factorization methods use the idea of the sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
to determine efficiently which members of a list of numbers can be completely factored into small primes.