2026-08-29 · article エルデシュ問題未解決問題組合せ論

エルデシュ等差数列予想 — k=3 の記録 3.0085385 と k=4 の記録 4.4397535 は、どちらも一つの機械検査済みの定理

Lean機械検査済み（Lean 4 + mathlib、標準三公理以下、sorryAx・native_decide なし。定理名を添える） 紙証明はあるが機械検査は未了 計算この端末で確かめた範囲。外に出す主張にはしない 既知言い換え・既知の定理・外の文献の確認

エルデシュが生前、5,000 ドルを懸けた予想があります。

エルデシュ等差数列予想：正整数の集合 A について Σ_a∈A 1/a = ∞ ならば、A は任意の長さの等差数列を含む。

「逆数和が発散するほど濃い集合は、いくらでも長い等差数列を避けられない」。素数の逆数和は発散するので、これが正しければ素数はいくらでも長い等差数列を含むことになります（この特別な場合は Green–Tao が 2004年に別途証明しました）。

この予想は、一つの数の列に翻訳できます。

これがエルデシュ問題 #169 です。そして——

エルデシュの問いは二つです。f(k) を見積もること、そして lim f(k)/log W(k) = ∞ か（W(k) は van der Waerden 数）。後者は f(k)/log W(k) ≥ 1/2 が自明で、1/2 より大きいどの定数も未解決です。

下界の既知は三つの層になっています——Berlekamp 1968 の (log 2/2)·k、Gerver 1977 の (1−o(1))·k log k、そして Walker 2025 の個別の k の記録。この記事は三層目を動かす話です。

壁は「対数の指数 1」のところにある

なぜ k=3 だけが解決していて、k=4 以上が未解決なのか。一箇所に集約できます。

k-AP-free な集合の [N, 2N) の部分の密度を δ_k(N) = r_k(N)/N（r_k は最大サイズ）と書くと、逆数和は次で抑えられます。

ここに既知の上界 rk(N) ≪ N/(log N)θ を入れると δ_k(2^j) ≈ j^−θ なので——

Σ j^−θ が収束するのは θ > 1 のときだけ。
予想を k について示すことは、「対数の指数 θ を 1 より上に上げること」に等しい。

この一本の線に、既知の結果が全部並びます。

k≥5 の上界は、c < 1 である限りどんな多項対数よりも弱い（exp(−(log log N)^c) 対 exp(−c·log log N)）。θ の目盛りに乗ってすらいません。

そして k=4 について、Green–Tao は自分の論文で「これが我々の手法の限界である」と書いています。手法の限界と、壁の位置が、k=4 でちょうど重なっています。

下界の側 — 実際に作られている集合

Walker 2025 の還元 — 探索空間が有限次元になる

ケンプナー集合だけ考えれば十分。すなわち「基数 b と数字集合 S を決め、b 進表記の各桁が全部 S に入る整数の集合」の形だけで、任意の k と ε について f(k) − ε に到達できる。

無限集合の海が、(b, S) の対の探索になります。この記事の作業は、全部この定理の上に乗っています。

※ ただし「十分」は極限の話で、有限の b で届くとは言っていません。「十分」を「実用的に十分」と読み替えやすい箇所です（縮めた語を再膨張させる型の飛躍）。

上界を上げるのは無理です。下界＝実際に集合を作る側に回りました。必要な道具は二つで、どちらも書けました。

二つ目が肝です。「10⁶ まで探して等差数列が無かった」ではなく、「存在しない」が有限の計算で言えます。

道具ができたら、まず既知の答えで検算する

2025年の査読済みの記録を、独立に再現しました。ここから先の数字は信用してよいことになります。

※ 5 と 6 の末尾の差（1.2×10⁻⁸）は格子の補間誤差であって改善ではありません。

貪欲だけが落ちませんでした。残りの五つは、探索の仕組みも探索空間の広さも違うのに、同じ集合を返しています。Walker は同じ場所を C++ で 8,679 コア時間かけて探索し、"an influential local maximum" と書いています。

その一点にあるもの — Szekeres 集合（1962年）

上の帯がカントール集合の形をしています。あらゆる尺度で同じ模様——これが後で効きます。下の曲線は逆数の部分和で、4,000 個を足しても、まだ 0.019 足りません。数え上げでこの値に到達するのは事実上不可能で、関数方程式を解く以外に道がない——それが §03 の道具が要った理由です。

