全脳科学帳

これを好む者はこれを楽しむ者に如かず

素数が無限に存在することの証明 (6) 〜 素数の逆数和 その1 〜

6つ目の証明は、ポール・エルデシュによるもの。生涯に約1500本もの論文を発表したことや、それらの多くが共著だったことで知られる人。この証明では、素数の逆数の和が無限大に発散することを示す。素数が有限個しか存在しないなら逆数の和は有限の値になるはずであるから、逆数の和が発散することを示せれば素数が無限に存在することが言える。

素数の逆数の和が無限大に発散することを初めて証明したのはオイラーらしいのだが、後にエルデシュが以下のような初等的な証明を与えた。

証明
背理法で証明する。素数の逆数和が有限の数  \alpha に収束する、つまり

 \displaystyle \sum_{i=1}^\infty \frac{1}{p_i} = \alpha

と仮定する(ただし  p_i i 番目の素数。素数が有限の  L 個しか存在しない場合には、  i \gt L については  \displaystyle \frac{1}{p_i} = 0 とみなす)。

極限の定義より、上式は、任意の  \varepsilon \gt 0 に対して自然数  M が存在して

 \displaystyle n \ge M ならば  \displaystyle \Biggl | \sum_{i=1}^n \frac{1}{p_i} - \alpha \Biggr | \lt \varepsilon

となることを意味する。ここで  \displaystyle \varepsilon = \frac{1}{2} とおき、総和の部分が単調増加であることを考え合わせると、自然数  M が存在して

 \displaystyle n \ge M ならば  \displaystyle 0 \le \alpha - \sum_{i=1}^n \frac{1}{p_i} \lt \frac{1}{2}

である。したがって、この  M に対して

 \displaystyle \alpha - \sum_{i=1}^M \frac{1}{p_i} =\sum_{i=M+1}^\infty \frac{1}{p_i} \lt \frac{1}{2} \quad (*1)

となる。

自然数  N 以下の自然数のうち

 \displaystyle p_{M+1}, p_{M+2}, \ldots のいずれかで割り切れる自然数の個数を  N_1
 \displaystyle p_{M+1}, p_{M+2}, \ldots のいずれでも割り切れない自然数( p_1, \ldots, p_M のいずれかでのみ割り切れる自然数と1)の個数を  N_2

とする。このとき  N = N_1 + N_2 である。  N 以下の  p の倍数の個数は、床関数(その数を越えない最大の整数)を用いて  \displaystyle \Bigl\lfloor \frac{N}{p} \Bigr\rfloor と表せるから、

 \displaystyle N_1 \le \sum_{i=M+1}^\infty \Bigl\lfloor \frac{N}{p_i} \Bigr\rfloor \le\sum_{i=M+1}^\infty \frac{N}{p_i} \lt \frac{N}{2}   (最後の不等号には(*1)を使った)

次に、 p_{M+1}, p_{M+2}, \ldots のいずれでも割り切れない N 以下の自然数  n をとり、 n = uv^2 と自然数の積で表す。ただし  u は平方因数を持たないものとする。このとき、 u p_1, \ldots, p_M のたかだか1個ずつの積であるから、 u のとりうる値はたかだか  2^M 通りである。また  v^2 \le n \le N であるから  v \le \sqrt{N}。したがって  n がとりうる値の個数  N_2 について  \displaystyle N_2 \le 2^M \sqrt{N}となる。

以上より、

 \displaystyle N = N_1 + N_2 \lt \frac{N}{2} + 2^M \sqrt{N}

となる。

ところが、 N 2^{2M+2} を代入すると

 \displaystyle 2^{2M+2} \lt \frac{2^{2M+2}}{2} + 2^M \sqrt{2^{2M+2}} =2^{2M+2}

となって矛盾する。 よって、素数の逆数和が収束するという仮定が誤りであり、素数の逆数和は正の無限大に発散する。したがって素数は無限に存在する。(証明終)

素数の逆数和は発散するのだが、その増加は非常に遅い。現在計算されているところまででまだ4ぐらいがせいいっぱいらしい。調和級数がだいたい  \log n (自然対数)のオーダーで、これでも相当に遅いが、素数の逆数和は  \log (\log n) のオーダーとのこと。実際、 \displaystyle \lim_{n \to \infty} (\sum_{p \le n} \frac{1}{p_i} - \log (\log n)) は収束し、その値( =0.26149721\ldots)はMeissel–Mertens定数と呼ばれる。 計算してみると、 \log (\log n) が4になるのは  n が10進数で24桁の数のときであり、5になるのは65桁の数のときである。10になるには9566桁の数にまで  n を大きくしないといけない。

さて、上記の証明を背理法を使わずに書くにはどうすればよいか? 証明の道筋を逆にたどれば何とかなりそうである。

証明
 M を自然数とし、 N = 2^{2M+2} とする。 N 以内の自然数のうち、

 \displaystyle p_{M+1}, p_{M+2}, \ldots のいずれかで割り切れる自然数の個数を  N_1
 \displaystyle p_{M+1}, p_{M+2}, \ldots のいずれでも割り切れない自然数( p_1, \ldots, p_M のいずれかでのみ割り切れる自然数と1)の個数を  N_2

とする。このとき  N = N_1 + N_2 である。

次に、 p_{M+1}, p_{M+2}, \ldots のいずれでも割り切れない  N 以下の自然数  n をとり、 n = uv^2 と自然数の積で表す。ただし  u は平方因数を持たないものとする。このとき、 u p_1, \ldots, p_M のたかだか1個ずつの積であるから、 u のとりうる値はたかだか  2^M 通りである。また  v^2 \le n \le N であるから  v \le \sqrt{N}。したがって  n がとりうる値の個数  N_2 について

 \displaystyle N_2 \le 2^M \sqrt{N} = 2^M \cdot 2^{M+1} = 2^{2M+1} = \frac{N}{2}

 \displaystyle \therefore N_1 = N - N_2 \ge \frac{N}{2}

一方、 N 以下の  p の倍数の個数が床関数を用いて  \displaystyle \Bigl\lfloor \frac{N}{p} \Bigr\rfloor と表せることから、

 \displaystyle N_1 \le \sum_{i=M+1}^\infty \Bigl\lfloor \frac{N}{p_i} \Bigr\rfloor \le\sum_{i=M+1}^\infty \frac{N}{p_i}

これらから、 M によらず常に

 \displaystyle \sum_{i=M+1}^\infty \frac{N}{p_i} \ge\frac{N}{2} つまり  \displaystyle \sum_{i=M+1}^\infty \frac{1}{p^i} \ge \frac{1}{2} \quad (*2)

が成り立つ。

素数の逆数和が収束値  \alpha を持つためには

 \displaystyle n \ge M ならば  \displaystyle 0 \le \alpha - \sum_{i=1}^n \frac{1}{p_i} \lt \frac{1}{2}

となる  M が存在することが必要であり、このためには

 \displaystyle \sum_{i=1}^\infty \frac{1}{p_i} - \sum_{i=1}^M \frac{1}{p_i} = \sum_{i=M+1}^\infty \frac{1}{p_i} \lt \frac{1}{2}

となるような  M が存在しなければならないが、(*2)よりそのような  M をとることはできない。これは素数の逆数和が収束しないことを意味する。(証明終)

背理法とどう違うのかと言われると微妙だが、とにもかくにも「ウソを仮定→矛盾」という論法は避けられた。