Legendreの篩と篩法入門

前回はEratosthenesの篩について考えました。
mathnote.info
今回はEratosthenesの篩における”素数をふるい出す”という操作のLegendreによる数式表現を与え、篩が双子素数やGoldbach予想などと関連する様子を紹介します。

参考文献
素数の場合
Legendreによる定式化
素数の場合(2)
Legendreの篩の欠点
双子素数の場合
Goldbach予想の場合
篩法とはなにか
おわりに

参考文献

篩法の入門的なテキストをいくつか紹介します。とくにHalberstam&Richertは篩法の伝統的なテキストで、リーズナブルなうえに情報量が豊富でkindre版もあるのでおすすめです。日本語だと内山先生のテキストが有名ですが絶版のようなので図書館の蔵書検索のリンクを載せておきます。

(1)Sieve Methods (Dover Books on Mathematics) (English Edition)

kindre版

リンク

ペーパーバック版

リンク

(2)Sieves in Number Theory (A Series of Modern Surveys in Mathematics, 43)

リンク

(3)内山三郎素数の分布(宝文館出版)
CiNii 図書 - 素数の分布

素数の場合

$x\ge2$ とします。Eratosthenesの篩によって次の同値性が保証されます。

$\sqrt{x} \; {<}\; n\le x$ が素数
$n$ は $p\le \sqrt{x}$ なる任意の素数 $p$ と互いに素

後の応用を考えて変数 $z$ を導入します。 $\sqrt{x} \le z < x$ を仮定すると次の同値性がわかります。

$z\;{<}\;n \le x$ が素数
$n$ は $p\le z$ なる任意の素数 $p$ と互いに素

さらに $P(z)$ を
\begin{equation*}
P(z)=\prod_{\substack{p\; : \; \mathbb{素数}\\ p \le z }}p
\end{equation*}と定めれば最後の条件は $(n,P(z))=1$ と同値です。したがって $\pi(x)$ を $x$ 以下の素数の個数とすると
\begin{equation}
\pi(x)-\pi(z)+1=\sum_{(n,P(z))=1}1 \quad (\sqrt{x} < z \le x)　\label{Le1}
\end{equation}と書くことができます。ここで左辺の1は右辺の和において $n=1$ を足してしまう分を調節するための項です。こうして得られた\eqref{Le1}はEratosthenesの篩のもっともシンプルな数式化と考えられます。

続いて $2 \le z \le \sqrt{x}$ の場合を考えます。この場合は
\begin{equation*}
\sum_{(n,P(z))=1}1 = 1+\sum_{\substack{z{<} n \le x \\ (n,P(z))=1}}1 \ge 1+\pi(x)-\pi(z)
\end{equation*}となるので
\begin{equation}
\pi(x)-\pi(z)+1 \le \sum_{(n,P(z))=1}1 \quad (2\le z\le \sqrt{x}) \label{Le2}
\end{equation}が得られます。

以上の議論からEratosthenesの篩を素数に用いる際
\begin{equation*}
\sum_{(n,P(z))=1}1
\end{equation*}を調べる必要があることがわかりました。

Legendreによる定式化

より一般の場合を考察するために整数列 $\mathcal{A}$ を考えます。この $\mathcal{A}$ は篩にかける数表に対応していて、同じ整数が複数回現れても良いこととします。さらに整数 $d$ に対し
\begin{align*}
&S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A} \\ (a,P(z))=1}}1 \\
&\mathcal{A}_d =\{ a \in \mathcal{A} | a\equiv 0 \; （\mathbb{mod} \; d)\}
\end{align*}と定めます*1。目標は $S(\mathcal{A},z)$ の評価です。

Legendreによる定式化を導入するためにMöbius関数
\begin{align*}
\mu(n)=
\begin{cases}
1 \quad &(n=1)\\
0 \quad &(\exists p \; \mathrm{s.t.} \; p^2|n) \\
(-1)^k \quad &(n=p_1 \cdots p_k,\; p_i \neq p_j \; (i\neq j))
\end{cases}
\end{align*}を用います。ここで定義中の $p_i$ は素数です。

