4n+1型素数でベルトラン・チェビシェフの定理を考える

ベルトラン・チェビシェフの定理,整数,整数コン

1277

ベルトラン・チェビシェフの定理

まず, 今回のテーマであるベルトラン・チェビシェフの定理について紹介する.

ベルトラン・チェビシェフの定理

任意の正整数 $n$ に対して $n < p \leq 2 n$ をみたす素数 $p$ が存在する.

これには次のような初等的な証明が知られている.

正整数 $n$ に対して $_{2 n} C_{n} \leq \frac{4^{n}}{2}$ であり, 整数 $n \geq 4$ に対して $\frac{4^{n}}{n} <_{2 n} C_{n}$ である.

いずれも帰納法で容易に示される.

正の実数 $x$ に対し, $P (x)$ を $x$ 以下の素数の積とすると, $P (x) < 4^{x}$ . ただし, $0 < x < 2$ のとき $P (x) = 1$ とする.

$0 < x < 2$ では明らか. したがって, 任意の整数 $n \geq 2$ に対して $P (n) < 4^{n}$ を示せば十分. $n = 2$ のときは明らか. $m \geq 2$ に対して $\frac{P (2 m - 1)}{P (m)} = \frac{P (2 m)}{P (m)}$ は $_{2 m - 1} C_{m} = \frac{_{2 m} C_{m}}{2}$ の約数であるため, 補題2の1つ目の結果とあわせて $\frac{P (2 m - 1)}{P (m)} = \frac{P (2 m)}{P (m)} \leq 4^{m - 1}$ . この式を用いると帰納法で示すことができる.

正整数 $n$ に対して素数 $p$ が $p \leq \frac{2 n}{3}$ のとき $v_{p} (_{2 n} C_{n}) \leq \log_{p} 2 n$ . 特に, $\sqrt{2 n} < p \leq \frac{2 n}{3}$ のとき $v_{p} (_{2 n} C_{n}) \leq 1$ .
また, 整数 $n \geq 3$ と素数 $p \geq 3$ が $\frac{2 n}{3} < p \leq n$ のとき $v_{p} (_{2 n} C_{n}) = 0$ .

前者について, 実数 $x$ に対して $⌊ 2 x ⌋ - 2 ⌊ x ⌋ \leq 1$ であるため,
$v_{p} (_{2 n} C_{n}) = \sum_{i = 1}^{⌊ \log_{p} 2 n ⌋} ⌊ \frac{2 n}{p^{i}} ⌋ - 2 ⌊ \frac{n}{p^{i}} ⌋ \leq ⌊ \log_{p} 2 n ⌋$
であるため示された.
後者について, $2 n < p^{2}$ より, $v_{p} (_{2 n} C_{n}) = ⌊ \frac{2 n}{p} ⌋ - 2 ⌊ \frac{n}{p} ⌋ = 2 - 2 \times 1 = 0$ より示された.

以上の補題からベルトラン・チェビシェフの定理を示す.

(定理1 ベルトラン・チェビシェフの定理)

$2, 3, 5, 7, 11, 19, 37, 67, 131$ が素数であるため, $n < 128$ のときについては示された.
ある整数 $n \geq 128$ について, $n < p \leq 2 n$ をみたす素数 $p$ が存在しないと仮定すると補題4より $_{2 n} C_{n} \leq P (\frac{2 n}{3}) \times (2 n)^{\frac{\sqrt{2 n}}{3} + 2}$ である. なお, ここで $\sqrt{2 n}$ 以下の素数が高々 $(\frac{\sqrt{2 n}}{3} + 2)$ 個であることを用いた. 補題2,3を用いると, $2^{\frac{2 n}{3} + 1} < (2 n)^{\frac{\sqrt{2 n}}{3} + 3}$ . $x = \sqrt{2 n}$ とおくと, $2^{\frac{x^{2}}{3} + 1} < x^{\frac{2 x}{3} + 6}$ . よって, $\log 2 < (2 + \frac{18}{x}) (\frac{\log x}{x})$ であり, 右辺は $x > e$ において単調減少. ここで, $n \geq 128$ より $x \geq 16 (> e)$ であるが, $(2 + \frac{18}{x}) (\frac{\log x}{x}) \leq (2 + \frac{18}{16}) (\frac{\log 16}{16}) < \log 2$ であるため矛盾. なお, $x \geq e$ において $\frac{\log x}{x}$ が単調減少であることは微分法により容易に確かめられる.