ベルマン方程式まで一般化する

ケンプナー集合は「全部の桁で同じ (b, S)」の形です。桁ごとに、さらに枝ごとに変えてよいはず。

この族の 3-AP-free 十分条件は「各節点で F が ℤ/cℤ の中で 3-AP-free」。逆数和は F について線形なので、最大化が最適性方程式になります。

求める下界は 1 + U*(1)。重要なのは、U=0 から反復するとどの段階の値も正しい下界だということです。n 回目は「深さ n の木」＝有限の 3-AP-free 集合に対応するので、途中で止めても嘘になりません。

x = 1 でも x = 0.5 でも、最適な政策は同じ (c=3, F={0,1}) でした。階層ごとに構造を変える自由を与えても、Szekeres が選ばれ続けます。

k=3 では族の外に記録がありました。k=4 は違います。

十分条件は、k=3 と同じ形で通る

V に公差 D > 0 の 4-AP があるとする。v_i = f_i + c·u_i と一意に書くと、mod c で f_i は公差 D mod c の等差数列。
D ≡ 0 (mod c) なら f_i は全部同じ f で、u_i が V^(f) の中の 4-AP。→ 下の階層へ（帰納法）。
D ≢ 0 なら (f₁,f₂,f₃,f₄) は ℤ/cℤ の非定数な 4-AP で、全項が F に入る。

よって「各節点で F が ℤ/cℤ の非定数 4-AP を含まない」が十分条件。∎

記録集合が族に入っている — 出発点が記録以上になる

Walker の S が ℤ/55ℤ で非定数 4-AP を含まないかを、全通り（55×54 の組）調べました。含みません。

よって全階層で (55, S) を使う政策はこの族に入り、族の最適値は 4.4397534 以上であることが確定します。問題は真に超えるかだけ。

上がるための必要条件を、先に測る

ベルマンで値が上がるのは、最良の (c,F) が x によって入れ替わるときだけです。

符号が変わりません。Walker が全 x で優位——悪い兆候でした。ただし c = 11、たった 6 桁の集合が 4.4217475 を出していて、記録との差は 0.018 しかない。小さい基数が肉薄していること自体は、混ぜる望みがある形でした。

測る前に、予測を書く

回した結果 — 動かない

基数 4〜70 の全部について、現在の U に対して最良の F を整数計画で厳密に作り、候補の池に足す（列生成）。候補を 92 個追加しても、値は 4.439753373 のまま。

より強い形 — 不動点であることを証明する

価値反復は遠回りでした。ベルマン作用素 T について T(U_W) = U_W なら、U_W は不動点＝族の最適値です（T は単調な縮小写像なので不動点は一意）。だから U_W から一歩だけ当てて、超える F があるかを見ればよい。

ここは慎重にやる必要がありました。c=55 では Walker 自身の S が実行可能なので、最大値は必ず U_W 以上です。つまり「超えるかどうか」がぎりぎりの一点で決まる。暫定解では答えになりません。時間をかけて、整数計画に最適性を証明させました。

c = 55 の全ての x で、最適性が証明されました。最大の超過は −8.482×10⁻¹³。
負の値は数値誤差の範囲で、実質はちょうどゼロ——Walker の政策が、まさに不動点になっています。

なぜ動かないのか — 基数 55 は特別だった

ケンプナー集合 K(F,c) の元の個数は N^{log|F|/log c} で増えます。この指数を次元と呼ぶことにします。各基数について、ℤ/cℤ で非定数 4-AP を持たない最大の F を整数計画で求め、次元を計算しました。

c = 4 から 157 まで調べて、55 の次元が最大でした。そして上位三つが 11、55 = 5×11、121 = 11²。11 という基数が、この問題では特別です。Walker が 8,679 コア時間かけて 55 を見つけたのは、偶然ではありませんでした。

ただし次元だけでは決まりません。c=22 では、同じ |F| = 10 でも逆数和が 3.135 と 4.420 に割れます。F の位置——小さい数字を含むかどうか——が強く効く。

この節の「動かない」は、ケンプナー集合の族の中での結論です——階層ごとに基数 c と桁集合 F を選ぶ族の中では、Walker の集合が不動点でした。その族の外に出ると動きます。Walker の集合を途中で切り、その先に Behrend 型のブロックを継ぐと、記録を厳密に超えます。§07 末尾の「k=4 の記録も動いた」を参照。

