素数の数は有限？無限？自分なりに調べてみました！

こんにちは！

This is a penです！

突然ですが、皆さんは素数を数えたことってありますか？

f:id:tanpe_kanpinuyep_ne:20200131213734p:plain

「ジョジョの奇妙な冒険第６部」では、エンリコ・プッチ神父が落ち着くために素数を数えていましたね！

dic.pixiv.net

もしも、素数の数が有限だったらどうでしょうか？

そうしたら、そのうち全ての素数を数え終わってしまいます！

これでは、落ち着くことができません！

f:id:tanpe_kanpinuyep_ne:20200131214819p:plain

どうしよう･･････

とても困りますね！

今回は、素数が有限か無限か調べてみたので、その結果を書いてみたいと思います。

１．そもそも素数って？
２．素数の数は有限？無限？
３．素数の数は無限？
４．証明を切り貼りしてみました！
５．まとめ
６．参考にしたもの

１．そもそも素数って？

f:id:tanpe_kanpinuyep_ne:20200131215437p:plain

そもそも、素数って何でしょうか？

Wikipediaを見てみると、

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。

（素数 - Wikipedia）

のだそうです！

1と自分自身でしか割り切れないって何だかすごいですね！

２．素数の数は有限？無限？

さらに調べてみると、素数の数については、色々な人が論文を書いていることが分かりました！

ja.wikipedia.org

Εὐκλείδηςさんは紀元前3世紀の人で、Saidakさんの証明は2006年のものです。

よく見ると、Εὐκλείδηςさんのδηςって、「デース」ですね！

こんなに長い間熱い議論が交わされているということは、素数の数が有限か無限かは、とても難しい問題であると言えるかもしれませんね！

f:id:tanpe_kanpinuyep_ne:20200131220919p:plain

３．素数の数は無限？

なかでも、とても興味深いことを言っている人がいました！

その名もWoodsさん！

数学や計算機科学を研究している方のようです！

これは期待が持てますね！

このWoodsさんが言うには、

無限に多くの素数が存在する

のだそうです！

今までの論争に終止符を打つカッコイイ発言ですね！

今回は、Woodsさんの1981年の論文"Some problems in logic and number theory, and their connections"を元にして、その根拠を探ってみましょう！

４．証明を切り貼りしてみました！

ここでは、原論文のChapter 1 §3の証明･･･

･･･がちょっとよく分からなかったので、適当に切り貼りしてみました！

真偽については保証しません（笑）

Woodsさんは、一体なぜ素数が無限にあると思ったのでしょうか？

Woodsさんは、Chapter 1 §3で次の定理を証明しているようです。

$1 ≦ x ≦ y$ となるような $x, y$ について、

$y+1, y+2, y+3, ..., y+i, ..., y+x$

の中には、 $x ＜ p$ となる素因数を持つものが存在する。

Chapter 1 §3 では $x^5 ≦ y$ の場合を証明していますが、論文の後ろのほうでは一般的な場合で成立させているようです！

よく分かりません！！

今回は、Chapter 1 §3 を自分なりにまとめてみました！なので、 $x ≪ y$ の場合だけを考えます！！

さて、もしも、世界に素数が有限個しかなかったとしてみましょう。

このとき、素数を順番に数えていった、一番後ろの素数が最大の素数 $p_{max}$ ということになります。

それに対して、 $p_{max} ≦ n ≪ m$ となるような $n$ と $m$ を持ってきましょう！！！

$p_{max}$ が最大の素数なので、

$m + 1, m + 2, m + 3, ..., m + i, ..., m + n$

の素因数分解の中には、 $p_{max}$ までの素数しか現れないはずです！！！

さっきと言っていることが違う？

否定の導入です！！！

では、素因数分解をしてみましょう！！！

ja.wikipedia.org

総乗記号を使って、

$x = \prod_{j=1} ^ {v(x)} p_j ^ {e_j}$

と書くことにしましょう！

※ $v(x)$ は、 $x$ を割り切れる素数の数とします！！！

上記の $m + 1, m + 2, m + 3, ..., m + i, ..., m + n$ を素因数分解したものは、