Lemma1(Möbius関数の基本公式)

\begin{equation*}
\sum_{d|n}\mu (d)=
\begin{cases}
1 \quad &(n=1)\\
0 \quad &(n>1)
\end{cases}
\end{equation*}

証明 $n=1$ のときは明らか。 $n>1$ のときはMöbiusの定義から $n=p_1\cdots p_k,$ $(p_i \neq p_j, \; i\neq j)$ と素因数分解できるときに示せば十分である。このとき約数 $d|n$ の選び方は $n$ の $k$ 個の素因数の中から $0\le m \le k$ 個選ぶ組み合わせの数だけある。 $d$ の素因数が $m$ 個のとき $\mu(d)=(-1)^m$ なので二項定理を用いれば
\begin{align*}
\sum_{d|n}\mu(d)=\sum_{m=0}^k\binom{k}{m}(-1)^m =(1-1)^k =0
\end{align*}となり主張が示される。(QED)

次の定理がLegendreによるEratosthenesの篩の定式化で、一般にLegendreの篩と呼ばれるものです*2。

Theorem2 (Legendreの篩)

\begin{equation*}
S(\mathcal{A},z)=\sum_{d|P(z)}\mu (d)|\mathcal{A}_d|
\end{equation*}

証明 Lemma1を用いれば $S(\mathcal{A},z)$ は
\begin{align*}
S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A} \\ (a,P(z))=1}}1=\sum_{a \in \mathcal{A}}\sum_{d|(a,P(z))}\mu (d)
\end{align*} $d|(a,P(z)) \Leftrightarrow d|a,d|P(z)$ なので
\begin{align*}
=\sum_{a \in \mathcal{A}}\sum_{d|a,P(z)}\mu(d)=\sum_{d|P(z)}\mu(d) \sum_{\substack{a\in \mathcal{A} \\ d|a}}1=\sum_{d|P(z)}\mu(d)|\mathcal{A}_d|
\end{align*}と計算できる。(QED)

素数の場合(2)

Legendreの篩を先の素数の場合に用いてみます。つまり
\begin{equation*}
\mathcal{A}=\{ n\in \mathbb{N}|1\le n \le x\}
\end{equation*}の場合を計算します。応用として
\begin{equation*}
\pi(x) \ll \frac{x}{\log \log x} \quad (x\to \infty)
\end{equation*}を導きます。

これ以降の議論では $z\ge 2$ とし整数 $d$ は $\mu(d)\neq 0$ を満たすこととします。Legendreの篩よりこの仮定の下でも一般性が保たれています。

Prop3

$\mu(d) \neq 0$ なる任意の整数 $d$ に対して
\begin{equation*}
{|}\mathcal{A}_d|=\frac{x}{d}+R_d
\end{equation*}が成立。ここで $R_d$ は $|R_d|\le 1$ を満たす関数とする。特に
\begin{equation*}
S(\mathcal{A},z)=x\prod_{p\le z}\left( 1-\frac{1}{p}\right) +O\left(2^{\pi(z)}\right)
\end{equation*}が成立する。

証明 \begin{equation*}
{|}\mathcal{A}_d|=\sum_{0{<} k \le x/d} 1=\left[ \frac{x}{d} \right]=\frac{x}{d}+\left\{ \frac{x}{d}\right\}
\end{equation*}より $R_d=\{ x/d \}$ に対して一つ目の等式が従う。これをLegendreの篩に代入すれば
\begin{align}
S(\mathcal{A},z)&=\sum_{d|P(z)}\mu(d) \left( \frac{x}{d}+R_d \right)\notag \\
&=x\sum_{d|P(z)}\frac{\mu(d)}{d} +O\left( \sum_{d|P(z)}1 \right) \label{Le3}
\end{align}\eqref{Le3}の第一項の和は $\mu(d)$ が乗法的なので
\begin{equation*}
\sum_{d|P(z)}\frac{\mu(d)}{d}=\prod_{p\le z} \left( 1-\frac{\mu(p)}{p}\right)=\prod_{p\le z}\left(1-\frac{1}{p}\right)
\end{equation*}と分解できる。第二項は二項定理から
\begin{equation*}
\sum_{d|P(z)}1=\sum_{m=0}^{\pi(z)} \binom{\pi(z)}{m} =2^{\pi(z)}
\end{equation*}と計算できる。したがって\eqref{Le3}は
\begin{equation*}
S(\mathcal{A},z)=x\prod_{p\le z}\left( 1-\frac{1}{p}\right) +O\left( 2^{\pi(z)} \right)
\end{equation*}となる。(QED)

