← 戻る ライブラリ › 組合せ論と離散数学 › 加法的組合せ論 組合せ論と離散数学
グリーン・タオの定理 素数は任意の有限の長さの等差数列を含むことが、2004年に証明された。
直観 直感:どんどん疎になる集合の中の構造 素数はますます稀になる:最初の N N N N / log N N/\log N N / log N N N N
素数にわたる指数和 S ( θ ) = ∑ p ≤ N e ( θ p ) S(\theta) = \sum_{p \le N} e(\theta p) S ( θ ) = ∑ p ≤ N e ( θ p ) θ \theta θ 大学 主張と密度0が障害である理由 ∀ k ≥ 3 , ∃ a , r > 0 : { a , a + r , … , a + ( k − 1 ) r } ⊆ P \forall\, k \ge 3,\ \exists\, a, r > 0 : \{a, a+r, \dots, a+(k-1)r\} \subseteq \mathcal{P} ∀ k ≥ 3 , ∃ a , r > 0 : { a , a + r , … , a + ( k − 1 ) r } ⊆ P これが定理である:素数の集合を P \mathcal{P} P k k k a a a r r r { a , a + r , … , a + ( k − 1 ) r } \{a, a+r, \dots, a+(k-1)r\} { a , a + r , … , a + ( k − 1 ) r } k k k
π ( N ) ∼ N log N \pi(N) \sim \frac{N}{\log N} π ( N ) ∼ log N N ここで π ( N ) \pi(N) π ( N ) N N N π ( N ) ∼ N log N \pi(N) \sim \frac{N}{\log N} π ( N ) ∼ l o g N N { 1 , … , N } \{1,\dots,N\} { 1 , … , N } P \mathcal{P} P
存在性と明示的計算の対比 側面 分かっていること 出典・年 任意の長さ k k k 証明済み:P \mathcal{P} P k k k k k k グリーン・タオ、2004年 明示的に見つかった最長のもの 分散コンピュータ探索で見つかった27個の素数からなる等差数列 PrimeGrid、2019年
発展 証明のアイデア:擬似ランダムな優関数への移送 k ≥ 3 k \ge 3 k ≥ 3 P \mathcal{P} P k k k P \mathcal{P} P
なぜ正しいのか? 障害は密度0であり、定理は P \mathcal{P} P Z \mathbb{Z} Z
証明 第1段階(障害)。フォン・マンゴルト関数 Λ ( n ) \Lambda(n) Λ ( n ) n = p j n=p^j n = p j log p \log p log p E [ Λ ] ≈ 1 \mathbb{E}[\Lambda] \approx 1 E [ Λ ] ≈ 1 Λ \Lambda Λ P \mathcal{P} P
第2段階(擬似ランダムな優関数)。Goldston–Yıldırım型のふるい重みのアイデアを用い、GreenとTaoは素数を優越する測度 ν ( n ) ≥ 0 \nu(n) \ge 0 ν ( n ) ≥ 0 E [ ν ] ≈ 1 \mathbb{E}[\nu] \approx 1 E [ ν ] ≈ 1 K K K Λ ( n ) ≤ K ν ( n ) \Lambda(n) \le K\nu(n) Λ ( n ) ≤ K ν ( n )
第3段階(相対セメレディの定理)。GreenとTaoは、正の相対密度 E [ f ] ≥ δ \mathbb{E}[f] \ge \delta E [ f ] ≥ δ 0 ≤ f ≤ ν 0 \le f \le \nu 0 ≤ f ≤ ν ν \nu ν k k k f f f ν \nu ν ν \nu ν
第4段階(まとめ)。Goldston–Yıldırım型の ν \nu ν f = Λ / K f = \Lambda / K f = Λ/ K E [ Λ ] ≈ 1 \mathbb{E}[\Lambda] \approx 1 E [ Λ ] ≈ 1 Λ \Lambda Λ k k k k k k k k k
素数からなる3項等差数列は無限に存在する。実際、すべての項が ≤ N \le N ≤ N c > 0 c>0 c > 0 c N 2 / log 3 N c \, N^2/\log^3 N c N 2 / log 3 N
なぜ正しいのか? この特別な場合はグリーン・タオより65年前のものであり、一般の k k k k = 3 k=3 k = 3
証明 第1段階(指数和による重み付き計数)。S ( θ ) = ∑ n ≤ N Λ ( n ) e ( θ n ) S(\theta) = \sum_{n \le N} \Lambda(n) e(\theta n) S ( θ ) = ∑ n ≤ N Λ ( n ) e ( θ n ) ≤ N \le N ≤ N p 1 + p 3 = 2 p 2 p_1 + p_3 = 2p_2 p 1 + p 3 = 2 p 2 ∫ 0 1 S ( θ ) 2 S ( − 2 θ ) d θ \int_0^1 S(\theta)^2 S(-2\theta) \, d\theta ∫ 0 1 S ( θ ) 2 S ( − 2 θ ) d θ
第2段階(主要弧)。q q q θ ≈ a / q \theta \approx a/q θ ≈ a / q S ( θ ) S(\theta) S ( θ ) S ( N ) N 2 / log 3 N \mathfrak{S}(N) \, N^2 / \log^3 N S ( N ) N 2 / log 3 N S ( N ) \mathfrak{S}(N) S ( N ) q q q
第3段階(副次弧)。分母の小さい有理数から離れた場所では、Vinogradovの評価により S ( θ ) S(\theta) S ( θ ) A A A O ( N ( log N ) − A ) O(N (\log N)^{-A}) O ( N ( log N ) − A ) o ( N 2 / log 3 N ) o(N^2/\log^3 N) o ( N 2 / log 3 N )
第4段階(結論)。主要弧の主要項 S ( N ) N 2 / log 3 N \mathfrak{S}(N)\,N^2/\log^3 N S ( N ) N 2 / log 3 N N 2 / log 3 N → ∞ N^2/\log^3 N \to \infty N 2 / log 3 N → ∞
大学 実世界での応用と具体例 この証明のために発明された移送原理——稠密な集合に関する定理を、擬似ランダムな優関数の内部にある疎な集合へと移す手法——は、素数の中の等差数列をはるかに超えて使われる一般的な道具となった:TaoとZieglerによる2008年の素数内の多項式数列への拡張の基盤となり、ZhangとMaynardによる素数間の有界な間隔の突破の背後にあるふるい理論的機構に知見を与え、理論計算機科学(稠密モデル定理、擬似ランダム性、計算量理論的正則性)にも類似物を持つ。計算の側では、PrimeGridのような分散探索プロジェクトが、定理の局所因子から出てくる素数階乗(primorial)の整除制約を用いて、記録的な長さの数列を探す際に探索空間を何桁も絞り込んでいる。
例: 5個の素数からなる等差数列と、その公差が6の倍数である理由
5 , 11 , 17 , 23 , 29 5, 11, 17, 23, 29 5 , 11 , 17 , 23 , 29 a > 5 a > 5 a > 5 r r r 30 = 2 ⋅ 3 ⋅ 5 30 = 2 \cdot 3 \cdot 5 30 = 2 ⋅ 3 ⋅ 5
解答 第1段階:5 , 11 , 17 , 23 , 29 5, 11, 17, 23, 29 5 , 11 , 17 , 23 , 29 6 6 6 ≤ 5 \le 5 ≤ 5 a = 5 , r = 6 a=5, r=6 a = 5 , r = 6
第2段階:任意の素数 p ≤ 5 p \le 5 p ≤ 5 p ∈ { 2 , 3 , 5 } p \in \{2,3,5\} p ∈ { 2 , 3 , 5 } p ∤ r p \nmid r p ∤ r j j j a + j r a + jr a + j r p p p p p p p p p
第3段階:もし a > 5 a > 5 a > 5 p p p p p p p ∈ { 2 , 3 , 5 } p \in \{2,3,5\} p ∈ { 2 , 3 , 5 } p ∣ r p \mid r p ∣ r 30 ∣ r 30 \mid r 30 ∣ r 5 , 11 , 17 , 23 , 29 5,11,17,23,29 5 , 11 , 17 , 23 , 29 a = 5 a=5 a = 5 2 ⋅ 3 = 6 ∣ r 2 \cdot 3 = 6 \mid r 2 ⋅ 3 = 6 ∣ r
例: 記録的な27項素数等差数列と、その公差に23#が現れる理由
明示的に知られている最長の素数等差数列は27項からなり、2019年にRob GahanとPrimeGridによって発見された:n = 0 , 1 , … , 26 n = 0, 1, \dots, 26 n = 0 , 1 , … , 26 224584605939537911 + 81292139 ⋅ 23 # ⋅ n 224584605939537911 + 81292139 \cdot 23\# \cdot n 224584605939537911 + 81292139 ⋅ 23# ⋅ n 23 # = 2 ⋅ 3 ⋅ 5 ⋯ 23 = 223092870 23\# = 2 \cdot 3 \cdot 5 \cdots 23 = 223092870 23# = 2 ⋅ 3 ⋅ 5 ⋯ 23 = 223092870 23 # 23\# 23#
解答 第1段階:p ≤ 23 p \le 23 p ≤ 23 p p p r r r 27 ≥ p 27 \ge p 27 ≥ p n = 0 , … , 26 n=0,\dots,26 n = 0 , … , 26 a + n r a + nr a + n r p p p p p p p p p
第2段階:この数列の27個の項はすべて18桁の数であり23よりはるかに大きいので、p ≤ 23 p \le 23 p ≤ 23
第3段階:したがってすべての素数 p ≤ 23 p \le 23 p ≤ 23 r r r 23 # = 223092870 23\# = 223092870 23# = 223092870 r r r 23 # 23\# 23#
よくある誤り. この定理が主張していない3つのこと:(1) 数列の中の素数が連続する素数であることは要求しない——a a a a + r a+r a + r r = 2 r=2 r = 2 r r r 歴史的ノート
LagrangeとWaringは18世紀にすでに素数が長い等差数列を作るだろうと推測していた。ファン・デル・コルプットは1939年に円周法を用いて k = 3 k=3 k = 3
テレンス・タオ ジェームズ・メイナード
研究の最前線 2026年時点
計算面では、2026年時点で明示的に知られている最長の素数等差数列は、2019年9月にRob GahanとPrimeGridが発見した27項の数列 224584605939537911 + 81292139 ⋅ 23 # ⋅ n 224584605939537911 + 81292139 \cdot 23\# \cdot n 224584605939537911 + 81292139 ⋅ 23# ⋅ n n = 0 , … , 26 n=0,\dots,26 n = 0 , … , 26 k k k k k k k ≥ 5 k \ge 5 k ≥ 5
グリーン・タオの定理は素数の集合 P \mathcal{P} P
P \mathcal{P} P P \mathcal{P} P k k k 双子素数 ( p , p + 2 ) (p, p+2) ( p , p + 2 ) P \mathcal{P} P なぜセメレディの定理を素数に直接適用できなかったのか、またグリーン・タオの証明で欠けている密度の仮定を何が置き換えているのか?
素数は密度0を持つ。証明は代わりにそれらを擬似ランダムな優測度の中に正の相対密度で埋め込み、相対セメレディの定理を証明する 素数は密度1を持ち、セメレディの定理には大きすぎる 証明はコンピュータで数列を1つずつ確認することでセメレディの定理を完全に回避する 証明は k = 3 k=3 k = 3 a > 5 a > 5 a > 5 a , a + r , … , a + 4 r a, a+r, \dots, a+4r a , a + r , … , a + 4 r r r r
2 2 2 6 = 2 ⋅ 3 6 = 2 \cdot 3 6 = 2 ⋅ 3 30 = 2 ⋅ 3 ⋅ 5 30 = 2 \cdot 3 \cdot 5 30 = 2 ⋅ 3 ⋅ 5 a a a 2026年時点で明示的に知られている最長の素数等差数列の長さはいくつか、またそれよりはるかに長いものが書き下されていないのはなぜか?
長さ27(2019年にPrimeGridが発見)。グリーン・タオの証明は天文学的な評価を伴う存在証明であるため、具体例を見つけるには大規模なコンピュータ探索が必要である 長さ5。それより長い素数の等差数列は存在しない 長さ1000。2004年の論文の公式から直接計算された 長さ3。ファン・デル・コルプットの場合しか明示的に見つかっていない