Bertrand-Chebyshevの定理の初等的な証明について

この記事ではBertrand-Chebyshevの定理と呼ばれる整数論の定理を紹介します。この記事で行う証明は高校数学の内容が分かっていれば十分に理解できるものになっています。
$\def\floor#1{\left\lfloor #1 \right\rfloor}$

Bertrandの予想とChebyshevによる解決
証明の準備
証明
まとめ
参考文献

Bertrandの予想とChebyshevによる解決

1845年，フランスのJoseph Bertrandは素数の分布について次のような予想を提出しました。

予想 1.1任意の正の整数 $n$ に対して， $n < p \le 2n$ を満たす素数 $p$ が存在する。

この予想を提出したとき，Bertrandは $n \le 3 \times 10^6$ の場合にこれが正しいことを検証したようです。

さて，時が流れること5年，ロシアのPafnuty Chebyshevはガンマ関数を用いてこの予想 1.1を肯定的に解決しました。このことから，現在では予想 1.1は「Bertrand-Chebyshevの定理」と呼ばれています。ちなみにChebyshevは「ロシア数学の父」と呼ばれることもある数学者で，統計や確率論でたくさんお世話になるChebyshevの不等式にもその名前を残しています。教え子の中には「Markov連鎖」に名を残すAndrey Markovもいるようです。

Chebyshevによる証明が行われてからおよそ80年後，1932年にはハンガリーのPaul Erdősがこの主張を初等的な数学を用いて証明しました。ちなみに「Erdös」ではなく「Erdős」です。さて，本記事ではこのErdősによる証明をさらに洗練させた，栃折の証明方法[栃折 2013]で予想 1.1を証明しましょう。

証明の準備

まず，Bertrand-Chebyshevの定理を証明するにあたっていくつか準備を進めます。以下に示す命題の証明はそこまで難しくないため詳細は割愛します。

補題 2.1正の数 $x$ に対して $x$ 以下の素数の個数を $\pi(x)$ で表すと， $\pi(x) < \dfrac{1}{3} x + 2$ が成り立つ。

証明の概略
$2$ と $3$ 以外の素数は， $2$ の倍数でも $3$ の倍数でもない。また， $1$ も素数ではない。このことから，
\begin{align}
\pi(x) \le \floor{x} - \left( \floor{\frac{x}{2}} + \floor{\frac{x}{3}} - \floor{\frac{x}{6}} \right) + 1
\end{align}
と評価できる。ただし， $\floor{x}$ は $x$ を超えない最大の整数を返す関数で床関数 (floor function)と呼ばれる。あとは， $x = 6m + r$ （ $m$ は整数， $0 \le r < 6$ ）とでもおいて細かく場合分けすればよい。なお， $r = 0$ と $0 < r < 2$ を区別すると等号の成立条件を考えなくてもうまくいくことに注意。■

ここで $P(x)$ を $x$ 以下の素数の総積とする。このとき，次の補題 2.2が成り立つ。

補題 2.2 $n$ を正の整数，実数 $x$ は $x \ge 3$ を満たすとする。このとき次の2つが成立する。
(1) $\dfrac{P(2n-1)}{P(n)} \le {}_{2n-1}\mathrm{C}_{n} \le 2^{2n-2}$
(2) $P(x) < 2^{2x-3}$

証明の概略
(1) ${}_{2n-1}\mathrm{C}_{n}$ の分子には $n+1$ 以上 $2n-1$ 以下の素数がすべて現れることに着目する。これらの積は分母と約分されないことから，左側の不等式が成り立つ。右側の不等式も計算により示すことができる。
(2) まず $x$ が整数のときだけ考えればよいことを示す。 $x$ が整数の場合については帰納法を使って示すことができる。初めに $x = 3, 4$ での成立を示すとうまくいく。途中で(1)を使う。■

補題 2.3 $n \ge 4$ を正の整数とする。 ${}_{2n}\mathrm{C}_{n} > \dfrac{2^{2n}}{n}$ が成り立つ。

証明の概略
$n$ に関する帰納法を用いて示すことができる。■

ここで， ${}_{2n}\mathrm{C}_{n}$ の素因数 $p$ に対して， $a_p$ をその指数とする。すなわち， ${}_{2n}\mathrm{C}_{n}$ は $p^{a_p}$ では割り切れるが， $p^{a_p + 1}$ では割り切れないとする。 $a_p$ は整数論の言葉ではオーダー (order)とも呼ばれ， $\operatorname{ord}_{p}({}_{2n}\mathrm{C}_{n})$ とも書かれる。このオーダーについて次の補題 2.4が成り立つ。