Lemma４

$z\ge 2$ に対して
\begin{equation*}
\prod_{p\le z}\left( 1-\frac{1}{p} \right) \ll \frac{1}{\log z} \quad (z\to \infty)
\end{equation*}が成立する。

証明逆数を下から評価する。等比数列の和の公式より
\begin{equation*}
\prod_{p{<}z} \left( 1-\frac{1}{p}\right)^{-1} =\prod_{p{<}z} \left( 1+\frac{1}{p}+\frac{1}{p^2}+\cdots \right)
\end{equation*}
右辺の積を展開して得られる和において、少なくとも $1/n \; (n \le z)$ なる項は全て現れるから
\begin{equation*}
> \sum_{n\le z} \frac{1}{n} \gg \log z \quad (z\to \infty)
\end{equation*}となり*3主張が得られる。(QED)

Theorem5

\begin{equation*}
\pi(x)\ll \frac{x}{\log \log x} \quad (x\to \infty)
\end{equation*}

証明 \eqref{Le2}より
\begin{equation*}
\pi(x) \le S(\mathcal{A},z)+\pi(z)-1 \quad (2\le z <\sqrt{x})
\end{equation*}Prop3、Prop4及び自明な不等式 $\pi(z)\le z$ を用いれば
\begin{equation}
\ll \frac{x}{\log z} +2^z+z \quad (z< \sqrt{x}, z\to \infty) \label{Le4}
\end{equation}が得られる。この不等式において $z=\log x$ と取ると
\begin{equation*}
\pi(x) \ll \frac{x}{\log \log x} +x^{\log 2} + \log x
\end{equation*}したがって $\log 2<1$ に注意すれば所望の評価が得られる。(QED)

Legendreの篩の欠点

Legendreの定式化によってEratosthenesの篩を用いて素数に関する定量的な評価であるTheorem5を得ることができました。しかし一方でTheorem5の評価は実際の素数の個数とくらべて非常に荒い評価になっています。Chebyshevは初等的な方法で
\begin{equation*}
\frac{x}{\log x} \ll \pi(x) \ll \frac{x}{\log x}
\end{equation*}を示していますからLegendreの方法はChebyshevの方法と比較してはるかに劣った評価しか得られないことがわかります。

Legendreの方法において何が問題になっているかを考えてみます。 $\pi(x)$ の評価のために\eqref{Le4}を用いましたが明らかに $2^z$ の項が $\pi(x)$ の評価を邪魔していることがわかります。例えばChebyshvの評価が得たいのなら $z=x^{\varepsilon}$ と取りたいものですがこれでは $2^z$ があまりに大きくなりすぎるため有効な結果が得られません。一方で $z$ が小さすぎると今度は $x/\log z$ の項が大きくなってしまいます。

この邪魔な $2^z$ はそもそも\eqref{Le3}における $\sum_{d|P(z)}1$ から生じています。この和が長すぎるがゆえに $2^{\pi(z)}$ が現れてしまうことで最終的な評価に対する誤差項の影響が大きくなってしまうというわけです。せっかくLegendreの篩という等式が得られているのに、それを単純に用いてしまうと良い評価が得られなくなってしまいます。

先にネタバレですが、この問題点を解決する方法がBrunの篩と呼ばれるものです。簡単に説明するとBrunはLegendreの篩における等式を不等式に置き換えることで、Legendreの篩を用いるよりもはるかに良い結果を生み出すことに成功しました。等式を不等式に置き換えると評価が良くなるというなんとも不思議なことが起こるわけです*4。

Brunの篩についてはいずれ別記事で紹介します。

双子素数の場合

