Editing Sieve theory (section)

== 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>.