素数定理 - Security Akademeia

目次 †

目次
素数定理とその直観的な意味
素数定理の証明
素数定理あれこれ
参考文献

↑

素数定理とその直観的な意味 †

[定理]素数定理（ガウスが10代の頃に予想、ルジャンドルも予想、1896年にアダマールとド・ラ・バレ＝プーサンがほとんど同時かつ独立に証明）
$\pi(x)~\sim~{\Bigint}_{2}^{x}~\frac{dx}{\log{x}}$
ただし、π(x)はx以下の素数の個数、即ちπ(x)=def#{p：素数|p≦x}とする。

　～という記号の意味は、x→∞のときに左辺と右辺の比が1に収束するということである。

[定理]x→∞のとき、 $\frac{\pi(x)}{{\Bigint}_{2}^{x}~\frac{dx}{\log{x}}}~\to~1$

　x→∞のときに最も大きくなる項のことを主要項、それ以外の項を誤差項（あるいは第二項）という。この主要項に注目すると、素数定理はπ(x)の主要項のみを与えている定理といえる。素数定理の右辺は部分積分によって、次のように分母のlog(x)の次数が高くなる級数の形に展開される[1]。

$\frac{x}{\log{x}}+\frac{x}{(\log{x})^2}+\frac{2x}{(\log{x})^3}+~\cdots$

　この級数の主要項は $\frac{x}{\log{x}}$ 、誤差項はそれ以外になる。よって、素数定理は次のように表現できる（もちろん誤差項を残した先ほどの表現の方がよく近似している）。

[定理]簡略版の素数定理
$\pi(x)~\sim~\frac{x}{\log{x}}$

　この表現から読み取れることは、直観的にxくらいの大きさの数が素数である確率は約 $\frac{1}{\log{x}}$ ということになる。

　ところで、xを限りなく大きくするとき、 $\frac{x}{\log{x}}$ はいくらでも大きくなる。なぜならば、 $\log{x}=n$ とおくとき、 $x=e^n$ であり、

$\frac{x}{\log{x}}~=~\frac{e^n}{n}$

となる。xが限りなく大きくなるとき、nも限りなく大きくなる。つまり、指数関数enも急激に増えて息、そのスピードはnよりも速い。よって、 $\frac{e^n}{n}$ はいくらでも大きくなる[2]。

例： $f(x)=~\frac{x}{\log{x}}$ とする[4]。

このとき、

$f'(x)$
$=\frac{\log{x}~-~x~\cdot~\frac{1}{x}}{(\log{x})^2}$
$=\frac{\log{x}~-~1}{(\log{x})^2}$
$\approx~\frac{1}{\log{x}}$

　よって、x=10100のとき、 $f'(10^{100})~=~0.0043429448190325175~=~4.3429448190325175~\times~10^{-3}$ である。
　計算に用いたMathematicaのコードは次の通り。//Nは近似値を求めるときに付ける。このNは数値を意味する語"Numerical"の頭文字をとったもので，大文字でなければいけない。

1/Log[10^100]//N

　したがって、x=10100付近の素数同士の平均ギャップは $\frac{1}{4.3429448190325175~\times~10^{-3}}~\approx~230.259~\approx~230$ になる。

　次に、x=10100から始めて何回チェックすれば素数が見つかることが期待できるかを調べる。ただし、2以外はすべての素数が奇数なので、奇数だけを調べるとする。

　x=10100付近の素数同士の平均ギャップは230なので、この平均ギャップの下で、2つの素数の中間点から始めたと仮定すると（10100は明らかに素数でない）、 $\frac{230}{4}~=57.5\approx~58$ 回調べれば次の素数が出てくることが期待できる。

[考察]例えば、1,024ビットならば数千個に1個の素数が存在する[5]。

　ところが、素数をまったく含まない任意に長い区間がある（素数砂漠）。

　なぜならば、

(n+1)!+2　←2で割り切れる
(n+1)!+3　←3で割り切れる
…
(n+1)!+(n+1)　←n+1で割り切れる

　このn個の間には素数が1つも入っていないからである。

↑

素数定理の証明 †

素数定理はリーマン・ゼータ関数の零点（ζ(s)=0となるs）を研究することで得られた。

↑

素数定理あれこれ †

素数定理の誤差項は未解決だが、リーマン・ゼータ関数の零点（ζ(s)=0となる複素数sのこと）を用いて表すことができる[1]。
- 零点は無限にたくさんあることが知られている。
- 素数定理の誤差項の次数はζ(s)の零点の実部の上限に等しい。つまり、とおくと、誤差項はの形をしている。
  - ρの値を求める問題は未解決である。ρ=1/2であることが広く信じられていて、これをリーマン予想という。
素数定理と素測地線定理は非常に似ている[1]。
- セルバーグ・ゼータ関数の零点の実部の最大値を $\rho~=~\sup~\{~Re(s)~+~1~|~\zeta(s)~=~0~\}$ とおくと、素測地線定理の誤差項は $x^{\frac{\rho~+~1}{2}}$ と表される。
- ρを求める問題は未解決。
- $\frac{1}{2}~\le~\rho~\le~1$ が成り立つ。
- $\rho~=~\frac{1}{2}$ というリーマン予想は信じられている。
- 素数の場合と異なり、ρ＞1/2のとき零点sは有限個しかないことが証明されている。

↑

参考文献 †

[1]『数学セミナー　1999年3月号』特集：アナロジーが織りなす世界　素数と素サイクル pp.18-21
[2]『関数とはなんだろう』pp.180-181
[3]講座：数学の発見　第6回（その1）「私がこの人生で見た整数論の発展」
[4]『暗号・符号・バーコードの仕組みがわかる応用代数学入門』（ピアソン・エデュケーション）第7章：フェルマーの定理とオイラーの定理　練習問題7.4.9 pp.160
[5]講義「数論基礎」ノート

Top / 素数定理素数定理

目次 †

素数定理とその直観的な意味 †

素数定理の証明 †

素数定理あれこれ †

参考文献 †

Top / 素数定理
素数定理