2017-11-09

Dicksonの予想ととある疑問

素数に関する次のような予想が知られています。自然数はこの記事では正の整数とします。

Dicksonの予想 (1904) 自然数 $k$ に対し、 $a_1, \dots, a_k$ は自然数、 $b_1, \dots, b_k$ は整数とする。もし、「各素数 $p$ 毎に自然数 $n$ が存在して積 $(a_1n+b_1)\cdots (a_kn+b_k)$ は $p$ で割り切れない」が成り立つならば、 $a_1n+b_1, \dots, a_kn+b_k$ が全て素数となるような自然数 $n$ が無数に存在する。

ある素数 $p$ に対して任意の自然数 $n$ で $(a_1n+b_1)\cdots (a_kn+b_k) \equiv 0 \pmod{p}$ が成り立つならば、どんな自然数 $n$ を考えても少なくとも一つの $a_in+b_i$ は $p$ で割れてしまい、 $n$ が十分大きい場合は合成数となってしまいます。すなわち、 $a_1n+b_1, \dots, a_kn+b_k$ が全て素数となるような自然数 $n$ は無数に存在しえません。Dicksonの予想はこのような絶対ダメな状況でさえなければいつでも $a_1n+b_1, \dots, a_kn+b_k$ が全て素数となるような自然数 $n$ が無数に存在するだろうと主張しています。

算術級数定理

$k=1, a_1=a, b_1=b$ で $a, b$ が互いに素なとき( $an+b$ )を考えると、 $p \mid a+b$ のとき $p \nmid 2a+b$ なので条件を満たし、Dicksonの予想はDirichletの算術級数定理を含んでいることがわかります。

ふたご素数予想

$k=2, a_1=1, b_1=0, a_2=1, b_2=2$ のとき( $n$ と $n+2$ )を考えると、 $1\times (1+2)=3$ , $2\times (2+2)=8$ を見れば条件を満たすことがわかり、Dicksonの予想はふたご素数予想を含んでいることがわかります。

Sophie Germain素数の無限性

$k=2, a_1=1, b_1=0, a_2=2, b_2=1$ のとき( $n$ と $2n+1$ )を考えると、 $1 \times (2\times 1+1)=3$ , $2\times (2\times 2+1)=10$ を見れば条件を満たすことがわかり、Dicksonの予想からSophie Germain素数が無数に存在することが従います。

素数 $k$ 組予想

ふたご素数予想は次のように拡張されます。

定義整数の $k$ 組 $(b_1, \dots, b_k)$ が許容 $k$ 組であるとは、任意の素数 $p$ に対して集合 $\{b_1 \bmod{p}, \dots, b_k\bmod{p}\}$ が $p$ 元集合とならないときにいう。

$(0, 2, 4)$ は $\{0 \bmod{3}, 2 \bmod{3}, 4 \bmod{3}\}=\{0 \bmod{3}, 1 \bmod{3}, 2 \bmod{3}\}$ なので非許容的であり、 $(0, 2, 6)$ は $\{0 \bmod{2}, 2 \bmod{2}, 6 \bmod{2}\}=\{0 \bmod{2}\}$ , $\{0 \bmod{3}, 2 \bmod{3}, 6 \bmod{3}\}=\{0 \bmod{3}, 2 \bmod{3}\}$ なので許容的です。

予想 (素数 $k$ 組予想) $(b_1, \dots, b_k)$ が許容 $k$ 組であれば、 $n+b_1, \dots, n+b_k$ が全て素数となるような自然数 $n$ が無数に存在する。

Dicksonの予想において $a_1=\cdots =a_k=1$ かつ $(b_1, \dots, b_k)$ が許容 $k$ 組であるとき、任意の素数 $p$ に対して $\{n+b_1 \bmod{p}, \dots, n+b_k \bmod{p}\}$ が $0 \bmod{p}$ を含まないような自然数 $n$ が存在するので条件を満たすことがわかります。よって、Dicksonの予想から素数 $k$ 組予想が従います。

Green-Taoの定理

$a_1=1, a_2=2, \dots, a_k=k, b_1=\cdots =b_k=1$ のとき( $n+1, 2n+1, \dots, kn+1$ )を考えると、

