ベルトラン・チェビシェフの定理
まず, 今回のテーマであるベルトラン・チェビシェフの定理について紹介する.
これには次のような初等的な証明が知られている.
いずれも帰納法で容易に示される.
正の実数に対し, を以下の素数の積とすると, . ただし, のときとする.
では明らか. したがって, 任意の整数に対してを示せば十分. のときは明らか. に対してはの約数であるため, 補題2の1つ目の結果とあわせて. この式を用いると帰納法で示すことができる.
正整数に対して素数がのとき. 特に, のとき.
また, 整数と素数がのとき.
前者について, 実数に対してであるため,
であるため示された.
後者について, より, より示された.
以上の補題からベルトラン・チェビシェフの定理を示す.
(定理1 ベルトラン・チェビシェフの定理)
が素数であるため, のときについては示された.
ある整数について, をみたす素数が存在しないと仮定すると補題4よりである. なお, ここで以下の素数が高々個であることを用いた. 補題2,3を用いると, . とおくと, . よって, であり, 右辺はにおいて単調減少. ここで, よりであるが, であるため矛盾. なお, においてが単調減少であることは微分法により容易に確かめられる.
型素数バージョンを作る
さて, ここからはベルトラン・チェビシェフの定理の考え方を応用する.
りぼーす氏がTwitterにて2023年5月3日に発表した
整数コンテスト
の問5を考えよう.
で割って余る素数は無限に存在することが知られている. これらを小さい順にとおいたとき, 正の整数から実数への変数関数を一つ決め, それが以下を満たすことを示せ.
任意の正の整数に対して
ただし, の表示として用いてよいのは, 実数の定数, 多項式, 指数, 対数, 階乗およびそれらの四則演算, 合成のみであり, 正の整数全体で定義されている必要がある.
をみたす整数に対してで割った余りがの素数を型素数と呼ぶ.
平方剰余の第一補充則より, 正整数に対しての素因数はまたは型素数である. よって, の素因数は以上であるため, 例えばとすると問題の条件をみたす.
このようにして, 条件をみたすの存在をいうのはさほど難しくないが, より小さく厳しいを探してみよう.
補題3を利用すると, よりが条件をみたすことがわかる. これでは階乗を使わず表すことができた. さらに, が互いに素な正整数のとき, の素因数がまたは型素数であるため, の素因数は以上である. ここで, 補題3の証明の途中で出てきた不等式を用いると, が条件をみたすことがわかる.
型素数のみかければよいところで, すべての素数をかけているのはを厳しい関数にする上でロスになっているため, その部分の評価を改善しよう. 正の実数に対してを以下の型素数の積とする. ただし, 以下の型素数が存在しないときはとする. を上手く上からおさえてより厳しい評価を得ることがひとまずの目標である.
補題3での評価をするときを用いたが, の評価をするために新しくのかわりとなるの関数を用意する.
正の実数に対してを以下ので割った余りがとなる正整数すべての積とする. ただし, 以下ので割った余りがとなる正整数が存在しないときはとする.
よって.
を奇素数, を正整数とする. 以下の正整数のうちで割った余りがでの倍数であるものは個である. よって,
ゆえに, はで割り切れる.
帰納法で容易に示される.
任意の整数に対してを示せば十分. のときは明らか. に対してはの約数であるため, 補題6とあわせて. この式とを用いると帰納法で示すことができる.
さて, 補題7及びその証明で登場する不等式を利用してより小さいをみつけよう. の素因数は以上である. したがって, が条件をみたすことがわかった.
ここまでの議論では指数関数でおさえられているが, ベルトラン・チェビシェフの定理の証明の流れをなぞると一次関数でおさえることができる. ベルトラン・チェビシェフの定理の証明におけるのかわりとなるの関数を用意したい. 補題7で用いたを利用すると実数においてを同様に示すことによって十分大きいにおいてが条件をみたすことがわかる. しかし, ここでは使う関数をもう少しだけ工夫してが条件をみたすことを示してみよう.
正整数に対し,
とおく.
正整数に対して奇素数がのとき.
特に, 型素数がのとき.
また, 型素数がのとき.
さらに, 整数と型素数がのとき.
正整数に対して, のとき, 以下の正のの倍数でで割った余りがのものは個, で割った余りがのものは個である. のとき, 以下の正のの倍数でで割った余りがのものは個, で割った余りがのものは個である.
正整数, 正の奇数に対してを
と定義する. このとき,
が成り立つ.
実数に対してであるため, 奇数がのとき
が成り立つ.
また, のとき
またはが成り立つ. なぜなら, とをみたす整数が存在すると仮定するとより矛盾するからである. ゆえに, 前者の場合は
が成り立つ. 後者の場合は
よって, いずれの場合も.
これらを利用することで補題9はいずれも容易に示される.
については個別に調べて正しいことが確かめられる.
よって,
より帰納法で示される.
(命題8)
が型素数であるため, のときについては示された.
ある整数について, をみたす型素数が存在しないと仮定すると補題9よりである. なお, ここで以下の奇素数が高々個であること及びを用いた. 補題7,10を用いて変形すると, . とおくと, . よって, であり, 右辺はにおいて単調減少. ここで, よりであるが,
であるため矛盾.
型素数についても, を利用して実数に対してがわかり,
とおいて同様に, 任意の正整数に対してをみたす型素数が存在することが示せる.