Legendre予想

同義語：Legendreの予想Legendre's conjecture

概要

前提知識: 素数, Bertrandの仮説, 素数計数関数, 素数定理

$1$ と $4$ の間には素数 $2,3$ があり、$4$ と $9$ の間には $5,7$、$9$ と $16$ の間には $11,13$、$16$ と $25$ の間には $17,19,23$ がある。どんな正の整数 $n$ をとっても、連続する平方数 $n^2$ と $(n+1)^2$ の間に素数が必ずあるだろうか。これが Legendre 予想（Legendre's conjecture）であり、現在も未解決である（HW60 §2.8、p. 19 は素数についての未解決の予想の一つとして挙げている）。
Bertrandの仮説は $n$ と $2n$ の間に素数があることを保証するが、区間 $(n^2,(n+1)^2)$ の長さは $2n+1$ しかなく、左端 $x=n^2$ で測ると長さはおよそ $2\sqrt x$ である。区間が左端に比べてずっと短いので、Bertrand の仮説はもちろん、素数定理からも従わない。
この記事では、予想の主張と小さい $n$ での様子を述べたあと、予想を連続する素数の間隔の言葉に言い換える。間隔が $2\sqrt{p}+3$ 以下なら予想が成り立ち、逆に予想が成り立てば間隔は $4\sqrt p+4$ 未満であることを証明する（prop-lgc-gap-sufficient・prop-lgc-gap-necessary）。この言い換えと、$4\cdot10^{18}$ までの素数の間隔の計算結果を組み合わせると、$n\le10^9$ では予想が正しいことが分かる（cor-lgc-verified）。最後に、素数定理や Riemann 予想の誤差評価からはこの予想が導けない理由を説明する。

主張

以下、$p$ は素数を表し、$\pi(x)$ は $x$ 以下の素数の個数（素数計数関数）とする。

Legendre予想

任意の正の整数 $n$ に対して、$n^2< p<(n+1)^2$ を満たす素数 $p$ が存在する。

$n\ge1$ では $n^2$ も $(n+1)^2$ も素数でない（$1$ は素数でなく、$2$ 以上の平方数は合成数である）ので、端点を含めても含めなくても主張は同じであり、$\pi$ を使えば
$$ \pi\bigl((n+1)^2\bigr)-\pi(n^2)\ge1\qquad(n\ge1) $$
と書ける。

小さい $n$ での素数

$n=1,\dots,10$ について、$n^2$ と $(n+1)^2$ の間の素数は次のとおりである。
$$ \begin{array}{c|c|l} n & (n^2,(n+1)^2) & \text{素数}\\ \hline 1 & (1,4) & 2,3\\ 2 & (4,9) & 5,7\\ 3 & (9,16) & 11,13\\ 4 & (16,25) & 17,19,23\\ 5 & (25,36) & 29,31\\ 6 & (36,49) & 37,41,43,47\\ 7 & (49,64) & 53,59,61\\ 8 & (64,81) & 67,71,73,79\\ 9 & (81,100) & 83,89,97\\ 10 & (100,121) & 101,103,107,109,113 \end{array} $$
個数はどの行でも $2$ 以上ある。$n\le2000$ の範囲で個数が最小の $2$ になるのは $n=1,2,3,5$ だけで、$n=10,100,1000,10000$ では個数はそれぞれ $5,23,152,1081$ である（いずれも計算で確かめられる）。

個数は $n$ とともに増えていく。素数定理による目安では、$x$ の近くで素数が現れる割合はおよそ $1/\log x$ なので、長さ $2n+1$ の区間 $(n^2,(n+1)^2)$ には平均しておよそ $(2n+1)/\log(n^2)\approx n/\log n$ 個の素数があると期待される。$n=10,100,1000,10000$ では $n/\log n$ は $4.3,\ 21.7,\ 144.8,\ 1085.7$ であり、上の個数とよく合う。予想が難しいのは、この「平均」がすべての区間で $1$ 以上になることを保証する方法が知られていないからである。

素数の間隔による言い換え

