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

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

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

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

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

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

前者について, 実数$x$に対して$\lfloor2x\rfloor-2\lfloor x\rfloor\leq1$であるため,
$$v_p({}_{2n} \mathrm{ C }_n)=\sum_{i=1}^{\lfloor \log_{p}{2n} \rfloor}{\bigg\lfloor\frac{2n}{p^i}\bigg\rfloor-2\bigg\lfloor\frac{n}{p^i}\bigg\rfloor}\leq\lfloor \log_{p}{2n} \rfloor$$
であるため示された.
後者について, $2n< p^2$より, $v_p({}_{2n} \mathrm{ C }_n)={\Big\lfloor\frac{2n}{p}\Big\rfloor-2\Big\lfloor\frac{n}{p}\Big\rfloor}=2-2\times1=0$より示された.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

正整数$m,a$に対して, $a\equiv1\pmod4$のとき, $m$以下の正の$a$の倍数で$4$で割った余りが$1$のものは$\lfloor\frac{m+3a}{4a}\rfloor$個, $4$で割った余りが$3$のものは$\lfloor\frac{m+a}{4a}\rfloor$個である. $a\equiv3\pmod4$のとき, $m$以下の正の$a$の倍数で$4$で割った余りが$1$のものは$\lfloor\frac{m+a}{4a}\rfloor$個, $4$で割った余りが$3$のものは$\lfloor\frac{m+3a}{4a}\rfloor$個である.
正整数$n$, 正の奇数$a$に対して$f(n,a)$を
\begin{eqnarray} f(n,a)= \left\{ \begin{array}{l} \bigg\lfloor\dfrac{\frac{3n}{2}+3a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{n+3a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{\frac{n}{2}+a}{4a}\bigg\rfloor\quad(a\equiv1\pmod4)\\ \bigg\lfloor\dfrac{\frac{3n}{2}+a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{n+a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{\frac{n}{2}+3a}{4a}\bigg\rfloor\quad(a\equiv3\pmod4) \end{array} \right. \end{eqnarray}
と定義する. このとき,
$$v_p(c_n)=\sum_{i=1}^{\lfloor \log_{p}{\frac{3n}{2}} \rfloor}{f(n,p^i)}$$
が成り立つ.
実数$x,y$に対して$\lfloor x+y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor\leq1$であるため, 奇数$a$が$a\equiv1\pmod4$のとき
$$f(n,a)\leq\bigg\lfloor\dfrac{\frac{3n}{2}+3a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{n+3a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{\frac{n}{2}}{4a}\bigg\rfloor\leq1$$
が成り立つ.
また, $a\equiv3\pmod4$のとき
$\bigg\lfloor\dfrac{\frac{3n}{2}}{4a}\bigg\rfloor=\bigg\lfloor\dfrac{\frac{3n}{2}+a}{4a}\bigg\rfloor$または$\bigg\lfloor\dfrac{\frac{n}{2}+3a}{4a}\bigg\rfloor=\bigg\lfloor\dfrac{\frac{n}{2}+4a}{4a}\bigg\rfloor$が成り立つ. なぜなら, $\dfrac{\frac{3n}{2}}{4a}< m_1\leq\dfrac{\frac{3n}{2}+a}{4a}$と$\dfrac{\frac{n}{2}+3a}{4a}< m_2\leq\dfrac{\frac{n}{2}+4a}{4a}$をみたす整数$m_1, m_2$が存在すると仮定すると$2<3m_2-m_1<3$より矛盾するからである. ゆえに, 前者の場合は
$$f(n,a)=\bigg\lfloor\dfrac{\frac{3n}{2}+4a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{n+a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{\frac{n}{2}+3a}{4a}\bigg\rfloor-1\leq0$$
が成り立つ. 後者の場合は
$$f(n,a)=\bigg\lfloor\dfrac{\frac{3n}{2}+a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{n+a}{4a}\bigg\rfloor-\bigg\lfloor\dfrac{\frac{n}{2}}{4a}\bigg\rfloor-1\leq0$$
よって, いずれの場合も$f(n,a)\leq0$.
これらを利用することで補題9はいずれも容易に示される.

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

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