Legendreによる篩の定式化は数列 $\mathcal{A}$ を任意に取ることができるという意味において一般的です。ここでは素数の例を参考にして適切な $\mathcal{A}$ を選択することで $S(\mathcal{A},z)$ が双子素数の個数とつながる様子を計算します。

$n$ が双子素数とは $n$ と $n+2$ の両方が素数になることを言います。素数の場合と同様にEratosthenesの篩を用いれば $\sqrt{x+2} \le z < x$ に対して

$z\; {<}\; n \le x$ が双子素数
$(n,P(z))=1$ かつ $(n+2,P(z))=1$

が同値であることがわかります。ここで $z$ は $n+2$ が素数であるかを判定するために $\sqrt{x+2}\le z$ を満たすようにとる必要があります。最後の条件は明らかに $(n(n+2),P(z))=1$ と同値です。したがって $\pi_2(x)$ を
\begin{align*}
\pi_2(x)=\# \{ p\le x | p:\mathbf{双子素数} \}
\end{align*}とし数列 $\mathcal{A}$ を
\begin{equation*}
\mathcal{A}=\{ n(n+2)| n \le x\}
\end{equation*}と定めれば
\begin{equation*}
\pi_2(x)-\pi_2(z)= S(\mathcal{A},z) \quad (\sqrt{x+2} \le z \;{<} \;x)
\end{equation*}が得られます*5。

一方で $2 \le z <\sqrt{x+2}$ に対しては\eqref{Le2}と同様に
\begin{equation*}
\pi_2(x)-\pi_2(z) \le S(\mathcal{A},z)
\end{equation*}となります。

Prop6

$\mu (d) \neq 0$ なる整数 $d$ に対して
\begin{equation*}
\rho (d)= \# \{ 1\le m \le d| m(m+2)\equiv 0 \;(\mathrm{mod}\; d) \}
\end{equation*}とする。このとき
\begin{equation*}
{|}\mathcal{A}_d|=x\frac{\rho (d)}{d}+R_d
\end{equation*}が成立する。ここで $R_d$ は
\begin{equation*}
{|}R_d|\le \rho (d)\quad (\mu(d)\neq 0)
\end{equation*}を満たす。

証明 $|\mathcal{A}_d|$ の定義より
\begin{align*}
{|}\mathcal{A}_d{|}&=\sum_{\substack{n\le x \\ n(n+2)\equiv 0 \; (\mathrm{mod}\; d)}}1 \\
&=\sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}\sum_{\substack{n \le x\\ n \equiv m \; (\mathrm{mod}\; d)}}1 \\
&= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}\left( \left[ \frac{x-m}{d} \right]+1 \right) \\
&= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}} \left( \frac{x}{d}+r(m) \right)
\end{align*}と書ける。ここで $r(m)$ は
\begin{equation*}
{|}r(m)|=\left| 1- \left\{ \frac{x-m}{d} \right\} -\frac{m}{d} \right| \le 1
\end{equation*}を満たす。従って
\begin{equation*}
R_d= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}r(m)
\end{equation*}とすれば $|R(d)| \le \rho(d)$ であり
\begin{equation*}
{|}\mathcal{A}_d| =x\frac{\rho(d)}{d}+R_d
\end{equation*}が成立する。(QED)

この公式をLegendreの篩に代入すれば双子素数の場合も素数と似たような議論ができそうです。そのためには $\rho$ についての乗法性が必要になります。

Prop7

$\rho(d)$ は乗法的な数論的関数である。

