Microsoft Research 证明 31 年前的 KLS 猜想

微软研究员与协作者将新的数学思想与人类主导的 AI 相结合，解决了高维几何与概率论中的一个核心问题

概览

• 基础科学突破：研究人员解决了 Kannan-Lovász-Simonovits（KLS）猜想，这是一个已有 31 年历史的问题，被广泛视为高维几何中最核心的未解问题之一，对统计学、优化、算法和计算机科学均有影响。
• 普适几何原理：该结果确立了 log-concave 分布的一条普适几何原理，表明简单的平坦切割能够在固定倍数内捕捉其最窄瓶颈，与维度无关。 
• 人机协作：这一突破源自一个由人类主导的智能体研究过程，其中 AI 系统探索数学可能性，而研究人员则评估、筛选并重新引导搜索方向。
• 独立验证：多位独立研究人员已对本研究进行了验证，认定其核心判据是关键突破，随后又通过了机器校验的形式化验证。 

数十年来，一个关于高维空间计算难度的根本性问题始终未能得到证明。新研究解决了这一问题，消除了理解科学与计算领域所用随机算法效率的一大理论障碍。

Kannan–Lovász–Simonovits（KLS）猜想于 1995 年提出。它追问的是：对于一大类高维概率分布，最佳的平坦切割或超平面切割是否总是几乎与任意形状的最佳切割同样有效。更确切地说，KLS 预测两者之间的差距不超过一个普适常数，与维数无关。这将确立一条与维度无关的几何原理，对高维几何、概率论和理论计算机科学具有重要意义。由于这些切割的几何性质决定了随机游走探索分布的速度，KLS 在高维采样理论中也扮演着核心角色。

自 1995 年以来，数学家们不断积累证据表明该猜想成立，但完整证明始终难以企及。如今，包括微软研究院机器学习和优化组的 Xinzhi Zhang 在内的两位研究人员证明了 KLS 猜想（在新标签页中打开）。他们证明，无论一个形状有多少维，这种关系都以一个固定界成立。在此工作之前，2026 年 7 月确立的最佳已知结果（在新标签页中打开）允许该界随维数增加而缓慢增长。这项工作确立了一条基本几何原理：高维空间的行为比此前已知的更为良好，而穿越它们的障碍并不会随着维数增加而无界增长。 

早在 KLS 猜想被解决之前，其重要性就已在整个领域得到公认。在其 2017-18 年度报告中，数学科学研究所 (MSRI) (opens in new tab) 称其为“高维凸几何中的一个核心未解问题”。西蒙斯研究所 (opens in new tab) 将其描述为“凸几何中最重要的未解问题之一”。在 2022 年国际数学家大会 (ICM) (opens in new tab) 的会议录中，Ronen Eldan 指出了它对高维凸几何和计算几何的广泛影响。Quanta Magazine (opens in new tab) 写道，KLS“处于统计学和计算机科学中许多问题的核心”。

技术细节

作者们首先改进了 2026 年 7 月的结果，以使数学界更精确。在结构化、由人类主导的流程中与 AI 智能体合作，他们探索了 100 多种候选方法，其中许多涉及使用高阶张量进行冗长计算。这产生了一个新的数学判据，成为最终证明的基础。

作者们随后发现，这一新判据可以被递归地应用。每个改进后的界都可以反馈回同一个论证中，从而产生一个更紧的界。在 2026 年 10 月 1 日版本的论文中，这将维度的依赖性降低到了迭代对数。这个函数增长得极其缓慢，但它仍然随维度增长，因此尚未完全解决该猜想。

最后一步是重复整个递归精化过程，而不是只应用一次。这一想法受到作者们此前关于线性规划快速算法工作的启发。作者们证明了每个阶段引入的小误差收缩得足够快，使得它们的总和保持在一个与维度无关的通用常数之内。这消除了对维度数的依赖，并在 2026 年 10 月 4 日版本的论文中完成了证明。

递归方法、其重复应用，以及关于累积误差保持有界的证明，都是研究人员的原创贡献。AI 工具帮助探索候选方法、进行详细推导、准备手稿并执行内部证明检查。研究人员确定了数学方向，选择了有前景的想法，将它们组织成最终论证，并验证了证明。

独立确认

在作者们发布完整证明的同一天，另一个由顶尖专家组成的独立小组发布了一份完整证明 (opens in new tab)，是他们并行开发的。他们的工作建立在微软论文第一版 (opens in new tab)的发现之上，称其为“证明中的关键一步”。同一天单独出现的第三个证明 (opens in new tab)依赖于一个密切相关的想法。此外，随后发布了一个Lean 4 形式化 (opens in new tab)，将第一篇微软论文的关键判据与额外研究结合起来。 

独立证明是数学中最有力的验证形式之一，因为它们表明一个结果并非建立在单一的推理链条之上。随后出现的替代方法和形式化验证进一步增强了人们的信心：该领域发现的是一条真正的基础原理，而非一个脆弱的技术论证。作者还缩短了他们的证明，并在 Lean 中验证了精简后的论证；他们计划在最终审查后发布两者。这些进展共同提供了互补形式的确认。

人类与 AI 的引导

在证明 KLS 的过程中，这项研究还展示了让研究人员引导 AI 的力量，而不是简单地要求 AI 通过前沿模型或智能体的单次端到端运行来解决一个复杂问题。作者使用了一种带有人工辅助迭代式“剪枝”的智能体搜索过程：当多个智能体并行探索一个想法的各种变体时，研究人员检查它们的中间结果，淘汰没有前景的方向，并将最有希望的结果传递到下一轮。在关键突破出现之前，大约探索了一百条研究轨迹。 

在项目的另一条独立路线中，作者使用几个领先的 AI 模型，以与主过程大致相同的总 token 预算，对同一问题进行了多次无引导的尝试。这项努力未能达到目标。最终的成功既取决于 AI 系统的能力，也取决于研究人员的数学判断力。 

结论

综合来看，解决 KLS 解决了高维几何中的一个核心问题。许多此前依赖于将该猜想作为假设的结果，现在都可以无条件地陈述。因此，这一证明为凸几何、概率论和理论计算机科学的研究提供了更坚实的基础。

这项工作还表明，经过精心引导的人机协作如何能够为真正的科学发现做出贡献，同时增强而非取代人类洞察力。它凸显了科学判断在识别有前景的方向、认识概念联系以及看出部分洞察何时指向更深层结果方面的持续重要性。作者目前正在简化证明并扩展其形式化验证，以便数学和理论计算机科学界能够更容易地审查这一结果并在此基础上继续发展。

致谢 

感谢我们的合著者赵松对本工作的贡献，以及 Victor Reis（在新标签页中打开） 和 Ishai Menache 在整个项目过程中的有益讨论。 

在新标签页中打开

文章 解决数学领域长达31年之久的重大挑战——KLS 猜想 最初发表于 Microsoft Research。