Brunの篩（素数による篩）

$\chi_i(d)$ は、$\{1, 2, \ldots, n\}$ の部分集合 $I$ に対する関数 $\chi_i(I)$ に読み替えることができる。
$z$ より小さい素数を大きいものから順に $q_1>q_2>\cdots>q_n=2$ とおき、$I\subset\{1, 2, \ldots, n\}$ に対しては
$$\chi_i(I)=\chi_i(\prod_{j\in I}q_j)$$
と定める。

このとき、\eqref{eq2}のように素因数分解される数 $d$ に
$$I=\{a_1, a_2, \ldots, a_r\}, p_i=q_{a_i}$$
を対応させると、$\chi_i(I)=\chi_i(d)$ となる。

$$\chi_i(d)=1\Longleftrightarrow[\omega(\gcd(d, P_{z_k, z}))\leq 2(b+k)+i-1\ (1\leq k\leq s)] \Longleftrightarrow[p_{2(b+k)+i}< z_k\ (1\leq k\leq s, 2(b+k)+i\leq r)]$$
となるから、
$1\leq k\leq s$ に対し、$q_i< z_k\leq q_{i-1}$ となる $i$ を $f_{b+k}$ とし、
$$f_0=f_1=\cdots f_b=f_{b+1}, f_{b+s}=f_{b+s+1}=\cdots =0$$
と定めると
$$\begin{split} \chi_i(I)=1 \Longleftrightarrow& [q_{a_{2(b+k)+i}}< z_k\ (1\leq k\leq s, 2(b+k)+i\leq r)] \\ \Longleftrightarrow& [a_{2(b+k)+i}\geq f_{b+k}\ (1\leq k\leq s, 2(b+k)+i\leq r)] \\ \Longleftrightarrow& [a_{2k+i}\geq f_k\ (1\leq 2k+i\leq r)] \end{split}$$
となる。また、$S=S(A, z)$ となるからBrunの篩より
$$\sum_{d\mid P(z)}\chi_0(d)\# A_d \leq S(A, z)\leq \sum_{d\mid P(z)}\chi_1(d)\# A_d$$
となる。よって左辺と右辺に\eqref{eq1}を代入して\eqref{eq3}が成り立つ。

$\bar\chi_i(d)\ (i=0, 1)$ を
$$\bar\chi_0(p_1 p_2 \ldots p_{2n})=1\Longleftrightarrow [(n\geq b)\land (p_{2n}\geq z_{n-b}) \land (m< n\Longrightarrow p_{2m}< z_{m-b})]$$
および
$$\bar\chi_1(p_1 \ldots p_{2n+1})=1\Longleftrightarrow [(n\geq b)\land (p_{2n+1}\geq z_{n-b}) \land (m< n\Longrightarrow p_{2m+1}< z_{m-b})]$$
により定める。
これは一般形で導入した $\chi_0, \chi_1$ に相当するもので、 一般形に関する補題2 と同様に
$$\begin{split} \chi_0(d)= & 1-\sum_{2j\leq r} \bar\chi_0(p_1 p_2 \cdots p_{2j}), \\ \chi_1(d)= & 1-\sum_{2j+1\leq r} \bar\chi_0(p_1 p_2 \cdots p_{2j+1}) \end{split}$$
が成り立つので
$$\label{eq4}\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}=\sum_{d\mid P(z)}\mu(d)\frac{\rho(d)}{d}-\sum_{\substack{d\mid P(z),\\ d=p_1 p_2 \cdots p_r,\\ p_1>p_2>\cdots >p_r}}\mu(d)\frac{\rho(d)}{d}\sum_{2j+i\leq r} \bar\chi_i(p_1 p_2 \cdots p_{2j+i})\mu(p_1 p_2 \cdots p_{2j+i})\tag{4}$$
となる。

$\mu(d)\rho(d)/d$ は乗法的関数だから、\eqref{eq4}の右辺のひとつめの項は
$$\label{eq5}\begin{split} \sum_{\delta\mid P(z))} \mu(d)\frac{\rho(d)}{d} = & \prod_{p< z}\left(1+\mu(p)\frac{\rho(p)}{p}\right) \\ = & \prod_{p< z}\left(1-\frac{\rho(p)}{p}\right) \\ = & W(z) \end{split}\tag{5}$$
である。

