篩理論

のために${\displaystyle {\mathcal {P}}}$定義する

${\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}}$

そして各素数に対して${\displaystyle p\in {\mathcal {P}}}$部分集合を表す${\displaystyle E_{p}\subseteq A}$倍数の${\displaystyle E_{p}:=\{pn:n\in \mathbb {N} \}}$そして${\displaystyle |E_{p}|}$濃度とする。

ここでは、${\displaystyle A_{\operatorname {sift} }}$そのため、ふるい分け範囲は${\displaystyle {\mathcal {P}}}$形式の素数の具体的な例となる${\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}}$。

濃度を計算したい場合${\displaystyle A_{\operatorname {sift} }}$包含排除原理を適用できます。このアルゴリズムは次のように機能します。まず、の濃度からを削除します。${\displaystyle |A|}$基数${\displaystyle |E_{2}|}$そして${\displaystyle |E_{3}|}$. 1 で割り切れる数を除去したので${\displaystyle 2}$そして${\displaystyle 3}$2回、カーディナリティを追加する必要があります${\displaystyle |E_{6}|}$次のステップでは、${\displaystyle |E_{5}|}$そしてさらに${\displaystyle |E_{10}|}$そして${\displaystyle |E_{15}|}$また削除する必要がある。${\displaystyle |E_{30}|}$つまり、で割り切れるすべての数の濃度${\displaystyle 2,3}$そして${\displaystyle 5}$これは包含排除原理につながる。

${\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots }$

これは次のように書けることに注目してください。

${\displaystyle |A_{\operatorname {sift} }|=\sum \limits _{d|P}\mu (d)|E_{d}|}$

どこ${\displaystyle \mu }$はメビウス関数であり、${\displaystyle P:=\prod \limits _{p\in {\mathcal {P}}}p}$すべての素数の積${\displaystyle {\mathcal {P}}}$そして${\displaystyle E_{1}:=A}$。

ルジャンドルの恒等式を用いて、ふるい分け関数を書き換えることができる。

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

メビウス関数といくつかの関数を使用すること${\displaystyle A_{d}(x)}$要素によって誘発される${\displaystyle {\mathcal {P}}}$

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

そこで、${\displaystyle A_{d}(x)}$次のように書くことができます

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

どこ${\displaystyle g(d)}$は密度であり、乗法関数である。

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

そして${\displaystyle X}$は近似値です${\displaystyle A_{1}(x)}$そして${\displaystyle r_{d}(x)}$は何らかの剰余項です。ふるい分け関数は次のようになります。

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

または簡単に言うと

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

そこで、以下の上限と下限を見つけることで、ふるい分け関数を推定しようと試みる。${\displaystyle S}$それぞれ${\displaystyle G}$そして${\displaystyle R}$。

ふるい分け関数の部分和は交互に過剰カウントと過少カウントを行うため、剰余項は巨大になります。これを改善するというBrunのアイデアは、${\displaystyle \mu (d)}$重みシーケンスを用いたふるい分け機能において${\displaystyle (\lambda _{d})}$制限されたメビウス関数から構成される。適切な2つのシーケンスを選択する。${\displaystyle (\lambda _{d}^{-})}$そして${\displaystyle (\lambda _{d}^{+})}$ふるい分け関数を次のように表す${\displaystyle S^{-}}$そして${\displaystyle S^{+}}$元のふるい分け関数の下限値と上限値を取得できます。

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

以来${\displaystyle g}$乗法的なので、恒等式を使って作業することもできます。

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

表記法：表記法に関して注意すべき点として、文献ではしばしばシーケンスの集合を識別している。${\displaystyle {\mathcal {A}}}$セットと共に${\displaystyle A}$それ自体。これは、次のように書くことを意味します。${\displaystyle {\mathcal {A}}=\{s:s\leq x\}}$シーケンスを定義する${\displaystyle {\mathcal {A}}=(a_{n})}$また文献では合計${\displaystyle A_{d}(x)}$は、濃度として表記されることもあります。${\displaystyle |A_{d}(x)|}$ある集合の${\displaystyle A_{d}(x)}$定義した一方で${\displaystyle A_{d}(x)}$すでにこの集合の濃度になっている。 ${\displaystyle \mathbb {P} }$素数の集合を表すために、${\displaystyle (a,b)}$最大公約数​​${\displaystyle a}$そして${\displaystyle b}$。