Theo Conjectureが35年前の数学問題を解決し、誰も予測しなかった項を発見
Theo Conjecture solves 35-year-old math problem, finds a term no one predicted (firstprinciples.com)
要約
AIシステム「Theo Conjecture」が、35年間未解決だった数学上の予想を証明しました。この予想は、1980年代にGraffitiというプログラムが提起したもので、Paul Erdősも注目していました。AIは、整数間の共通約数グラフにおける最大独立集合のサイズと素数の個数の関係を証明し、さらに誰も予測しなかった「余分な項」を発見しました。これは、AIと人間の数学者が協力して問題を解決する一例です。
全文翻訳
AIシステム「Theo Conjecture」が35年前の数学的予想を解決、誰も予測しなかった項を発見
1980年代に、Graffitiというプログラムが誰も考えつかなかった問いを投げかけ始め、そのうちの一つがPaul Erdősの注目を引きました。それから約40年後、Randy Davilaはこの同じ問いを、数理的アイデアを提案、テスト、修正するループで機能する大規模言語モデルに支えられた自動発見システムであるTheo-Conjectureに託しました。その結果、Erdősとその共同研究者たちが推測していた答えの証明と、誰も予測していなかった意外な追加項、そしてAIエージェントと人間の数学者が協力して問題を解く様子の垣間見ることができました。
頭の中でこの絵を思い浮かべてください。2から30までの整数を取り、それぞれを点として描きます。2つの数が1より大きい共通因数を共有する場合、その2つの点の間を線で結びます。例えば、6と10は、両方が2で割り切れるため接続され、15と25は、両方が5で割り切れるため接続されます。
[画像: 2から30までの頂点を含むネットワーク図。合成数は、目に見える青灰色のエッジを持つ、密なティール色のクラスターを形成しています。素数は金色で、外側に広がり、合成数の倍数と接続する金色のエッジがあります。注釈には、素数が最大の辺のない集合を形成し、G sub 30 のアルファが pi of 30 に等しいと記載されています。]
これにより、数学的な意味でのグラフ、つまり点(頂点)と線(辺)で結ばれたものが得られます。素数を金色に塗りつぶします。2つの異なる素数は決して共通の因数を共有しないため、金色の点は互いに触れ合うことはありません。
驚くべき点は何でしょうか?素数は単なる unconnected dots の集まりではありません。それらは、互いに全く接続のない最大のグループを形成しています。数学者たちはこのようなグループに「独立集合」という名前を付けています。素数がこのコンテストで勝つ理由を見る価値はあります。
グラフ内の任意の独立集合を選んでください。その中のすべての数は、それ自身の中の他のすべての数と互いに素でなければなりません(それが「共通の因数がない」という意味です)。次に、各数から1つの素因数を取り出します。それらの数は因数を共有しないため、取り出した素数はすべて互いに異なる必要があります。つまり、そもそも素数から引き出すことができる数よりも多くの数を独立集合に集めることはできません。数式で書くと次のようになります。
α(Gₙ) = π(n)
ここで、Gₙは2からnまでの整数から構築されたグラフ、α(Gₙ)はその最大の独立集合のサイズ、π(n)はnまでの素数の数を表す古典的な素数計数関数です。
これはそれ自体で興味深い恒等式であり、素数を数える問題がグラフの問題に変わります。しかし、それはまた、グラフの構造に関する算術演算だけを使用して素数とは明白な関係がない、数値を素早く計算できる、より奇妙なものへの扉を開きます。
機能しないはずのショートカット(しかし機能する)
グラフにおける最大の独立集合を見つけることは、一般的に、スケーリングがうまくいかないため、計算上困難な問題です。しかし、より簡単に取得できる数値があります。それは、頂点の次数、つまりエッジがそれに触れる数です。
次数を独立集合の最小値に変換するトリックがあり、Havel-Hakimi手順と呼ばれます。各頂点の次数を大きい順にリストします。最大の数(dとする)を取り、それを消去し、リストの次のd個のエントリから1を引きます。再度ソートします。繰り返します。
最終的にはゼロだけが残ります。それらを数えます。そのカウントはグラフの残差(residue)と呼ばれ、R(G)と表記されます。
残差の計算は高速であり、常に予測可能な方向で真実を下回ります。
R(G) ≤ α(G)
つまり、残差は、その集合を見つける必要なしに、最大の独立集合のサイズの下限を保証する、数秒で計算できる証明書です。これを素数グラフに適用すると、次のようになります。
R(Gₙ) ≤ π(n)
では、本当の質問は何でしょうか。この残差計算は次数にしか注目しません。どの頂点がどの頂点に接続しているかには注目しません。その単純化されたビューは、素数を数えるための正しいオーダーの大きさを捉えるのでしょうか?それとも、すべての構造的な詳細を捨てることで、答えも捨ててしまうのでしょうか?
その質問は驚くほど長い歴史を持っており、機械が独自に数学を提案しようとした最初の真剣な試みの一つから始まります。
Graffiti、Erdős、そして壁に残された問い
[画像]
Siemion FajtlowiczとPaul Erdős、1992年(出典:Jerry Grossmanのウェブページ)。
ヒューストン大学の数学者であるSiemion Fajtlowiczは、1980年代半ばにGraffitiというプログラムを開発しました。このプログラムは、グラフのライブラリとその数値的特性を保存し、それらの特性間の候補となる不等式を生成し、真実だが退屈なものを除外するためのヒューリスティックセットを使用しました。Fajtlowiczは単に公式を生成しようとしたのではなく、数学的ステートメントが数学者の時間を費やす価値があるものにする理由を理解しようとしていました。
Graffitiの予想は、数百の論文のインスピレーションとなり、Paul Erdős、Fan Chung、László Lovász、Paul Seymourのような数学者の注目を集めました。特にErdősは自然な適合者でした。彼は生涯の多くを共同研究者、具体的な例、数論と組合せ論の未解決問題の間を行き来して過ごし、Fajtlowiczはかつて、その男と機械の類似性を一言で要約しました。
「違いは何であれ、ErdősとGraffitiには共通点が一つあった:彼らのアイデアは例に深く根ざしていた。」
1987年11月、Fajtlowiczは残差をGraffitiの不変量として導入し、それが独立集合数を超えることは決してないと予想しました。Favaron、Mahéo、Sacléは翌年それを証明し、その証明は1991年に出版されました。その後Graffitiは整数上の共通因数グラフに焦点を移し、その問題はWritten on the Wallと呼ばれる未解決問題の実行リスト、予想448として掲載されました。
Erdősは、残差が素数計数関数と同じn / log nという速度で少なくとも速く成長することを示しました。グラフ理論家のWilliam Statonとの共同研究で、彼は主要な定数をより正確に特定しました。
ζ(2) − 1 = π² / 6 − 1 = 0.644934...
[画像: 青い襟付きシャツにネクタイをしたBill Statonが屋内の木製の壁の前に立っている。]
Dr. William A. “Bill” Staton III(出典:HT Media)
ここでζ(2)はリーマンゼータ関数のよく知られた値であり、数学で最も有名な未解決問題の中心にある関数と同じものです。Erdősは次に、同じオーダーの対応する上限を見つけることができるかどうかを尋ねました。Fajtlowiczは定数が2/3かもしれないと推測しました。しかし、Statonは異なる見方をしました。彼は、Erdős-Statonの下限は単なる下限ではなく、正確な答えであると仮説を立てました。Written on the Wallは彼の立場を明確に記録しています:「Bill Statonは、残差…が漸近的に(π²/6 − 1) n / log nであると考えている。」
n=10,000までの数値チェックはそれを裏付けました。しかし、誰も証明を提示しませんでした、少なくとも誰も見つけられる記録に残るようなものではありませんでした。
問題が再び持ち上がる
Randy Davilaはグラフ理論家であり、FirstPrinciplesのテクニカルスタッフメンバーであり、ライス大学との学術的提携を持っています。2016年以来、彼はFajtlowiczの元のプログラムの現代的な後継者であるTxGraffitiを構築してきました。コアアイデアはそのまま引き継がれ、すべての例と不変量が、数学者がそれを見て、それを突き、そして押し戻すことができるように明確に配置されています。
[画像: 1987年、1988年、1989年、1991年、2025年、2026年を示す水平タイムライン。残差の実装、一般的な不等式、Erdős-Statonゼータバウンドと予測、一般的な不等式の証明の公開、Davilaの再構築、および最新のAI主導の証明をたどります。]
共通因数残差問題は、Fajtlowiczによる1987年の残差実装から、2026年のTheo-Conjecture証明ワークフローまで、2つの時代の機械支援数学にわたって発展しました。
Davilaは共通因数グラフを独立に再発見し、そのデータをゼロから再構築しました。2025年、彼は計算とグラフを数論家のJeffrey Lagariasに送信しました。Lagariasは、見つけにくいFajtlowiczの文書セットをたどってこの質問を掘り起こし、彼自身がFan Chungと行った関連研究に言及しました。Chung自身の出版リストには現在、日付のないプレプリント「Bounds for Havel-Hakimi residues of non-coprime graphs」が掲載されており、Chung、Erdős、Lagarias、Statonと共同クレジットされていますが、関連する原稿や定理ステートメントは添付されていません。直接指摘する価値があるのは、この年表は非公開の書簡に基づくものであり、確定した歴史として扱う前にLagariasとChungに独立に確認されるべきであるということです。
それでも、この再構築は2つの有用なことを行いました。それは、予想が主張していたことを正確に確認し、真の進歩がどのようなものになるかを明確にしました。つまり、Erdős-Staton定数と一致する上限、理想的には主要項以上の何かです。
それが、DavilaがTheo-Conjectureループに投入した問題の形状です。Theo-Conjectureはチャットボットではなく、公式を吐き出す機械でもありません。それは、人間のアドバイザーがループに組み込まれた発見システムであり、大規模言語モデルがエージェントとして機能し、組合せ論的な予想エンジンを繰り返し呼び出し、正確な計算を実行し、進化する数学的メモリを更新していきます。
[画像: 5つのボックスが、オブジェクト、値、述語のレジストリから、Theo-Conjecture関係検索、LLMエージェント、正確な反例テスト、および人間によって監査された定理へと流れます。曲線的なフィードバック矢印は、失敗したステートメントがレジストリ行になり、新しい記述子がレジストリに戻ることを示しています。下部のボックスは、人間のアドバイザーの数学的判断を表しています。]
アドバイザー監督下のTheo-Conjectureループ。レジストリは検査可能なテーブルであり、その行は実行可能な数学的オブジェクトであり、列は定義された数値不変量またはブール述語です。LLMエージェントはレジストリを構築および改訂し、Theo-Conjectureを呼び出し、そのランク付けされた関係を解釈し、正確な反例検索を起動します。広範な手続き的自律性でこのサイクルを繰り返すことができます。人間のアドバイザーは目的、重要性、および証明の受諾を制御します。
すべての試みは、モデルが後で検索して構築できる実行中の記録に保持されます(失敗したものも含みます)。重要なのは、モデルがそう言ったから、あるいは多くの例に一致したからといって、何も証明されたとはみなされないことです。人間の数学者が承認するまで、それは真の結果とはみなされません。
それが、失敗が浪費ではなく有用になった理由です。アイデアが通用しなかったとき、それは記録に残され、次に試されることを形作ったのであり、静かに却下されるのではなく。
失敗から実際に学んだこと
システムの最初のアイデアは間違っていました。それは、ある範囲内の素因数が繰り返されない数の数を使って残差を説明しようとしましたが、予測は広く、そして増大する誤差を伴い、大きな値では739の誤差がありました。それはそのアイデアを完全に排除しました。
より良い一致は、Caro-Wei和と呼ばれる量から得られました。これは、特定の数が接続されているかではなく、各数がいくつの接続を持っているかに注目します。これを使用すると、古いζ(2) − 1定数が自然に導き出され、誰も予測していなかった2番目の項も追加されました。それでも、それは物語の半分、つまり下限しか証明しませんでした。ギャップを埋めるには真の洞察が必要であり、残差は接続されている特定の数ではなく、各数が持つ接続の数にのみ関心があることに気づきました。したがって、グラフ全体を再描画できます。ただし、各数が開始した接続数と同じ数を維持する必要があります。
[画像]
証明は、素数と合成数の遭遇を、同じ次数の素数頂点のクリークに置き換え、その後、他の場所で合成数の次数を修復します。すべての次数は保持されますが、再配線されたグラフはより単純な独立集合構造を持ちます。
その再描画がどのように見えるかを示します。同じ数の接続を持つ素数を、互いに接続されたタイトなクラスターにグループ化し、移動した接続を通常の合成数に吸収させます。素数がそのようにクラスター化されると、一度に1つしか選択できないことが簡単にわかります。これは、Statonが予測したまさにそのバウンドです。
結果
これらすべてを組み合わせることで、Statonの元の予測が証明され、誰も見つけられなかった2次項が追加されます。
R(Gₙ) = c₀ · n/log n + (c₀ − A) · n/log²n + O(n/log³n)
ここで
c₀ = ζ(2) − 1 および A = Σ(k=2 to ∞) log k / [k²(k−1)] = 0.3201986326...
これにより、極限で次のようになります。
R(Gₙ) · log n / n → ζ(2) − 1
平易な言葉で言うと、その定理は、高速で次数のみの計算が、nが増加するにつれて、真の素数カウントの固定された予測可能な割合を捉えていることを示しています。比率を反転させると、同じように明確に読めます。
π(n) / R(Gₙ) → 1.550546...
[画像: 折れ線グラフは、グラフ残差にlog nを掛けた値にnを割ったものの正確な青い値を、0.644934の破線水平線に向かって下降して示しています。赤い2項近似は青いデータを追跡しています。サイドパネルは、定数がゼータの2マイナス1であることを示しています。]
正規化された正確な残差は、(\zeta(2)-1=0.644934\ldots)に近づきます。赤い曲線は新しい2項漸近式を示しており、これは極限定数単独よりも有限サイズの接近をより正確に説明しています。
これを明確にするために、これが何ではないかというと、素数を数えるためのより高速な方法ではなく、リーマン仮説にも触れていません。しかし、ここでゼータ関数が登場するのは偶然ではありません。それは、素数除数の階層的で乗法的な構造を合計することから自然に導き出され、グラフ理論的な証明は、次数にしか注目しない残差が、なぜ同じ主要な振る舞いを捉えるのかを正確に説明しています。
2次項は、本当に新しい部分です。それは、残差が漸近的にどこに向かっているかだけでなく、有限グラフがその目的地にどれだけ速く近づくかを示しています。
よりタイトな謎、まだ未解決
これらすべてから出てきた特にクリーンな質問が一つあり、まだ解決されていません。n=10,000までの連続したすべてのテスト値、および100万までの散発的なチェックポイントで、残差は丸められたCaro-Wei和から2整数以上外れることはありませんでした。
⌈CW(Gₙ)⌉ ≤ R(Gₙ) ≤ ⌈CW(Gₙ)⌉ + 2
誰もまだそれを証明していません。もしそれが真実であれば、定理の現在の漸近誤差項を最大2のハードな絶対バウンドに置き換えることになり、現在の次数交換引数よりもはるかに正確にHavel-Hakimi手順の細かい振る舞いを説明することになります。
これの根底にある、より大きなポイントもあります。Graffitiの役割は関係を提案し、それを数学者に判断を委ねることでした。Theo-Conjectureは、同じ交換を実行可能な反復ループに変換します。そのレジストリは例と公式を保持しますが、失敗した予想、反例、放棄された表現、そして誰も完了していない証明義務も保持します。言語モデルは問題を再編成し、次に何を試すかを決定します。予想エンジンは規律ある幅を提供します。正確な計算は「いいえ」と言うことができます。そして人間のアドバイザーは、検索の目的と最終的な証明に対して責任を負い続けます。
FajtlowiczからErdősとStatonを経て、Davila、Lagarias、Chung、そして最終的にはTheo-Conjectureループへと線をたどると、機械が数学者を置き換える物語ではなく、数学的メモリが実際に実行可能なものになり、言語モデルが単独で推論しようとするのではなく、専門的な発見システムに繰り返し依存することで、真のてこ入れを得る物語になります。何十年も壁に残されていた問いは、ついにそれを異なる方法で読み取れる世代のツールを見つけました。
続きを読む
*Ermelinda DeLaViña、Some History of the Development of Graffiti (uhd.edu)
*Siemion Fajtlowicz、“On Conjectures of Graffiti,” Discrete Mathematics (1988)
*Randy Davila、“Automated conjecturing in mathematics with TxGraffiti” (arXiv:2409.19379)
*Paul Erdős biography、MacTutor History of Mathematics
Jeffrey Lagarias, University of Michigan
Fan Chung Graham's publication list、日付のない共通因数残差プレプリントリストを含む
Odile Favaron, Maryvonne Mahéo, and Jean-Francois Saclé、On the residue of a graph (Journal of Graph Theory, 15(1):39–64, 1991)
ここで説明されている定理と証明は、準備中の研究原稿に含まれており、まだ査読を完了していません。非公開の書簡に基づく歴史的主張は、編集ソースノートで明示的に特定されています。