篩法 (sieve method) は、全体集合から、与えられた条件をすべて満足する（あるいはいずれも満足しない）ものの個数を評価する技法である。

最も古い篩法は、与えられた範囲内の素数をすべて発見するEratosthenesの篩であるが、20世紀になって篩法が素数に関する様々な問題の研究に盛んに用いられるようになり、近年では他の数論や組合せ論の問題への応用も行われるようになっている。本章では篩法の歴史と一般原理について簡単に解説する。

はじめに

本章では篩法の研究が本格的に進展する以前に論じられた古典的な篩法について解説する。本章で解説する篩法はいわば現代的な篩の前史とよぶべきものである。

Eratosthenes-Legendreの篩

Brunの篩

**篩法** (*sieve method*) は、全体集合から、与えられた条件をすべて満足する（あるいはいずれも満足しない）ものの個数を評価する技法である。

たとえば、与えられた実数 $X>0$ について
$$\sqrt{X}<p\leq X$$
の範囲にある素数 $p$ 全体は、後述のように $X$ 以下の整数で、$\sqrt{X}$ 以下のいずれの素数でも割り切れないもの全体と一致する。
また、$p, p+2$ が双子素数の対で、$p$ が上記の範囲にあるための必要十分条件は、$p+2$ が素数の平方でなく、かつ $p$ を $\sqrt{X}$ 以下のどの素数で割っても余りが $0, p-2$ とはならないことである。

最も古い篩法は、与えられた範囲内の素数をすべて発見するEratosthenesの篩である。LegendreはEratosthenesの篩をもとに集合の数え上げとして定量化することで、与えられた数 $X$ 以下の素数の個数 $\pi(X)$ の $X$ に対する比 $\pi(X)/X$ は $0$ に近づくことを示した。

本格的な篩法の発展は1910年代に始まる。1911年にMerlinがEratosthenesの篩を拡張することで双子素数問題やGoldbach予想の研究に利用できるかも知れないと主張したが、Merlinは第一次世界大戦で戦死してしまった。
BrunはMerlinの議論に触発され、本格的に篩法を研究し、組合せ論的な議論を工夫することで1915年に双子素数の逆数の和が収束することを証明し、さらに1920年に次の一連の定理を証明した。

1. $n, n+2$ がどちらも重複も含めて$9$個以下の素因数しかもたない整数 $n$ が無限に多く存在する。
2. $X$ が大きいとき、$X$ 以下の双子素数の個数は $100X/\log^2 X$ より小さい。
3. $n$ が十分大きい偶数のとき、$n$ は重複も含めて$9$個以下の素因数しかもたない$2$つの整数の和としてあらわされる。
4. $n$ が大きいとき、$n$ と $n+\sqrt{n}$ の間には、重複も含めて$11$個以下の素因数しかもたない整数が存在する。

その後、Selbergが $\lambda^2$ 法を用いて、より単純な篩法を構成した。Selbergの篩は当初は個数の上からの評価しか得られなかったが、その後、下からの評価が得られるようになり、Jing-run Chen（陳景潤）はこの方法により、十分大きな偶数が素数と、$2$個以下の素因数しかもたない整数の和としてあらわされること、および $p+2$ が$2$個以下の素因数しかもたない素数 $p$ が無限に多く存在することを示した。

一方、RosserとIwaniecはBrunとは別の組合せ論的な構成法を用いて特殊な場合に上からの評価と下からの評価を改良し、Iwaniecはこの方法を用いて $x^2+y^2+1$ の形の素数が無限に多く存在することを示した。Iwaniecはさらに誤差項を詳しく調べることで、$n^2+1$ の形の、$2$個以下の素因数しかもたない整数が無限に多く存在することを示した。

また、Goldston, Pintz, YıldırımはSelbergの$\lambda^2$法を変形した新しい篩の議論を導入し、$n$ 番目の素数 $p_n$ と $n+1$ 番目の素数 $p_{n+1}$ の間隔について
$$\liminf \frac{p_{n+1}-p_n}{\log p_n}=0$$
となることを示し、Yitang Zhang（張益唐）はこの方法を改良して
$$\liminf (p_{n+1}-p_n)<7\times 10^7$$
を示した。その後Polymath projectが
$$\liminf (p_{n+1}-p_n)\leq 246$$
を示した。

篩法の解説書としては[[HR]]がChenの定理の証明まで解説した古典的名著である。[[Nat]]は加法的整数論について取り扱っているが、そのうち、6章・9章・10章では篩法の解説と、双子素数予想やGoldbach予想への応用について分かりやすく説明している。[[Gre]]は数論における篩法の基礎理論について詳しく取り扱っている。

# 記法

$O$ 記号については[Landau記号](/glossaries/Rbm0v1DpSK7G3GzcEc9Q)を参照。
また、$O^*(T)$ は絶対値が $T$ 以下の量をあらわす。たとえば
$$F(X)=G(X)+O^*(H(X))$$
は
$$\abs{F(X)-G(X)}\leq H(X)$$
を意味する。