補題 2.4 $N = \floor{\log_p(2n)}$ とする。このとき， $a_p = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right)$ が成り立つ。

証明
${}_{2n}\mathrm{C}_{n} = \dfrac{(2n)!}{(n!)^2}$ となるため， $M = \floor{\log_p(n)}$ とおくと，
\begin{align}
a_p = \operatorname{ord}_p((2n)!) - 2 \operatorname{ord}_p(n!) = \sum_{i=1}^{N} \floor{\frac{2n}{p^i}} - 2 \sum_{i=1}^{M} \floor{\frac{n}{p^i}} = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right) +2 \sum_{i=M+1}^{N} \floor{\frac{n}{p^i}}.
\end{align}
ここで， $i \ge M+1 > \log_p(n)$ のとき， $\dfrac{n}{p^i} < 1$ となるから，最後のシグマは $0$ である。これより主張は成り立つ。■

以上で準備は終わりです。これらの事実を活用してBertrand-Chebyshevの定理を証明しましょう。

証明

証明は背理法による。すなわち，ある正の整数 $n$ が存在して，区間 $(n, 2n ]$ の範囲に素数が存在しないとする。
ちょっと頑張ると $64$ 未満の正の整数 $m$ の場合は区間 $(m, 2m ]$ の範囲に素数を見つけられるため，この $n$ は $n \ge 64$ を満たす。

$p$ を ${}_{2n}\mathrm{C}_{n}$ の素因数として， $a_p = \operatorname{ord}_p({}_{2n}\mathrm{C}_{n})$ とする。
$p > \dfrac{2}{3}n$ と仮定する。このとき，素因数 $p$ は $n$ より大きくなれないため， $\dfrac{2}{3}n < p \le n$ を満たす。
特に $n \ge 5$ であるから $2n < \dfrac{4}{9} n^2$ であり， $\dfrac{4}{9}n^2 < p^2$ である。これらより，
\begin{align}
\log_p(2n) = \frac{\log(2n)}{\log p} < \frac{\log\left(\dfrac{4}{9} n^2\right)}{\log p} < \frac{\log(p^2)}{\log p} = 2
\end{align}
となるため， $\floor{\log_p(2n)} \le 1$ である。すると補題 2.4から
\begin{align}
a_p \le \floor{\frac{2n}{p}} - 2 \floor{\frac{n}{p}} = 2 - 2 \times 1 = 0.
\end{align}
ここで $1 \le \dfrac{n}{p} < \dfrac{3}{2}$ を用いた。 $p$ は ${}_{2n}\mathrm{C}_{n}$ の素因数としたから $a_p \ge 1$ であるためこれは矛盾する。
よって， $p \le \dfrac{2}{3}n$ が成り立つ。

また任意の実数 $x$ に対して $\floor{2x} - 2 \floor{x} = 0,1$ であることに注意すれば，
\begin{align}
a_p = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right) \le \sum_{i=1}^{N} 1 = N \le \log_p(2n) \tag{I}
\end{align}
である。したがって $p^{a_p} \le 2n$ となる。特に $p > \sqrt{2n}$ であれば， $a_p < 2$ となり， $a_p =1$ に確定する。
なお， $n \ge 5$ では $\sqrt{2n} < \dfrac{2}{3}n$ が成り立つことからこのような素数 $p$ は存在しうることに注意。