証明 $d_1,d_2$ を互いに素な整数とする。Euclidの互除法より $d_1x_1+d_2x_2=1$ となる整数 $x_1,x_2$ が存在する。 $m_1 ,m_2$ を
\begin{equation}
m_i(m_i+2)\equiv 0 \; (\mathrm{mod}\; d_i ) \quad (i=1,2) \label{Le5}
\end{equation}を満たす整数とし、 $n=m_1d_2x_2+m_2d_1x_1$ と置く。このとき
\begin{equation*}
n\equiv m_i(1-d_ix_i) \equiv m_i \; (\mathrm{mod}\; d_i) \quad (i=1,2)
\end{equation*}であるから\eqref{Le5}より
\begin{equation*}
n(n+2)\equiv 0 \; (\mathrm{mod}\; d_1d_2)
\end{equation*}が成立する。
一方で整数 $n$ が $n(n+2)\equiv 0 \; (\mathrm{mod} \; d_1d_2)$ を満たすなら $m_1=m_2=n$ とすれば\eqref{Le5}が成立する。さらに
\begin{equation*}
m_1d_2x_2+m_2d_1x_1 \equiv n \; ( \mathrm{mod}\; d_1 d_2)
\end{equation*}が成立する。
以上よりそれぞれの法における解が一対一に対応するので
\begin{equation*}
\rho(d_1d_2)=\rho(d_1)\rho(d_2)
\end{equation*}が示された*6。(QED)

Legendreの篩を用いて素数の場合の計算と同じことを双子素数に対して行ってみます。

Theorem8*7

\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log\log x)^2} \quad (x\to \infty)
\end{equation*}

証明 $\rho$ の乗法性と $|R_d|\le \rho(d)$ を用いればLegendreの篩から
\begin{align*}
S(A,z)&= x\sum_{d|P(z)}\frac{\mu(d)\rho(d)}{d}+O\left(\sum_{d|P(z)}\rho(d) \right)
\end{align*}が成立。簡単に $\rho(2)=1, \rho(p)=2 \; (p\neq 2)$ がわかるので
\begin{align*}
\sum_{d|P(z)}\frac{\mu(d)\rho(d)}{d} &=\frac{1}{2} \prod_{3\le p\le z}\left(1-\frac{2}{p}\right) \\
&=\frac{1}{2}\prod_{3\le p \le z} \left(1-\frac{1}{(p-1)^2}\right) \left(1-\frac{1}{p}\right)^2\\
&=2\prod_{3\le p \le z}\left( 1-\frac{1}{(p-1)^2}\right) \prod_{p\le z}\left(1-\frac{1}{p}\right)^2 \\
&\ll \frac{\mathfrak{S}_2}{(\log z)^2}
\end{align*}ここで
\begin{equation*}
\mathfrak{S}_2=2\prod_{p\ge 3} \left(1-\frac{1}{(p-1)^2}\right)
\end{equation*}と置いた*8。さらに
\begin{equation*}
\sum_{d|P(z)}\rho(d)=\prod_{p\le z} (1+\rho(p)) \le 3^{\pi(z)} \le 3^z
\end{equation*}が成立する。したがって
\begin{equation*}
S(A,z) \ll \mathfrak{S}_2\frac{x}{(\log z)^2}+3^{z}
\end{equation*}が得られる。先の議論より
\begin{equation*}
\pi_2(x) \le S(A,z)+\pi_2(z) \ll \frac{x}{(\log x)^2}+3^{z}+z
\end{equation*}が成立するので $z=(\log x)/(\log 9)$ とすれば所望の評価が得られる。(QED)

以上で篩を用いて双子素数の評価ができました。しかしヒューリスティックには $p+2$ が素数である確率は $1/\log x$ であるため
\begin{equation*}
\pi_2(x) \sim \frac{\pi(x)}{\log x} \ll \frac{x}{(\log x)^2}
\end{equation*}であると期待できます。さらに、証明をすることはできないものの上述の証明において
\begin{equation*}
\mathfrak{S}_2\frac{x}{(\log z)^2}
\end{equation*}の項が $S(\mathcal{A},z)$ の大きさを支配していると期待できます。実際次のような予想があります。

Hardy-Lettlewood予想

\begin{equation*}
\pi_2(x)\sim \mathfrak{S}_2\frac{x}{(\log x)^2}\quad (x\to \infty)
\end{equation*}

Hardy-Littlewood予想(と素数定理)によると双子素数の素数に対する相対漸近密度は0である*9、つまり
\begin{equation*}
\frac{\pi_2(x)}{\pi(x)}\sim \frac{\mathfrak{S}_2}{\log x} =o(1) \quad (x\to \infty)
\end{equation*}が得られますがTheorem8からはこれを導出することはできません。

