Legendre's identity

We can rewrite the sifting function with Legendre's identity

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)}$

by using the Möbius function and some functions ${\displaystyle A_{d}(x)}$ induced by the elements of ${\displaystyle {\mathcal {P}}}$

${\displaystyle A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.}$

Approximation of the congruence sum

One assumes then that ${\displaystyle A_{d}(x)}$ can be written as

${\displaystyle A_{d}(x)=g(d)X+r_{d}(x)}$

where ${\displaystyle g(d)}$ is a density, meaning a multiplicative function such that

${\displaystyle g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P} }$

and ${\displaystyle X}$ is an approximation of ${\displaystyle A_{1}(x)}$ and ${\displaystyle r_{d}(x)}$ is some remainder term. The sifting function becomes

${\displaystyle 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)}$

or in short

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).}$

One tries then to estimate the sifting function by finding upper and lower bounds for ${\displaystyle S}$ respectively ${\displaystyle G}$ and ${\displaystyle R}$.

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 ${\displaystyle \mu (d)}$ in the sifting function with a weight sequence ${\displaystyle (\lambda _{d})}$ consisting of restricted Möbius functions. Choosing two appropriate sequences ${\displaystyle (\lambda _{d}^{-})}$ and ${\displaystyle (\lambda _{d}^{+})}$ and denoting the sifting functions with ${\displaystyle S^{-}}$ and ${\displaystyle S^{+}}$, one can get lower and upper bounds for the original sifting functions

${\displaystyle S^{-}\leq S\leq S^{+}.}$^[1]

Since ${\displaystyle g}$ is multiplicative, one can also work with the identity

${\displaystyle \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} .}$

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