$4 n + 1$ 型素数バージョンを作る

さて, ここからはベルトラン・チェビシェフの定理の考え方を応用する.

りぼーす氏がTwitterにて2023年5月3日に発表した整数コンテストの問5を考えよう.

$4$ で割って $1$ 余る素数は無限に存在することが知られている. これらを小さい順に $p_{1}, p_{2}, \dots$ とおいたとき, 正の整数から実数への $1$ 変数関数 $F$ を一つ決め, それが以下を満たすことを示せ.

任意の正の整数 $i$ に対して $p_{i + 1} \leq F (p_{i + 1})$

ただし, $F$ の表示として用いてよいのは, 実数の定数, 多項式, 指数, 対数, 階乗およびそれらの四則演算, 合成のみであり, 正の整数全体で定義されている必要がある.

$0 \leq b < a$ をみたす整数 $a, b$ に対して $a$ で割った余りが $b$ の素数を $a n + b$ 型素数と呼ぶ.

平方剰余の第一補充則より, 正整数 $m$ に対して $m^{2} + 1$ の素因数は $2$ または $4 n + 1$ 型素数である. よって, $(2 p_{1} p_{2} \dots p_{i})^{2} + 1$ の素因数は $p_{i + 1}$ 以上であるため, 例えば $F (n) = 4 (n!)^{2} + 1$ とすると問題の条件をみたす.
このようにして, 条件をみたす $F$ の存在をいうのはさほど難しくないが, より小さく厳しい $F$ を探してみよう.

補題3を利用すると, $2 p_{1} p_{2} \dots p_{i} < P (p_{i}) < 4_{i}^{p}$ より $F (n) = 16^{n} + 1$ が条件をみたすことがわかる. これで $F$ は階乗を使わず表すことができた. さらに, $m_{1}, m_{2}$ が互いに素な正整数のとき, $m_{1}^{2} + m_{2}^{2}$ の素因数が $2$ または $4 n + 1$ 型素数であるため, $(P (\frac{p_{i} + 1}{2}))^{2} + (\frac{P (p_{i})}{P (\frac{p_{i} + 1}{2})})^{2}$ の素因数は $p_{i} + 1$ 以上である. ここで, 補題3の証明の途中で出てきた不等式 $\frac{P (2 m - 1)}{P (m)} \leq 4^{m - 1}$ を用いると, $F (n) = 5 \times 4^{n - 1}$ が条件をみたすことがわかる.

$4 n + 1$ 型素数のみかければよいところで, すべての素数をかけているのは $F$ を厳しい関数にする上でロスになっているため, その部分の評価を改善しよう. 正の実数 $x$ に対して $P_{(a, b)} (x)$ を $x$ 以下の $a n + b$ 型素数の積とする. ただし, $x$ 以下の $a n + b$ 型素数が存在しないときは $P_{(a, b)} (x) = 1$ とする. $P_{(4, 1)} (x)$ を上手く上からおさえてより厳しい評価を得ることがひとまずの目標である.

補題3で $P (n)$ の評価をするとき $_{2 n - 1} C_{n}$ を用いたが, $P_{(4, 1)} (n)$ の評価をするために新しく $_{2 n - 1} C_{n}$ のかわりとなる $n$ の関数を用意する.
正の実数 $x$ に対して $(x)!_{(a, b)}$ を $x$ 以下の $a$ で割った余りが $b$ となる正整数すべての積とする. ただし, $x$ 以下の $a$ で割った余りが $b$ となる正整数が存在しないときは $(x)!_{(a, b)} = 1$ とする.

正整数 $n$ に対して $2^{n - 1} (4 n)!_{(4, 1)}$ は $n!$ で割り切れる.