k=3 の記録には、どうやっても 0.00055 届きません。その 0.00055 が何なのかを測ります。

逆数和は、小さい数に支配される

最初の 4 個で 3 分の 2 です。だから「どこまで大きな数を取れるか」より、「小さい数をどれだけ取れるか」が効きます。

より密な集合は、逆に悪い

3-AP-free 集合として最も密なのは Behrend 集合（1946、密度 N^{−c√(log N)}）。どんなカントール型よりも漸近的に密です。作り方は「d 進 n 桁で各桁を d/2 未満に制限し、桁の二乗和を固定する」——球面上にあり、球面は凸なので 3 点が等差数列になりません。

Behrend 型は、圧倒的に悪い。最良でも 0.890 で、Szekeres の 3 割にも届きません。
漸近的に密であることと、小さい数を取れることは別です。Behrend 集合は範囲 25 で 2 個しか取れません。

では、有限区間の最適は何か

[1, M] の 3-AP-free 部分集合で逆数和が最大のものを、整数計画で厳密に解きました。最適性を証明できた M だけを載せます（打切りの値は使いません）。

M ≤ 52 では、Szekeres がちょうど最適です。整数計画が、1962年の集合と同じものを返す。
M = 53 で初めて負けます（1 刻みで挟み撃ちにして確定）。差は 0.0013298——記録との差 0.00055 より、すでに大きい。

負け方も示唆的です。

最初の 8 個は完全に同じ。分かれるのは 9 番目からで、Szekeres が 28 を取るところで最適は 30 を取る。そして最適は 53（区間の端）まで使い切って 1 個多く詰め込みます。Szekeres は端を使い切りません——自己相似な構造がそこで切れているからです。

その優位は、地平線を延ばすと罠になる（厳密）

M = 53 の最適集合 A は、Szekeres を +0.0013298 上回ります。ではこの A から先を最適に続けたら、優位は残るのか。頭を固定して [54, H] を整数計画で厳密に最適化し、二つの出発点を比べました。

※ 四つの最適化すべてで最適性を証明済み（打切りではない）。

53 での +0.0013 の優位は、地平線 128 で −0.0347 の負債に変わります。
しかも [54, 80] には、どちらの頭からも一つも足せません——Szekeres 自身が 41 の次を 82 まで飛ばすのは、このためです。

早取りは、罠です。局所の改善が大域の費用になる——「自己相似性の代価」が、動く形で、単一の数字として証明されました。
（Szekeres の頭からの [54,128] の最適な続きは、Szekeres 自身の続きとちょうど一致します。これも証明済みです。）

局所の手術では、どこも動かない（厳密）

逆向きも確かめました。未来を Szekeres に固定したとき、途中を作り直せるか。土台を Szekeres ∩ [1, 6561]（256 元）とし、区間を丸ごと自由化して——その区間の Szekeres 元も外して、ゼロから選び直して——厳密に最適化しました。

Szekeres の空白は、怠慢ではなく完全に塞がれています。前後を Szekeres に固定すると、空白帯には一つも足せず、ブロックを丸ごと自由化しても Szekeres 自身が返ってくる。

早取りの罠（前項）と合わせると、こう言えます——Szekeres は局所的に手術不能です。有限のどの窓をいじっても、外が Szekeres である限り、Szekeres が最適。
したがって、記録（3.00849）の集合は、有限の場所で Szekeres と違うのではなく、ある尺度から先の「続け方」ごと、大域的に違っていなければなりません。

それでも Szekeres が勝つのは、尾を継げるから

有限の頭 H ⊆ [1, M] に、離れた位置の尾 T = {c·v : v ∈ V, v ≥ 1} を継ぐ場合、c > 2M なら 3-AP-free になります（頭2・尾1 は t = 2h₂−h₁ ≤ 2M < c ≤ min T で不可能。頭1・尾2 は 2t₁−t₂ = c(2v₁−v₂) で、0 でなければ絶対値が c 以上になって頭に入らず、0 なら正の元にならない。頭を挟む形 t₁+t₂ = 2h も c > 2M に反する。尾3 は尾自身が 3-AP-free）。