篩の方法を本格的に進展させたBrunの最初の考えは、$\mu(I)$ において $I$ の個数を与えられた個数以下に制限した関数
$$\mu_k(I)=\left\{\begin{array}{cl}
(-1)^{\# I} & (\# I\leq k), \\
0 & (\# I>k)
\end{array}\right.$$
を利用するものである。

たとえば $k=1$ のとき、$\mu_1(\emptyset)=1$, $\mu_1(\{i\})=-1$ でそれ以外の $I$ については $\mu_1(I)=0$ となるので
$$\sum_{I\subset\{1, 2, \ldots, n\}}\mu_1(I) \# A_I=\# A-\sum_{i=1}^n\# A_i\leq \# S$$
が明らかに成り立つ。Brunの最初の篩（Brun's pure sieveと呼ばれる）の基本原理はこれを次のように一般化したものである。

&&&thm Brun's pure sieve （一般形）[th1]
$k$ が奇数のとき
$$\# S\geq \sum_{I\subset\{1, 2, \ldots, n\}}\mu_k(I) \# A_I \ \ (1.1)$$
となり、$k$ が偶数のとき
$$\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\mu_k(I) \# A_I \ \ (1.2)$$
となる。
&&&

&&&prf
$x\in A_i$ となる $i$ 全体の集合を $J(x)$ とおくと
$$\#S=\sum_{x\in S}\sum_{J(x)=\emptyset}1$$
となる。

$J(x)=\emptyset$ のとき
$$\sum_{I\subset J}\mu_k(I)=\mu_k(\emptyset)=1$$
となる。
よって、一般に任意の空でない有限集合 $J$ について $k$ が奇数のとき
$$\sum_{I\subset J}\mu_k(I)\leq 0,$$
$k$ が偶数のとき
$$\sum_{I\subset J}\mu_k(I)\geq 0$$
となることを示せばよい。$m=\# J\geq 1$ とおくと
$$\sum_{I\subset J}\mu_k(I)=\sum_{j=0}^k \sum_{\# I=j}(-1)^j=\sum_{j=0}^k (-1)^j\binom{m}{j}$$
となるが、[「初等整数論」二項係数:定理5](/textbooks/gDWQ3LLZ9Owb8113FxQU/EwSTUZeXpfdSQzHTGSBI)で述べた等式から
$$\sum_{I\subset J}\mu_k(I)=(-1)^k\binom{m-1}{k}$$
となり、右辺の和は $k$ が奇数のとき $0$ 以下、$k$ が偶数のとき $0$ 以上となるので、定理が従う。
&&&

Brunの最初の篩（一般形）

Eratosthenesは、ある範囲の素数をすべて列挙する方法を与えた。

1. $p_1=2$ は素数である。一方で $2$ 自身を除く $2$ の倍数はすべて合成数だから、取り除く。
2. $2$ から先の数で、残った数の中で最小のものである $p_2=3$ は素数である。一方で $3$ 自身を除く $3$ の倍数はすべて合成数だから、取り除く。
3. 以下同様に、 $p_k$ 自身を除く $p_k$ の倍数を取り除いた後に残った数の中で、$p_k$ から先の数で最小のものを $p_{k+1}$ とおいて、$p_{k+1}$ 自身を除く $p_{k+1}$ の倍数を取り除く。

このようにして、与えられた $k$ に対して、最初の $k$ 個の素数 $p_1=2, p_2=3, \ldots, p_k$ を得る。

&&&ex [ex1]
$50$ までの整数
$$\begin{split}
& 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \\
& 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, \\
& 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, \\
& 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, \\
& 31, 32, 33, 34, 35, 36, 37, 38, 39, 50\\
\end{split}$$
にEratosthenesの篩を適用する。まず、$2$ は素数なので、$2$ 自身を除く $2$ の倍数を取り除く。
$$\begin{split}
& 1, \mathbf{2}, 3, \xcancel{4}, 5, \xcancel{6}, 7, \xcancel{8}, 9, \xcancel{10}, \\
& 11, \xcancel{12}, 13, \xcancel{14}, 15, \xcancel{16}, 17, \xcancel{18}, 19, \xcancel{20}, \ldots, \\
& 21, \xcancel{22}, 23, \xcancel{24}, 25, \xcancel{26}, 27, \xcancel{28}, 29, \xcancel{30}, \ldots, \\
& 31, \xcancel{32}, 33, \xcancel{34}, 35, \xcancel{36}, 37, \xcancel{38}, 39, \xcancel{40}, \ldots, \\
& 41, \xcancel{42}, 43, \xcancel{44}, 45, \xcancel{46}, 47, \xcancel{48}, 49, \xcancel{50}\\
\end{split}$$
$2$ から先に残った数で最小の $3$ が素数なので、$3$ 自身を除く $3$ の倍数を取り除く。
$$\begin{split}
& 1, \underline{2}, \mathbf{3}, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \xcancel{9}, \cancel{10}, \\
& 11, \cancel{12}, 13, \cancel{14}, \xcancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\
& \xcancel{21}, \cancel{22}, 23, \cancel{24}, 25, \cancel{26}, \xcancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\
& 31, \cancel{32}, \xcancel{33}, \cancel{34}, 35, \cancel{36}, 37, \cancel{38}, \xcancel{39}, \cancel{40}, \ldots, \\
& 41, \cancel{42}, 43, \cancel{44}, \xcancel{45}, \cancel{46}, 47, \cancel{48}, 49, \cancel{50}\\
\end{split}$$
$3$ から先に残った数で最小の $5$ が素数なので、$5$ 自身を除く $5$ の倍数を取り除く。
$$\begin{split}
& 1, \underline{2}, \underline{3}, \cancel{4}, \mathbf{5}, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, \\
& 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\
& \cancel{21}, \cancel{22}, 23, \cancel{24}, \xcancel{25}, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\
& 31, \cancel{32}, \cancel{33}, \cancel{34}, \xcancel{35}, \cancel{36}, 37, \cancel{38}, \cancel{39}, \cancel{40}, \ldots, \\
& 41, \cancel{42}, 43, \cancel{44}, \cancel{45}, \cancel{46}, 47, \cancel{48}, 49, \cancel{50}\\
\end{split}$$
$5$ から先に残った数で最小の $7$ が素数なので、$7$ 自身を除く $7$ の倍数を取り除く。
$$\begin{split}
& 1, \underline{2}, \underline{3}, \cancel{4}, \underline{5}, \cancel{6}, \mathbf{7}, \cancel{8}, \cancel{9}, \cancel{10}, \\
& 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \ldots, \\
& \cancel{21}, \cancel{22}, 23, \cancel{24}, \cancel{25}, \cancel{26}, \cancel{27}, \cancel{28}, 29, \cancel{30}, \ldots, \\
& 31, \cancel{32}, \cancel{33}, \cancel{34}, \cancel{35}, \cancel{36}, 37, \cancel{38}, \cancel{39}, \cancel{40}, \ldots, \\
& 41, \cancel{42}, 43, \cancel{44}, \cancel{45}, \cancel{46}, 47, \cancel{48}, \xcancel{49}, \cancel{50}\\
\end{split}$$
残る最初の数は $11$ だから、$11$ までの素数が確かめられる。

また、$49$ 以下の合成数は $\sqrt{49}=7$ 以下の素因数をもたなければならないから、除外されずに残っている $13, 17, \ldots, 47$ も素数であることがわかる。
&&&

Eratosthenesの篩

数え上げ組合せ論の記事にもあるように、一般の有限集合において、[包含と除去の原理](/glossaries/ysNUEDROZjbRdJIgrMWr#thie)はつぎのようにして証明される。
$A$ が有限集合で、$A_i (i=1, 2, \ldots, n)$ がその部分集合とし、
$I\subset\{1, 2, \ldots, n\}$ に対して、$A_I=\cap_{i\in I}A_i$ と定める。
このとき、
$$\mu(I)=(-1)^{\# I}$$
と定義すると、
$$\sum_{J\subset I}\mu(J)=(1-1)^{\# I}=\left\{\begin{array}{cl}
1 & (I=\emptyset), \\
0 & (I\neq\emptyset)
\end{array}\right.$$
となる。よって $x\in A_i$ となる $i$ 全体の集合を $J(x)$ とおくと
$$\sum_{I\ni x}\mu(I)=\sum_{I\subset J(x)}\mu(I)=\left\{\begin{array}{cl}
1 & (J(x)=\emptyset), \\
0 & (J(x)\neq\emptyset)
\end{array}\right.$$
となるから
$$S=A\setminus\left(\bigcup_{i=1}^n A_i\right)$$
を $A$ の要素のうち、どの $A_i$ にも属さないもの全体の集合とすると
$$\#S = \sum_{I\subset J(x)}\mu(I)= \sum_{x\in A} \sum_{I\ni x}\mu(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\mu(I) \#A_I$$
となる。

ここで、ある実数 $X$ が存在し、さらに各 $i=1, 2, \ldots, n$ に対して実数 $\delta_i$ が対応し、$\delta(I)=\prod_{i\in I} \delta_i$, $\delta(\emptyset)=1$ とおくと、各 $I\subset \{1, 2, \ldots, n\}$ について
$$\# A_I=\frac{\delta(I)}X+R_I$$
となるとする。それで $\abs{R_I}$ が小さいとき、$A_I$ は $X\delta(I)=X\prod_{i=1}^r \delta_i$ で近似されるといえる。確率論的には $A$ の要素が $A_I$ に属する確率が $\delta(I)=\prod_{i=1}^r \delta_i$ で近似されている（よって $A$ の要素が $A_i$ に属する事象は異なる $i$ についてほぼ独立である）といえる。

$A_1, A_2, \ldots, A_k$ に属する要素をすべて $A$ から取り除いた集合の要素の個数を
$$S(A, k)=\# \left[A\setminus\left(\bigcup_{i=1}^n A_i\right)\right]$$
とおくと、包含と除去の原理から
$$S(A, k)=\sum_{I\subset \{1, 2, \ldots, k\}} (-1)^{\# I} \#A_d=X\prod_{i=1}^k (1-\delta_i)+\sum_{I\subset\{1, 2, \ldots, k\}} (-1)^{\# I}R_I$$
となる。

Eratosthenes-Legendreの篩はこれをそのまま用いるものであったが、誤差項となる右辺の和は大きなものになりうる。Brun以降の篩法の出発点は、$\mu(d)$ を別の関数 $\lambda(I)$ で置き換えるところにある。

包含と除去の原理

対称式の値に関する次の評価は、Brunの篩にあらわれる和の評価に有用である。
&&&lem [lm1]
$s_k(x_1, \ldots, x_r)$ を $k$ 次基本対称式とおくと
$x_1, \ldots, x_r\geq 0$ ならば
$$s_k(x_1, \ldots, x_r)\leq\frac{(x_1+\cdots +x_r)^k}{k!}$$
が成り立つ。
&&&

&&&prf
$$(x_1+\cdots +x_r)^k=\sum_{1\leq i_1, i_2, \ldots, i_k\leq r} x_{i_1}x_{i_2}\cdots x_{i_k}
\geq \sum_{\substack{1\leq i_1, i_2, \ldots, i_k\leq r,\\ i_p=i_q\Longrightarrow p=q}} x_{i_1}x_{i_2}\cdots x_{i_k}$$
となる。

$1\leq j_1<j_2<\ldots<j_k\leq r$ となる $(j_1, j_2, \ldots, j_k)$ をひとつとる。右辺の和のなかにある項で、$x_{i_1}x_{i_2}\cdots x_{i_k}=x_{j_1}x_{j_2}\cdots x_{j_k}$ となるのは、$(i_1, i_2, \ldots, i_k)$ が $(j_1, j_2, \ldots, j_k)$ の置換であるものであり、そのようなものに限られるから、
$$(x_1+\cdots +x_r)^k=\sum_{1\leq i_1, i_2, \ldots, i_k\leq r} x_{i_1}x_{i_2}\cdots x_{i_k}
\geq (k!)\sum_{1\leq j_1<j_2< \cdots< j_k\leq r} x_{j_1}x_{j_2}\cdots x_{j_k}=(k!)s_k(x_1, \ldots, x_r)$$
となる。
&&&

Brun's pure sieveから、ひとつの素数を法とする複数の剰余類を取り除くとき、つぎの評価が得られる。

&&&thm [th2]
$z>0$ を正の実数とする。$\rho(n)$ は乗法的関数で、
$$\label{eq1}\sum_{p<z}\frac{\rho(p)}{p}\leq\kappa\log\log z+B_0\tag{1}$$
が成り立つとする。
$$A=\Z\cup (M, M+X]=\{n\in\Z: M<n\leq M+X\}$$
とおく。さらに、各素数 $p$ について、$\rho(p)$ 個の剰余類 $a(p, 1), \ldots, a(p, \rho(p))\Mod{p}$ が対応するとし、
$$A_p=\{n\in A: n\equiv a(p, 1), a(p, 2), \ldots, a(p, \rho(p))\Mod{p}\}$$
とおく。

このとき、
$$S(A, z)=A\setminus \left(\bigcup_{p<z}A_p\right)$$
を、どの $p<z$ となる素数についても $A_p$ に属さない $A$ の要素の全体の集合とすると、
$m>2e(\kappa\log\log z+B_0)$ となるよう偶数 $m$ に対して、
$$\# S(A, z)=X\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)+O^*\left(\frac{X}{2^m}+\left(1+\sum_{p<z}\rho(p)\right)^m\right)$$
となる。
&&&

&&&prf
相異なる素数の積 $d$ について、
$$A_d=\bigcap_{p\mid d} A_p$$
とおくと、
$$A_d=\#\{n: M<n\leq M+X, p\mid d\Longrightarrow (1\leq \exists u(p)\leq \rho(p))[n\equiv a(p, u(p))\Mod{p}]\}$$
となる。

[中国式剰余定理](/textbooks/gDWQ3LLZ9Owb8113FxQU/bpjs1f3UFU5yy5mJG8st)から、相異なる素数の積 $d=p_1 p_2 \cdots p_k$ について、
$$n\equiv r_i\Mod{p_i}\ (\forall i=1, 2, \ldots, k)\Longleftrightarrow n\equiv U(r_1, r_2, \ldots, r_k)\Mod{d}$$
となる剰余類 $U(r_1, r_2, \ldots, r_k)\Mod{d}$ が一意的に定まる。$1\leq d_i\leq \rho(p_i)\ (1\leq i\leq k)$ となる $(d_1, d_2, \ldots, d_k)$ について
$$U(a(p_1, d_1), a(p_2, d_2), \ldots, a(p_k, d_k))\Mod{d}$$
は相異なる剰余類で、
$$A_d=\#\{n: M<n\leq M+X, n\equiv U(a(p_1, d_1), a(p_2, d_2), \ldots, a(p_k, d_k))\Mod{d}\}$$
となる（ただし、各 $d_i$ は $1\leq \exists d_i\leq \rho(p_i)$ となる整数）ので、
$$\# A_d\leq \rho(d)\left(\floor{\frac{(M+X)}{d}}-\floor{\frac{M}{d}}\right)<\frac{\rho(d)X}{d}+\rho(d)$$
かつ
$$\# A_d\geq \rho(d)\left(\floor{\frac{(M+X)}{d}}-\floor{\frac{M}{d}}\right)>\frac{\rho(d)X}{d}-\rho(d)$$
となる。つまり
$$\label{eq2}\abs{\# A_d-\frac{X}{d}}<\rho(d)\tag{2}$$
が成立する。

$$\mu_k(d)=\left\{\begin{array}{cl}
\mu(d)=(-1)^{\omega(d)} & (\omega(d)\leq k), \\
0 & (\omega(d)>k)
\end{array}\right.$$
とおくと、$m$ が偶数のときBrunの最初の篩より
$$\# S(A, z)\leq \sum_{d\mid P(z)} \mu_m(d)\# A_d$$
となる。

そこで、$m>2e(\kappa\log\log z+B_0)$ となるように偶数 $m$ をとると、 \eqref{eq2}より
$$\label{eq3}\begin{split}
\# S(A, z)\leq & \sum_{d\mid P(z), \omega(d)\leq m} \mu(d) \# A_d \\
= & \sum_{d\mid P(z), \omega(d)\leq m} \left(\frac{\mu(d)\rho(d) X}{d}+O^*(\rho(d))\right) \\
= & X\sum_{d\mid P(z)} \frac{\mu(d)\rho(d)}{d} \\
& +O^*\left(X\sum_{d\mid P(z), \omega(d)\geq m+1} \mu(d)\frac{\rho(d)}{d}+\sum_{d\mid P(z), \omega(d)\leq m} \rho(d)\right)
\end{split}\tag{3}$$
が成り立つ。以下、この右辺の各項について考察する。

まず、$\mu(d)\rho(d)/d$ は乗法的関数だから
$$\label{eq4}\sum_{d\mid P(z)} \frac{\mu(d)\rho(d)}{d}=\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)\tag{4}$$
となる。

$z$ 以下の素数を $p_1, \ldots, p_r$ とおくと
$$\begin{split}
\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}
= & \sum_{k=m+1}^r \sum_{d\mid P(z), \omega(d)=k} \frac{\rho(d)}{d} \\
= & \sum_{k=m+1}^r \sum_{\{i_1, \ldots, i_k\} \subset \{1, \ldots, r\}} \left(\frac{\rho(p_{i_1})}{p_{i_1}}\right)\cdots\left(\frac{\rho(p_{i_k})}{p_{i_k}}\right) \\
= & \sum_{k=m+1}^r s_k\left(\frac{\rho(p_1)}{p_1}, \ldots \frac{\rho(p_r)}{p_r}\right)
\end{split}$$
となるので、[補題1](#lm1)およびStirlingの公式より
$$\begin{split}
\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}
\leq & \sum_{k=m+1}^r \frac{1}{k!}\left(\sum_{p<z} \frac{\rho(p)}{p}\right)^k \\
< & \sum_{k=m+1}^r \left(\frac{e}{k}\right)^k \left(\sum_{p<z} \frac{\rho(p)}{p}\right)^k \\
< & \sum_{k=m+1}^r \left(\frac{e}{m}\right)^k \left(\sum_{p<z} \frac{\rho(p)}{p}\right)^k
\end{split}$$
となるが、仮定より
$$\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}<\sum_{k=m+1}^r \left(\frac{e(\kappa \log\log z+B_0)}{m}\right)^k$$
となる。
$m>2e(\kappa\log\log z+B_0)$ となるように $m$ をとっているので、
$$\label{eq5}\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}<\sum_{k=m+1}^r \frac{1}{2^k}=\frac{1}{2^m}\tag{5}$$
となる。

さらに、仮定より
$$\label{eq6}\begin{split}
\sum_{d\mid P(z), \omega(d)\leq m} \rho(d)
= & \sum_{k=1}^m\sum_{\{i_1, \ldots, i_k\} \subset \{1, \ldots, r\}}\rho(p_{i_1})\cdots \rho(p_{i_k}) \\
\leq & \sum_{k=1}^m \left(\sum_{p<z}\rho(p)\right)^k \\
\leq & \left(1+\sum_{p<z}\rho(p)\right)^m
\end{split}\tag{6}$$
となる。

\eqref{eq4}, \eqref{eq5}, \eqref{eq6}を\eqref{eq3}に適用して
$$\# S(A, z)=X\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)+O^*\left(\frac{X}{2^m}+\left(1+\sum_{p<z}\rho(p)\right)^m\right)$$
となって、定理が証明される。
&&&


Brunの最初の篩（素数による篩）

LegendreはEratosthenesの篩をつぎのように変形し、素数の個数を数えることを試みた。

$X$ までの正の整数
$$1, 2, \ldots, X$$
から $\sqrt{X}$ 以下の素数 $p$ で割り切れるものをすべて取り除く。
$n\leq X$ が合成数ならば、$n$ は $\sqrt{n}\leq \sqrt{X}$ 以下の素因数をもつから、取り除かれる。
一方で、$\sqrt{X}$ 以下の素数 $p$ は自分自身で割れるので取り除かれるが、
$\sqrt{X}<p\leq X$ となる素数は、$p$ より小さい素数で割れないから取り除かれずに残る。
よって、取り除かれずに残る数全体は $\sqrt{X}<p\leq X$ となる素数全体と一致する。

つまり
$$A=A(X)=\{1, 2, \ldots, \floor{X}\}=\Z\cap [1, X]$$
について
$$A_d=\{n\mid n\in A, d\mid n\}$$
を $A$ の要素のうち、$d$ で割り切れるもの全体の集合、
$$S(A, P)=\#\{n\mid n\in A, \gcd(n, P)=1\}$$
を $A$ の要素のうち、$P$ と互いに素なもの、つまり $P$ のどの素因数でも割り切れないもの全体の個数、
$$P(z)=\prod_{p\leq z} p$$
を $z$ 以下の素数の積とすると、$z=\sqrt{X}$ とおけば、 $S(A, P(\sqrt{X}))$ は $A$ の要素のうち、$\sqrt{X}$ 以下の素因数をもたないもの全体の個数となるから、
$$\pi(X)-\pi(\sqrt{X})=S(A, P(\sqrt{X}))$$
となる。

さらに一般に、$z\leq X$ となる実数 $z$ に対して、$p$ が $z$ より大きな素数ならば、$p$ は $z$ より小さな素因数をもたないので
$$\pi(X)-\pi(z)\leq S(A, P(z))$$
となる（$p_0$ が $\sqrt{X}$ 以下の最大の素数で、$z$ が $p_0$ より小さいときは、$p_0^2$ は合成数だが、$S(A, P(z))$ に数えられるため、等号は成り立たない）。

$S(A, P(z))$ は $A$ の要素のうち、$z$ 以下の素因数をもたないもの全体の個数となるから、明らかに
$$S(A, P(z))=A\backslash \bigcup_{p\leq z}A_p$$
となる。よって[包含と除去の原理](/glossaries/ysNUEDROZjbRdJIgrMWr#thie)より
$$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d) \#A_d=\sum_{d\mid P(z)}(-1)^\mu(d)\floor{\frac{X}{d}}$$
となる。$\mu(d)$ は[Möbius関数](/textbooks/gDWQ3LLZ9Owb8113FxQU/fy5s0h9sA2NHQnlJGvIH)である。

$$0\leq \frac{X}{d}-\floor{\frac{X}{d}}<1$$
となることから
$$S(A, P(z))=\sum_{d\mid P(z)}(-1)^\mu(d)\left(\frac{X}{d}+O^*(1)\right)$$
となる。$P(z)$ の約数の個数は
$$2^{\omega(P(z))}=2^{\pi(z)}<2^z$$
となる。また
$$\sum_{d\mid P(z)}\frac{(-1)^\mu(d)}{d}=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$$
を用いると
$$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$
が成り立つ。

$$\prod_{p\leq z}\left(1-\frac{1}{p}\right)^{-1}\geq \sum_{n\leq z}\frac{1}{z}>\log z$$
より
$$S(A, P(z))<\frac{X}{\log z}+2^z$$
となるので、
$z=(\log X-\log\log X)/\log 2$ とおくと、
$$\pi(X)\leq z+S(A, P(z))<\frac{X(1+o(1))}{\log\log X}$$
となることがわかる。
とくに、
$$\frac{\pi(X)}{X}\rightarrow 0\ (X\rightarrow\infty)$$
となることが示される。

これは、素数定理はもちろん、初等的かつ比較的容易に得られる結果、たとえば
[「初等整数論」素数の分布（初等的理論）: x 以下の素数の個数:定理1の系](/textbooks/gDWQ3LLZ9Owb8113FxQU/EGeYZnTTqCHLrdUd0E6d#th1c)および[「初等整数論」素数の分布（初等的理論）:Chebyshev関数の初等的評価の定理2](/textbooks/gDWQ3LLZ9Owb8113FxQU/snTEyc0tTRhT3O7wUmQd#th2)から得られる
$$\pi(X)=O\left(\frac{X}{\log X}\right)$$
よりも弱い。和の中の項の個数が $2^z$ 個となって $z$ に比べて大きすぎるためである。

一方で、この考察は $N$ 個の連続する整数 $M+1, M+2, \ldots, M+N$、あるいは
長さ $X$ の区間 $(U, U+X]$ に属する整数にも一般化できる。すなわち
$$A=A(X)=\{n\mid U<n\leq U+X\}=\Z\cap (U, X]$$
について
$$A_d=\{n\mid n\in A, d\mid n\}$$
とおくと、
$$\abs{\#A_d-\frac{X}{d}}=\abs{\floor{\frac{U+X}{d}}-\floor{\frac{U}{d}}-\frac{U+X}{d}+\frac{U}{d}}<1$$
となるので、上と同様に
$$S(A, P(z))=X\prod_{p\leq z}\left(1-\frac{1}{p}\right)+O^*(2^z)$$
が成り立つ。このことから $z=(\log X-\log\log X)/\log 2$ とおくと、区間 $(U, U+X]$ のとり方によらず
$$\pi(U+X)-\pi(U)\leq z+S(A, P(z))<\frac{X}{\log z}+2^z<\frac{X(1+f(X))}{\log\log X}$$
となる関数 $f(X)\rightarrow 0\ (X\rightarrow +\infty)$ が存在することがわかる（Hardy-Littlewood, 1923）。
これは素数定理のみからは従わず、さらにRiemann予想と同値な評価
$$\pi(X)=\mathrm{li} X+O(X^{1/2}\log X)$$
を用いても得られない結果である。


Legendreの篩

Brun以降の篩法の出発点は、$\mu(d)$ を別の関数 $\lambda(I)$ で置き換えるところにある。一般的には次の定理が成り立つ。

&&&thm [th1]
$\lambda^+(I)$ が $\{1, 2, \ldots, n\}$ の部分集合に関する関数で、すべての $I\subset \{1, 2, \ldots, n\}$ について
$$\sum_{J\subset I}\mu(J) \leq \sum_{J\subset I}\lambda^+(J)$$
が成り立つとき、
$$\# S \leq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \#A_I$$
が成り立つ。同様に、$\lambda^-(I)$ が $\{1, 2, \ldots, n\}$ の部分集合に関する関数で、すべての $I\subset \{1, 2, \ldots, n\}$ について
$$\sum_{J\subset I}\mu(J) \geq \sum_{J\subset I}\lambda^-(J)$$
が成り立つとき、
$$\# S \geq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \#A_I$$
が成り立つ。
&&&

&&&prf
各 $x$ について
$$\sum_{I\subset J(x)}\mu(I) \leq \sum_{I\subset J(x)}\lambda^+(I)$$
が成り立つから
$$\# S \leq \sum_{x\in A} \sum_{I\subset J(x)}\lambda^+(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \# A_I$$
となる。同様に各 $x$ について
$$\sum_{I\subset J(x)}\mu(I) \geq \sum_{I\subset J(x)}\lambda^-(I)$$
だから
$$\# S \geq \sum_{x\in A} \sum_{I\subset J(x)}\lambda^-(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\lambda^-(I) \# A_I$$
となる。
&&&

整数論において篩法を用いる場合の多くは素数を法とする剰余類を取り除く。このことはつぎのようにあらわすことができる。

$A$ をものの集まりとし、各素数 $p$ に対して $A$ の部分集合 $A_p$ が与えられ、
相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について $A_d=\bigcap_{i=1}^r A_p$ と定め、$A_1=A$ と定める。
一方、各素数 $p$ に対して実数（整数でなくてもよい） $\rho(p)$ が対応し、相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について
$$\rho(d)=\prod_{i=1}^r \rho(p), \rho(1)=1$$
と定める。
そして各 $d$ について
$$\# A_d=\frac{\rho(d)}{d}X+R_d=X\prod_{p\mid d}\frac{\rho(p)}{p}+R_d$$
となるとする（先述の $\delta_i$ に対して $\rho(p)/p$ が対応している）。
このとき $z$ よりも小さい素数 $p$ に対する $A_p$ をすべて $A$ から取り除いた集合の要素の個数を
$$S(A, z)=\# \left(A\setminus \bigcup_{p<z} A_p\right)$$
とおくと、包含と除去の原理から
$$S(A, z)=\sum_d \mu(d)\#A_d=X\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)+\sum_d \mu(d)R_d\tag{1}$$
となる。

この場合も、誤差項となる右辺の和は大きなものになりうるので、$\mu(d)$ を別の関数 $\lambda(d)$ で置き換えることがBrun以降の篩法の出発点であることは先の一般的な場合と同様である。

篩法の一般原理

Brunの最初の篩により、双子素数の個数の上からの評価を得ることができる。
&&&thm 
$a, b$ が互いに素な整数とする。
$\pi_2(a, b; x)$ を $ap+b$ も素数となる、素数 $p\leq x$ の個数とおくと
$$\pi_2(a, b; x)<\frac{ab CX (\log\log X)^2}{\varphi(ab) \log^2 X}$$
となる絶対定数 $C$ が存在する。
&&&

&&&prf
$$A_p=\{n\in A: (p\mid n)\lor(an+b\equiv 0\Mod{p})\}$$
と定める。
このとき $p$ が $a$ を割り切るとき、$p$ は $b$ を割り切らないので $\rho(p)=1$、
$p$ が $b$ を割り切るとき、$p$ は $a$ を割り切らないので、やはり $\rho(p)=1$
となり、$ab$ を割り切らない素数 $p$ について、
$au\equiv b\Mod{p}$ となる $k$ を $u(p)$ とおくと
$$A_p=\#\{n: M<n\leq M+X, (n\equiv 0\Mod{p})\lor(n\equiv u(p)\Mod{p})\}$$
より $\rho(p)=2$ となる。よって[Mertensの第3定理](/textbooks/gDWQ3LLZ9Owb8113FxQU/0Jr3r7kACWdqEm8ck2dv)より
$$\begin{split}
\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)
= & \prod_{p<z, p\mid ab}\left(1-\frac{1}{p}\right)\prod_{p<z, p\nmid ab}\left(1-\frac{2}{p}\right) \\
< & \prod_{p<z, p\mid ab}\left(1-\frac{1}{p}\right)^{-1}\prod_{p<z}\left(1-\frac{1}{p}\right)^2 \\
< & \left(\prod_{p<z, p\mid ab}\left(1-\frac{1}{p}\right)^{-1}\right) \frac{C_1}{\log^2 z} \\
= & \frac{ab C_1}{\varphi(ab) \log^2 z}
\end{split}$$
となる。また、[「初等整数論」素数の分布（初等的理論）: x 以下の素数の個数:定理1の系](/textbooks/gDWQ3LLZ9Owb8113FxQU/EGeYZnTTqCHLrdUd0E6d#th1c)および[「初等整数論」素数の分布（初等的理論）:Chebyshev関数の初等的評価の定理2](/textbooks/gDWQ3LLZ9Owb8113FxQU/snTEyc0tTRhT3O7wUmQd#th2)から、$\pi(z)<C_2 z/\log z$ となる定数 $C_2$ が存在するので、
$$1+\sum_{p<z}\rho(p)<1+2\pi(z)<\frac{C_3 z}{\log z}$$
となる。

これらのことから、$m$ が $2e(2\log\log z+C_4)$ より大きい偶数のとき、
$$\# S(A, z)<\frac{ab C_1 X}{\varphi(ab) \log^2 z}+\frac{X}{2^m}+\left(\frac{C_3 z}{\log z}\right)^m \ \ (1.9)$$
であることがわかる。定数 $c$ を $2e$ より大きく選び、
$$z=X^{1/(3c\log\log X)}, m=2\floor{c\log\log X}$$
とおくと、$X$ が大きいとき、
$$m>2(c\log\log X-1)>2e(2\log\log X+C_4)>2e(2\log\log z+C_4)$$
より、$m$ は $2e(2\log\log z+C_4)$ より大きい偶数なので、$(1.9)$ が成り立つ。$X$ が大きいとき、$z$ も大きくなるので
$$\begin{split}
\# S(A, z)< & \frac{ab C_1 X}{\varphi(ab) \log^2 z}+\frac{X}{2^m}+z^m \\
< & \frac{9ab C_1 c^2 X (\log\log X)^2}{\varphi(ab) \log^2 X}+\frac{4X}{\log^{2c\log 2} X}+X^{2/3}
\end{split}$$
となる。


さて、$p, ap+b$ がともに素数で $p\geq z$ ならば、$p, ap+b$ はいずれも $z$ より小さい素因数をもたないから $p$ は $S(A, z)$ に含まれる。よって
$$\begin{split}
\pi_2(a, b; x)\leq & \# S(A, z)+\pi(z) \\
< & \frac{9ab C_1 c^2 X (\log\log X)^2}{\varphi(ab) \log^2 X}+\frac{4X}{\log^{2c\log 2} X}+X^{2/3}+z
\end{split}$$
となるから、定理が成り立つ。
&&&

このことから、$ap+b$ も素数となる素数 $p$ の逆数の和が収束することがわかる。とくに、$p+2$ も素数となる素数 $p$ の逆数の和は収束する。よって双子素数 $p, p+2$ の逆数の和
$$\sum_{p, p+2: \textrm{prime}}\left(\frac{1}{p}+\frac{1}{p+2}\right)
=\left(\frac{1}{3}+\frac{1}{5}\right)+\left(\frac{1}{5}+\frac{1}{7}\right)+\left(\frac{1}{11}+\frac{1}{13}\right)+\cdots$$
は収束する。この逆数の和を**Brun定数** (*Brun's constant*) という。

Brunの最初の篩（応用）

ところで、先の $(1)$ の右辺に現れる積
$$\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)$$
の大きさも知る必要がある。Legendreの篩の場合はすべての素数に対して $\rho(p)=1$ であったから
[Mertensの第3定理](/textbooks/gDWQ3LLZ9Owb8113FxQU/0Jr3r7kACWdqEm8ck2dv)より
$$\prod_{p<z}\left(1-\frac{1}{p}\right)^{-1}=\frac{e^{-\gamma}}{\log z}\left(1+O\left(\frac{1}{\log z}\right)\right)$$
となることがわかる。このことから $z>w>1$ のとき
$$\prod_{w\leq p<z}\left(1-\frac{1}{p}\right)=\frac{\log w}{\log z}\left(1+O\left(\frac{1}{\log w}\right)\right)$$
となることもわかる。ただし、この右辺の $O$ 記号における定数は $w$ にも $z$ にも依存しない絶対定数である。

さらに、
$$\log\prod_{w\leq p<z}\left(1-\frac{k}{p}\right)=\sum_{w\leq p<z}\log\left(1-\frac{k}{p}\right)=-k\sum_{w\leq p<z}\frac{1}{p}+O\left(\frac{1}{p^2}\right)$$
となるから、有限個の素数を除いて $\rho(p)=k$ となるとき
$$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}=(1+o(1))\left(\frac{\log z}{\log w}\right)^k$$
となる（この右辺の $o(1)$ は $w\rightarrow +\infty$ のとき $0$ に近づく）。とくに
$$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}=O\left(\left(\frac{\log z}{\log w}\right)^k\right)$$
が成り立つ。ただし、この右辺の $O$ 記号における定数は $w$ にも $z$ にも依存しない絶対定数である。

一般に、実数（整数でなくてもよい） $k$ に対して上記の式が成り立つとき、$k$ を**篩密度** (*sifting density*) という。この場合の篩を **$k$ 次元の篩** (*$k$-dimensional sieve*) という。

&&&thm [th1]
与えられた定数 $k$ について、つぎの $(1)$ が成り立つとき $(2)$ が成り立ち、$(2)$ が成り立つとき $(3)$ が成り立つ。

$(1)$
$$\sum_{w\leq p<z}\rho(p)\leq k\int_w^z\frac{dt}{\log t}+A_0$$
となる定数 $A_0$ が存在する。

$(2)$
$$\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}\leq k\log\left(\frac{z}{w}\right)+A_1$$
となる定数 $A_1$ が存在する。

$(3)$
$$\sum_{w\leq p<z}\frac{\rho(p)}{p}\leq k(\log\log z-\log\log w)+\frac{A_2}{\log w}$$
となる定数 $A_2$ が存在する。

さらに、$(3)$ が成り立つとき
$$\sum_{p<z}\rho(p)\leq (k+A_2)\mathrm{Li} z+\frac{2A_2}{\log 2}$$
となる。かつ、このとき
$$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}
<\left(\frac{\log z}{\log w}\right)^k\left(1+\frac{A_3}{\log w}\right)$$
となる定数 $A_3$ が存在する。なお、[[対数積分]]の定義で定めたように、
$$\mathrm{Li} z=\int_2^z \frac{dt}{\log t}$$
である。
&&&

&&&
$(1)$ が成り立つとして、左辺を
$$S_1(w, z)=\sum_{w\leq p<z}\rho(p)$$
とおく。[Abelの総和公式](/glossaries/fqEDxfQC5cz8BAIc7S1g#Abelの総和公式)より
$$\begin{split}
\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}= & \frac{S_1(w, z)\log z}{z}+\int_w^z \frac{S_1(w, t)(1+\log t)}{t^2}dt \\
< & \frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right)-\int_w^z\left(k\int_w^t\frac{du}{\log u}+A_0\right)\frac{1+\log t}{t^2}dt \\
= & \frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right)-\frac{S_1(w, z)\log z}{z}+\int_w^z\frac{kdt}{t} \\
< & k\left(\log\frac{z}{w}\right)+\frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right)
\end{split}$$
となるが、[対数積分:定理1](/glossaries/LZ41mVthM1FhMERCYa5E#th1)より
$$\int_w^z\frac{dt}{\log t}<\frac{z}{\log z}+\sqrt{z}+\frac{4z}{\log^2 z}$$
となるので
$$\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}\leq k\log\left(\frac{z}{w}\right)+A_1$$
となる定数 $A_1$ がとれるので、 $(2)$ が成り立つ。

つぎに $(2)$ が成り立つとして、左辺を
$$S_2(w, z)=\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}$$
とおくと、先と同様に、
$$\begin{split}
\sum_{w\leq p<z}\frac{\rho(p)}{p}= & \frac{S_2(w, z)}{\log z}+\int_w^z\frac{S_2(w, t)}{t\log^2 t}dt \\
< & \frac{k\log (z/w)}{\log z}+\frac{A_1}{\log z}+\int_w^z \frac{k}{t\log t}+\frac{A_1-k\log w}{t\log^2 t}dt \\
= & k(\log\log z-\log\log w)+\frac{A_1}{\log w}+\frac{k\log (z/w)}{\log z}-k\left(1-\frac{\log w}{\log z}\right) \\
= & k(\log\log z-\log\log w)+\frac{A_1}{\log w}
\end{split}$$
となるので、$(3)$ が成り立つ。

$(3)$ が成り立つとして、左辺を
$$S_3(z)=\sum_{w\leq p<z}\frac{\rho(p)}{p}$$
とおく。
$$\begin{split}
\int_2^z S_3(w, z)dw= & \sum_{w\leq p<z}\left(\int_2^p\frac{\rho(p)}{p} dt\right) \\
= & \sum_{w\leq p<z}\frac{\rho(p)(p-2)}{p} \\
= & S_1(2, z)-2S_3(2, z)
\end{split}$$
なので、
$$\begin{split}
S_1(2, z)= & 2S_3(2, z)+\int_2^z S_3(w, z)dw \\
\leq & 2k(\log\log z-\log\log 2)+\frac{2A_2}{\log 2}+\int_2^z k(\log\log z-\log\log t)+\frac{A_2}{\log t}dt
\end{split}$$
となる。ここで
$$\int_2^z \log\log tdt=z\log\log z-2\log\log 2-\int_2^z \frac{dt}{\log t}$$
であるから
$$\begin{split}
\int_2^z k(\log\log z-\log\log t)+\frac{A_2}{\log t}dt
= & k((z-2)\log\log z-z\log\log z+2\log\log 2)+\int_2^z \frac{k+A_2}{\log t}dt \\
= & 2k(\log\log 2-\log\log z)+(k+A_2)\mathrm{Li} z
\end{split}$$
となるので、
$$S_1(2, z)\leq (k+A_2)\mathrm{Li} z+\frac{2A_2}{\log 2}$$
となることがわかる。

また、$(3)$ が成り立つとき
$$\frac{\rho(p)}{p}\leq -\log (1-\frac{\rho(p)}{p})\leq \frac{\rho(p)}{p}+\frac{\rho(p)}{2p^2}+\frac{\rho(p)}{3p^3}+\cdots\leq \frac{\rho(p)}{p}+\frac{\rho(p)}{p^2}$$
となるから
$$\exp \sum_{w\leq p<z}\frac{\rho(p)}{p}<\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}<\exp\left(\sum_{w\leq p<z}\frac{\rho(p)}{p}+\frac{\rho(p)}{p^2}\right)$$
が成り立つ。ここで、
$$\begin{split}
\sum_{w\leq p<z}\frac{\rho(p)}{p^2}= & \frac{S_3(w, z)}{z}+\int_w^z \frac{S_3(w, t)}{t^2}dt \\
< & \frac{k(\log\log z-\log\log w)}{z}+\frac{A_2}{z\log w}+\int_w^z \frac{k(\log\log t-\log\log w)}{t^2}+\frac{A_2}{t^2\log w} dt \\
< & \frac{k\log\log z}{z}+\frac{A_2}{z\log w}+\int_w^z \frac{k\log t}{t^2}+\frac{A_2}{t^2\log w} dt \\
< & \frac{k\log\log z}{z}+\frac{k(1+\log w)}{w}+\frac{A_2}{w\log w}　\\
< & \frac{A_4}{\log w}
\end{split}$$
となる定数 $A_4$ が存在するので、
$$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}<\exp\left(k(\log\log z-\log\log w)+\frac{A_2+A_4}{\log w}\right)<\left(\frac{\log z}{\log w}\right)^k\left(1+\frac{A_3}{\log w}\right)$$
となることがわかる。
&&&