$v_{2} (n!) = \sum_{i = 1}^{⌊ \log_{2} n ⌋} ⌊ \frac{n}{2^{i}} ⌋ \leq \sum_{i = 1}^{⌊ \log_{2} n ⌋} \frac{n}{2^{i}} \leq n - 1$
よって $v_{2} (2^{n - 1} (4 n)!_{(4, 1)}) \geq v_{2} (n!)$ .
$p$ を奇素数, $i$ を正整数とする. $4 p^{i} ⌊ \frac{n}{p^{i}} ⌋$ 以下の正整数のうち $4$ で割った余りが $1$ で $p^{i}$ の倍数であるものは $⌊ \frac{n}{p^{i}} ⌋$ 個である. よって,
$\begin{aligned} v_{p} ((4 n)!_{(4, 1)}) & = \sum_{i = 1}^{⌊ \log_{p} 4 n ⌋} (4 n 以下の正整数のうち 4 で割った余りが 1 で p^{i} の倍数であるものの個数) \\ \geq \sum_{i = 1}^{⌊ \log_{p} n ⌋} ⌊ \frac{n}{p^{i}} ⌋ = v_{p} (n!) \end{aligned}$
ゆえに, $2^{n - 1} (4 n)!_{(4, 1)}$ は $n!$ で割り切れる.

正整数 $n$ に対して $\frac{2^{n - 1} (4 n)!_{(4, 1)}}{n!} \leq 2^{3 n - 3}$ .

帰納法で容易に示される.

実数 $x \geq 2$ に対して $P_{(4, 1)} (x) \leq 2^{x - 2}$ .

任意の整数 $n \geq 2$ に対して $P_{(4, 1)} (n) \leq 2^{n - 2}$ を示せば十分. $n = 2, 3, 4$ のときは明らか. $m \geq 2$ に対して $\frac{P_{(4, 1)} (4 m - 3)}{P_{(4, 1)} (m)}$ は $\frac{2^{m - 1} (4 m)!_{(4, 1)}}{m!}$ の約数であるため, 補題6とあわせて $\frac{P_{(4, 1)} (4 m - 3)}{P_{(4, 1)} (m)} \leq 2^{3 m - 3}$ . この式と $P_{(4, 1)} (4 m - 3) = P_{(4, 1)} (4 m - 2) = P_{(4, 1)} (4 m - 1) = P_{(4, 1)} (4 m)$ を用いると帰納法で示すことができる.

さて, 補題7及びその証明で登場する不等式を利用してより小さい $F$ をみつけよう. $\frac{1}{2} ((P_{(4, 1)} (\frac{p_{i} + 3}{4}))^{2} + (\frac{P_{(4, 1)} (p_{i})}{P_{(4, 1)} (\frac{p_{i} + 3}{4})})^{2})$ の素因数は $p_{i} + 1$ 以上である. したがって, $F (n) = 2^{\frac{n - 7}{2}} + 2^{\frac{3 n - 5}{2}}$ が条件をみたすことがわかった.

ここまでの議論で $F$ は指数関数でおさえられているが, ベルトラン・チェビシェフの定理の証明の流れをなぞると一次関数でおさえることができる. ベルトラン・チェビシェフの定理の証明における $_{2 n} C_{n}$ のかわりとなる $n$ の関数を用意したい. 補題7で用いた $\frac{2^{n - 1} (4 n)!_{(4, 1)}}{n!}$ を利用すると実数 $x \geq 1$ において $P_{(4, 3)} (x) \leq 2^{x - 1}$ を同様に示すことによって十分大きい $i$ において $F (n) = \frac{5}{2} n$ が条件をみたすことがわかる. しかし, ここでは使う関数をもう少しだけ工夫して $F (n) = \frac{3}{2} n + \frac{11}{2}$ が条件をみたすことを示してみよう.

任意の正整数 $n$ に対して $n < p \leq \frac{3}{2} n + \frac{11}{2}$ をみたす $4 n + 1$ 型素数 $p$ が存在する.

正整数 $n$ に対し,
$c_{n} = \frac{(\frac{3 n}{2})!_{(4, 1)}}{(n)!_{(4, 1)} (\frac{n}{2})!_{(4, 3)}}$
とおく.