$k$ 番目の素数を $p_k$ と書き（$p_1=2$、$p_2=3$、$p_3=5,\dots$）、連続する素数の間隔を
$$ g_k:=p_{k+1}-p_k $$
とおく。予想が破れる区間 $(n^2,(n+1)^2)$ があれば、それをまたぐ間隔が大きくなる。この観察を両方向に精密にしたのが次の 2 つの命題である。

間隔が小さければ予想が成り立つ

$n\ge2$ とし、区間 $(n^2,(n+1)^2)$ に素数がないとする。$n^2$ より小さい最大の素数を $p_k$ とすると
$$ g_k\ge2n+3>2\sqrt{p_k}+3 $$
である。したがって、ある実数 $X$ について「$p_k\ge X$ を満たすすべての $k$ で $g_k\le2\sqrt{p_k}+3$」が成り立てば、$n^2/2-1\ge X$ を満たすすべての $n\ge2$ について conj-lgc-main が成り立つ。特に、すべての $k$ で $g_k\le2\sqrt{p_k}+3$ ならば、Legendre 予想は正しい（$n=1$ では区間 $(1,4)$ に素数 $2$ がある）。

空の区間をまたぐ間隔を見る

$n\ge2$ なので $n^2\ge4$ であり、$n^2$ より小さい素数（たとえば $2$）があるから $p_k$ は定まる。$n^2$ は合成数なので $p_k\le n^2-1$ である。次の素数 $p_{k+1}$ は $p_k$ より大きく、$p_k$ と $n^2$ の間には（$p_k$ の選び方から）素数がなく、$n^2$ は素数でなく、仮定から $(n^2,(n+1)^2)$ にも素数がなく、$(n+1)^2$ も素数でない。よって $p_{k+1}\ge(n+1)^2+1$ であり、
$$ g_k=p_{k+1}-p_k\ge(n+1)^2+1-(n^2-1)=2n+3 $$
となる。$p_k< n^2$ より $\sqrt{p_k}< n$ なので $2n+3>2\sqrt{p_k}+3$ である。
後半を示す。$n\ge2$ で $n^2/2-1\ge X$ とし、区間 $(n^2,(n+1)^2)$ に素数がないと仮定する。$m:=\lfloor n^2/2\rfloor\ge1$ に Bertrandの仮説の定理「Bertrand–Chebyshevの定理」を使うと、$m< p\le2m\le n^2$ を満たす素数 $p$ がある。$n^2$ は素数でないので $p< n^2$ であり、$p_k\ge p>m\ge n^2/2-1\ge X$ となる。前半により $g_k>2\sqrt{p_k}+3$ であり、これは仮定に反する。$\square$

予想から間隔の上界が従う

Legendre 予想が正しければ、すべての $k$ について
$$ g_k<4\sqrt{p_k}+4 $$
である。とくに $g_k=O(\sqrt{p_k})$ である。

次の次の平方数までに素数がある

$n:=\lfloor\sqrt{p_k}\rfloor$ とおくと $n\ge1$ で $n^2\le p_k<(n+1)^2$ である。予想を $n+1$ に使うと、$(n+1)^2< p<(n+2)^2$ を満たす素数 $p$ があり、$p>p_k$ なので $p_{k+1}\le p<(n+2)^2$ である。よって
$$ g_k< (n+2)^2-n^2=4n+4\le4\sqrt{p_k}+4 $$
である。$\square$

予想は区間ごとに素数を 1 つずつ保証するので、素数の個数についての下界も与える。

予想から得られる素数の個数の下界

Legendre 予想が正しければ、すべての $N\ge1$ について $\pi(N^2)\ge N-1$ であり、すべての $k\ge1$ について $p_k<(k+1)^2$ である。

互いに交わらない区間から 1 つずつとる

$N=1$ では明らかである。$N\ge2$ のとき、$j=1,\dots,N-1$ の区間 $(j^2,(j+1)^2)$ は互いに交わらず、どれも $N^2$ 以下の数からなる。予想により各区間に素数が少なくとも 1 つあるので、$N^2$ 以下の素数は $N-1$ 個以上ある。後半は $N=k+1$ とすると $\pi((k+1)^2)\ge k$ であり、$(k+1)^2$ は素数でないので、$k$ 番目の素数は $(k+1)^2$ より小さい。$\square$

