Microsoft Research、31年未解決のKLS予想の証明を解説　研究者の選別でAI探索100超の候補を絞り込む

KLS予想（Kannan–Lovász–Simonovits予想）は、等方的な対数凹確率測度と呼ばれる広い分布のクラスについて、境界の切り口を測るCheeger定数が次元によらず普遍的な定数で下から抑えられるかを問う問題です。切り口の幾何はランダムウォークが分布をどれだけ速く回れるかを決めます。ここから高次元サンプリングや最適化アルゴリズムの理論との関係が生まれます。2026年7月時点の最良既知結果では、上界が次元とともに緩やかに増える状態が残っていました。

論文「An O(1) Bound for the KLS Constant」（arXiv:2610.01447）は、2026年10月1日版で次元依存を反復対数まで減らしました。反復対数は極端にゆっくり増える関数ですが、増え続ける点は残ります。最後の一歩は、改良を一度でなく繰り返し適用する発想です。各段階で生じる小さな誤差の合計が次元によらず有界に収まることを示し、10月4日版で予想を解決しています。この再帰的な手法と誤差評価は研究者自身の貢献だと説明されています。

研究過程は人間が指揮するエージェント探索でした。複数のエージェントが一つのアイデアの変種を並列に調べ、研究者が途中結果を吟味して見込みの薄い方向を刈り込み、有望な結果を次のラウンドへ渡します。鍵となる判定条件が現れるまでに100超の候補アプローチを探索し、多くは高階テンソルを扱う長い計算を含みました。別系統の試みとして、主要なAIモデルに同じ問題を誘導なしで解かせる試行も同程度のトークン予算で繰り返しましたが、目標には届きませんでした。使用したモデル名と予算の総額は公表されていません。

証明の確からしさは複数の別ルートで補強されています。10月4日、Pierre Bizeul、Boaz Klartag、Joseph Lehecのグループが別の証明をarXiv（2610.05474）で公開しました。要旨は、SongとZhangによるtilt平均の高階導関数に関する判定条件を「証明における決定的な一歩」と位置付けています。彼らの議論はSong–Zhangと独立に構成されたものの、判定条件は利用しており、完全に無関係な発見ではありません。10月6日にはBalasubramanian氏とKasiviswanathan氏が、次元非依存のPoincaré定数評価（定数25以下）を別の方法で示す論文（arXiv:2610.07728）を公開しました。

Hongru Zhao氏によるLean 4形式化「KLS500」も公開されています。Poincaré定数500以下の次元非依存評価を機械検証したもので、BizeulらのアプローチにSong–Zhangの判定条件を組み合わせた構成です。Song–Zhang本人の証明の形式検証ではありません。Zhang氏とSong氏は証明を短縮し、そのLean検証も済ませたうえで、最終レビュー後に公開する予定だと説明しています。

解決の意味は理論面にあります。KLS予想を仮定して主張されてきた幅広い結果は、無条件の定理として言い直せます。サンプリングや最適化のアルゴリズムに理論的な前提を与える一方で、具体的なソフトウェアや製品の性能が上がることが実証されたわけではありません。arXiv公開は査読済みの学術誌掲載と同義ではなく、第三者による検証はこれから進みます。「AIが31年の難問を単独で解いた」という表現は、公開された説明と一致しません。途中経過の吟味、仮説の管理、探索の打ち切り判断といった作業を研究者が担い、AIはその指揮下で探索と計算を広げた、というのが著者自身の説明です。

焦点は、本人らの短縮版とLean検証版の公開、複数の証明の相互比較、KLS予想を仮定していた理論結果の無条件化がどこまで進むかです。研究プロセスの再現性を評価するには、使用モデルや探索予算の追加開示が鍵になります。