Theorem8の評価はHardy-Littlewood予想と比較してはるかに弱いものですが、それでもLegendreの篩を発展させれば双子素数を数えることができるという可能性を見出すには十分な結果だと思います。

コメントとして上述の $\mathfrak{S}_2$ は双子素数に対する特異級数と呼ばれる定数です。特異級数は問題設定によって取り換えられますが、いずれも素数分布の理論においてそれ単体が研究対象になる重要な定数です。この後Goldbach予想についても議論しますが、そこでもGoldbach予想に関する特異級数が現れます。

Goldbach予想の場合

つぎに $\mathcal{A}$ を取り換えることでGoldbach予想についても篩を用いることができることを紹介します。Goldbach予想とは4以上の任意の偶数 $N$ を
\begin{equation*}
N=p+p'
\end{equation*}と二つの素数の和で表すことができるかという問題です。

原理的には $1\le n \le N$ に対して

$n$ と $N-n$ がどちらも素数
となることを確かめれば $N$ を二つの素数の和に分解できることかどうかがわかります。従ってこの場合に篩にかける数列は
\begin{align*}
\mathcal{A}=\mathcal{A}(N)=\{ n(N-n)| 1\le n\le N\}
\end{align*}と定めます。

Prop9

$\mu(d)\neq 0$ なる整数 $d$ に対して乗法的関数 $\rho(d)$ を
\begin{equation*}
\rho(d)=\rho_N(d)=\# \{ 1\le m \le d| m(N-m) \equiv 0 \; (\mathrm{mod}\; d)\}
\end{equation*}とする。このとき
\begin{equation*}
{|}\mathcal{A}_d|=N\frac{\rho(d)}{d}+R_d
\end{equation*}が成立する。ここで $R_d$ は
\begin{equation*}
{|}R_d|\le \rho (d) \quad (\mu (d)\neq 0)
\end{equation*}を満たす。

証明 Prop6 及びProp7と同様に示される。(QED)

Eratosthenesの篩を用いて $n$ と $N-n$ が素数か判定する場合、 $n,N-n >\sqrt{N}$ である、つまり $\sqrt{N} < n < N-\sqrt{N}$ であるような $n$ に対して

$n,N-n$ はどちらも素数
$(n(N-n),P(\sqrt{N}))=1$

が同値です。さらにパラメータ $z$ を $\sqrt{N} \le z < N/2$ を満たすようにとれば $z < n < N-z$ に対して

$n,N-n$ がどちらも素数
$(n(N-n),P(z))=1$

が同値になります。つまり
\begin{equation*}
S(\mathcal{A},z)=\# \{(p,p')| N=p+p' , p,p' > z\}+O(1)
\end{equation*}です*10。ここで最後の $O(1)$ は $n=1$ もしくは $n=N-1$ のときに $(n(N-n),P(z))=1$ となる可能性分の誤差です。

したがって $G(N)$ を
\begin{equation*}
G(N)=\# \{ (p,p')| N=p+p'\}
\end{equation*}と定めれば
\begin{align*}
G(N)&=S(A,z)+O(1)+\# \{ (p,p')| N=p+p',p\; \mathrm{or} \; p' \le z\} \\
\\
&=S(\mathcal{A},z)+O(z) \quad (\sqrt{N}\le z < N/2)
\end{align*}が成立します。

$z\le \sqrt{N}$ のときは\eqref{Le2}と同様に
\begin{align*}
S(\mathcal{A},z)=\sum_{\substack{z\le n \le N-z \\ (n(N-n),P(z))=1}}1+O(1) \ge G(N)-O(z)
\end{align*}となります。したがって
\begin{equation}
G(N) \le S(\mathcal{A},z) +O(z) \quad (2\le z < N/2) \label{Le6}
\end{equation}を得ることができます。

以下Legendreの篩を用いて $S(\mathcal{A},z)$ を評価しますが、計算の大略はTheorem8とほとんど同じなのでGoldbach予想に関する特異級数の導出のみ確かめていきます。

Theorem10