この下界は個数としては弱い。素数定理によれば $\pi(N^2)$ はおよそ $N^2/(2\log N)$ であり、$N-1$ よりはるかに大きい。Legendre 予想の内容は、素数が「平均として多い」ことではなく、「どの短い区間からも消えない」ことにある。後半の $p_k<(k+1)^2$ も、Bertrand の仮説から帰納法で得られる $p_k\le2^k$ と比べると強い上界である。

記録的な間隔と上界の比較

$4\cdot10^{18}$ より小さい範囲で最大の間隔 $g_k=1476$ は $p_k=1425172824437699411\approx1.43\times10^{18}$ から始まる（OeS）。このとき $\sqrt{p_k}\approx1.19\times10^9$ なので、prop-lgc-gap-sufficient の閾値 $2\sqrt{p_k}+3$ はおよそ $2.4\times10^9$ であり、実際の間隔はその $100$ 万分の $1$ 程度にすぎない。予想が難しいのは、このような大きな余裕が計算できる範囲を超えて一般に保たれることを示す方法がないからである。

2 つの命題を比べると、Legendre 予想は「素数の間隔がおよそ $\sqrt{p_k}$ の定数倍で押さえられる」という主張と、定数を除いてほぼ同じ強さである（prop-lgc-gap-sufficient は定数 $2$、prop-lgc-gap-necessary は定数 $4$）。

計算による確認

連続する素数の間隔は、大きな範囲まで計算機で調べられている。T. Oliveira e Silva らは $4\cdot10^{18}$ より小さいすべての素数について次の素数までの間隔を計算し、その最大値が $1476$（$p_k=1425172824437699411$ から）であることを報告している（OeS）。これを prop-lgc-gap-sufficient に入れると、次が得られる。

$10^9$ 以下の $n$ での成立

$4\cdot10^{18}$ より小さい素数 $p_k$ について $g_k\le1476$ であることを認めると、$1\le n\le10^9$ を満たすすべての $n$ について conj-lgc-main が成り立つ。

小さい $n$ は直接、大きい $n$ は間隔の上界で

$n\le736$ の場合は、各 $n$ について $(n^2,(n+1)^2)$ の整数を順に調べれば素数が見つかる（有限個の計算。実際には $n\le10^5$ まで確かめられる）。
$737\le n\le10^9$ とし、区間 $(n^2,(n+1)^2)$ に素数がないと仮定する。prop-lgc-gap-sufficient の前半により、$n^2$ より小さい最大の素数 $p_k$ について $g_k\ge2n+3\ge1477$ である。一方 $p_k< n^2\le10^{18}<4\cdot10^{18}$ なので、認めた計算結果から $g_k\le1476$ であり、矛盾する。$\square$

$p_k$ が十分大きければ、$1476$ のような値は $2\sqrt{p_k}+3$ よりずっと小さい。実際 $2\sqrt{p}+3\ge1476$ は $p\ge(1473/2)^2=542432.25$ と同値であり、prop-lgc-gap-sufficient の条件は、計算された範囲では大きな余裕をもって満たされている。

Cramér の予想との関係

H. Cramér は確率的な考察から、間隔 $g_k$ の大きな値は $(\log p_k)^2$ の程度で増えると予想した（OeS の序論）。これを「ある定数 $C$ について、十分大きいすべての $k$ で $g_k\le C(\log p_k)^2$」という形で仮定すると、Legendre 予想は十分大きいすべての $n$ で成り立つ。実際、$C(\log x)^2/\sqrt x\to0$（$x\to\infty$）なので、ある $X$ があって $x\ge X$ なら $C(\log x)^2\le2\sqrt x+3$ となり、prop-lgc-gap-sufficient の後半が使える。Cramér の予想そのものも未解決である。

素数定理・Riemann 予想との関係

