Microsoft Research 研究人員證明 Kannan–Lovász–Simonovits（KLS）猜想，解決 31 年數學難題

Microsoft 研究人員與合作者結合新的數學思路與由人類主導的 AI，解決高維幾何與機率中的一個核心問題

簡介

• 基礎科學重大突破：研究人員解決了 Kannan-Lovász-Simonovits (KLS) 猜想。這個提出了 31 年的問題，被廣泛視為高維幾何領域最核心的未解問題之一，並對統計學、最佳化、演算法及電腦科學具有深遠影響。
• 普遍幾何原理：研究成果為對數凹分佈確立了一項普遍幾何原理，指出簡單的平面切割可以在固定倍數範圍內捕捉其最狹窄的瓶頸，不受維度影響。 
• 人類與 AI 協作：這項突破源於一個由人類主導的代理式研究流程：AI 系統探索數學上的可能性，研究人員則評估、篩選並重新引導搜尋方向。
• 獨立確認：多名獨立研究人員已驗證這項研究，並指出其核心判準是關鍵突破；其後亦完成了經機器核查的形式驗證。 

數十年來，一個關於在高維空間中進行計算有多困難的根本問題一直未能獲得證明。最新研究解決了這個問題，消除了一項重大的理論障礙，有助理解科學與計算領域所用隨機演算法的效率。

Kannan–Lovász–Simonovits (KLS) 猜想於 1995 年提出。它探討的是：對一大類高維機率分佈而言，最佳的平面或超平面切割是否總是幾乎與任何形狀的最佳切割同樣有效。更精確地説，KLS 猜想預測兩者之間的差異不會超過某個普遍常數，不論維度有多少。這將確立一項與維度無關的幾何原理，對高維幾何、機率及理論電腦科學具有重要意義。由於這些切割的幾何形狀決定了隨機漫步探索某個分佈的速度，KLS 亦在高維抽樣理論中佔有核心地位。

自 1995 年以來，數學家累積了支持猜想成立的證據，但一直未能找到完整證明。如今，包括 Microsoft Research 機器學習與最佳化組的 Xinzhi Zhang 在內的兩名研究人員，已證明 KLS 猜想（在新索引標籤中開啟）。他們證明，無論形狀有多少維度，兩者之間的關係都存在一個固定上限。在這項研究之前，已知的最佳結果（在新索引標籤中開啟）於 2026 年 7 月確立，當時的上限會隨維度增加而緩慢上升。這項研究確立了一項基礎幾何原理：高維空間比以往所知的更有規律，而隨著維度增加，探索這些空間的障礙不會無限增大。 

KLS 猜想的重要性早在問題獲得解決前，已獲整個領域認可。在 2017-18 年度報告中，Mathematical Sciences Research Institute (MSRI)（在新分頁開啟）稱之為「高維凸幾何中的核心未解問題」。Simons Institute（在新分頁開啟）形容它是「凸幾何中最重要的未解問題之一」。在2022 年國際數學家大會（ICM）（在新分頁開啟）的會議論文集中，Ronen Eldan 指出，這個猜想對高維凸幾何和計算幾何有廣泛影響。Quanta Magazine（在新分頁開啟）指出，KLS「是統計學和電腦科學許多問題的核心」。

技術細節

作者首先改進了 2026 年 7 月的結果，以令數學界限更加精確。他們在有系統、由人類主導的流程中與 AI Agent 合作，探索了超過 100 種候選方法，其中許多涉及以高階張量進行冗長計算。這得出一項新的數學判準，並成為最終證明的基礎。

作者其後發現，新的判準可以遞迴應用。每個改進後的界限都可以代回同一論證，以得出更緊的界限。在論文的 2026 年 10 月 1 日版本中，這將對維度的依賴降至迭代對數。這個函數的增長極其緩慢，但仍會隨維度增加而增長，因此尚未完全解決這個猜想。

最後一步是重複整個遞迴改進過程，而非只應用一次。這個想法受到作者早前有關線性規劃快速演算法的研究啟發。作者證明，每個階段引入的小誤差會以足夠快的速度縮小，令誤差總和仍受一個通用常數所限，且不受維度影響。這消除了對維度數目的依賴，並在論文的 2026 年 10 月 4 日版本中完成了證明。

遞迴方法、重複應用該方法，以及證明累積誤差仍然有界，都是研究人員的原創貢獻。AI 工具協助探索候選方法、進行詳細推導、準備論文稿，以及執行內部證明檢查。研究人員決定數學研究方向、選出有前景的想法、將其組合成最終論證，並驗證證明。

獨立驗證

作者發表完整證明的同一天，另一組頂尖專家也發表了完整證明（在新分頁開啟），該證明是他們同步開展研究所得。他們的研究建基於 Microsoft 論文第一個版本（在新分頁開啟）中的發現，並稱之為「證明中的關鍵一步」。同日另行發表的第三份證明（在新分頁開啟）則採用了密切相關的想法。此外，其後亦發布了Lean 4 形式化證明（在新分頁開啟），結合了 Microsoft 論文第一個版本中的關鍵判準與其他研究成果。 

獨立證明是數學中最有力的驗證方式之一，因為它們表明某項結果並非只依賴單一推理鏈。隨後出現的其他方法及形式化驗證，進一步增強了人們的信心，讓人相信數學界發現的是真正的底層原理，而非脆弱的技術性論證。作者亦已縮短證明，並在 Lean 中驗證精簡後的論證；他們計劃在最後審核後發布兩者。這些進展合起來提供了互補的確認方式。

人類與 AI 協作引導

在證明 KLS 的過程中，這項研究亦展現了由研究人員引導 AI 的力量，而不是單純要求 AI 透過前沿模型或 Agent 的單次端到端執行來解決複雜問題。作者採用了 Agent 式搜尋流程，進行反覆、由人類協助的「剪枝」：多個 Agent 平行探索某個想法的不同變體時，研究人員會檢視其中間結果，剔除沒有希望的方向，並把最有希望的結果交給下一輪。關鍵突破出現前，研究團隊探索了約一百條研究路徑。 

在項目的另一條研究線上，作者曾多次嘗試在沒有引導的情況下，使用數個領先 AI 模型解決同一問題，所用的 token 總預算大致與主要流程相同。這番嘗試未能達成目標。最終成功同時有賴 AI 系統的能力，以及研究人員的數學判斷力。 

結論

總括而言，KLS 問題的解決，為高維幾何中的一個核心問題作出了定論。許多原本須以該猜想為前提的結果，現在都可以在不附帶條件的情況下陳述。因此，這項證明為凸幾何、機率論及理論計算機科學的研究提供了更穩固的基礎。

這項研究亦顯示，經審慎引導的人類與 AI 協作，如何在強化而非取代人類洞見的同時，為真正的科學發現作出貢獻。它突顯了科學判斷力在辨識有前景的方向、看出概念之間的聯繫，以及察覺初步洞見何時指向更深層結果方面，仍然十分重要。作者現正簡化證明並擴展其形式化驗證，讓數學界和理論計算機科學界更容易檢視這項結果，並在此基礎上繼續研究。

鳴謝 

感謝共同作者 Zhao Song 對這項研究的貢獻，也感謝 Victor Reis（在新分頁開啟） 和 Ishai Menache 在整個項目期間提供寶貴意見。 

在新分頁開啟

這篇文章最初刊登於 解決數學界 31 年來的重大挑戰——KLS 猜想，刊載平台為 Microsoft Research。