$m + 1 = \prod_{j=1} ^ {v(m+1)} p_{1j} ^ {e_1j}$

$m + 2 = \prod_{j=1} ^ {v(m+2)} p_{2j} ^ {e_2j}$

$m + 3 = \prod_{j=1} ^ {v(m+3)} p_{3j} ^ {e_3j}$

...

$m + i = \prod_{j=1} ^ {v(m+i)} p_{ij} ^ {e_ij}$

...

$m + n = \prod_{j=1} ^ {v(m+n)} p_{nj} ^ {e_nj}$

と書けますね！！！

だからどうした！

と思いますね！！！！

このとき、各数について、

$e_{11} (log(p_{11}) + 1) + e_{12} (log(p_{12}) + 1) +e_{13} (log(p_{13}) + 1) +e_{14} (log(p_{14}) + 1)...$

のようなものを考えてみましょう！

ってWoodsさんが言っていました！！

と思います！！！

言ってないような気もします！！！

ちなみに、単に $log$ と書いていますが、

実際には

$log_2$ の整数部分

を表しています！！！

嘘ついてごめんなさい！！！

これって、実は

2進数表示したときの桁数 $-1$

と同じだったりします！！！

何度も $e_{??} (log(p_{??}) + 1)$ と書くのはアレなので、 $a_{??}$ と書きましょう！！

何事もエコです！

ja.wikipedia.org

Woodsさんは、各数の和の算出をするときに、上限を設けています！

エコですね！

上限を $log (m)$ として、それを超える部分は計算打ち切りとします！！！！

ということは

そのときの最後の1項を $h_i$ 番目として

$e_{ih_i} (log(p_{ih_i}) + 1)$

とすると、

$h_i ≦ v(i)$

$a_{ih_i} ≦ e_{ih_i} (log(p_{ih_i}) + 1)$

となっています！

ちょっと小さいと言うことですね！

ということで、シグマ

ja.wikipedia.org

を使って、

$\sum_{j=1}^{h_1} a_{1j} ( = log(m))$

$\sum_{j=1}^{h_2} a_{2j} ( = log(m))$

$\sum_{j=1}^{h_3} a_{3j} ( = log(m))$

...

$\sum_{j=1}^{h_i} a_{ij} ( = log(m))$

...

$\sum_{j=1}^{h_n} a_{nj} ( = log(m))$

と書けるということですね！！！

これを全部足したものを $S_a$ としましょう！！！

エコですね！

つまり、

$S_a = \sum_{i=1}^n \sum_{j=1} ^ {h_i} a_{ij} = n log(m)$

です！！！よく分かりませんね！！！

同じように、

$1, 2, 3, ..., k, ..., n$ も素因数分解をして、 $log$ を取って、足すという操作を考えてみてください。

なんで？って･･･？

なんででしょう！！！

不思議ですね！！！

ただし、今回は和の上限は設けません！

どうしたんでしょうか？

とにかく

$\sum_{s=1}^{v(1)} a_{1s} ( = 0 + 1 = 1)$

$\sum_{s=1}^{v(2)} a_{2s} ( = 1 + 1 = 2)$

$\sum_{s=1}^{v(3)} a_{3s} ( = 1 + 1 = 2)$

$\sum_{s=1}^{v(4)} a_{4s} ( = 2×(1 + 1) = 4)$

...

$\sum_{s=1}^{v(k)} a_{ks}$

...

$\sum_{s=1}^{v(n)} a_{ns} (＜ 2log(n))$

ということですね！！

さっきと同じように、この和を $S_b$ とすると、

$S_b ＜ 2log(n) × n = 2nlog(n)$

が成り立ちます！！

$log$ の性質か何かだと思います！！！

ja.wikipedia.org

ここで、 $S_a$ の各項について、各素数の優勝者を決めます！！！！

具体的には、素数 $p$ について、

$e_{ij} (log(p) + 1)$

の $e_{ij}$ の数字が最も大きい項を優勝者とします！！