\begin{equation*}
G(N) \ll \mathfrak{S}(N) \frac{N}{(\log \log N)^2} \quad (2|N\ge 4)
\end{equation*}ここで
\begin{equation*}
\mathfrak{S}(N)=2\left(\prod_{\substack{p\ge 3 \\ p|N}} \frac{p-1}{p-2} \right)\prod_{p\ge 3} \left( 1-\frac{1}{(p-1)^2} \right)
\end{equation*}

証明素数 $p$ に対して
\begin{equation*}
m(N-m)\equiv 0 \; (\mathrm{mod}\; p) \Leftrightarrow m\equiv 0 \; \mathrm{or} \; N-m \equiv 0
\end{equation*}なので $p|N$ なら $\rho (p)=1$ でそうでないなら $\rho (p)=2$ となる。したがってLegendreの篩を用いるときに現れる素数積は
\begin{align*}
\prod_{p\le z} \left(1-\frac{\rho(p)}{p} \right)&= \frac{1}{2} \prod_{\substack{3\le p \le z \\ p|N}}\left(1-\frac{1}{p}\right) \prod_{\substack{3\le p\le z \\ p\nmid N}}\left( 1-\frac{2}{p}\right)\\
&= \frac{1}{2}\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{2}{p}\right) \\
&=\frac{1}{2}\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{1}{p-1)^2}\right) \\
&\quad \times \prod_{3\le p \le z}\left(1-\frac{1}{p}\right)^2\\
&=2\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{1}{(p-1)^2}\right) \\
&\quad \times \prod_{p \le z}\left(1-\frac{1}{p}\right)^2
\end{align*}したがって
\begin{align*}
\prod_{p\le z} \left(1-\frac{\rho(p)}{p} \right) \ll \frac{\mathfrak{S}(N)}{(\log z)^2}
\end{align*}が成立する。残りの議論はTheorem8と同様に済む。(QED)

Goldbach予想は偶数が二つの素数の和で書けるかという予想ですが、より強く $G(N)$ の漸近式が予想されています。

Hardy-Lettlewood予想

\begin{equation*}
G(N)\sim \mathfrak{S}(N)\frac{N}{(\log N)^2} \quad (2|N, N\to \infty)
\end{equation*}

篩法とはなにか

ここまで素数、双子素数、Goldbach予想について計算してきましたが、総じて次のような問題に集約されます。

篩法の問題設定

$\mathcal{A}$ を整数列とし $\mathcal{A}_d=\{ a\in \mathcal{A}| a\equiv 0 \; (\mathrm{mod}\; d)\}$ とする。さらにある $X>0$ と乗法的関数 $\rho (d)$ と $|R_d| \le \rho(d)$ を満たす関数 $R_d$ に対して
\begin{equation*}
{|} \mathcal{A}_d|=\frac{\rho(d)}{d} X+R_d \quad (\mu(d) \neq 0)
\end{equation*}が成立していると仮定する。このとき
\begin{equation*}
S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A}\\ (a,P(z))=1}}1=\sum_{d|P(z)}\mu(d)|\mathcal{A}_d|
\end{equation*}の良い評価を得よ。

これが最も基本的な問題設定であり、この問題に取り組む過程で篩法は一大理論として発展していきました。現状では篩法は双子素数予想などに有効なほとんど唯一の方法として存在感を高めており、さらには素数への応用だけでなくゼータ関数の理論などにも応用されています。

おわりに

いかがでしたか。もしかすると篩法に興味がわいてきたのではないでしょうか...!
篩法のBrunによる発展はごく初等的な計算のみによるもので大学一年生程度の知識があれば概ね理解可能です。それにもかかわらず篩法の発見はRiemann zeta関数による素数定理の証明より20年以上後のことであることも面白い点だと思います。もしかすると数学にはまだまだ人類の知らない簡単かつ強力な理論が隠されているのかもしれないと思うとわくわくしますね!

*1: $\mathcal{A}$ を篩にかけるとはすなわち $S(\mathcal{A},z)$ を考察することである。その意味で $S$ を $\mathcal{A}$ を引数に持つSieving function(直訳は篩関数)などと呼ぶことがある。