ガウスの素数定理 - tsujimotterのノートブック

ガウスの素数定理とは、ある数が素数である確率についての定理です。その定理は、自然対数を使って次のように表せます。

ガウスの素数定理：
十分大きな整数 $x$ が素数である確率 $p(x)$ は次のように近似できる。

$\displaystyle p(x) \sim \frac{1}{\log(x)}$

今回の記事では、この素数定理とその証明の概略を解説したいと思います。

素数定理のイメージとしては、素数サイコロをイメージすればよいでしょう。自然対数はそのサイコロの面の数を表しているのです。

f:id:tsujimotter:20140408114502p:plain:w360

図：12分の1で素数(p) が出るサイコロ

たとえば、 $x=100000$ のときには、その自然対数 $\log(100000)$ はおよそ $11.5$ となりますから、ほぼ12と考えて、正12面体の１面に「素数」と書かれているサイコロを振っているのと同じです。

下の表は、素数定理で予想されるサイコロの面の数 ( $\log(x)$ ) をまとめたものです。

f:id:tsujimotter:20140408111807p:plain:w400

適当に数を選んだときに 100付近であれば4.6個に1個は素数で、1000付近であれば6.9個に1個は素数なのですね。

素数定理の数値的な評価

もちろん、ある数 $x$ が素数であるかどうかは、最初から決まっていて、確率で決まるようなものではありません。

一方で、たとえば「1から100000までのざっくりとした素数の個数がしりたい」といったときに、一個ずつ素数かどうか判定していたら大変ですよね。多少間違ってもよければ、確率を使って統計的に考えても十分かもしれません。

$x$ 以下の素数の個数 $\pi(x)$ を近似的に求める公式は、上記の確率 $p(x)$ を使って次のように近似できるでしょう。

$\displaystyle \pi(x)\sim p(2) + p(3) + p(4) + p(5) + \cdots = \sum_{n=2}^{x} p(n)$

もうちょっと正確に計算するなら、積分を使って次のようにしたらよいでしょう。

$\displaystyle \pi(x)\sim \int_{2}^{x} p(t) {\rm d}t$

この右辺は、対数積分と呼ばれていて、素数の個数関数 $\pi(x)$ の良い近似となっています。

対数積分：

$\displaystyle {\rm li}(x) = \int_{2}^{x} \frac{{\rm d}t}{\log(t)}$

実際に、素数の個数と対数積分を比べてみましょう。

図：素数の個数関数 $\pi(x)$ （赤線）と対数積分 ${\rm li}(x)$ （緑線）

多少ずれはありますが、大雑把にいえば近似できているとみてよいでしょう。

また、このずれの比率は、 $x$ が大きくなるにつれて無視できるほど小さくなることが知られています。

素数定理とゼータ関数

ところで、ガウスの素数定理はどのように証明されたのでしょうか。
「ガウスの～」と言っていますが、ガウス自身は予想しただけで証明はしていません。

この定理は、ド・ラ・ヴァレ・プーサンとジャック・アダマールという二人の数学者によって独立に証明されました。証明が完結したの 1896 年ですから、ガウスが予想した 1792 年から実に 100年近く未解決問題だったわけです。

Wikipediaの「素数定理」によると、

終的には1896年にド・ラ・ヴァレー・プーサンとジャック・アダマールがそれぞれ独立に証明した。当初与えられた証明はゼータ関数と複素関数論を用いる高度なものであった

とあります。

そう、ゼータ関数です。

$\displaystyle \zeta(s)=\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\cdots$

今回の素数定理がゼータ関数とどのように関係があるのでしょう。

私はその点に興味を持ちました。

調べてみたところ、素数定理の厳密は証明は、そう簡単ではないようです。

そこで今回は、あくまで直感的な議論に基づいて、「ゼータ関数と素数定理が関係する仕組み」を「証明」と称して議論したいと思います。この流れを読んでいけば「素数である確率が自然対数で表せる」という事実が、（感覚的ではありますが）イメージできるようになるかと思います。

もちろん、厳密な証明ではまったくありませんので、近似の仕方はかなりいい加減で、多分に論理の飛躍を含んでいるかと思います。その点はご了承ください。

証明の流れ

ざっくり流れを述べると次のようになります。

素数の確率 $p(x)$ を式で表現する
この式をゼータ関数 $\zeta(1)$ のオイラー積（の部分積）で表す
オイラー積（の部分積）を展開すると調和数 $H(x)$ になる
調和数は自然対数で近似できる。よって $p(x)$ が自然対数で近似できる

