Eratosthenesの篩(ふるい)と篩法

素数分布論における手法である篩法*1に関する入門記事です。本記事では篩法の原点であるEratostheneの篩と双子素数やGoldbach予想との関連を簡単に紹介します。

素数に関する諸問題
篩法で何がわかるのか
Eratosthenesの篩
おわりに
参考文献

素数に関する諸問題

解析的な素数分布論におけるもっとも基本的な問題は素数の個数を問う問題です。つまり $x$ 以下の素数の個数 $\pi (x)$ について調べよという問題です。この問題とRiemann zeta関数 $\zeta(s)$ との関係は非常に有名で $\zeta(s)$ の零点分布についての考察することで素数定理
\begin{equation*}
\pi(x)\sim \frac{x}{\log x} \quad (x\to \infty)
\end{equation*}を示すことができます。素数定理を代表されるように $\zeta(s)$ の性質は様々な素数の性質を導きます。

つづいて素数に関する有名な二つの未解決問題を紹介します。

双子素数予想

素数 $p$ で $p+2$ も素数であるようなものが無限に存在する。

Goldbach予想

4以上の全ての偶数は二つの素数の和で書ける。

これらの問題は100年以上考察されていますが未解決のままです。その主な理由としてRiemann zeta関数を用いた議論だけではこの問題に一切アプローチができないことが挙げられます。残念なことに双子素数の性質を記述する"ゼータ関数"は今のところ発見されていません。

この状況を打開するために開発された方法が篩法です。篩法の特徴的な点として

双子素数予想やGoldbach予想にアプローチするほとんど唯一の方法である
ほとんどの議論が初等的な計算のみで構成される
Riemann zeta関数の理論と合わせることで非常に強力な結果が得られる

などが挙げられます。ここで初等的な計算というのは概ね大学1年生の解析学程度の知識があればできる計算のことです。

篩法で何がわかるのか

篩法はEratosthenesの篩のLegendreによる定式化をViggo Brunが応用したことから始まりました。まずは篩法を用いるとどんな定理が証明できるのか？について適当な代表例を紹介します。

Thm A (V. Brun, 1919)

$\pi_2(x)$ を素数 $p\le x$ のうち $p+2$ もまた素数であるようなもの( $x$ 以下の双子素数)の個数とする。このとき
\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log x)^2} \quad (x\to \infty)
\end{equation*}が成立する。特に双子素数の逆数和は収束する。

Thm B (J. Chen, 1973)

十分大きな任意の偶数 $n$ に対し素数 $p$ と高々二つの素数の積である数 $q$ が存在して
\begin{equation*}
n=p+q
\end{equation*}が成立。

Thm C (J. Maynard, 2015)

$\{p_n\}_{n\ge 1}$ で昇順に並べた素数全体の列とする。このとき\begin{equation*}
\liminf_{n\to \infty} (p_{n+1}-p_n) \le 600
\end{equation*}が成立する。

Thm Aは双子素数予想に関連する命題でVigoo Brun(1919)によって証明されました。篩法における最初の結果で、これを皮切りに篩法の理論が構築されていくことになります。
Thm BはGoldbach予想に関連する問題で、 $q$ の素因子をあと一つ減らせばGoldbach予想が解決するというところまで迫った結果です。
Thm Cも双子素数予想に関連する問題です。双子素数予想は
\begin{equation*}
\liminf_{n\to \infty} (p_{n+1}-p_n)=2
\end{equation*}と同値であることが容易にわかります。双子素数予想より弱い主張である
\begin{equation*}
\liminf_{n\to \infty}(p_{n+1}-p_n)< \infty
\end{equation*}はBounded gap conjectureと呼ばれ長い間関心を集めていました。Bounded gap conjecture自体はMaynardのThm Cより早くY. Zhang(2013)において解決されていましたが、MaynardによるThm Cの証明が非常に簡単なためこちらの方が有名な気がします。

プライムスでも双子素数予想やGoldbach予想を題材に幾つかの記事に分けて篩法を学習し、上述の定理の証明を目標にして執筆していきます。

Eratosthenesの篩

篩法の原点はEratosthenesの篩にあります。ここではEratosthenesの篩を紹介し、それがどのように双子素数予想やGoldbach予想に関連するのかを考えます。

Thm (Eratosthenesの篩)

$n$ を自然数とする。このとき次の二つは同値。
(i) $n$ は素数
(ii) $n$ は $\sqrt{n}$ 以下の素因子を持たない

証明 $n$ が $\sqrt{n}$ 以下の素数で割り切れるなら明らかに $n$ は素数ではない。したがって(i) $\Rightarrow$ (ii)が成立。一方で $n$ が合成数なら $n$ を割り切る二つの素数 $p_1, p_2$ が存在する。もし $p_1, p_2 > \sqrt{n}$ なら $p_1p_2 >n$ となり矛盾する。したがって少なくとも片方の素数は $\sqrt{n}$ 以下でなければならない。つまり(ii) $\Rightarrow$ (i)が成立。 (QED)

定義から $n$ が素数であるかを判定するためには $n$ 以下の素数で割り算を実行する必要がありますが、Eratosthenesの篩によって $\sqrt{n}$ 以下の素数のみ確かめれば良いことがわかりました。実際に与えられたEratosthenesの篩を用いて与えられた数表から素数を見つけてみます。

このような操作によって数表から素数をふるいだしたことのある方は多いと思います。
今度は少々工夫してEratosthenesの篩によって双子素数を見つけ出したいと思います。

このような数表を用意してEratosthenesの篩にかけることで双子素数も見つけ出すことができます。
さらに工夫して今度はGoldbach予想について考えてみます。偶数 $N$ に対して
\begin{equation*}
G(N)=\# \{(p,p')| p,p':\mathbf{素数}, N=p+p'\}
\end{equation*}と定めます。Eratosthenesの篩を用いることで機械的に $G(N)$ の値を求めることができます。具体的に $G(30)$ を計算してみます。