Theo Conjectureが35年前の数学問題を解決し、誰も予測しなかった項を発見

ブログ AIシステム「Theo Conjecture」が35年前の数学予想を解決、誰も予測しなかった項を発見 FirstPrinciples 2026年7月29日•4分で読めます 共有 ニュースレターを購読する ありがとうございます！送信が完了しました！ エラー！フォームの送信中に問題が発生しました。 1980年代、Graffitiというプログラムが誰も考えつかなかった質問を投げかけ始め、そのうちの一つがPaul Erdősの注目を集めました。約40年後、Randy Davilaはその同じ質問を、ループで数学的アイデアを提案、テスト、改訂する自動発見システムであるTheo-Conjectureに託しました。返ってきたのは、Erdősとその共同研究者が推測していた答えの証明、誰も予測しなかった予期せぬ追加項、そしてAIエージェントと人間の数学者が協力して問題を解決する様子の一端でした。 ここに、頭に思い浮かべるべき絵があります。2から30までの整数をそれぞれ点として描いてください。2つの数が1より大きい共通の因数を共有する場合、それらの点間に線を描きます。例えば、6と10は両方とも2で割り切れるので接続され、15と25は両方とも5で割り切れるので接続されます。 共通約数グラフ G₃₀。 頂点は2から30までの整数であり、共通の因数を持つ場合に結合されます。金色のエッジは素数頂点に接続し、青灰色のエッジは合成数頂点同士を結合し、10個の金色の素数頂点は互いに接続せず、最大の独立集合を形成します。 最終的に得られるのは、数学的な意味でのグラフ、つまり線（エッジ）で結ばれた点（頂点）の集まりです。素数を金色に塗りつぶしてください。金色の点は互いに触れ合うことはありません。なぜなら、異なる2つの素数が共通の因数を共有することはないからです。 驚くべき点？素数は単なる unconnected dots の集まりではありません。それらは、互いに接続のない点の最大のグループを形成します。数学者たちは、このようなグループに名前を付けています - 独立集合です。素数がこのコンテストで勝つ理由を見る価値があります。任意の独立集合を選んでください。その中の各数は、他のどの数とも互いに素でなければなりません（それが「共通の因数がない」という意味です）。次に、各数から1つの素因数を取り出します。それらの数は因数を共有しないので、取り出した素因数はすべて互いに異なる必要があります。つまり、素数の数よりも多くの数を独立集合に集めることは決してできません。数式で書くと次のようになります： α(Gₙ) = π(n) ここで、Gₙは2からnまでの整数から構築されたグラフ、α(Gₙ)はその最大の独立集合のサイズ、π(n)は古典的な素数計数関数、つまりnまでの素数の個数です。 これはそれ自体で興味深い恒等式であり、素数を数える問題がグラフの問題に変わります。しかし、それはまた、グラフの構造上の算術演算のみを使用して迅速に計算できる、より奇妙なものへの扉を開きます。それは素数とは明らかに無関係な数です。 機能するはずのないショートカット（しかし機能する） グラフの最大の独立集合を見つけることは、一般的に計算が困難な問題です。なぜなら、スケーリングがうまくいかないからです。しかし、もっと簡単に手に入れられる数があります。それは頂点の次数、つまりそれに接続するエッジの数です。 次数を独立集合の最小値に変換するトリックがあります。これはHavel-Hakimi手順と呼ばれます。各頂点の次数を大きい順にリストします。最大の数を選び、dと呼び、それを消去し、リストの次のd個のエントリから1を引きます。再度ソートします。繰り返します。 最終的にはゼロしか残りません。それらを数えます。そのカウントはグラフの残差と呼ばれ、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と呼ばれる未解決問題のリストに入り、Conjecture 448となりました。 Erdősは、残差がn / log nという、素数計数関数と同じ速度で少なくとも速く成長することを示しました。グラフ理論家のWilliam Statonと協力して、彼は主要な定数をより正確に特定しました： ζ(2) − 1 = π²/6 − 1 = 0.644934... ここで、ζ(2)はリーマンゼータ関数のよく知られた値であり、数学で最も有名な未解決問題の中心にある関数と同じ関数です。Erdősは、同じオーダーの対応する上限を見つけることができるかどうかを尋ねました。Fajtlowiczは定数が2/3になるかもしれないと推測しました。しかし、Statonは異なる考えを持っていました。彼は、Erdős-Statonの下限は単なる下限ではなく、正確な答えであると仮説を立てました。Written on the Wallは彼の立場を明確に記録しています：「Bill Statonは、残差...が漸近的に(π²/6 − 1) n / log nであると考えている。」n = 10,000までの数値チェックはそれを裏付けました。しかし、誰も証明を提示しませんでした。少なくとも、誰もが見つけられる記録に残るようなものではありませんでした。 Dr. William A. “Bill” Staton III（出典：HT Media） 問題が再び持ち上がる Randy Davilaはグラフ理論家であり、FirstPrinciplesのテクニカルスタッフメンバーであり、ライス大学との学術的な関係を持っています。2016年以来、彼はFajtlowiczの元のプログラムのモダンな後継機であるTxGraffitiを構築してきました。コアアイデアはそのまま引き継がれ、すべての例とすべての不変量が、数学者がそれを見て、それを突き、そして反論できるほど明確に配置されています。 共通約数残差の問題は、1987年のFajtlowiczによる残差の実装から2026年のTheo-Conjectureの証明ワークフローまで、2つの時代の機械支援数学にわたって発展しました。 Davilaは共通約数グラフを独立に再発見し、そのデータをゼロから再構築しました。2025年に彼は計算結果とグラフを数論家のJeffrey Lagariasに送りました。Lagariasは、見つけにくいFajtlowiczの文書のセットをたどって質問を特定し、Fan Chungとの関連研究に言及しました。Chung自身の出版リストには、日付のないプレプリント「Bounds for Havel-Ha」が掲載されています。