Bertrandの仮説の命題「十分大きい $x$ での狭い区間」によれば、素数定理から、任意の $\varepsilon>0$ について十分大きい $x$ では $(x,(1+\varepsilon)x]$ に素数がある。$x=n^2$ とすると、この区間の長さは $\varepsilon n^2$ であり、$2n+1$ よりはるかに長い。$\varepsilon$ を $n$ に応じて $\varepsilon=(2n+1)/n^2$ ととれれば予想が従うが、この命題の $x_0$ は $\varepsilon$ ごとに決まるので、そのような使い方はできない。
区間の素数の個数を直接評価するには、$\pi(x)$ の近似の誤差が区間の長さより小さくなければならない。$\pi((n+1)^2)-\pi(n^2)$ の主要項はおよそ $n/\log n$ なので、必要なのは
$$ \pi(x)=\operatorname{li}(x)+(\text{誤差}),\qquad \lvert\text{誤差}\rvert=o\!\left(\frac{\sqrt x}{\log x}\right) $$
という形の評価である。

Riemann 予想を仮定しても足りないこと

Riemann予想の定理「誤差項による言い換え」とその後の注意によれば、Riemann 予想を仮定すると $x\ge2657$ で $\lvert\pi(x)-\operatorname{li}(x)\rvert<\frac1{8\pi}\sqrt x\log x$ が成り立つ（Schoenfeld の評価）。この評価を $x=n^2$ と $x=(n+1)^2$ に使うと、$n$ が大きいとき
$$ \pi\bigl((n+1)^2\bigr)-\pi(n^2)>\bigl(\operatorname{li}((n+1)^2)-\operatorname{li}(n^2)\bigr)-\frac{1}{8\pi}\Bigl(n\log n^2+(n+1)\log(n+1)^2\Bigr) $$
となる。$\operatorname{li}$ の導関数は $1/\log t$ なので、右辺の第 1 項は $\int_{n^2}^{(n+1)^2}\frac{dt}{\log t}\le\frac{2n+1}{2\log n}$ 以下であり、第 2 項は $\frac1{2\pi}n\log n$ 以上である。$n$ が大きいと $\frac{2n+1}{2\log n}<\frac{1}{2\pi}n\log n$ となるので右辺は負になり、この評価だけからは区間に素数があることは導けない。誤差の大きさは主要項の $(\log n)^2$ 倍程度ある。

例と反例

予想の区間の長さ $2n+1$ がどれほど大事かを、長さを変えた例で見る。

外す条件	反例	成り立たなくなること
区間の長さが $2n+1$（$x=n^2$ に対しておよそ $2\sqrt x$）	$n=5$ で長さを $2\log n\approx3.2$ に縮めた区間 $(25,\,28.2)$	区間に素数がある
区間の長さが左端とともに増える	長さ $k+1$（$k\ge2$）を固定した区間 $\bigl((k+1)!+1,\,(k+1)!+k+2\bigr)$	区間に素数がある

反例の確認

1 行目：$26=2\cdot13$、$27=3^3$、$28=2^2\cdot7$ はどれも合成数である。2 行目：Bertrandの仮説の例「反例：素数を含まない長い区間」により、この開区間の整数 $(k+1)!+2,\dots,(k+1)!+(k+1)$ はすべて合成数である。2 つの行は、区間の長さが短すぎても、長さが左端とともに増えなくても、素数のない区間が現れることを示している。一方、予想の区間の長さ $2n+1$ に対する条件 $g_k\le2\sqrt{p_k}+3$（prop-lgc-gap-sufficient）は、$7\times10^5$ までの素数では常に成り立ち、この範囲の間隔の最大値は $114$（$p_k=492113$ から）である（計算で確かめられる）。

補足

HW60 §2.8（p. 19）は、Legendre 予想を、$n^2+1$ の形の素数が無限にあるか、Goldbach の問題などと並べて、経験的な根拠は強いが証明のない予想として挙げている。L. Moser の講義録も古典的な未解決問題の第 13 問として「連続する平方数の間に少なくとも 1 つの素数があるか」を挙げている（Mos11 p. 73）。予想より弱い主張として、$n^2$ と $2n^2$ の間に素数があることは Bertrand の仮説から直ちに従う（$m=n^2$ に使う）が、区間 $(n^2,2n^2]$ の長さ $n^2$ と予想の区間の長さ $2n+1$ の差は大きい。