同率が複数いる場合は、 $i$ の数字が最も小さいものを勝者とします！！

おめでとうございます！！！

そして、優勝者達については、シグマごと特等席に移動して貰って計算します！！

当然ですね！！！

この部分の合計は、 $p_{max}$ までの素数の個数を $π(n)$ 個とすると、

$π(n) × \sum_{j=1}^{h_i} a_{ij} = π(n) log(m)$

となります！！

また、 $n$ をある程度大きくしておくと、 $π(n)$ は $[ n / 2 ]$ ( $n / 2$ の整数部分)未満になります。というか、たぶん $1/3$ にも $1/4$ にもなると思います！！！

とにかく、

$S_c = [ n / 2 ] log(m)$ とすると、

$π(n) log(m) ＜ S_c$

となるわけですね！！！

このとき、準優勝者以下、つまり $S_a - π(n) log(m)$ の各項について考えてみましょう！

例えば、 $n = 63, m = 319$ としたときには、

$m + 1 = 320$

$m + 2 = 321$

$m + 3 = 322$

...

$m + 63 = 382$

です！

素数 $2$ について考えてみると、

優勝者は $320 = 2^6 × 5$ です！！

$a_{ij}$ の形式に変換すると、 $6×(log(2) + 1) + 1×(log(5) + 1)$ ですが、これがそっくり特等席に移動します！！

準優勝者以下は、

$2^5$ は、1個( $352$ )

$2^4$ は、3個( $336, 352, 368$ )

......

です！！！確かに優勝者以下ですね！！！

ここで $1～n$ のほうに目を向けてみましょう！！

$2^5$ は、1個( $32$ )

$2^4$ は、3個( $16, 32, 48$ )

...

ちょうど同じものがあります！！！

$2^5$ は、 $a_{ij}$ に変換すると、

$5 × (log (2) + 1)$

ですし、 $2^4$ は、 $a_{ij}$ に変換すると、

$4 × (log (2) + 1)$

です

なのでこれは、 $m～m+n$ の側も、 $1～n$ の側も同じものが出現することになります！！！

全く同じです！！！

つまり、素数 $2$ について、準優勝者以下に絞れば、 $a_{ij}$ の合計は、 $S_a$ 側も $S_b$ 側も等しくなる･･･

はずです！！！

Woodsさんは、総和に言及していないので、よく分かりません！！！

成立するものとして話を進めます！

素数 $3, 5, ..., p_{max}$ も同じ話ができるはずです。ということは、準優勝者以下の $S_a$ 側と、 $S_b$ 側は、完全に等しくなる･･････

ように見えます！

が！しかし！

実は $S_a$ 側は後ろのほうを計算打ち切りにしているのでした！！

ということは、

$S_a - π(n) log(m) ＜ S_b$

となるということですね！

$π(n) log(m) ＜ S_c$ だったことを思い出すと、

$S_a ＜ S_b + S_c$

ですね！！！

思い出すと言えば、

$S_a = n log(m)$

$2 n log(n) ＜ S_b$

$[n / 2 ] log(m)＜ S_c$

$n ≪ m$

でした！

$n$ と $m$ の関係性は、大小関係があればいいので、

$n^{5} ＜ m$ (Woods 1981)とか

$n^{10} ＜ m$ (Paris, Wilkie, Woods 1988)とか、

何なら $n^{50} ＜ m$ とかにもできますね。なので、

$S_a ＞ S_b + S_c$

とできることが分かりますね！

？？？

どういうことでしょうか？？？

５．まとめ

いかがでしたか？

残念ながら、惜しくも結論は出せませんでしたが、今回は素数が有限か無限かについて調べてみました！

続報があったら、是非まとめてみたいと思います！

ここまで見ていただき、ありがとうございました！

６．参考にしたもの

A. Woods, "Some problems in logic and number theory and their connections". Ph. D. Thesis, Univ. of Manchester, 1981.

J. B. Paris, A. J. Wilkie and A. R. Woods, "Provability of the Pigeonhole Principle and the Existence of Infinitely Many Primes" J. Symbolic Logic, 53, 1988.