§C3.10ベルトランの仮説

証明. まず$\binom{2n}{k}$が$k = n$で最大になることを確かめます。$0 \le k \le 2n-1$について

であり、この値が$1$以上であることと$2n - k \ge k+1$、すなわち$k \le n - 1/2$とは同値です。$k$は整数なので、$k \le n-1$のとき増加し、$k \ge n$のとき減少します。よって最大値は$k = n$で取ります。

二項定理より$\sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n} = 4^n$です。この$2n+1$個の項のうち、両端の$\binom{2n}{0} = \binom{2n}{2n} = 1$を一つにまとめると、値$2$の項が一つと、$k = 1, \dots, 2n-1$に対応する$2n-1$個の項の、合わせて$2n$個の項になります。$n \ge 1$より$\binom{2n}{n} \ge 2$であるから、どの項も$\binom{2n}{n}$以下です。したがって

であり、両辺を$2n$で割ると主張を得ます。▨

証明.$1$から$m$までの各整数$a$について、$a$の素因数分解における$p$の指数は、$p^i$が$a$を割り切るような$i$の個数に等しくなります。$m!$における$p$の指数はこれらの総和なので、$i$を先に固定して数え直すと、$1$から$m$までに含まれる$p^i$の倍数の個数、すなわち$\lfloor m/p^i \rfloor$を$i$について足したものになります。▨

証明.$N = \dfrac{(2n)!}{n!\,n!}$であるから、定理 4.1により

です。実数$x$を$x = \lfloor x \rfloor + f$（$0 \le f < 1$）と書くと$\lfloor 2x \rfloor = 2\lfloor x \rfloor + \lfloor 2f \rfloor$であり、$\lfloor 2f \rfloor$は$0$か$1$です。したがって上の和の各項は$0$か$1$です。

$p^i > 2n$となる$i$については、$\lfloor 2n/p^i \rfloor$も$\lfloor n/p^i \rfloor$も$0$なので、項は$0$です。よって$0$でない項は、$p^i \le 2n$を満たす$i$に限られます。そのような$i$の最大値を$I$とすると$r_p \le I$であり、$p^I \le 2n$であるから$p^{r_p} \le 2n$です。$p > 2n$のときは$I$が存在しないので$r_p = 0$です。これが 1 です。

$p^2 > 2n$のときは$i \ge 2$の項がすべて$0$なので、$r_p$は$i = 1$の項だけであり、$r_p \le 1$です。これが 2 です。▨

証明.$2n/3 < p \le n$より$2p \le 2n < 3p$であり、また$p \le n < 2p$です。したがって

であり、定理 4.2の証明に現れる和の$i = 1$の項は$2 - 2 \cdot 1 = 0$です。

$i \ge 2$の項については、$p > 2n/3$より$p^2 > 4n^2/9$であり、$n \ge 5$のとき$4n^2/9 - 2n = \dfrac{2n(2n - 9)}{9} > 0$であるから$p^2 > 2n$です。よって$i \ge 2$の項はすべて$0$です。以上より指数は$0$です。▨

証明.$m$についての強い帰納法で示します。$m = 1$のとき左辺は$1$、右辺は$4$です。$m = 2$のとき左辺は$2$、右辺は$16$です。

$m \ge 3$が偶数のとき、$m$は素数ではないので、$m$以下の素数と$m-1$以下の素数は一致します。帰納法の仮定より、左辺は$4^{m-1} < 4^m$未満です。

$m = 2k+1$（$k \ge 1$）が奇数のとき、積を二つに分けます。

第二の積に現れる素数$p$は$k+1 < p \le 2k+1$を満たします。このとき$p$は$(2k+1)!$を割り切り、$p > k+1$より$k!$も$(k+1)!$も割り切りません。素因数分解の一意性により、$p$は

を割り切ります。これらの素数は相異なるので、その積も$\binom{2k+1}{k}$を割り切り、第二の積は$\binom{2k+1}{k}$以下です。さらに$\binom{2k+1}{k} = \binom{2k+1}{k+1}$であり、この二つは$\sum_{j=0}^{2k+1} \binom{2k+1}{j} = 2^{2k+1}$の項なので