正整数 $n$ に対して奇素数 $p$ が $p \leq \frac{3 n}{10}$ のとき $v_{p} (c_{n}) \leq \log_{p} \frac{3 n}{2}$ .
特に, $4 n + 1$ 型素数 $p$ が $\sqrt{\frac{3 n}{2}} < p \leq \frac{3 n}{10}$ のとき $v_{p} (c_{n}) \leq 1$ .
また, $4 n + 3$ 型素数 $p$ が $\sqrt{\frac{3 n}{2}} < p$ のとき $v_{p} (c_{n}) \leq 0$ .
さらに, 整数 $n \geq 17$ と $4 n + 1$ 型素数 $p$ が $\frac{3 n}{10} < p \leq n$ のとき $v_{p} (c_{n}) \leq 0$ .

正整数 $m, a$ に対して, $a \equiv 1 (\mod 4)$ のとき, $m$ 以下の正の $a$ の倍数で $4$ で割った余りが $1$ のものは $⌊ \frac{m + 3 a}{4 a} ⌋$ 個, $4$ で割った余りが $3$ のものは $⌊ \frac{m + a}{4 a} ⌋$ 個である. $a \equiv 3 (\mod 4)$ のとき, $m$ 以下の正の $a$ の倍数で $4$ で割った余りが $1$ のものは $⌊ \frac{m + a}{4 a} ⌋$ 個, $4$ で割った余りが $3$ のものは $⌊ \frac{m + 3 a}{4 a} ⌋$ 個である.
正整数 $n$ , 正の奇数 $a$ に対して $f (n, a)$ を
$\begin{array}{r} f (n, a) = {\begin{cases} ⌊ \frac{\frac{3 n}{2} + 3 a}{4 a} ⌋ - ⌊ \frac{n + 3 a}{4 a} ⌋ - ⌊ \frac{\frac{n}{2} + a}{4 a} ⌋ (a \equiv 1 (\mod 4)) \\ ⌊ \frac{\frac{3 n}{2} + a}{4 a} ⌋ - ⌊ \frac{n + a}{4 a} ⌋ - ⌊ \frac{\frac{n}{2} + 3 a}{4 a} ⌋ (a \equiv 3 (\mod 4)) \end{cases} \end{array}$
と定義する. このとき,
$v_{p} (c_{n}) = \sum_{i = 1}^{⌊ \log_{p} \frac{3 n}{2} ⌋} f (n, p^{i})$
が成り立つ.
実数 $x, y$ に対して $⌊ x + y ⌋ - ⌊ x ⌋ - ⌊ y ⌋ \leq 1$ であるため, 奇数 $a$ が $a \equiv 1 (\mod 4)$ のとき
$f (n, a) \leq ⌊ \frac{\frac{3 n}{2} + 3 a}{4 a} ⌋ - ⌊ \frac{n + 3 a}{4 a} ⌋ - ⌊ \frac{\frac{n}{2}}{4 a} ⌋ \leq 1$
が成り立つ.
また, $a \equiv 3 (\mod 4)$ のとき
$⌊ \frac{\frac{3 n}{2}}{4 a} ⌋ = ⌊ \frac{\frac{3 n}{2} + a}{4 a} ⌋$ または $⌊ \frac{\frac{n}{2} + 3 a}{4 a} ⌋ = ⌊ \frac{\frac{n}{2} + 4 a}{4 a} ⌋$ が成り立つ. なぜなら, $\frac{\frac{3 n}{2}}{4 a} < m_{1} \leq \frac{\frac{3 n}{2} + a}{4 a}$ と $\frac{\frac{n}{2} + 3 a}{4 a} < m_{2} \leq \frac{\frac{n}{2} + 4 a}{4 a}$ をみたす整数 $m_{1}, m_{2}$ が存在すると仮定すると $2 < 3 m_{2} - m_{1} < 3$ より矛盾するからである. ゆえに, 前者の場合は
$f (n, a) = ⌊ \frac{\frac{3 n}{2} + 4 a}{4 a} ⌋ - ⌊ \frac{n + a}{4 a} ⌋ - ⌊ \frac{\frac{n}{2} + 3 a}{4 a} ⌋ - 1 \leq 0$
が成り立つ. 後者の場合は
$f (n, a) = ⌊ \frac{\frac{3 n}{2} + a}{4 a} ⌋ - ⌊ \frac{n + a}{4 a} ⌋ - ⌊ \frac{\frac{n}{2}}{4 a} ⌋ - 1 \leq 0$
よって, いずれの場合も $f (n, a) \leq 0$ .
これらを利用することで補題9はいずれも容易に示される.

整数 $n \geq 2$ に対して $\frac{1}{n^{2}} (\frac{27}{4})^{\frac{n}{8}} < c_{n}$ .

$2 \leq n \leq 9$ については個別に調べて正しいことが確かめられる.
$\frac{3 n}{2} (\frac{3 n}{2} + 4) (\frac{3 n}{2} + 8) < \frac{(\frac{3 (n + 8)}{2})!_{(4, 1)}}{(\frac{3 n}{2})!_{(4, 1)}}$
$\frac{1}{(n + 4) (n + 8)} < \frac{(n)!_{(4, 1)}}{(n + 8)!_{(4, 1)}}$
$\frac{1}{\frac{n}{2} + 4} < \frac{(\frac{n}{2})!_{(4, 3)}}{(\frac{n + 8}{2})!_{(4, 3)}}$
よって,
$\frac{27 n^{2}}{4 (n + 8)^{2}} < \frac{\frac{3 n}{2} (\frac{3 n}{2} + 4) (\frac{3 n}{2} + 8)}{(n + 4) (n + 8) (\frac{n}{2} + 4)} < \frac{c_{n + 8}}{c_{n}}$
より帰納法で示される.

(命題8)

$\begin{matrix} 5, 13, 17, 29, 37, 61, 97, 149, 229, 337, 509, 709, 1061, \\ 1597, 2357, 3529, 5297, 7933, 11897, 17789, 26669 \end{matrix}$
が $4 n + 1$ 型素数であるため, $n < \frac{2 \times 200^{2}}{3} < 26667$ のときについては示された.
ある整数 $n \geq \frac{2 \times 200^{2}}{3}$ について, $n < p \leq \frac{3}{2} n + \frac{11}{2}$ をみたす $4 n + 1$ 型素数 $p$ が存在しないと仮定すると補題9より $c_{n} \leq P_{(4, 1)} (\frac{3 n}{10}) \times (\frac{3 n}{2})^{\sqrt{\frac{n}{6}} - 2}$ である. なお, ここで $\sqrt{\frac{3 n}{2}}$ 以下の奇素数が高々 $(\sqrt{\frac{n}{6}} - 2)$ 個であること及び $v_{2} (c_{n}) = 0$ を用いた. 補題7,10を用いて変形すると, $9 \times 3^{\frac{3 n}{8}} < 2^{\frac{11 n}{20}} \times (\frac{3 n}{2})^{\sqrt{\frac{n}{6}}}$ . $x = \sqrt{\frac{3 n}{2}}$ とおくと, $9 \times 3^{\frac{x^{2}}{4}} < 2^{\frac{11 x^{2}}{30}} \times x^{\frac{2}{3} x}$ . よって, $15 \log 3 - 22 \log 2 < \frac{40 \log x}{x}$ であり, 右辺は $x > e$ において単調減少. ここで, $n \geq \frac{2 \times 200^{2}}{3}$ より $x \geq 200 (> e)$ であるが,
$\begin{aligned} \frac{40 \log x}{x} & \leq \frac{40 \log 200}{200} < \log 3 \\ < 15 \log 3 - 22 \log 2 \end{aligned}$
であるため矛盾.

$4 n + 3$ 型素数についても, $\frac{2^{n - 1} (4 n)!_{(4, 3)}}{n!} \leq 2^{3 n - 3}$ を利用して実数 $x \geq 1$ に対して $P_{(4, 3)} (x) \leq 2^{x - 1}$ がわかり, $c_{n} = \frac{(\frac{3 n}{2})!_{(4, 3)}}{(n)!_{(4, 3)} (\frac{n}{2})!_{(4, 1)}}$
とおいて同様に, 任意の正整数 $n$ に対して $n < p \leq \frac{3}{2} n + \frac{5}{2}$ をみたす $4 n + 3$ 型素数 $p$ が存在することが示せる.