しかし、この尾はほとんど何も足しません。寄与は Σ 1/(c·v) = 3.007939/c で、c = 161（M = 80）なら 0.0187 です。

離せば安全だが、離した分だけ逆数和を失う。Szekeres が強いのはあらゆる尺度で薄く混ざっているから——尾が頭の隙間に入り込んでいて、離す必要がない。

離すことの代価が、この節の測った数です。
記録の超過 0.00055 のほぼ全部は、Behrend 型の尾が自己相似な続きの尾より濃くなる尺度 2^24.4 から先で生まれています（§08）。この節の有限区間の計算が示しているのは、その手前——低い尺度では自己相似な続きが手術不能であること——です。

ここまでは既知のものを測り直す作業でした。この節だけが、新しい下界です。k=3 も k=4 も、集合が等差数列を含まないことと記録を超えることは一つの Lean の定理です。節末の「この節の限界」まで含めて読んでください。

LeanShiori959.erdos169_lower_record_939 — 84 段の集合は 3-AP を含まず、逆数和は 3.0085385 を超える（1984 年の記録 3.00849 も超える）。Wróblewski の補題 1・2 も証明文を書き下して機械検査に載せてあり、外から借りている命題はありません。

何を変えたのか

Wróblewski の構成は二つの部品でできています。頭（Szekeres 集合を 21 523 361 で切ったもの、逆数和 3.0042100）と、その先に継ぎ足していくブロックの列です。継ぎ方——集合 Z の後ろにブロック T の平行移動コピーを三つ置く操作——は、彼の補題がそのまま保証します。

継ぎ方も頭も変えていません。ブロックの列だけを替えました。

ここで B(p,q,r) は Behrend 型のブロックで、桁を p 通りから選び、基数 2p−1 で並べ、桁の二次形式の和を r に固定したものです。

なぜそれで増えるのか

ブロック B(p,·,·) の元の個数は、その幅 N に対して N^(log p / log(2p−1)) で増えます。この指数——次元——は p とともに上がります。

Wróblewski は p = 6 に固定していました。1983年の計算機（ODRA 1305）で選んだパラメータが、そのまま 42 年残っていたことになります。

逆数和は小さい数に支配されるので、低い尺度では基数の小さいブロックが得です。しかし尺度が育つほど、次元の高い——つまり p の大きい——ブロックの方が得になります。
尺度とともに基数を育てる。それだけで、記録が動きました。

これは §02 で見た「壁は対数の指数のところにある」という構図と同じ形をしています。下界の側でも、効いているのは指数でした。

どこまで厳密か

浮動小数を一度も経由していません。

84 段の値が 3.0085385221 です。打ち切りは下界を下げる方向にしか働かないので、この値はそのまま下界になります。Lean が保証するのは 3.0085385 まで、10 桁の値そのものは整数の厳密演算の側にあります。

※ 独立に組んだ浮動小数の実装（中心化モーメント展開）と、段ごとの寄与が 10⁻⁹ 以内で一致することも確かめました。

この節の限界

• 上界には何も言っていません。f(3) が有限であることは既に分かっており、この作業はその中で「実際に作れる集合」を一つ改善しただけです
• 効くかどうかは、固定した尺度での次元の比較ではなく、尾の落ち方で決まります。同じ形が k=4 でも効きます（下の「k=4 の記録も動いた」）。k ≥ 5 には当てていません
• 段の選び方（ベルマン）の最適性は主張しません。この枠の中に残っている余地は、粗い見積りで 5×10⁻⁶ 程度です

k=4 の記録も動いた

§05 では、ケンプナー集合の族の中で Walker の集合が不動点であることを証明しました。族の外に出ると動きます。使ったのは §07 と同じ発想です——自己相似な続きを途中で切って、Behrend 型のブロックに乗り換える。k=3 で Wróblewski が Szekeres 集合に対してやったことを、k=4 で Walker の集合に対してやりました。

なぜ継げるのか — 補題が一つ

ブロックを継ぐとき、下の窓の一点と上の窓の k−1 点からなる k-AP が問題になります。Tao はこの問題のフォーラム（2025 年 9 月）でこの穴を指摘し、確率的に間引いて塞いでいますが、それでは数値の下界には使えません。次の補題は、同じ穴を損失なしに塞ぎます。

