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 direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms.
[citation needed] 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.
More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight functions 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.
The term sieve was first used by the Norwegian mathematician Viggo Brun in 1915.
[1] However Brun's work was inspired by the works of the French mathematician Jean Merlin who died in the World War I and only two of his manuscripts survived.
We follow the Ansatz from Opera de Cribro by John Friedlander and Henryk Iwaniec.
[3] We start with some countable sequence of non-negative numbers
In the most basic case this sequence is just the indicator function
Next we introduce a general set of prime numbers called the sifting range
The goal of sieve theory is to estimate the sifting function In the case of
of numbers, that are coprime to the prime factors of
We now introduce a way to calculate the cardinality of
This algorithm works like this: first one removes from the cardinality of
This leads to the inclusion–exclusion principle Notice that one can write this as where
The Möbius function is negative for every prime, so we get One assumes then that
is a density, meaning a multiplicative function such that and
The sifting function becomes or in short One tries then to estimate the sifting function by finding upper and lower bounds for
The partial sum of the sifting function alternately over- and undercounts, so the remainder term will be huge.
Brun's idea to improve this was to replace
in the sifting function with a weight sequence
consisting of restricted Möbius functions.
, one can get lower and upper bounds for the original sifting functions Since
is multiplicative, one can also work with the identity Notation: a word of caution regarding the notation, in the literature one often identifies the set of sequences
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.
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 (Halberstam & Richert 1974) and a more modern text is (Iwaniec & Friedlander 2010).
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.