Editing Sieve theory

{{Short description|Ways to estimate the size of sifted sets of integers}}
'''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 number]]s 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.{{Citation needed|date=May 2018}} 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.{{Citation needed|date=May 2018}}

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 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 [[Indicator function|characteristic function]] of the set.

The term ''sieve'' was first used by the [[Norway|Norwegian]] mathematician [[Viggo Brun]] in 1915.<ref>{{cite journal|first=Viggo |last=Brun |date=1915 |journal=Archiv for Math. Naturvidenskab |title=Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare |volume=34}}</ref> However Brun's work was inspired by the works of the [[France|French]] mathematician [[Jean Merlin]] who died in the [[World War I]] and only two of his manuscripts survived.<ref>{{cite book |first1=Alina Carmen |last1=Cojocaru |first2=M. Ram |last2=Murty |title=An Introduction to Sieve Methods and Their Applications |publisher=Cambridge University Press |doi=10.1017/CBO9780511615993 |date=2005|isbn=978-0-521-84816-9 }}</ref> 
== 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]].<ref>{{cite book |title=Opera de Cribro |first1=John |last1=Friedlander |first2=Henryk |last2=Iwaniec |publisher = American Mathematical Society |date=2010 |isbn=978-0-8218-4970-5 |series=American Mathematical Society Colloquium Publications | volume=57}}</ref>

We start with some [[countable]] sequence of non-negative numbers <math>\mathcal{A}=(a_n)</math>. In the most basic case this sequence is just the [[indicator function]] <math>a_n=1_{A}(n)</math> of some set <math>A=\{s:s\leq x\}</math> 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'' <math>\mathcal{P}\subseteq \mathbb{P}</math> and their product up to <math>z</math> as a function <math>P(z)=\prod\limits_{p\in\mathcal{P}, p<z}p</math>.

The goal of sieve theory is to estimate the ''sifting function''
:<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{n\leq x, \text{gcd}(n,P(z))=1}a_n.</math>
In the case of <math>a_n=1_{A}(n)</math> this just counts the [[cardinality]] of a subset <math>A_{\operatorname{sift}}\subseteq A</math> of numbers, that are [[coprime]] to the [[prime factor]]s of <math>P(z)</math>.

=== The inclusion–exclusion principle ===
For <math>\mathcal{P}</math> define
:<math>A_{\operatorname{sift}}:=\{a\in A|(a,p_1\cdots p_k)=1\}, \quad p_1,\dots,p_k\in\mathcal{P}</math>
and for each prime <math>p\in \mathcal{P}</math> denote the subset <math>E_p\subseteq A</math> of multiples <math>E_p:=\{pn:n\in\mathbb{N}\}</math> and let <math>|E_p|</math> be the cardinality.

We now introduce a way to calculate the cardinality of <math>A_{\operatorname{sift}}</math>. For this the sifting range <math>\mathcal{P}</math> will be a concrete example of primes of the form <math>\mathcal{P}:=\{2,3,5,7,11,13\dots\}</math>.

If one wants to calculate the cardinality of <math>A_{\operatorname{sift}}</math>, one can apply the [[inclusion–exclusion principle]]. This algorithm works like this: first one removes from the cardinality of <math>|A|</math> the cardinality <math>|E_2|</math> and <math>|E_3|</math>. Now since one has removed the numbers that are divisible by <math>2</math> and <math>3</math> twice, one has to add the cardinality <math>|E_6|</math>. In the next step one removes <math>|E_5|</math> and adds <math>|E_{10}|</math> and <math>|E_{15}|</math> again. Additionally one has now to remove <math>|E_{30}|</math>, i.e. the cardinality of all numbers divisible by <math>2,3</math> and <math>5</math>. This leads to the inclusion–exclusion principle
:<math>|A_{\operatorname{sift}}|=|A|-|E_2|-|E_3|+|E_6|-|E_5|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots</math>

Notice that one can write this as
:<math>|A_{\operatorname{sift}}|=\sum\limits_{d|P} \mu(d)| E_d|</math>
where <math>\mu</math> is the [[Möbius function]] and <math>P:=\prod\limits_{p\in\mathcal{P}} p</math> the product of all primes in <math>\mathcal{P}</math> and <math>E_1:=A</math>.

=== Legendre's identity ===
We can rewrite the sifting function with ''Legendre's identity''
:<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{d\mid P(z)}\mu(d)A_d(x)</math>
by using the [[Möbius function]] and some functions <math>A_d(x)</math> induced by the elements of <math>\mathcal{P}</math>
:<math>A_d(x)=\sum\limits_{n\leq x, n\equiv 0\pmod{d}}a_n.</math>
==== Example ====
Let <math>z=7</math> and <math>\mathcal{P}=\mathbb{P}</math>. The Möbius function is negative for every prime, so we get
:<math>\begin{align}
S(\mathcal{A},\mathbb{P},7)&=A_1(x)-A_2(x)-A_3(x)-A_5(x)+A_6(x)+A_{10}(x)+A_{15}(x)-A_{30}(x).
\end{align}</math>

=== Approximation of the congruence sum ===
One assumes then that <math>A_d(x)</math> can be written as
:<math>A_d(x)=g(d)X+r_d(x)</math>
where <math>g(d)</math> is a ''density'', meaning a [[multiplicative function]] such that
:<math>g(1)=1,\qquad 0\leq g(p)<1 \qquad p\in \mathbb{P}</math>
and <math>X</math> is an approximation of <math>A_1(x)</math> and <math>r_d(x)</math> is some remainder term. The sifting function becomes
:<math>S(\mathcal{A},\mathcal{P},z)=X\sum\limits_{d\mid P(z)}\mu(d)g(d)+\sum\limits_{d\mid P(z)}\mu(d)r_d(x)</math>
or in short
:<math>S(\mathcal{A},\mathcal{P},z)=XG(x,z)+R(x,z).</math>
One tries then to estimate the sifting function by finding upper and lower [[Upper and lower bounds|bounds]] for <math>S</math> respectively <math>G</math> and <math>R</math>.

The partial sum of the sifting function alternately over- and undercounts, so the remainder term will be huge. [[Viggo Brun|Brun]]'s idea to improve this was to replace <math>\mu(d)</math> in the sifting function with a weight sequence <math>(\lambda_d)</math> consisting of restricted Möbius functions. Choosing two appropriate sequences <math>(\lambda_d^{-})</math> and <math>(\lambda_d^{+})</math> and denoting the sifting functions with <math>S^{-}</math> and <math>S^{+}</math>, one can get lower and upper bounds for the original sifting functions
:<math>S^{-}\leq S\leq S^{+}.</math><ref>{{cite book |title=Opera de Cribro |first1=John |last1=Friedlander |first2=Henryk |last2=Iwaniec |publisher = American Mathematical Society |date=2010 |isbn=978-0-8218-4970-5 |series=American Mathematical Society Colloquium Publications | volume=57}}</ref>

Since <math>g</math> is multiplicative, one can also work with the identity
:<math>\sum\limits_{d\mid n}\mu(d)g(d)=\prod\limits_{\begin{array}{c} p|n ;\; p\in\mathbb{P}\end{array}}(1-g(p)),\quad\forall\; n\in\mathbb{N}.</math>

'''Notation:''' a word of caution regarding the notation, in the literature one often identifies the set of sequences <math>\mathcal{A}</math> with the set <math>A</math> itself. This means one writes <math>\mathcal{A}=\{s:s\leq x\}</math> to define a sequence <math>\mathcal{A}=(a_n)</math>. Also in the literature the sum <math>A_d(x)</math> is sometimes notated as the cardinality <math>|A_d(x)|</math> of some set <math>A_d(x)</math>, while we have defined <math>A_d(x)</math> to be already the cardinality of this set. We used 
<math>\mathbb{P}</math> to denote the set of primes and <math>(a,b)</math> for the [[greatest common divisor]] of <math>a</math> and <math>b</math>.

== Types of sieving ==

Modern sieves include the [[Brun sieve]], the [[Selberg sieve]], the [[Turán sieve]], the [[large sieve]], the [[larger sieve]] and the [[Goldston–Pintz–Yıldırım 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 theorem]]'', which shows that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of all primes diverges);
# ''[[Chen's theorem]]'', which shows that there are infinitely many primes ''p'' such that ''p'' + 2 is either a prime or a [[semiprime]] (the product of two primes); a closely related theorem of [[Chen Jingrun]] 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 theory]]'', which 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 <math>N^\varepsilon</math> iterations provided that <math>\varepsilon</math> 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 <math>N^{1/2}</math> 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 <math>a^2 + b^4</math>.
# [[Yitang Zhang|Zhang]]'s theorem {{harv|Zhang|2014}}, which shows that there are infinitely many [[prime gap|pairs of primes within a bounded distance]]. The Maynard–Tao theorem {{harv|Maynard|2015}} generalizes Zhang's theorem to arbitrarily long sequences of primes.

== Techniques of sieve theory ==

The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the ''[[parity problem (sieve theory)|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 {{harv|Halberstam|Richert|1974}} and a more modern text is {{harv|Iwaniec|Friedlander|2010}}.

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.

==Literature==
* {{citation | last1= Cojocaru | first1 = Alina Carmen|author1-link= Alina Carmen Cojocaru | last2= Murty | first2= M. Ram | author-link2 = M. Ram Murty | title= An introduction to sieve methods and their applications | publisher= [[Cambridge University Press]] | year= 2006 | isbn= 0-521-84816-4 | series= London Mathematical Society Student Texts | volume= 66 | mr= 2200366 }}
*{{citation | last=Motohashi | first=Yoichi |title=Lectures on Sieve Methods and Prime Number Theory | series=Tata Institute of Fundamental Research Lectures on Mathematics and Physics | volume=72 | publisher=[[Springer-Verlag]] | date=1983 | isbn=3-540-12281-8 | location=Berlin | mr=0735437}}
* {{citation | last=Greaves | first=George | title=Sieves in number theory | series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3) | volume=43 | publisher=[[Springer-Verlag]] | year=2001 | isbn=3-540-41647-1 | location=Berlin | mr=1836967 | doi=10.1007/978-3-662-04658-6}}
* {{cite book | last=Harman | first=Glyn | author-link=Glyn Harman | title=Prime-detecting sieves | series=London Mathematical Society Monographs | volume=33 | publisher=Princeton University Press | year=2007 | isbn=978-0-691-12437-7 | zbl=1220.11118 | mr=2331072 | location=Princeton, NJ}}
* {{cite book | first1=Heini | last1=Halberstam | author-link1=Heini Halberstam | first2=Hans-Egon | last2=Richert | author-link2=Hans-Egon Richert | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6 | location=London-New York | mr=0424730 | series=London Mathematical Society Monographs | volume=4}} 
* {{citation | last1=Iwaniec | first1=Henryk | author-link1=Henryk Iwaniec | last2=Friedlander |first2= John | author-link2=John Friedlander | title=Opera de cribro | publisher=[[American Mathematical Society]] | date=2010 | isbn=978-0-8218-4970-5 | mr=2647984 | location=Providence, RI | series=American Mathematical Society Colloquium Publications | volume=57}}
* {{citation | last=Hooley | first=Christopher | author-link=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=[[Cambridge University Press]] | date=1976 | isbn=0-521-20915-3 | series=Cambridge Tracts in Mathematics | volume=70 | location=Cambridge-New York-Melbourne | mr=0404173}}
* {{cite journal | title=Small gaps between primes | last=Maynard | first=James | author-link=James Maynard (mathematician) | year=2015 | journal=[[Annals of Mathematics]] | volume=181 | issue=1 | pages=383–413 | mr=3272929 | doi=10.4007/annals.2015.181.1.7 | arxiv=1311.4600 }}
* {{citation | title=Introduction to Analytic and Probabilistic Number Theory | first=Gérald | last=Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-41261-7 | pages=56–79 | mr=1342300 | others=Translated from the second French edition (1995) by C. B. Thomas }}
* {{cite journal | title = Bounded gaps between primes | first = Yitang | last = Zhang | author-link=Yitang Zhang | journal = [[Annals of Mathematics]] | year=2014 | volume=179 | issue=3 | pages=1121–1174 | doi=10.4007/annals.2014.179.3.7  | mr=3171761 | doi-access=free }}

==External links==

* {{SpringerEOM | title=Sieve method | id=Sieve_method&oldid=34162 | last=Bredikhin | first=B.M. | author-link= }}

==References==
<references />

{{DEFAULTSORT:Sieve Theory}}
[[Category:Sieve theory| ]]