です。$k+1 < 2k+1 = m$であるから、帰納法の仮定より第一の積は$4^{k+1}$未満です。以上を合わせると

を得ます。▨

証明.$n \ge 2048$とし、$n < p \le 2n$を満たす素数が存在しないと仮定します。$N = \binom{2n}{n}$とし、$N$の素因数分解における素数$p$の指数を$r_p$と書きます。

第一段：$N$に現れる素数は$2n/3$以下に限られます。定理 4.2の 1 により、$p > 2n$ならば$r_p = 0$です。仮定により、$n < p \le 2n$でも$r_p = 0$です。$n \ge 5$であるから定理 4.3により、$2n/3 < p \le n$でも$r_p = 0$です。よって

です。

第二段：この積を上から評価します。積を$p \le \sqrt{2n}$の部分と$\sqrt{2n} < p \le 2n/3$の部分に分けます。

前半について、定理 4.2の 1 より各因子は$p^{r_p} \le 2n$です。$\sqrt{2n}$以下の素数は$2, 3, \dots, \lfloor \sqrt{2n} \rfloor$の中にあるので、その個数は$\sqrt{2n} - 1$以下です。よって前半は$(2n)^{\sqrt{2n} - 1}$以下です。

後半について、$p > \sqrt{2n}$より$p^2 > 2n$であるから、定理 4.2の 2 より$r_p \le 1$です。よって後半は$2n/3$以下の素数の積以下であり、定理 5.1により$4^{2n/3}$未満です。

以上より

です。

第三段：二つの評価を突き合わせます。定理 3.1と合わせると

であり、両辺に$2n$を掛けて$4^{2n/3}$で割ると

を得ます。両辺の$2$を底とする対数を取り、$t = \sqrt{2n}$とおくと、$\log_2 (4^{n/3}) = 2n/3 = t^2/3$、$\log_2 \bigl( (2n)^{\sqrt{2n}} \bigr) = t \log_2 (t^2) = 2t\log_2 t$であるから

です。

第四段：この不等式が成り立たないことを示します。$n \ge 2048$より$2n \ge 4096 = 2^{12}$であり、$t = \sqrt{2n} \ge 2^6 = 64$です。$m = \lfloor \log_2 t \rfloor$とおくと$m \ge 6$、$2^m \le t$、$\log_2 t < m+1$です。

$m \ge 6$について$2^m \ge 6(m+1)$が成り立つことを、$m$についての帰納法で確かめます。$m = 6$のとき$2^6 = 64 \ge 42 = 6 \cdot 7$です。$2^m \ge 6(m+1)$を仮定すると

です。よってすべての$m \ge 6$で成り立ちます。

したがって$t \ge 2^m \ge 6(m+1) > 6\log_2 t$となり、第三段で得た$t < 6\log_2 t$に矛盾します。

よって、$n \ge 2048$のとき$n < p \le 2n$を満たす素数が存在します。▨

証明. 次の$13$個の素数を順に並べます。

これらを$q_1 < q_2 < \cdots < q_{13}$と書くと、隣り合う二つは$q_{j+1} < 2q_j$を満たします。実際$3 < 4$、$5 < 6$、$7 < 10$、$13 < 14$、$23 < 26$、$43 < 46$、$83 < 86$、$163 < 166$、$317 < 326$、$631 < 634$、$1259 < 1262$、$2503 < 2518$です。

$n = 1$のときは$p = 2$が$1 < 2 \le 2$を満たします。

$2 \le n \le 2502$とします。$q_1 = 2 \le n$であり$n \le 2502 < 2503 = q_{13}$であるから、$q_j \le n < q_{j+1}$を満たす番号$j$（$1 \le j \le 12$）を取ることができます。このとき

であるから、$p = q_{j+1}$が$n < p \le 2n$を満たします。▨

証明 (ベルトランの仮説の証明).$n \ge 2048$の場合は定理 6.1が、$1 \le n \le 2502$の場合は定理 7.1が主張を与えます。$2048 \le 2502$であるから、二つの範囲はすべての正の整数を覆います。▨