$(p+1)(2p+1)\cdots (kp+1) \equiv 1 \pmod{p}$

なので条件を満たすことがわかり、Dicksonの予想から $n+1, 2n+1, \dots, kn+1$ が全て素数であるような自然数 $n$ が無数に存在することがわかります。特に、Green-Taoの定理が従います。

Erdős-Turán予想について

Erdős-Turán予想について気になっていることがあるのですが、まずは予想の主張を思い出します。

Erdős-Turán予想 自然数からなる集合 $A$ が条件

$\displaystyle \sum_{a \in A}\frac{1}{a} = \infty$

を満たせば、 $A$ は任意の長さの等差数列を含む。

素数の逆数和は発散するためErdős-Turán予想はGreen-Taoの定理を含んでいます。一方、例えば

$\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^3} = \zeta(3) < \infty$

であり、立方数からなる長さ $3$ の等差数列は存在しない(= Euler-Legendreの定理)のでこれはErdős-Turán予想とconsistentです。

ただ、こういう解説を受けると錯覚する人もいると思うのですが、逆数和が発散するということは任意長等差数列を含むための必要十分条件ではありません。

Brunの定理により、ふたご素数の逆数和は収束します。なので、錯覚を起こしていると、ふたご素数から構成される任意の長さの等差数列は存在しないのかなという気になります。

ところが、 $k \mapsto 2k, a_1=a_2=1, a_3=a_4=2, \dots, a_{2k-1}=a_{2k}=k$ , $b_1=b_3=\cdots =b_{2k-1}=-1$ , $b_2=b_3=\cdots =b_{2k}=1$ のとき( $n-1, n+1, 2n-1, 2n+1, \dots, kn-1, kn+1$ )を考えると、

$(p-1)(p+1)(2p-1)(2p+1)\cdots (kp-1)(kp+1) \equiv (-1)^k \pmod{p}$

なので条件を満たすことがわかり、Dicksonの予想から $n\pm 1, 2n\pm 1, \dots, kn\pm 1$ が全て素数であるような自然数 $n$ が無数に存在することがわかります。つまり、次を予想してよいことになります。

予想ふたご素数からなる任意の長さの等差数列が存在する。

主張の意味は「ふたご素数のペアをなす小さい方の素数からなる任意の長さの等差数列が存在する」と思ってください。これは当然未解決ですが、最近次のようなプレプリントが出ています。

[1708.08629] The Green-Tao theorem for primes of the form $x^2+y^2+1$

$n^2+1$ 型の素数の無限性は未解決でした(Landauの第四問題)。一変数で二次式の形をした素数の無限性が証明されているケースは一つもありませんが、二変数にすると証明されているケースがあります。

tsujimotter.hatenablog.com

こちらの記事で紹介されているように $x^2+y^2$ 型素数の無限性は簡単にわかります(しかも約半数の素数はこの形です)。一方、1960年にLinikが $x^2+y^2+1$ 型素数が無数に存在することを証明しており、こちらははるかに深い定理です。その後、Iwaniecによって $N$ 以下の $x^2+y^2+1$ 型素数の個数を $\pi_{x^2+y^2+1}(N)$ とするとき、

$\displaystyle \pi_{x^2+y^2+1}(N) \asymp \frac{N}{\log^{\frac{3}{2}}N}, \quad N \to \infty$

が示されました。このことから、 $x^2+y^2+1$ 型素数の逆数和は収束することがわかります。一方、先ほど紹介したプレプリントは次の定理を証明したと主張しています(Green-Tao以降の相対Szemerédiの定理とIwaniec以降のテクニックの組み合わせ)。

定理' (Sun-Pan) $x^2+y^2+1$ 型素数からなる任意の長さの等差数列が存在する。

証明が正しければ、ふたご素数の場合の予想のときより強い根拠を持って「逆数和の発散」というErdős-Turán予想の条件は究極の条件ではないかもしれないことがわかります。

自然数全体に対して正の密度を持てば任意長等差数列を含むというSzemerédiの大定理を超えて、密度が零だけど素数列は任意長等差数列を含むことを示すことが出来るよということがGreen-Taoの定理の一つの魅力でした。Szemerédi-barrierを突破したわけです。

