素数の無限性の証明はたくさん知られています。昔はそれらを調べることが趣味でしたが、もう飽きてしまって久しいです。
ですが、トゥエによる証明とよばれている古いアイデアがあって、それを久しぶりに読む機会があったので、まあちょっとエッセイでも書こうかという気分になったのであります。
素数というのはどこにいるかというと、以上の整数を持ってくれば、必ずその整数の素因数という形でおります。
ということは以上の整数を無限に持ってくれば、素数が無限にいるということが言えるかもしれません。
ですが、何の工夫もしないと失敗します。
例えば、以上の整数を全部考えて、各についての素因数を1つとってとしましょう。すると、
という無限集合が得られて素数の無限性が論証できたかというと、そうはなりません。
というのも、異なるに対してかもしれないので、達が重なりまくって実は上の集合が有限集合だったという可能性を排除できていないからです。
そこで工夫をします。以上の整数を全部考えるのではなく、何か適切な数列を考えて、の素因数を1つとってとし、今度こそ
が無限集合であることを保証できるようにするのです。
のときとは互いに素であるとか、そうでなくとも、はとは互いに素な以上の因子を必ず持つとか、そういう条件を満たす数列であればOKです。
それで、そのような適切な数列というのは幾らでも見つかっていて、素数の無限性証明の1つの大きな系列を形成しているわけです。
ただ、数列を何かしらチョイスしないといけないので、常に人工的と言いますか、整数全体が協力する感じの証明にはなりません。一方で、この系列には属さないアイデアに基づく素数の無限性証明も大量に知られています。
さて、今回それらの中で注目したいのは「数え上げ」による証明です。自然数は数えることと密接に関係があります(cardinals)。
有限集合の元の個数が不変量として定まる(つまり、ものの個数はものを数える順番、方法によらない)ということはよくよく考えれば不思議なこと(非自明)でもありまして、数え上げによる素数の無限性証明はそのことを利用します。
を正整数として、からまでの整数全体の集合を、この記事ではと表すことにします。例).
このとき、集合の元の個数はです。それは定義だと言ってもいいですが、と順番に数えていって最後に唱えるが個数になっているということです。
一方で、他の数え方をしてもいいです。ここでは正整数が
と表されるという算術の基本定理(これこそ素数の基本的役割であり、自然数の集合の掛け算による構造です)に基づいて数えてみましょう。すると、素数が無限にないといけないということが見えてきます*1。ここでは、は小さい方から数えて番目の素数を表す記号とします。
そのような証明にはエルデシュによるものとトゥエによるものの少なくとも2種類の方法があります。エルデシュによる証明は優れた点があるのですが、一方で、算術の基本定理から一歩踏み込んで「正整数は無平方部分と平方部分の積としての一意的な表示を持つ」という事実と絡めて議論されます。
以下で述べるトゥエによる証明は、エルデシュによる証明とは違って、「無平方部分」について考えることのない証明だという特徴があると言えるでしょう。
集合を考えましょう。この集合は素朴に数えると元の個数は個です。
一方、に対しての素因数分解表示をすると、であることから、各は以下でなければならず(つまり、として選び得る場合の数は高々通り)、また、とできます(は以下の素数の個数を表す標準的な記号)。よって、素因数分解表示に基づいての元の個数を数え上げると、高々個であることがわかります。従って、
の成立がわかりました。
すると、もし素数が有限個しか存在しないのであれば、
となって矛盾します。つまり、こんな不等式はこの世では成立し得ないということから、素数は無限に存在してもらわないと個数勘定が合わなくなるのです。
エルデシュによる証明では、既に述べた通り「無平方部分」について考慮した上で数え上げが行われるため、の2通りの数え上げによって、もし素数が有限個しか存在しないのであれば
が得られて矛盾します。まとめると、トゥエとエルデシュの証明の差は「無平方部分」を考慮に入れるか入れないかであり、その結果、矛盾する数の挙動がとという異なった形で現れるのです。
最後に素数の逆数和の発散性についても少し述べておきます。エルデシュが最もオーソドックスなオイラーによるものとは異なる証明を与えていることは有名ですが、彼は以下のの倍数の個数がであることを用いて、単純な数え上げにより次を証明しています:
素数の逆数和が収束すると仮定すると、ある素数が存在して、より大きい素数では割り切れないの元全体のなす集合をと表すとき、
が成り立つ。
ここで言及に値するかもしれないことは、エルデシュによる素数の逆数和の発散性証明は2つの部分からなっており、彼による素数の無限性証明のアイデアとを組み合わせた証明であるが、と組み合わせることによって素数の逆数和の発散性証明を導出することができる素数の無限性証明というのはエルデシュによるものに限定されるわけではないということです。
エルデシュによる素数の無限性証明からが言えるので、と組み合わせると
となって矛盾するわけですが、別にトゥエのアイデアを用いてもが言えるので、と組み合わせると
となって矛盾するのです。
追記
読み返してみると、きっと次のようなことをやるのだろうと思う文章な気がしてきました: ある数え方をすると数えた個数に対してという表示が得られ、別の数え方をするとという表示が得られ、実は同じ集合の元の個数を数えていたことが言えるので、が示される。
ですが、実際行われている論法は次のようなものです: ある数え方をすると数えた個数に対してという表示が得られ、別の数え方をするとという表示が得られ、実は前者で数えた集合が後者で数えた集合の部分集合であることが判明するので、が示される。
このことがちゃんとわかるように文章を書き換えるべきな気もしますが、面倒なので、この追記でご勘弁ください。