Editing Sieve theory (section)

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