■素数の無限性(その26)

【2】エルデシュによる初等的証明

 チェビシェフは,漸近評価

  c1x/logx<π(x)<c2x/logx

を得るために,オイラーによって1740年に考案されたゼータ関数(のちにリーマンがこの名前を付けた)やガンマ関数を利用しましたが,ベルトランの仮説に対しては,ずっと簡単な証明がラマヌジャンやエルデシュ(1932年,19歳)によって与えられています.

 この結果を得るのには非常に巧みな組み合わせ的推論が用いられているのですが,エルデシュはまず二項係数の中央の値

  cn=2nCn=(2n)!/(n!)^2

を考えます.

 これは整数であり,素因数分解するとnより大きく2n以下の素数があれば,それらはすべて1乗の形の積として現れます.もしもその間に素数がなければ,n以下の素数の積で表されるはずです(実はさらに2n/3以下の素数の積なります.2n/3より大きくn以下の素数は分子に2回,分母に2回現れて約分される).

 nまでの素数全体の積は大体e^n暗いというのが素数定理のひとつの表現なのですが,もっと粗く4^nというのなら数学的帰納法で容易に証明できます.nと2nの間に素数がないならおおざっぱにいって

  cn≦4^(2n/3)

ですが,これはcn〜4^nという事実に反します.

 以下は割愛しますが,証明の一部は不等式

  2^2n/(2n+1)≦2nCn≦2^2n

に基づいています.上界はΣ2nCk=2^2nより明らか,下界は2n+1個の二項係数の中で2nCnが最大であり,平均が2^2n/(2n+1)であることから証明されます.この評価は簡単ではありますが,かなり正確です.

  4^n/2≦2nCn≦4^n

===================================

[補]2nCnについては,さらに正確な評価を与える

  2^2n/(2√n)≦2nCn≦2^2n/√2n

などの評価式もしばしば使われます.また,スターリングの公式を使うとより精密な結果

  2nCn〜2^(2n)/√(πn)

が得られますが,この評価は数論,素数定理などとも関係しています.

 これまで,この「閑話休題」では標本中央値の漸近分布を求めたり,自由が無限大のt分布が正規分布になることや1次元・2次元ランダムウォークが再帰的であるのに対して,3次元以上のランダムウォークが非再帰的(原点に戻ってこれない確率が正)であるを示すのに,スターリングの公式やウォリスの公式,あるいは,2nCn〜2^(2n)/√(πn)などを用いてきました.また,これらの公式は2項分布の正規分布への収束を示すド・モアブル=ラプラスの定理の証明などにも用いられますが,ド・モアブル=ラプラスの定理は中心極限定理の特別な場合に相当しています.

===================================