以上より，
\begin{align}
{}_{2n}\mathrm{C}_{n} = \left( \prod_{\substack{p \le \sqrt{2n}, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) \left( \prod_{\substack{\sqrt{2n} < p \le \frac{2}{3} n, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) = \left( \prod_{\substack{p \le \sqrt{2n}, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) \left( \prod_{\substack{\sqrt{2n} < p \le \frac{2}{3} n, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p \right) < \left( \prod_{p \le \sqrt{2n}} p^{a_p} \right) \dfrac{P\left( \dfrac{2}{3}n \right)}{P( \sqrt{2n})}
\end{align}
である。いま

$P\left( \dfrac{2}{3}n \right) < 2^{2\times \frac{2}{3} n - 3}$ （補題 2.2より），
$n \ge 5$ ならば $P(\sqrt{2n}) > P(3) = 6$ ，
$p^{a_p} \le 2n$ （式(I)より），
$\pi(\sqrt{2n}) < \dfrac{1}{3} \sqrt{2n} + 2$ （補題 2.1より）

であることから，
\begin{align}
\left( \prod_{p \le \sqrt{2n}} p^{a_p} \right) \dfrac{P\left( \dfrac{2}{3}n \right)}{P( \sqrt{2n})} < \frac{2^{\frac{4}{3}n - 3}}{6} (2n)^{\frac{1}{3}\sqrt{2n}+2} < 2^{\frac{4}{3}n - 5} (2n)^{\frac{1}{3}\sqrt{2n}+2}
\end{align}
である。これより，補題 2.3から
\begin{align}
\frac{2^{2n}}{n} < {}_{2n}\mathrm{C}_{n} < 2^{\frac{4}{3}n - 5} (2n)^{\frac{1}{3}\sqrt{2n}+2}
\end{align}
を得る。最左辺と最右辺の対数をとって，
\begin{align}
2n \log 2 - \log n < \left( \frac{4}{3}n - 5 \right) \log 2 + \left( \frac{1}{3}\sqrt{2n}+2 \right) \log(2n)
\end{align}
となる。整理して，
\begin{align}
\frac{\log(2n)}{\sqrt{2n}} + \frac{9}{2n} \log \frac{n}{2} - \log 2 > 0 \tag{II}
\end{align}
を得る。すなわち，区間 $(n, 2n]$ の範囲に素数が存在しないような $n$ に対しては式(II)が成り立つ。式(II)の左辺を $f(n)$ とおく。

詳細な計算は演習とするものの， $f(x)$ のふるまいを調べると， $f(x)$ は $x > 0$ の範囲では，ある $x_0 > 0$ を境に $0< x < x_0$ では増加， $x_0 < x$ では減少する。この $x_0$ はたとえば $f^{\prime}(8) = \dfrac{13}{128}(1-2\log2) < 0$ であることから， $x_0 < 8$ であると分かる。

これより， $n \ge 64$ のとき，
\begin{align}
f(n) \le f(64) = 2^{-7} \log 2 \times (56\sqrt{2} - 83) < 0
\end{align}
となる。これは式(II)と矛盾する。

以上より，すべての正の整数 $n$ に対して，区間 $(n, 2n]$ の範囲に素数が存在する。■

まとめ

整数の性質を示す上で解析的な性質を利用するというのが，解析的整数論の面白さでもあると思いますが，今回は解析的整数論の中でも高校のカリキュラムで扱うような微積の知識だけを用いて証明ができるBertrand-Chebyshevの定理を紹介しました。解析的整数論の成果としてはほかにも「正の整数 $m$ と，それと互いに素な整数 $a$ に対して， $m$ を法として $a$ と合同な素数 $p$ が無限に存在する」ということを主張するDirichletの算術級数定理や，「 $\pi(x)$ が漸近的に $\dfrac{x}{\log x}$ と同じように振る舞う*1」ということを主張する素数定理といった定理があります。これらは今回とは違い，高校の学習範囲を超えた知識を利用して主張を示すものです。私もまだこれらの証明を理解しているわけではないので，いつか理解したいと思います。

なお，上に述べた証明の出だしで「ちょっと頑張ると $64$ 未満の正の整数 $m$ の場合は区間 $(m, 2m]$ の範囲に素数を見つけられる」と書きました。ちゃんとした証明の中に「ちょっと頑張る」という表現は本当は良くないのですが，実際に行うことといえば一つ一つの $m$ に対して調べていくだけなのでお許しください。

参考文献

[Wikipedia]　ベルトランの仮説 - Wikipedia，Bertrand's postulate - Wikipedia．参照日: 2021/06/20
[栃折 2013]　「 $n$ と $2n$ の間に素数がある」の証明を考える ‐ ベルトラン・チェビシェフの定理のより強い評価による証明 ‐ ．栃折成紀．2013．

*1:2021年6月24日23:27追記。この部分は当初「 $\pi(x)$ が漸近的に $x \log x$ と同じように振る舞う」と書いてありましたがこれは誤りで，正しくは既に修正してあるように「 $\pi(x)$ が漸近的に $\dfrac{x}{\log x}$ と同じように振る舞う」です。大変失礼いたしました。