篩密度と篩の次元

その後、Brunは篩法をさらに拡張し、[はじめに](./81MAA2LYzk5Urhpgc2oB)で紹介した一連の結果を得た。この拡張された篩法を単に**Brunの篩** (*Brun's sieve*) と呼ぶ。
Brunの篩は次の事実に依拠している。

&&&thm Brun's sieve （一般形） [th1]
$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 を参照）。

&&&lem [lm2]
$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}$$
が成り立つ。
&&&

&&&prf
$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](th1)の証明に戻る。
$$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](./5pqGgOJZZyGKkZ3kCQwy#th1)を適用することで[定理1](th1)が示される。

この篩法から[Brunの最初の篩の一般形](./SJqv3EpLDmmVqNsHzVZe#th1)を導くこともできる。実際、
$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](#th1)の\eqref{eq1}が成り立つから、同定理から[Brunの最初の篩（一般形）](./SJqv3EpLDmmVqNsHzVZe)の $(1)$, $(2)$ が従う。

Brunの篩（一般形）

[前ページ](./UGuBNQyMJzsZoRdvfNE0)の定理から、Brunが考察した整数に関する問題については、つぎのことがいえる。
まず、$A$ をものの集まりとし、各素数 $p$ に対して $A$ の部分集合 $A_p$ が与えられ、相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について
$$A_d=\bigcap_{i=1}^r A_p, A_1=A$$
と定める。一方、各素数 $p$ に対して実数（整数でなくてもよい） $\rho(p)$ が対応し、相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について
$$\rho(d)=\prod_{i=1}^r \rho(p_i), \rho(1)=1$$
と定める。そして各 $d$ について
$$\label{eq1} \# A_d=\frac{\rho(d)}{d}X+R_d=X\prod_{p\mid d}\frac{\rho(p)}{p}+R_d \tag{1}$$
となるとする（$\delta_i$ に対して $\rho(p)/p$ が対応している）。このとき $z$ よりも小さい素数 $p$ に対する $A_p$ をすべて $A$ から取り除いた集合の要素の個数を
$$S(A, z)=\# \left(A\setminus \bigcup_{p<z} A_p\right)$$
とおくと、つぎの定理が成り立つ。

&&&thm [th1]
$$2=z_s<z_{s-1}<\cdots<z_0=z$$
となる実数列 $z_i\ (i=0, 1, \ldots, s)$ をとる。また $b$ は $0$ 以上の任意の整数とする。

$d$ が平方因数をもたない自然数で、
$$\label{eq2}d=p_1 p_2 \cdots p_r, z>p_1>p_2>\cdots >p_r\tag{2}$$
と素因数分解されるとき、$\chi_0(d), \chi_1(d)$ をそれぞれ
$$\chi_0(d)=1\Longleftrightarrow[\omega(\gcd(d, P_{z_k, z}))\leq 2(b+k)-1\ (1\leq k\leq s)]$$
および
$$\chi_1(d)=1\Longleftrightarrow[\omega(\gcd(d, P_{z_k, z}))\leq 2(b+k)\ (1\leq k\leq s)]$$
により定める。
このとき
$$\label{eq3}\begin{split}
& \sum_{d\mid P(z)}\chi_0(d)\mu(d)\frac{\rho(d)}{d}-\sum_{d\mid P(z)}\chi_0(d)\abs{R_d}
\leq \\
& S(A, z)\leq \sum_{d\mid P(z)}\chi_1(d)\mu(d)\frac{\rho(d)}{d}+\sum_{d\mid P(z)}\chi_1(d)\abs{R_d}.\end{split}
\tag{3}$$
&&&

&&&prf
$\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}が成り立つ。
&&&

そこで
$$\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}$$
および
$$\sum_{d\mid P(z)}\chi_i(d)\abs{R_d}$$
の形の和について考察する必要がある。前者について、つぎのことがいえる。

