※本記事は、はてなブログに投稿してたのを統合してMathlogの様式に合わせて移植したものになります。
以下、関数
また、関数
で定めます。ただし、
さて今回は、Legendreが発見した、次の素数計数関数に関する等式で遊んでみようと思います。
1以上の実数
が成り立つ。ただし、総和項は
まずはこれを証明しましょう。
まず、
を示すことになるが、これは
より成立する。
次に
と書ける。ここで、
すると、
と書けるので、
となる。また、この最右辺において
とできるので、包除原理により
が成り立つ。
以上から
を示せばよいことになるが、これはEratosthenesの篩を考えると成立はすぐに分かる。
すなわち、左辺は
となり矛盾するからである。
よって、両者の個数は一致するので、等式の成立が保証され、最初の等式が成り立つことが示された。
であることを考えると、Bertrandの仮説より、
証明を読んだら分かると思いますが、実はこの等式(1)はEratosthenesの篩に大きく関係していたのでした。昔初めて篩を習ったときは、単なる素数を見つける手法としか思っていませんでしたが、このように式として表現されると、色々と応用が利きそうに感じます。
というわけで、(1)式を用いて2つの命題を証明します。
素数は無限に存在する。
以下、
まず
もし素数が有限個であると仮定すると
なので、(1)式で
を得る。
次に、この総和を評価することを考える。そのために、Möbius関数と床関数について成り立つ不等式
を利用する。なぜこの不等式が成立するかというと、
となって、それぞれ明らかに成り立つことが分かるからである。
これより
と評価できる。さらに
および
と計算できる(ただし
が従う。この不等式で
は共に正の有限値に収束するので
となり、従って
が成り立つ。
これは、(2)式に明らかに矛盾する。ゆえに、素数が有限個だと仮定していたので、背理法により素数は無限に存在することが示された。
なんと、素数の無限性を証明できてしまいました。多分あまり知られていない証明法だと思います。
次に、素数密度零定理(正式名称知りません)を証明します。
素数は
が成り立つ。
実は、この証明のために(1)式を少し改変する必要があるのですが、天下り的になることを避けるために、まずはそのままの形で試してみようと思います(つまり、今から書くものは証明しようとして失敗したものになります)。
(1)式を用いて
さて、まず明らかに
を得る。また、素数の無限性の証明と同じ要領で
が成り立つことが分かるので、総和項は
と評価できる。よって
となり、
となる。しかし
が成り立つので、このままでは冒頭で述べた方針で証明できないことが発覚する。
何が問題なのかというと、
これをどうにかするために(1)式を手直しする必要があるわけです。といっても、式の構造を大幅に変えようとするとEratosthenesの篩の本質を失ってしまう可能性があるので、
そこで、次の不等式に辿り着きます。
が成り立つ。
一応軽く証明しておきましょう。
(3)式は、定理1と同様に包除原理を用いた議論をすることによって
と同値であることが分かる。
(4)式について、左辺は
よって、明らかに前者(左辺)より後者(右辺)の方が個数が多いので、(4)式は成立し、ゆえに(3)式が示された。
さて、この不等式(3)を用いた素数密度零定理の証明を考えると、証明においてネックだった
改めてキチンと書きましょう。
(3)式において
となるので、
が成り立ち
が従う。
これで証明は完了です。
いかがでしたでしょうか。素数の無限性や素数密度の情報を自明には含まないEratosthenesの篩からこんなに色々証明できて、僕は凄く面白いと思いました。
まだまだ弄れそうな気がするので、もっと色々考えてみたいですね。