インテジャーズ

INTEGERS

数、特に整数に関する記事。

トゥエによる素数の無限性の証明

素数の無限性の証明はたくさん知られています。昔はそれらを調べることが趣味でしたが、もう飽きてしまって久しいです。


ですが、トゥエによる証明とよばれている古いアイデアがあって、それを久しぶりに読む機会があったので、まあちょっとエッセイでも書こうかという気分になったのであります。



素数というのはどこにいるかというと、2以上の整数を持ってくれば、必ずその整数の素因数という形でおります。


ということは2以上の整数を無限に持ってくれば、素数が無限にいるということが言えるかもしれません。


ですが、何の工夫もしないと失敗します。



例えば、2以上の整数Nを全部考えて、各NについてNの素因数を1つとってp_Nとしましょう。すると、


\{p_N \mid N\in\mathbb{Z}, N\geq 2\}


という無限集合が得られて素数の無限性が論証できたかというと、そうはなりません。


というのも、異なるN, M\geq 2に対してp_N=p_Mかもしれないので、p_N達が重なりまくって実は上の集合が有限集合だったという可能性を排除できていないからです。


そこで工夫をします。2以上の整数を全部考えるのではなく、何か適切な数列2\leq a_1 < a_2 < a_3 < \cdotsを考えて、a_Nの素因数を1つとってp_Nとし、今度こそ


\{p_N \mid N\in\mathbb{Z}, N\geq 2\}


が無限集合であることを保証できるようにするのです。

N\neq Mのときa_Na_Mは互いに素であるとか、そうでなくとも、a_Np_1,\dots, p_{N-1}とは互いに素な2以上の因子を必ず持つとか、そういう条件を満たす数列であればOKです。


それで、そのような適切な数列というのは幾らでも見つかっていて、素数の無限性証明の1つの大きな系列を形成しているわけです。


ただ、数列(a_N)を何かしらチョイスしないといけないので、常に人工的と言いますか、整数全体が協力する感じの証明にはなりません。一方で、この系列には属さないアイデアに基づく素数の無限性証明も大量に知られています。





さて、今回それらの中で注目したいのは「数え上げ」による証明です。自然数は数えることと密接に関係があります(cardinals)。


有限集合Sの元の個数\#Sが不変量として定まる(つまり、ものの個数はものを数える順番、方法によらない)ということはよくよく考えれば不思議なこと(非自明)でもありまして、数え上げによる素数の無限性証明はそのことを利用します。



Nを正整数として、1からNまでの整数全体の集合を、この記事では[N]と表すことにします。例)[5]=\{1,2,3,4,5\}.


このとき、集合[N]の元の個数はNです。それは定義だと言ってもいいですが、1, 2, \dotsと順番に数えていって最後に唱えるNが個数になっているということです。


一方で、他の数え方をしてもいいです。ここでは正整数n


n=p_1^{e_1}\cdots p_k^{e_k}\quad (e_1,\dots, e_k\in\mathbb{Z}_{\geq 0}) \tag{1}


と表されるという算術の基本定理(これこそ素数の基本的役割であり、自然数の集合の掛け算による構造です)に基づいて数えてみましょう。すると、素数が無限にないといけないということが見えてきます*1。ここでは、p_iは小さい方から数えてi番目の素数を表す記号とします。



そのような証明にはエルデシュによるものとトゥエによるものの少なくとも2種類の方法があります。エルデシュによる証明は優れた点があるのですが、一方で、算術の基本定理から一歩踏み込んで「正整数は無平方部分と平方部分の積としての一意的な表示を持つ」という事実と絡めて議論されます。


以下で述べるトゥエによる証明は、エルデシュによる証明とは違って、「無平方部分」について考えることのない証明だという特徴があると言えるでしょう。



集合[2^N]を考えましょう。この集合は素朴に数えると元の個数は2^N個です。