以下、1. から順に示していきましょう。

1. 素数の確率

ある数 $x$ が素数であるということは、次のように定義されます。

素数は、1 と自分自身でしか割り切れない数のことである。

言い換えると次のようになります。

素数は、自分自身より小さいすべての素数の倍数にならない数のことである。

これをそのまま利用しましょう。

ある数 $x$ と $x$ より小さいすべての素数を用意します。

$2$ , $3$ , $5$ , $7$ , $11$ , ..., $p_x$
ここで $p_x$ は $x$ より小さい最大の素数。

$x$ が素数である確率を $p(x)$ とし、これを近似する式を作ります。

ある数 $x$ が素数である確率を求めたいわけですから「上記の素数すべての倍数にならない確率」を求めればよいでしょう。

$x$ が 2の倍数である確率は、 $\frac{1}{2}$ です。
逆に、2の倍数でない確率は $\left(1-\frac{1}{2}\right)$ となります。

次に $x$ が 2の倍数でなく、 3の倍数である確率は $\left(1-\frac{1}{2}\right)\frac{1}{3}$ 。
2の倍数でなく、 3の倍数でもない確率は $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)$ となります。

同様に、 $2$ , $3$ , $5$ , $7$ , $11$ , ..., $p_x$ のすべての倍数でない確率は、次のようになります。

$\displaystyle \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\cdots\left(1-\frac{1}{p_x}\right)$

これは、 $x$ が素数である確率に他ならないから、

$\displaystyle p(x) = \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\cdots\left(1-\frac{1}{p_x}\right)$

と求める確率が得られました。

2. ゼータ関数のオイラー積

先ほどの式を次のように変形します。

$\displaystyle \begin{eqnarray} p(x) &=& \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\cdots\left(1-\frac{1}{p_x}\right) \\ &=& \frac{1}{ \left(1-1/2\right)^{-1} \left(1-1/3\right)^{-1} \left(1-1/5\right)^{-1} \left(1-1/7\right)^{-1} \cdots \left(1-1/p_x\right)^{-1} } \end{eqnarray}$

ここで右辺の分母は、

$\displaystyle \zeta(s) = \left(\frac{1}{1-1/2^s}\right)\left(\frac{1}{1-1/3^s}\right)\left(\frac{1}{1-1/5^s}\right)\left(\frac{1}{1-1/7^s}\right)\cdots$

というゼータ関数のオイラー積に似ていますね。素数 $p_x$ で打ち切って、 $s=1$ とすればぴったり一致します。

参考：ゼータ関数のオイラー積 - tsujimotterのノートブック

3. 調和級数

ゼータ関数 $\zeta(s)$ なのですが、オイラー積を展開していくと次のようになりますね。

$\displaystyle \zeta(s) = \frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\cdots$

ここで $s=1$ とした式、すなわち、

$\displaystyle \zeta(s) = \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots$

は発散する級数として知られています。これには名前もついていて調和級数といいます。

調和級数の部分和も考えることが出来て、これを調和数 $H(x)$ といいます。

$\displaystyle H(x) = \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{x}$

ここが今回最も飛躍があるポイントです。
この調和数 $H(x)$ と先ほどのオイラー積の部分積が、十分大きい $x$ に対しては一致すると考えるのです。

つまり、十分大きな $x$ に対して、

$\displaystyle \frac{1}{ \left(1-1/2\right)^{-1} \left(1-1/3\right)^{-1} \left(1-1/5\right)^{-1} \left(1-1/7\right)^{-1} \cdots\left(1-1/p_x\right)^{-1} } \sim \frac{1}{H(x)}$

たしかに、 $x\rightarrow \infty$ においては、上式は一致します。

4. 自然対数への近似

さて、最後の仕上げです。

調和数は、これまた十分大きな $x$ に対して次のように近似できることが知られています。

$\displaystyle H(x)\sim \log(x)$

調和級数は、収束が非常に遅いことで有名ですが、この式は、その収束スピードが $\log$ 程度のオーダーだということを表しています。

これで材料は出揃いました。

$\displaystyle \begin{eqnarray} p(x) &\sim& \frac{1}{ \left(1-1/2\right)^{-1} \left(1-1/3\right)^{-1} \left(1-1/5\right)^{-1} \left(1-1/7\right)^{-1} \cdots\left(1-1/p_x\right)^{-1} } \\ &\sim& \frac{1}{ H(x) } \\ &\sim& \frac{1}{ \log(x) } \end{eqnarray}$