Brunの篩（一般形）
その後、Brunは篩法をさらに拡張し、
はじめに
で紹介した一連の結果を得た。この拡張された篩法を単にBrunの篩 (Brun's sieve) と呼ぶ。
Brunの篩は次の事実に依拠している。
$0$ 以上の整数列 $b_k$ を任意にとる。
$I\subset \{1, 2, \ldots, n\}$ に対して $0$ または $1$ をとる関数 $\chi_0(I), \chi_1(I)$ を
$I=\{a_1, a_2, \ldots, a_r\}, 1\leq a_1< a_2<\cdots a_r\leq n$ の形の表示に対して
$$\label{eq1}\chi_i(\{a_1, a_2, \ldots, a_r\})=1\Longleftrightarrow [a_{2k+i}\geq b_k\ (1\leq 2k+i\leq r)]\tag{1}$$
により定めると、
$$\label{eq2}\sum_{I\subset\{1, 2, \ldots, n\}}\chi_0(I)\mu(I) \# A_I\leq\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\chi_1(I)\mu(I) \# A_I \tag{2}$$
が成り立つ。
これは、つぎのように言い換えられる。$T_i\ (i=0, 1)$ を
$$T_1=\{\{a_1, a_2, \ldots, a_r\}: 1\leq a_1< a_2<\cdots a_r\leq n, a_{2k+1}\geq b_k\ (1\leq 2k+1\leq r)\}$$
および
$$T_0=\{\{a_1, a_2, \ldots, a_r\}: 1\leq a_1< a_2<\cdots a_r\leq n, a_{2k}\leq b_k\ (2\leq 2k\leq r)\}$$
と定め、
$\lambda_i(I)$ をそれぞれ $\mu(I)$ の $T_i$ への制限とする。このとき
$$\sum_{I\subset\{1, 2, \ldots, n\}}\lambda_0(I) \# A_I\leq\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda_1(I) \# A_I$$
つまり
$$\sum_{I\in T_0}(-1)^{\# I} \# A_I\leq\# S\leq \sum_{I\in T_1}(-1)^{\# I} \# A_I$$
が成り立つ。
この事実は、次のような補助関数を導入することで証明できる（この論法については Greaves, Chap. 3 を参照）。
$I\subset \{1, 2, \ldots, n\}$ に対して $0$ または $1$ をとる関数 $\bar\chi_0(I), \bar\chi_1(I)$ を $I=\{a_1, a_2, \ldots, a_r\}, 1\leq a_1< a_2<\cdots a_r\leq n$ の形の表示に対して
$$\bar\chi_i(\{a_1, a_2, \ldots, a_r\})=1\Longleftrightarrow r=2k+i\land a_r< b_k\land [j< k\Longrightarrow a_{2j+i}\geq b_j]$$
により定める。また $\bar\chi_0(\emptyset)=\bar\chi_1(\emptyset)=0$ と定める。
このとき空でない集合 $I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1< a_2<\cdots a_m\leq n$ に対して
$$\label{eq3}\chi_i(I)=1-\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})\tag{3}$$
が成り立つ。
$i$ を $0$ か $1$ の一方に定める。
空でない集合 $I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1< a_2<\cdots a_m\leq n$ について $\chi_i(I)=0$ とすると \eqref{eq1}より $a_{2j+i}< b_j$ となる $j$ が存在するので、そのような $j$ で最小のものを $k$ とおくと、
$$\bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=1\Longleftrightarrow j=k$$
となるので、$\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=1$ となる。
一方、$\chi_i(I)=1$ とすると\eqref{eq1}より、今度は $a_{2j+i}< b_j$ となる $j$ は存在しないので
$$\forall j[\bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=0]$$
となり、$\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=0$ となる。
ここで、$I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1< a_2<\cdots a_m\leq n$ について $J=\{a_1, a_2, \ldots, a_k\}$ となる $k$ が存在することを $J\Subset I$ とあらわすと
\eqref{eq3}は
$$\label{eq4}\chi_i(I)=1-\sum_{J\Subset I} \bar\chi_i(J)\tag{4}$$
とあらわすことができる。
このことから、
$$\label{eq5}\begin{split}\sum_{J\subset I} \chi_i(J)\mu(J)
= & \sum_{J\subset I} \left(\mu(J)-\sum_{K\Subset J} \mu(J)\bar\chi_i(K)\right) \\
= & \sum_{J\subset I}\mu(J)-\sum_K\bar\chi_i(K)\sum_{K\Subset J\subset I} \mu(J)
\end{split}\tag{5}$$
となる。
ここで
定理1
の証明に戻る。
$$L(K)=\{i:\max K< i\leq n\}$$
とおくと、
$$K\Subset J\subset I\Longleftrightarrow J=K\cup H, H\subset L(K)$$
となり、右辺において $H$ は $J$ により一意に定まり、かつ $K$ と共通部分をもたないから、
$$\sum_{K\Subset J\subset I} \mu(J)=\mu(K)\sum_{H\subset L(K)}\mu(H)$$
となる。これを\eqref{eq5}に代入し
$$\sum_{J\subset I} \chi_i(J)\mu(J)=\sum_{J\subset I}\mu(J)-\sum_K\bar\chi_i(K)\mu(K)\sum_{H\subset L(K)}\mu(H)$$
が得られるが、$L(K)=\emptyset\Longleftrightarrow \max K=n$ なので
$$\sum_{J\subset I} \chi_i(J)\mu(J)=\sum_{J\subset I}\mu(J)-\sum_{\max K=n}\bar\chi_i(K)\mu(K)$$
となる。
$\bar\chi_0(K)=1$ のとき $\#K$ は偶数なので $\mu(K)=1$ となるので、右辺の $K$ に関する和はつねに $0$ 以上である。
一方、$\bar\chi_1(K)=1$ のとき $\#K$ は奇数なので $\mu(K)=-1$ となるので、右辺の $K$ に関する和はつねに $0$ 以下である。よって
$$\sum_{J\subset I} \chi_0(J)\mu(J)\leq \sum_{J\subset I}\mu(J)\leq \sum_{J\subset I} \chi_1(J)\mu(J)$$
が成り立つ。よって$\lambda^-(I)=\chi_0(I)\mu(I), \lambda^+(I)=\chi_1(I)\mu(I)$ に対して
篩法の一般原理: 定理1
を適用することで
定理1
が示される。
この篩法から
Brunの最初の篩の一般形
を導くこともできる。実際、
$k=2\ell+i, i\in\{0, 1\}$ とおいて、
$$\chi_i(I)=\left\{\begin{array}{cl}
1 & (\# I\leq k), \\
0 & (\# I>k)
\end{array}\right.$$
と定めると $\mu_k(I)=\chi_i(I)\mu(I)$ となる。数列 $b_i$ を $j\geq \ell+1$ のとき $b_j=n$, $j\leq \ell$ のとき $b_j=0$ と定めると
定理1
の\eqref{eq1}が成り立つから、同定理から
Brunの最初の篩（一般形）
の $(1)$, $(2)$ が従う。
参考文献
