数学プレプリント理論1分で読めます

AIの証明を、人間のために描き直す

いくつかの点を描き、そのうちのいくつかを線で結ぼう。数学者はこれをグラフと呼ぶ。点は頂点、線は辺であり、ある点に接する線の数をその点の次数という。木とは、ループをもたず一つながりになっているグラフで、枝分かれした小枝のようなものだ。t個の点をもつ木には、必ずt − 1本の線がある。

1960年代初め、ポール・エルデシュ(Paul Erdős)とヴェラ・T・ショーシュ(Vera T. Sós)は単純な問いを立てた。グラフが与えられた大きさのあらゆる木を含むようになるには、何本の線があればよいのか。彼らの答えであるエルデシュ=ショーシュ予想は次のとおりだ。

グラフの平均次数がt − 2より大きければ、そのグラフはt個の頂点をもつあらゆる木を含む。

このしきい値はぎりぎりのものだ。t − 1個の点からなり、すべての点の組が結ばれた完全グラフのコピーをいくつか別々に用意してみよう。各点はちょうどt − 2個の隣接点をもつが、どの部分もt個の点からなる木を収めるには小さすぎる。難しさは平均という言葉にある。すべての点が少なくともt − 1個の隣接点をもっていれば、木を一枝ずつ苦もなく配置できるだろう。しかし平均は、個々の点については何も教えてくれない。何百もの隣接点をもつ点もあれば、ほとんどもたない点もあるかもしれない。

60年間の部分的な答え

論文で語られている歴史によれば、この問題は1962〜1964年にさかのぼり、どれだけの辺があれば特定のパターンが必ず現れるかを研究する数学の分野で中心的な問題となった。特殊な場合は次々に解かれた。星、パス、二重星、枝の少ない木などだ。1990年代初めには、アイタイ(Ajtai)、コムロシュ(Komlós)、シモノビッツ(Simonovits)、セメレディ(Szemerédi)の4人の数学者が非常に大きな木についての証明を発表したが、最近の論文が指摘するように、完全な原稿が公表されることはなかった。さらなる部分的な結果が2021年、2024年、2026年に得られた。2026年9月4日には、リード(Reed)とスタイン(Stein)が大きく密なグラフについての証明を公開し、AIを使わずに開発したと述べている。

そこへ、ある報告が現れた。2026年9月、トム・アダムチェフスキ(Tom Adamczewski)とトーマス・ブルーム(Thomas Bloom)は『FrontierMath Erdős』という文書の中で、予想全体の証明を、AIモデルGPT-6 Astraの公開前バージョンによるものとした。元の数え上げの議論は公開されており、付属するリポジトリには、AIが自律的に証明を探索した記録と、証明検証言語Leanによる形式的な検証が記録されている。報告の著者たちは、人間の専門家に、より詳しく伝統的な形の解説を書くよう呼びかけてもいた。

グラフを一度に一点ずつ明かす

カリフォルニア州立大学サクラメント校のジェイ・カミングス(Jay Cummings)は、その呼びかけに応えた。27ページの彼の論文は、AIによる中心的な数え上げの議論はそのままに、その語り方を変えている。

  1. グラフを少しずつ明かす。 頂点をある順番に並べ、すでに示された頂点どうしを結ぶ辺とともに、一つずつ明らかにしていく。
  2. より多くを求める。 木の任意のコピーではなく、選ばれた「根」がまさに最初の頂点にあるコピーを探す。より多くを求めることで、証明がかえって簡単になる。
  3. 早い隣接点を数える。 これは、そうしたコピーが現れる前に姿を見せる、最初の頂点の隣接点のことだ。あらゆる可能な順番について、それらを足し合わせる。
  4. 合計を抑える。 頂点や順番の中のまとまった区間を入れ替える操作(いつでも元に戻せる操作)によって、カミングスは、すべての順番について平均すると、早い隣接点が多くともt − 2個しかないことを示す。

最後のステップは短い。もしグラフに木のコピーが含まれていなければ、最初の頂点の隣接点は、どの順番でもすべて早い隣接点になるはずだ。すべての順番で平均すると、それはちょうど平均次数になる。仮定により、それはt − 2を超えている。矛盾である。木はそこに存在しなければならない。

この証明は、次数がどう分布しているかではなく、その合計しか使わない。カミングスは確率論的なバージョンも示し、4個と5個の頂点をもつ木について、具体的なグラフ上で詳しく解説している。

証明の絵本

論文には32枚の図が収められている。最後は古典的な帰結で締めくくられる。完全グラフのすべての線をq色で塗ると、グラフがq(t − 2) + 2個の頂点をもてば、ある一色は必ず与えられた木を含む、というものだ。末尾の声明でカミングスは、この文章をChatGPTとの長い対話の中で練り上げたこと、新しい提示の仕方のアイデア(早い隣接点、明示的な分割、図)は自分のものであること、そしてすべてを自分で確認し、全責任を負うことを説明している。

彼は自身の解説を、リオーダン(Riordan)とスコット(Scott)、ウッド(Wood)、フレデリクソン(Frederickson)による他の最近の解説と比較し、この手法がすでに向きのあるネットワークや「ハイパーグラフ」に拡張されていること、その拡張の一部もGPT-6 Astraによるものとされていることを指摘している。彼の貢献は、本人の言葉によれば、「読者を中心にすえた、議論の視覚的な解説であり、予想の新たな解決ではない」。