\eqref{eq4}の右辺の後の項は
$$\begin{split} \sum_{\substack{d\mid P(z),\\ d=p_1 p_2 \cdots p_r,\\ p_1>p_2>\cdots >p_r}}\mu(d)\frac{\rho(d)}{d}\sum_{2j+i\leq r} \bar\chi_i(p_1 p_2 \cdots p_{2j+i}) = & \sum_{\substack{\delta t\mid P(z),\\ \delta\mid P(q(t))}}\mu(\delta t)\frac{\rho(\delta t)}{\delta t}\bar\chi_i(t) \\ = & \sum_{t\mid P(z)}\mu(t)\frac{\bar\chi_i(t)\rho(t)}{t}\sum_{\delta\mid P(q(t))} \mu(\delta)\frac{\rho(\delta)}{\delta} \end{split}$$
となる。
$\mu(\delta)\rho(\delta)/\delta$ は乗法的関数だから、\eqref{eq5}と同様に
$$\sum_{\delta\mid P(q(t))} \mu(\delta)\frac{\rho(\delta)}{\delta}=W(q(t))$$
となる。
また、$\bar\chi_i(t)\neq 0$ のとき $\mu(t)=(-1)^i$ なので、
$$\label{eq6}\sum_{\substack{d\mid P(z),\\ d=p_1 p_2 \cdots p_r,\\ p_1>p_2>\cdots >p_r}}\mu(d)\frac{\rho(d)}{d}\sum_{2j+i\leq r} \bar\chi_i(p_1 p_2 \cdots p_{2j+i}) =(-1)^i \sum_{t\mid P(z)}\frac{\bar\chi_i(t)\rho(t)}{t}W(q(t))\tag{6}$$
であることがわかる。

\eqref{eq5}, \eqref{eq6}より \eqref{eq4}は
$$\label{eq7}\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}=W(z)-(-1)^i \sum_{t\mid P(z)}\frac{\bar\chi_i(t)\rho(t)}{t}W(q(t))\tag{7}$$
と書き直せる。

ここで、$\bar\chi_i(t)\neq 0$ のとき
$$t=p_1 p_2 \cdots p_{2\ell +i}, p_1>p_2>\cdots >p_{2\ell+i}\geq z_{\ell-b}$$
となる $\ell\geq b$ が存在するから、
$$\begin{split} \sum_{t\mid P(z)}\frac{\bar\chi_i(t)\rho(t)}{t}W(q(t)) = & \sum_{\ell\geq b} \sum_{\substack{t=p_1 p_2 \cdots p_{2\ell +i},\\ z>p_1>p_2>\cdots >p_{2\ell +i}\geq z_{\ell -b}}}\frac{\rho(t)}{t}W(p_{2\ell +i}) \\ \leq & \sum_{\ell\geq b} W(z_{\ell -b}) \sum_{\substack{t=p_1 p_2 \cdots p_{2\ell +i},\\ z>p_1>p_2>\cdots >p_{2\ell +i}\geq z_{\ell -b}}}\frac{\rho(t)}{t} \\ \leq & \sum_{k\geq 0} W(z_k)\sum_{\substack{t=p_1 p_2 \cdots p_{2(k+b)+i},\\ z>p_1>p_2>\cdots >p_{2(k+b)+i}\geq z_k}}\frac{\rho(t)}{t} \end{split}$$
となるが
$$\sum_{\substack{t=p_1 p_2 \cdots p_{2(k+b)+i},\\ z>p_1>p_2>\cdots >p_{2(k+b)+i}\geq z_k}}\frac{\rho(t)}{t} \leq \frac{1}{(2(k+b)+i)!}\left(\sum_{z_k\leq p< z}\frac{\rho(p)}{p}\right)^{2(k+b)+i}$$
なので、
$$\sum_{t\mid P(z)}\frac{\bar\chi_i(t)\rho(t)}{t}W(q(t))\leq\sum_{k\geq 0} \frac{W(z_k)}{(2(k+b)+i)!}\left(\sum_{z_k\leq p< z}\frac{\rho(p)}{p}\right)^{2(k+b)+i}$$
となる。
これによって、\eqref{eq7}から
$$(-1)^i\left(\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}-W(z)\right)\leq \sum_{k\geq 0}\frac{W(z_k)}{(2(k+b)+i)!}\left(\sum_{z_k\leq p< z}\frac{\rho(p)}{p}\right)^{2(k+b)+i}$$
が得られ、ここから定理が従う。