インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

ベルトランの仮説

定理解説

この記事では、次の記事で30の美しい性質を紹介するための準備として、Bertrandの仮説と呼ばれる素数に関する非常に美しい定理を証明します。

Bertrandの仮説 (1845) 任意の自然数nに対して、n < p \leq 2nを満たすような素数 p が少なくとも一つ存在する。

要は、てんでんばらばらに現れるように思える素数ですが、考えてる数からその二倍に至るまでには必ず素数に出会えるという主張です(素数の無限性よりははるかに強い主張)。

Bertrandはn \leq 3000000までをチェックし、予想として提出したそうです。その後、1852年にChebyshevが証明しました。1919年にはRamanujanがガンマ関数を用いたシンプルな証明を発表しており、現在では1932年にErdösが発表した証明*1が最も初等的かつ簡単な証明であると感じます。

この記事ではErdösの証明に基づいてBertrandの仮説を証明します。アイデアとしては「中心二項係数の素因数分解を考える」です。なお、自然対数を使って証明を書くことも多いですが、今回は自然対数を取らずに証明します(本質的には全く同じ)。

準備

和や積の記号に出てくる"p"は全て素数とする。条件を満たす素数が存在しない場合は、和のときは0、積のときは1と規約する。

補題1 実数x \geq 2に対し、\displaystyle \prod_{p \leq x}p \leq 2^{2x-3}が成り立つ。

これは
integers.hatenablog.com
において、補題として既に証明している。

補題2 n4以上の整数であるとき、\displaystyle \binom{2n}{n} > \frac{4^n}{n}が成り立つ。

証明. これはnに関する帰納法で証明できる。 Q.E.D.

補題3 実数x \geq 8に対して\displaystyle \pi (x) \leq \frac{x}{2}が成り立つ(\pi (x)は素数個数関数)。

証明. 4以上の偶数が素数でないことに注意すれば容易に確認できる。 Q.E.D.

補題4 自然数nに対して、中心二項係数を\displaystyle \binom{2n}{n} = \prod_pp^{a_p}と素因数分解するとき、\displaystyle a_p = \sum_{m=1}^{\infty}\left( \left[ \frac{2n}{p^m} \right] - 2\left[ \frac{n}{p^m} \right] \right) が成り立つ。

これは
integers.hatenablog.com
で紹介したLegendreの公式から分かります。

補題5 補題4の記号のもと、p^{a_p} \leq 2nが成り立つ。

証明. 一般に、[ 2x ] -2[ x ] = 0 \ \text{or} \ 1であることと、補題4の和公式が実質有限和で、m \leq \log_p(2n)までしか寄与しないことから、a_p \leq \log_p(2n)がわかる*2Q.E.D.

補題6 補題4の記号のもと、\sqrt{2n} < p \leq 2n \Longrightarrow a_p \leq 1 が成り立つ。

証明. \sqrt{2n} < pならば2n < p^2なので、a_p \leq \log_p(2n) < 2となる。 Q.E.D.

補題7 n \geq 3のとき、補題4の記号のもと、\displaystyle \frac{2n}{3} < p \leq n \Longrightarrow a_p \leq 0 が成り立つ。

証明. \binom{2n}{n} = \frac{(2n)!}{(n!)^2}において、2n < 3pであることから、分子にはpの倍数として、p, 2pの二つが存在し、p \leq nであることから、分母にはpの倍数としてpが二回現れる。よって、分母分子で相殺され、a_p=0となる。 Q.E.D.

Bertrandの仮説の証明

n32以上の自然数とし、

\displaystyle \binom{2n}{n} = A_1 A_2 A_3

と分解する。ここで、

\begin{align}A_1 &= \prod_{p \leq \sqrt{2n}}p^{a_p}\\
A_2 &= \prod_{\sqrt{2n} < p \leq n}p^{a_p}\\
A_3 &= \prod_{n+1 \leq p \leq 2n}p\end{align}

である。補題5、3より、

\displaystyle A_1 \leq (2n)^{\pi (\sqrt{2n})} \leq  (2n)^{\frac{\sqrt{2n}}{2}}

を得る。補題6、7、1より

\displaystyle A_2 \leq \prod_{\sqrt{2n} < p \leq \frac{2n}{3}}p \leq \frac{1}{8}\cdot 4^{\frac{2n}{3}}

を得る。補題2と合わせて

\displaystyle \frac{4^n}{n} < \binom{2n}{n} \leq (2n)^{\frac{\sqrt{2n}}{2}}\cdot \frac{1}{8} \cdot 4^{\frac{2n}{3}}A_3

となり、

\displaystyle A_3 > \frac{4^n/n}{(2n)^{\frac{\sqrt{2n}}{2}}\cdot \frac{1}{8}\cdot 4^{\frac{2n}{3}}}

が得られる。よって、

\displaystyle \frac{4^n}{n} \geq (2n)^{\frac{\sqrt{2n}}{2}}\cdot \frac{1}{8}\cdot 4^{\frac{2n}{3}}

が成り立つようなnに対して、主張が成り立つことが分かる。どのようなnに対してこの不等式が成立するかを調べればよいが、ここでは最善の結果を求めることはせず、初等的な手計算で確かめることを優先することにする。すなわち、補題1の2^{-3}の部分を削り、補題2の4^n/n3^nで置き換えよう(n \geq 7のとき置き換えられる)。こうすると、

 3^n \geq (2n)^{\frac{\sqrt{2n}}{2}}\cdot 4^{\frac{2n}{3}}

を満たすようなnに対して主張が成り立つことがわかる。3乗して、自然対数をとることにより、この不等式は

\displaystyle \log \frac{27}{16} \geq \frac{3\log (2n)}{\sqrt{2n}}

と同値であることがわかる。\log x/\sqrt{x}は減少関数であり、n=933で不等式は成立するので、n \geq 933で定理は示されたことになる。n \leq 932に対しては、素数列

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259

を視れば直接確認できる。 Q.E.D.

*1:私はこの証明を高校生のときに読みましたが、Erdösは高校生のときにこの証明を発見しました。

*2:\log_pは岩澤のp\logではなく、高校で習う底がpの対数です。