Green-Taoは素数全体に対して正の密度を持てば任意長等差数列を含むことまで示していました(素数版Szemerédiの定理)。

$x^2+y^2+1$ 型素数は素数全体における密度が $0$ なので、Sun-Paoの結果はGreen-Tao-barrierを更に突破したことになります。しかも、逆数和が収束するため、Erdős-Turán予想には含まれない定理です。

ふたご素数の密度は(包含関係はないですが) $x^2+y^2+1$ 型素数の密度よりも更に希薄です。では、相対密度の観点でどこまで下がっていくことが出来るのか、barrierは何度破ることが出来るのか、究極の予想は何かということが俄かに気になってきます。

強い形の素数 $k$ 組予想によれば、 $N$ 以下の素数 $k$ 組の個数は $\displaystyle \frac{N}{\log^kN}$ の定数倍に漸近すると予想されています(定数は許容 $k$ 組に依存して定まる)。そうして、次が予想できます。

予想 $(b_1, \dots, b_k)$ が許容 $k$ 組であれば、 $n+b_1, \dots, n+b_k$ が全て素数であるような自然数 $n$ 全体のなす集合は任意の長さの等差数列を含む。

Dicksonの予想から上記予想の導出

Dicksonの予想を仮定しているので、素数 $k$ 組予想も成立するものとしてよい。 $q+b_1, \dots, q+b_k$ がいずれも $k$ 個の整数

$\displaystyle \prod_{i=1}^k\prod_{j=1}^k\left|i+b_j-b_l\right|,\quad l=1, 2, \dots, k$

より大きい素数であるような自然数 $q$ を一つとって、多項式

$\displaystyle f(n)=\prod_{i=1}^k\prod_{j=1}^k(in+q+b_j)$

を考える。素数 $p$ が $q+b_1, \dots, q+b_k$ のいずれとも異なれば、

$\displaystyle f(p) \equiv (q+b_1)^k\cdots (q+b_k)^k \not \equiv 0 \pmod{p}$

が成り立つ。また、素数 $q+b_l$ については

$\displaystyle f(1) \equiv \prod_{i=1}^k\prod_{j=1}^k(i+b_j-b_l) \not \equiv 0 \pmod{q+b_l}$

である。よって、条件が満たされるので、Dicksonの予想から

$n+b_1, \dots kn+b_1, \ n+b_2, \dots, kn+b_2, \ \dots, \ n+b_k, \dots, kn+b_k$

が全て素数となるような自然数 $n$ が無数に存在し、予想が従う。 Q.E.D.

究極の予想は何か？

以上の考察の上で、タイトルにある疑問というのは次の疑問です。

疑問自然数からなる集合 $A$ が任意の $\varepsilon > 0$ に対して

$\#(A \cap \{1, 2, \dots, N\}) \gg_{\varepsilon} N^{1-\varepsilon}, \quad N \to \infty$

を満たすならば $A$ は任意の長さの等差数列を含むと言えるか？反例はあるか？

追記１

上の疑問「〜ならば $A$ は任意の長さの等差数列を含むと言えるか？」は正しくないことがわかっています*1。別の記事で少し解説します*2。

追記２

逆数和が収束するにも関わらず任意の長さの等差数列を含む数列の例として $x^2+y^2+1$ 型素数を紹介しましたが、それより前にふたご素数に関する予想に密接した例で示されているものがありました。

定義素数 $p$ が陳素数であるとは、 $p+2$ が素数または半素数であることと定義する。

1966年(証明を詳述したのは1973年)、陳景潤は陳素数が無数に存在することを証明しました。 $N$ 以下の陳素数の個数を $\pi_{\text{陳}}(N)$ と定義すると、

$\displaystyle \pi_{\text{陳}}(N) \gg \frac{N}{\log^2N}$

まで示されており、逆数和が収束することも示されています。この陳素数について2006年にGreen-Taoが陳素数からなる長さ $3$ の等差数列が無数に存在することを証明しており、2009年にはBinbin Zhouが陳素数からなる任意の長さの等差数列が存在することを証明しています。Sun-Paoと同じくZhouもGreen-Taoの手法で証明しています。

*1:これについて、山田氏からご指摘いただきました。

*2:書きました： integers.hatenablog.com

INTEGERS

数、特に整数に関する記事。