一方、n \in [2^N]に対して(1)素因数分解表示をすると、n\leq 2^Nであることから、各e_iN以下でなければならず(つまり、e_iとして選び得る場合の数は高々N+1通り)、また、k\leq \pi(2^N)とできます(\pi(x)x以下の素数の個数を表す標準的な記号)。よって、素因数分解表示に基づいて[2^N]の元の個数を数え上げると、高々(N+1)^{\pi(2^N)}個であることがわかります。従って、


\displaystyle 2^N\leq (N+1)^{\pi(2^N)}


の成立がわかりました。


すると、もし素数が有限個しか存在しないのであれば、


\displaystyle 2^N \leq N^{O(1)}\quad (N\to\infty) \tag{2}


となって矛盾します。つまり、こんな不等式はこの世では成立し得ないということから、素数は無限に存在してもらわないと個数勘定が合わなくなるのです。



エルデシュによる証明では、既に述べた通り「無平方部分」について考慮した上で数え上げが行われるため、[N^2]の2通りの数え上げによって、もし素数が有限個しか存在しないのであれば


\displaystyle N^2= O(N)\quad (N\to \infty) \tag{3}


が得られて矛盾します。まとめると、トゥエとエルデシュの証明の差は「無平方部分」を考慮に入れるか入れないかであり、その結果、矛盾する数の挙動が(2)(3)という異なった形で現れるのです。



最後に素数の逆数和の発散性についても少し述べておきます。エルデシュが最もオーソドックスなオイラーによるものとは異なる証明を与えていることは有名ですが、彼はN以下のpの倍数の個数が\lfloor N/p\rfloorであることを用いて、単純な数え上げにより次を証明しています:

素数の逆数和が収束すると仮定すると、ある素数pが存在して、pより大きい素数では割り切れない[N]の元全体のなす集合をE_Nと表すとき、


\displaystyle \#E_N\gg N \tag{4}


が成り立つ。


ここで言及に値するかもしれないことは、エルデシュによる素数の逆数和の発散性証明は2つの部分からなっており、彼による素数の無限性証明のアイデア(4)を組み合わせた証明であるが、(4)と組み合わせることによって素数の逆数和の発散性証明を導出することができる素数の無限性証明というのはエルデシュによるものに限定されるわけではないということです。


エルデシュによる素数の無限性証明から\#E_{N^2}=O(N)が言えるので、(4)と組み合わせると


\displaystyle N^2 \ll \#E_{N^2} \ll N \quad (N\to \infty)


となって矛盾するわけですが、別にトゥエのアイデアを用いても\#E_{2^N}\leq N^{O(1)}が言えるので、(4)と組み合わせると


\displaystyle 2^N \ll \#E_{2^N} \leq N^{O(1)} \quad (N\to \infty)


となって矛盾するのです。

追記

読み返してみると、きっと次のようなことをやるのだろうと思う文章な気がしてきました: ある数え方をすると数えた個数に対してAという表示が得られ、別の数え方をするとBという表示が得られ、実は同じ集合の元の個数を数えていたことが言えるので、A=Bが示される。

ですが、実際行われている論法は次のようなものです:  ある数え方をすると数えた個数に対してAという表示が得られ、別の数え方をするとBという表示が得られ、実は前者で数えた集合が後者で数えた集合の部分集合であることが判明するので、A\leq Bが示される。

このことがちゃんとわかるように文章を書き換えるべきな気もしますが、面倒なので、この追記でご勘弁ください。

*1:追記:ordinalsとしての自然数に積を考え、素因数分解という基本構造を見出した時点で素数の無限性がはっきりとわかるならばそれに越したことはありません。が、実際はそうではなく、なので素数の無限性というのは非自明だと認識できるわけですが、一方で「有限範囲で切って個数を数える」という1つの行為を加えると素数の無限性が瞬時にわかるというのがトゥエによる証明であり、とてもよい証明だと今回感じました。