補題（k ≥ 4）。頭が k-AP-free、各ブロックが (k−1)-AP-free、各ブロックの最小元がそれより前の全体の最大元の 2 倍より大きい（倍加税）ならば、和集合は k-AP-free。窓の長さに条件はない。

証明は場合分けで一頁です（頭とブロックの境目をまたぐ隣接対があれば、公差は境目の幅以上になり、二項目が頭からはみ出す）。k=4 では、ブロックは 3-AP-free で足ります。つまり §07 で使った Wróblewski のブロックが、そのまま使えます。k=3 に戻すと、条件は Wróblewski の倍加税 a > max(2z, z+t) と一致します。この補題は Lean 4 で証明されています（Shiori1109.lemma2_four、sorry なし、標準三公理のみ）。

なぜ超えるのか — 尾の落ち方

ケンプナー集合の尺度 z より上の尾は z^−β で落ちます（Walker の集合では β = 0.240）。Behrend 型ブロックの尾は exp(−c√log z) でしか落ちません。後者はいずれ前者より濃くなるので、十分先で切って乗り換えれば、どの k についても、どの k-AP-free ケンプナー集合 K についても、f(k) > H(K) が厳密に成り立ちます。Walker の Theorem 2.1 は f(k) がケンプナー集合の上限であることを言いますが、その上限はケンプナー集合では達成されません。k=3 では、この論法がそのまま Wróblewski 1984 の構成（Szekeres を 2.15×10⁷ で切って Behrend に継いだ）の説明になっています。

固定した尺度で次元を比べると k=4 には効かないように見えますが、それは見立ての側の誤りです。Behrend 型ブロックの次元は p とともに上がり（p = 400 で 0.897）、Walker の 0.7597 を超えます。ただし k=4 の頭は k=3 の頭（Szekeres、β = 0.369）より良いので、乗り換えの尺度が 10⁷ から 10³⁰ へ押し出されます。頭が良すぎて、機械の出番が遅れる——差が 8 桁目にしか出ないのはそのためです。

どこまで厳密か — k=3 と同じ水準

集合そのものが 4-AP-free で、逆数和が 4.439753474215620 を超えることは、Lean 4 の定理です（Shiori1112.setA4_apfree_and_lower、記録 4.439753369254541 を超える形は setA4_apfree_and_beats_walker。sorry なし、native_decide なし、標準三公理のみ）。Leanここは分けて書きます。Lean の外に残るのは二点で、Walker の集合の逆数和の値そのものと、頭が Walker の集合の切り詰めと等しいことです。

段の表（38 行、すべて整数）、計算スクリプト、そして Lean の検証環境一式（k=3 の配布物に k=4 の 19 本を重ねた tar.gz）は証明書の置き場にあります。表の内部整合と「記録を超えている」ことは標準ライブラリだけの検算で、集合そのものの主定理は Lean で確かめられます。

この節の限界

• 差は 8 桁目です。7 桁目より上で動かすには、Walker の探索（無条件で b ≤ 88、刈り込み付きで b ≤ 200）を超える桁集合 S が要ります。尾の側で残っているのは 9〜10 桁目だけです
• 段の選び方（ベルマン）の最適性は主張しません。選び方に使った見積りは浮動小数ですが、下界の正しさには関わりません
• 頭の逆数和の Lean 下界は、切り捨ての葉（k=3 と同じ方法）では精度が出ませんでした（必要な深さで葉が数千万、30 時間の見込み）。四項の展開 1/(1+u) ≥ 1−u+u²−u³ をモーメントの漸化式で証明して葉に使い、深さ 1、13,545 葉、取りこぼし 9.9×10⁻¹¹ で押さえています。方法を替えて通ったのであって、問題が軽かったのではありません

動いた宿題の現在地は 残っていること にある。ここには現時点の未決だけを置く。

現時点の未決

出典と再現

この記事の §07 以外に、新しい数学はありません。使った定理と、Wróblewski の構成の枠組みは公表されているものです。「書かれていないかもしれない」と書けるのは二箇所だけで、どちらにも但し書きが付きます。

この問題は、無作為の抽選で当たったものです。

仕組みの違う探索が六通り、同じ値を返す——それは、その点が本当に最大であることの強い示唆です。ただしその確信は、課した条件の内側でしか成り立ちません。条件の外に、42年前の記録があります。