&&&thm [th2]
$$H_i(z)=\frac{W(z_k)}{W(z)}\frac{1}{(2(k+b)+i)!}\left(\sum_{z_k\leq p<z}\frac{\rho(p)}{p}\right)^{2(k+b)+i}$$
とおくと、
$$\sum_{d\mid P(z)}\chi_0(d)\mu(d)\frac{\rho(d)}{d}\geq W(z)(1-H_0(z))$$
および
$$\sum_{d\mid P(z)}\chi_1(d)\mu(d)\frac{\rho(d)}{d}\leq W(z)(1+H_1(z))$$
が成り立つ。
&&&

&&&prf
$\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](./UGuBNQyMJzsZoRdvfNE0#lm2)と同様に
$$\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}$$
が得られ、ここから定理が従う。
&&&


Brunの篩（素数による篩）

ここで、$w\geq 2$ で、$z$ が大きいとき
$$\label{eqa}\sum_{w\leq p<z}\frac{\rho(p)}{p}<\kappa(\log\log z-\log\log w)+\frac{A}{\log w}\tag{*}$$
が成り立つ場合について考える。

$\lambda$ を
$$0<\lambda e^{1+\lambda}<1$$
となる定数とし（これは $0<\lambda<0.2784645427\cdots$ に同値である）、
$$\epsilon=\frac{1}{200e^{1/\kappa}}, \Lambda=\frac{2\lambda}{\kappa(1+\epsilon)}$$
と定める。さらに
$$\label{eq1}e^{(r-1)\Lambda}<\frac{\log z}{\log 2}\leq e^{r\Lambda} \tag{1}$$
となる整数 $r$ をとり、
$$\log z_k=e^{-k\Lambda} \log z\ (k=0, 1, \ldots, r-1), \log z_r=2$$
と定める。仮定より
$$\sum_{z_k\leq p<z}\frac{\rho(p)}{p}<\kappa(\log\log z-\log\log z_k)+\frac{A}{\log w}=k\Lambda+\frac{A}{\log w}$$
となるので、[篩密度と篩の次元:定理1](./N056lvfDe19oSv9Qn4E0#th1)より
$$\label{eq2}\frac{W(z_k)}{W(z)}\leq \left(\frac{\log z}{\log z_k}\left(1+\frac{A_1}{\log z_k}\right)\right)^\kappa\leq e^{k\Lambda\kappa+A_1\kappa/\log z_k} \tag{2}$$
となる、$A$ にのみ依存する定数 $A_1$ が存在する。
この仮定のもとで、次の事実が成り立つ。

&&&lem [lm1]
$$\frac{\log z}{\log 2}>\exp\frac{A_1e^\Lambda}{\epsilon\log 2}$$
が成り立つとする。このとき
$$\label{eq3}\sum_{z_k\leq p<z}\frac{\rho(p)}{p}<2k\lambda+\frac{\kappa  A_1}{\log z} \tag{3}$$
および
$$\label{eq4}\frac{W(z_k)}{W(z)}\leq e^{2k\lambda+\kappa  A_1/\log z} \tag{4}$$
が成り立つ。
&&&

&&&prf
\eqref{eq2}より
$$\log \frac{W(z_k)}{W(z)}\leq \kappa\left(k\Lambda+\frac{A_1 e^{k\Lambda}}{\log z}\right)
=k\kappa\left(\Lambda+A_1\frac{e^{k\Lambda}-1}{k\log z}\right)+\frac{\kappa A_1}{\log z}$$
となるが、\eqref{eq1}より
$$\frac{e^{k\Lambda}-1}{k}\leq \frac{e^{r\Lambda}-1}{r}<\Lambda\frac{e^{r\Lambda}}{r\Lambda}
\leq \Lambda\frac{e^\Lambda\log z}{\log 2\log(\log z/\log 2)}$$
となるから、
$$\log \frac{W(z_k)}{W(z)}\leq k\kappa\Lambda\left(1+A_1\frac{e^\Lambda}{\log 2\log (\log z/\log 2)}\right)+\frac{\kappa A_1}{\log z}$$
が成り立つ。
仮定より
$$\frac{A_1e^\Lambda}{\log 2\log (\log z/\log 2)}\leq \epsilon$$
となるので、
$$\log \frac{W(z_k)}{W(z)}\leq k\kappa\Lambda(1+\epsilon)+\frac{\kappa A_1}{\log z}
=2k\lambda+\frac{\kappa A_1}{\log z}$$
となって、\eqref{eq4}が成り立つ。また
$$\sum_{z_k\leq p<z}\frac{\rho(p)}{p}\leq \sum_{z_k\leq p<z} -\log\left(1-\frac{\rho(p)}{p}\right)=\log\frac{W(z_k)}{W(z)}$$
より\eqref{eq3}も成り立つ。
&&&

そこで、
$$\mu=\frac{\kappa A_1}{2\log z}$$
とおく。つぎの評価が成り立つ。

&&&lem [lm2]
$z$ が大きいとき\eqref{eqa}が成り立つとすると、やはり $z$ が大きいとき
$$\label{eq5}H_i(z)\leq e^{(2b+i+4)\mu/\lambda}\frac{2\lambda^{2b+i+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}. \tag{5}$$
&&&

&&&prf
\eqref{eq3}は
$$\sum_{z_k\leq p<z}\frac{\rho(p)}{p}<2(k\lambda+\mu)$$
とあらわされ、\eqref{eq4}は
$$\frac{W(z_k)}{W(z)}\leq e^{2(k\lambda+\mu)}$$
とあらわされる。
$k=0$ のとき
$$\sum_{z_k\leq p<z}\frac{\rho(p)}{p}=0$$
なので
$$\label{eq6}\begin{split}
H_i(z)= & \sum_{k\geq 1}\frac{W(z_k)}{W(z)(2(k+b)+i)!}\left(\sum_{z_k\leq p<z}\frac{\rho(p)}{p}\right)^{2(k+b)+i} \\
\leq & \sum_{k\geq 1}e^{2(k\lambda+\mu)}\frac{(2(k\lambda+\mu))^{2(k+b)+i}}{(2(k+b)+i)!}
\end{split}\tag{6}$$
となる。
$(2(k+b)+i)!\geq (2k)!(2k)^{2b+i}$ より
$$\begin{split}
\sum_{k\geq 1}e^{2(k\lambda+\mu)}\frac{(2(k\lambda+\mu))^{2(k+b)+i}}{(2(k+b)+i)!}
\leq & e^{2\mu}\sum_{k\geq 1}\left(\frac{k\lambda+\mu}{k}\right)^{2b+i}\frac{(2(k\lambda+\mu))^{2k}}{(2k)!} e^{2k\lambda} \\
\leq & e^{2\mu}(\lambda+\mu)^{2b+i}\sum_{k\geq 1}\frac{(2k)^{2k}}{(2k)!}\left(1+\frac{\mu}{k\lambda}\right)^{2k} (\lambda e^{\lambda})^{2k}
\end{split}$$
となるが、
$$\begin{split}
\log\frac{(2k/e)^{2k}}{(2k)!}= & 2k(\log(2k)-1)-\sum_{n=1}^{2k}\log n \\
= & 1+\int_1^{2k} \log tdt-\sum_{n=1}^{2k}\log n \\
= & 1+\sum_{n=2}^{2k}\left(\int_{n-1}^n (\log t-\log n)dt\right)
\end{split}$$
は減少関数なので、
$$\frac{(2k)^{2k}}{(2k)!}=e^{2k}\frac{(2k/e)^{2k}}{(2k)!}\leq \frac{2e^{2k}}{e^2}$$
となる。また
$$\left(1+\frac{\mu}{k\lambda}\right)^{2k}<e^{2\mu/\lambda}$$
だから
$$\begin{split}
\sum_{k\geq 1}e^{2(k\lambda+\mu)}\frac{(2(k\lambda+\mu))^{2(k+b)+i}}{(2(k+b)+i)!}
\leq & 2e^{2\mu-2}(\lambda+\mu)^{2b+i}\sum_{k\geq 1}\left(1+\frac{\mu}{k\lambda}\right)^{2k} (\lambda e^{1+\lambda})^{2k} \\
\leq & 2e^{2\mu-2+2\mu/\lambda}(\lambda+\mu)^{2b+i}\sum_{k\geq 1}(\lambda e^{1+\lambda})^{2k} \\
= & 2e^{2\mu-2+2\mu/\lambda}(\lambda+\mu)^{2b+i}\frac{(\lambda e^{1+\lambda})^2}{1-(\lambda e^{1+\lambda})^2} \\
= & e^{2\mu(1+1/\lambda)}\left(1+\frac{\mu}{\lambda}\right)^{2b+i}\frac{2\lambda^{2b+i+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}
\end{split}$$
となる。よって\eqref{eq6}から
$$H_i(z)\leq e^{2\mu(1+1/\lambda)}\left(1+\frac{\mu}{\lambda}\right)^{2b+i}\frac{2\lambda^{2b+i+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}$$
であることがわかる。ここで、$\lambda<1$ より
$$\left(1+\frac{\mu}{\lambda}\right)^{2b+i}<e^{(2b+i)\mu/\lambda}, e^{2\mu(1+1/\lambda)}<e^{4\mu/\lambda}$$
となるので、
$$H_i(z)\leq e^{(2b+i+4)\mu/\lambda}\frac{2\lambda^{2b+i+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}$$
であることがわかり、\eqref{eq5}が示される。
&&&

これと、[前ページの定理2](./tm4KtrHtiMOAIJIQTPVx#th2)から、
$$\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}$$
の評価が得られる。[前ページの定理1](./tm4KtrHtiMOAIJIQTPVx#th1)から、$S(A, z)$ の評価のためには、
$$\sum_{d\mid P(z)}\chi_i(d)\abs{R_d}$$
の評価を得ることができればよい。
そこで\eqref{eqa}に加えて
$$\label{eqb}\abs{R_d}\leq \rho(d)\tag{\dagger}$$
が成り立つ場合について考える。

&&&lem [lm3]
$d$ が平方因数をもたない自然数の時 $(\flat)$ が成り立ち、かつ $z\geq C_0$ のとき $(\sharp)$ が成り立つとすると、
$z\geq C_1$ のとき
$$\label{eq7}\sum_{d\mid P(z), \chi_i(d)=1}\rho(d)\leq z^{2b+i+1+2.01/(e^{2\lambda/\kappa}-1)} \tag{7}$$
となる。ここで $C_1$ は $C_0, \kappa, A$ にのみ依存する定数である。
&&&

&&&prf
仮定から
$$\sum_{d\mid P(z)}\chi_i(d)\abs{R_d}\leq \sum_{d\mid P(z), \chi_i(d)=1}\rho(d)$$
となるが、
$\chi_i(d)=1$ のとき、 $z_k$ 以上の素因数の個数は $2(b+k)+i-1$ 以下であるから、
$$\sum_{d\mid P(z), \chi_i(d)=1}\rho(d)\leq\left(1+\sum_{p<z}\rho(p)\right)^{2b+i+1}\prod_{k=1}^{r-1}\left(1+\sum_{p<z_k}\rho(p)\right)^2$$
となる。[篩密度と篩の次元:定理1](./N056lvfDe19oSv9Qn4E0#th1)より
$$\sum_{p<z}\rho(p)\leq (\kappa+A)\mathrm{Li} z+\frac{2A}{\log 2}$$
なので、
$$\begin{split}
\sum_{d\mid P(z), \chi_i(d)=1}\rho(d)\leq & \left(1+\sum_{p<z}\rho(p)\right)^{2b+i+1}\prod_{k=1}^{r-1}\left(1+\sum_{p<z_k}\rho(p)\right)^2 \\
\leq & \left(1+(\kappa+A)\mathrm{Li} z+\frac{2A}{\log 2}\right)^{2b+i+1} \prod_{k=1}^{r-1} \left(1+(\kappa+A)\mathrm{Li} z_k+\frac{2A}{\log 2}\right)^{2b+i+1}
\end{split}$$
となる。

[対数積分:定理1]](/glossaries/LZ41mVthM1FhMERCYa5E#th1)より
$$1+(\kappa+A)\mathrm{Li} x+\frac{2A}{\log 2}<\frac{B_1 x}{\log x}$$
となる、$\kappa, A$ にのみ依存する $B_1$ が存在するから
$$\begin{split}
\sum_{d\mid P(z), \chi_i(d)=1}\rho(d)\leq & \left(1+\sum_{p<z}\rho(p)\right)^{2b+i+1}\prod_{k=1}^{r-1}\left(1+\sum_{p<z_k}\rho(p)\right)^2 \\
\leq & \left(\frac{B_1 z}{\log z}\right)^{2b+i+1} \prod_{k=1}^{r-1} \left(\frac{B_1 z_k e^{k\Lambda}}{\log z}\right)^2 \\
= & \left(\frac{B_1 z}{\log z}\right)^{2b+i+1} \exp\left(2\log z \sum_{k=1}^{r-1} e^{-k\Lambda} \right) \prod_{k=1}^{r-1} \left(\frac{B_1 e^{k\Lambda}}{\log z}\right)^2 \\
\leq & \left(\frac{B_1 z}{\log z}\right)^{2b+i+1} z^{2/(e^\Lambda -1)} \left(\frac{B_1}{\log z}\right)^{2(r-1)} e^{\frac{r(r-1)\Lambda}{2}} \\
= & \left(\frac{B_1 z}{\log z}\right)^{2b+i+1} z^{2/(e^\Lambda -1)} \left(\frac{B_1e^{r\Lambda /2}}{\log z}\right)^{2(r-1)}
\end{split}$$
となる。$z$ が大きいとき $\log z>B_1$ となるから
$$\label{eq8}\sum_{d\mid P(z), \chi_i(d)=1}\rho(d)\leq z^{2b+i+1} z^{2/(e^\Lambda -1)} \left(\frac{B_1e^{r\Lambda /2}}{\log z}\right)^{2(r-1)} \tag{8}$$
であることがわかる。

ここで
$$e^{2\lambda/\kappa}-e^\Lambda<(e^{2\lambda/\kappa-\Lambda}-1)e^{2\lambda/\kappa}<\left(\frac{2\lambda}{\kappa}-\Lambda\right)e^{2\lambda/\kappa}$$
および
$$\frac{2\lambda}{\kappa}-\Lambda=\frac{2\lambda}{\kappa}\left(1-\frac{1}{1+\epsilon}\right)=\epsilon\Lambda$$
より
$$e^{2\lambda/\kappa}-e^\Lambda<\epsilon\Lambda e^{2\lambda/\kappa}$$
であることがわかる。よって
$$\frac{e^{2\lambda/\kappa}-1}{e^\Lambda -1}<1+\frac{\epsilon\Lambda e^{2\lambda/\kappa}}{e^\Lambda -1}$$
となるが、$\lambda<1/2$ なので
$$\frac{e^{2\lambda/\kappa}-1}{e^\Lambda -1}<1+\epsilon e^{2\lambda/\kappa}<1+\epsilon e^{1/\kappa}=\frac{201}{200}$$
となる。さらに $e^{(r-1)\Lambda}<\log z/\log 2$ より
$$\frac{e^{r\Lambda/2}}{\log z}\leq \frac{e^{2\lambda/\kappa+(r-1)\Lambda/2}}{\log z}<\frac{e^{1/\kappa}}{\sqrt{\log z}}$$
となるが、$z$ が大きいとき $\sqrt{\log z}>e^{1/\kappa}$ となるから、上記不等式の右辺は $1$ より小さくなる。
よって、\eqref{eq8}より\eqref{eq7}が示される。
&&&

[前ページ定理2](./tm4KtrHtiMOAIJIQTPVx#th2)および[補題2](#lm2)から得られる
$$\sum_{d\mid P(z)}\chi_i(d)\mu(d)\frac{\rho(d)}{d}$$
の評価と[補題3](#lm3)から得られる
$$\sum_{d\mid P(z)}\chi_i(d)\abs{R_d}$$
の評価から、[前ページ定理1](./tm4KtrHtiMOAIJIQTPVx#th1)より、ついに次の結果が得られる。

&&&thm [th4]
$d$ が平方因数をもたない自然数の時\eqref{eqb}が成り立ち、かつ $z\geq C_0$ のとき\eqref{eqa}が成り立つとすると、$z\geq C$ のとき、整数 $b\geq 0$ に対して
$$S(A, z)\geq XW(z)\left(1-e^{(b+2)\kappa A_1/\lambda\log z}\frac{2\lambda^{2b+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)-z^{2b+1+2.01/(e^{2\lambda/\kappa}-1)}$$
および
$$S(A, z)\leq XW(z)\left(1-e^{(b+5/2)\kappa A_1/\lambda\log z}\frac{2\lambda^{2b+3}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)+z^{2b+2+2.01/(e^{2\lambda/\kappa}-1)}$$
が成り立つ。ここで $C$ は $C_0, \kappa, A$ にのみ依存する定数である。
&&&


Brunの篩（素数による篩の評価）

[前ページの定理4](./RMaJ2IboVaIbU8qFodxz#th4)を再掲する。

&&&thm [th1]
$z\geq C_0$ のとき
$$\label{eqa}\sum_{w\leq p<z}\frac{\rho(p)}{p}<\kappa(\log\log z-\log\log w)+\frac{A}{\log w}\tag{*}$$
が成り立つとし、$d$ が平方因数をもたない自然数のとき
$$\label{eqb}\abs{R_d}\leq \rho(d)\tag{\dagger}$$
が成り立つとする。
このとき、さらに $z\geq C$ ならば、整数 $b\geq 0$ に対して
$$S(A, z)\geq XW(z)\left(1-e^{(b+2)\kappa A_1/\lambda\log z}\frac{2\lambda^{2b+2}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)-z^{2b+1+2.01/(e^{2\lambda/\kappa}-1)}$$
および
$$S(A, z)\leq XW(z)\left(1-e^{(b+5/2)\kappa A_1/\lambda\log z}\frac{2\lambda^{2b+3}e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)+z^{2b+2+2.01/(e^{2\lambda/\kappa}-1)}$$
が成り立つ。ここで $C$ は $C_0, \kappa, A$ にのみ依存する定数である。
&&&

この定理は素数に関する多くの未解決の問題について、部分的な解決を与える。たとえば、双子素数の予想に対する部分的解決が得られる。

そこで、$n$ と $an+b$ がともに $z$ より小さい素因数をもたない場合を考える。ただし $a, b$ は互いに素な整数で、$a>0$ かつ $ab$ は偶数とする。

$A$ を $X$ 以下の正の整数全体の集合、$A_p$ を $A$ の要素 $n$ のうち、$n$ あるいは $an+b$ の少なくとも一方が $p$ で割り切れるもの全体の集合とし、$p\mid a$ のとき $\rho(p)=0$、$p\mid b$ のとき $\rho(p)=1$、それ以外のとき $\rho(p)=2$ とする。

$p\mid a$ のとき $a, b$ は互いに素だから
$$an+b\equiv b\not\equiv 0\Mod{p}$$
となるから、$\# A_p=0$ となる。$p\mid b$ のとき $a, b$ は互いに素なので
$$p\mid (an+b)\Longleftrightarrow p\mid (an)\Longleftrightarrow p\mid n$$
であるから
$$A_p=\{n\leq X, p\mid n\}$$
となる。それ以外のとき、
$$an+b\equiv 0\Mod{p}\Longleftrightarrow n\equiv k\Mod{p}$$
となる、$0$ でない剰余類 $k\Mod{p}$ が一意的に定まるから、
$$A_p=\{n\leq X, n\equiv 0, k\Mod{p}\}$$
となる。
これらのことから、$d$ が平方因数をもたない自然数のとき
$$A_d=\{n\leq X, n\equiv r_1, r_2, \ldots, r_{\rho(d)}\Mod{d}\}$$
となる、相異なる $\rho(d)$ 個の剰余類 $r_1, r_2, \ldots, r_{\rho(d)}\Mod{d}$ がとれる。よって
$$\abs{\#A_d-\frac{\rho(d)X}{d}}\leq \rho(d)$$
であることがわかるので、\eqref{eqb}が成立する。
また、[Mertensの第1定理](/textbooks/gDWQ3LLZ9Owb8113FxQU/0Jr3r7kACWdqEm8ck2dv)より
$$\sum_{w\leq p<z} \frac{\rho(p)}{p}\leq \sum_{w\leq p<z} \frac{2\rho(p)}{p}<2(\log\log z-\log\log w)+\frac{A}{\log w}$$
となる定数 $A$ が存在するから、\eqref{eqa}が成立する。
さらに、$z$ が $ab$ の最大の素因数より大きいとき、[Mertensの第3定理](/textbooks/gDWQ3LLZ9Owb8113FxQU/0Jr3r7kACWdqEm8ck2dv)より
$$\label{eq1}\begin{split}
W(z)= & \prod_{p<z, p\mid b}\left(1-\frac{1}{p}\right)\prod_{p<z, p\not\mid ab}\left(1-\frac{2}{p}\right) \\
= & \prod_{p\mid b}\left(1-\frac{1}{p}\right)\prod_{p<z, p\not\mid ab} \left[\left(1-\frac{1}{p}\right)^2\left(1-\frac{1}{(p-1)^2}\right)\right] \\
= & c \prod_{p<z}\left(1-\frac{1}{p}\right)^2 \prod_{p\geq z}\left(1-\frac{1}{(p-1)^2}\right) \\
= & \frac{c}{e^{2\gamma} \log^2 z}\left(1+O\left(\frac{1}{\log z}\right)\right),
\end{split}\tag{1}$$
ここで
$$c=\prod_{p\mid b}\left(1-\frac{1}{p}\right)^{-1} \prod_{p\mid a}\left(1-\frac{1}{p}\right)^{-2} \prod_{p\not\mid ab} \left(1-\frac{1}{(p-1)^2}\right) $$
となる。$ab$ は偶数なので $c>0$ となる。

これらのことから、\eqref{eqa}および\eqref{eqb}が成立するので、Brunの篩において $b=0$ とおくと、$z$ が大きいとき
$$S(A, z)\geq XW(z)\left(1-e^{2/\lambda\log z}\frac{2\lambda^2 e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)-z^{1+2.01/(e^\lambda -1)}$$
および
$$S(A, z)\leq XW(z)\left(1-e^{5/2\lambda\log z}\frac{2\lambda^3 e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}\right)+z^{2+2.01/(e^\lambda -1)}$$
が成り立つ。
ここで、$\lambda=0.253$ とおくと
$$\frac{2\lambda^2 e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}=0.98523\cdots<1$$
および
$$1+2.01/(e^\lambda -1)=7.98199\cdots$$
より、$z$ が大きいとき
$$S(A, z)\geq 0.01476XW(z)-z^{7.982}$$
が成り立つ。$z=\max\{X+1, (aX+b+1)\}^{1/8}$ とおくと、 $(3.9)$ より
$$S(A, \max\{X+1, (aX+b+1)\}^{1/8})\geq \frac{c_3 X}{\log^2 X}-\frac{c_4 X}{\log^3 X}-\max\{X+1, (aX+b+1)\}^{0.99775}$$
となる定数 $c_3>0, c_4$ がとれる。
ここで、$n$ が $S(A, \max\{X+1, (aX+b+1)\}^{1/8})$ によって数え上げられるとき $n, an+b$ ともに $\max\{X+1, (aX+b+1)\}^{1/8}$ より小さい素因数をもたないが、$n$ は $X$ 以下の整数だから、$S(A, \max\{X+1, (aX+b+1)\}^{1/8})$ によって数え上げられる整数 $n$ については $n, an+b$ ともに重複度を含めても、多くても $7$ 個の素因数しかもたない。

ところで
$$\frac{2\lambda^2 e^{2\lambda}}{1-\lambda^2 e^{2(1+\lambda)}}=0.24926\cdots$$
および
$$2+2.01/(e^\lambda -1)=8.98199\cdots$$
が成り立つから
$z=X^{1/9}$ とおくと
$$S(A, X^{1/9})\leq 1.24927XW(z)+z^{8.982}<\frac{c_5 X}{\log^2 X}+\frac{c_6 X}{\log^3 X}+X^{0.998}$$
となる $c_5, c_6$ が存在する。
一方、$p, ap+b$ がともに素数で $p\geq X^{1/9}$ ならば $p, ap+b$ は $X^{1/9}$ より小さい素因数をもたない。よって
$$\pi_2(a, b; X)-\pi_2(a, b; X^{1/9})<S(A, X^{1/9})<\frac{c_5 X}{\log^2 X}+\frac{c_6 X}{\log^3 X}+X^{0.998}$$
となるから、
$$\pi_2(a, b; X)<\frac{c_5 X}{\log^2 X}+\frac{c_6 X}{\log^3 X}+X^{0.998}+X^{1/9}<\frac{c_7 X}{\log^2 X}$$
となる定数 $c_7$ が存在する。

つまり、次の定理が成り立つ。

&&&thm [th2]
$a$ と $b$ が互いに素な整数で $a>0$ であるとき、$n, an+b$ がいずれも重複度を含めて多くても $7$ 個の素因数しかもたない整数 $n$ が無限に多く存在する。一方、ある定数 $c_7$ について、$X$ 以下の素数 $p$ で、$ap+b$ も素数であるものの個数は必ず $c_7 X/\log^2 X$ より小さくなる。
&&&

これは、双子素数に関してBrunの最初の篩の応用よりも強い評価を与え、さらに、素数の代わりに重複度を含めて多くても $7$ 個の素因数しかもたない整数を考えると、そのような整数の組 $(n, n+2)$ は無限に多く存在することを示している。


Brunの篩はまた、Goldbach予想の部分的解決をも導く。$n$ を偶数とする。
$$A_p=\{x: 1\leq x\leq n-1, p\mid x(n-x)\}$$
とおくと、
$S(A, z)$ は $m, n-m$ がともに $z$ より小さな素因数をもたない正の整数 $m\leq x$ の個数となる。

$p\mid n$ のとき $\rho(p)=1$、それ以外のとき $\rho(p)=2$ とすると、先程と同様に\eqref{eqa}が成り立ち、また
$$\abs{\#A_d-\frac{\rho(d)n}{d}}\leq \rho(d)$$
となるので、\eqref{eqb}が成り立つ。また、
$$W(z)=\frac{c}{e^{2\gamma} \log^2 z}\left(1+O\left(\frac{1}{\log z}\right)\right),$$
ここで
$$c=\prod_{p\mid n}\left(1-\frac{1}{p}\right)^{-1} \prod_{p\not\mid n} \left(1-\frac{1}{(p-1)^2}\right)$$
となるから、
$$\frac{C_1}{\log^2 z}\prod_{p\mid n}\left(1+\frac{1}{p}\right)<W(z)<\frac{C_2}{\log^2 z}\prod_{p\mid n}\left(1+\frac{1}{p}\right)$$
となる正の絶対定数 $C_1, C_2$ がとれる。実際、$n$ は偶数なので、$c>0$ かつ $C_1>0$ であることがわかる。
$$f(n)=\prod_{p\mid n}\left(1+\frac{1}{p}\right)$$
とおくと、
$$\frac{C_1 f(n)}{\log^2 z}<W(z)<\frac{C_2 f(n)}{\log^2 z}$$
となる。

このことから、つぎの事実がわかる。前段はGoldbach予想の部分的解決となっており、後段はSchnirelmannによる、別の形でのGoldbach予想の部分的解決に用いられる。

&&&thm [th3]
十分大きな偶数は、重複度を含めても、多くても $7$ 個の素因数しかもたない数 $2$ つの和としてあらわされる。
また、$R(n)$ を、整数 $n$ を$2$つの素数の和 $p+q$ の形にあらわす方法の個数とする。ただし $p=q$ でもよく、また $p, q$ を入れ替えたものは別の表現として数える。このとき、$n$ が偶数のとき
$$R(n)<\frac{C_0 f(n)n}{\log^2 n}$$
となる絶対定数 $C_0$ が存在する。ただし、
$$f(n)=\prod_{p\mid n}\left(1+\frac{1}{p}\right)$$
とする。
&&&

&&&prf
Brunの篩から、$n$ が大きいとき先程と同様に
$$S(A, z)\geq 0.01476nW(z)-z^{7.982}$$
となるので、
$$S(A, n^{1/8})\geq \frac{C_3 f(n)n}{\log^2 n}$$
となる絶対定数 $C_3>0$ が存在する。整数 $m$ が $S(A, n^{1/8})$ によって数え上げられるとき $m, n-m$ はともに$n^{1/8}$ より小さい素因数をもたない $n-1$ 以下の正の整数だから、$m, n-m$ は重複度を含めても、多くても $7$ 個の素因数しかもたない。

一方、 $z=n^{1/9}$ とおくと、$z$ が大きいとき
$$S(A, n^{1/9})\leq 1.24927nW(z)+z^{8.982}<\frac{C_3 f(n)n}{\log^2 n}$$
となる絶対定数 $C_3$ がとれる。一方、$p, n-p$ がともに素数で、$n^{1/9}\leq p\leq n-n^{1/9}$ ならば $p, n-p$ は $n^{1/9}$ より小さい素因数をもたないから $p$ は $S(A, n^{1/9})$ によって数え上げられる。よって
$$R(n)\leq S(A, n^{1/9})+2n^{1/9}<\frac{C_0 f(n)n}{\log^2 n}$$
が成り立つ。
&&&

Brunの篩（応用）

Sieves in Number Theory

Sieve Methods, 2nd Edition

Additive Number Theory: The Classical Bases

篩法 (sieve method) は、全体集合から、与えられた条件をすべて満足する（あるいはいずれも満足しない）ものの個数を評価する技法である。

最も古い篩法は、与えられた範囲内の素数をすべて発見するEratosthenesの篩であるが、20世紀になって篩法が素数に関する様々な問題の研究に盛んに用いられるようになり、近年では他の数論や組合せ論の問題への応用も行われるようになっている。

この参考書では、20世紀以降飛躍的に進展した、篩法の素数に関する問題への応用について解説する。

Brunの最初の篩（一般形）

参考文献