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 prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical 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 numbers) 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 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. Brun's work was inspired by the works of French mathematician Jean Merlin. However, Merlin died in World War I, leaving only two surviving manuscripts.
Basic sieve theory For information on notation see at the end. We follow the Ansatz from Opera de Cribro by John Friedlander and Henryk Iwaniec. We start with some countable sequence of non-negative numbers A = ( a n ) {\displaystyle {\mathcal {A}}=(a_{n})} . In the most basic case this sequence is just the indicator function a n = 1 A ( n ) {\displaystyle a_{n}=1_{A}(n)} of some set A = { s : s ≤ x } {\displaystyle A=\{s:s\leq x\}} we want to sieve. However this abstraction allows for more general situations. Next we introduce a general set of prime numbers called the sifting range P ⊆ P {\displaystyle {\mathcal {P}}\subseteq \mathbb {P} } and their product up to z {\displaystyle z} as a function P ( z ) = ∏ p ∈ P , p < z p {\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p} . The goal of sieve theory is to estimate the sifting function
S ( A , P , z ) = ∑ n ≤ z , gcd ( n , P ( z ) ) = 1 a n . {\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq z,{\text{gcd}}(n,P(z))=1}a_{n}.}
In the case of a n = 1 A ( n ) {\displaystyle a_{n}=1_{A}(n)} this just counts the cardinality of a subset A sift ⊆ A {\displaystyle A_{\operatorname {sift} }\subseteq A} of numbers, that are coprime to the prime factors of P ( z ) {\displaystyle P(z)} .
The inclusion–exclusion principle For P {\displaystyle {\mathcal {P}}} define
A sift := { a ∈ A | ( a , p 1 ⋯ p k ) = 1 } , p 1 , … , p k ∈ P {\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}}
… excerpt ends here. Continue reading the full article.
