Solving a 31-year-old grand challenge in mathematics – the KLS conjecture

解决一个持续31年的数学难题——KLS猜想 - 微软研究院

/.itemprop=publisher

/itemprop=image

解决一个持续31年的数学难题——KLS猜想

发布日期：2026年10月21日

作者：张新志，高级研究员

分享此页面

• 在Facebook上分享

• 在X上分享

• 在LinkedIn上分享

• 在Reddit上分享

• 订阅我们的RSS源

/#single-header

微软研究员与合作者结合新数学思想与人类主导的AI，解决高维几何与概率领域的核心问题

一目了然

• 基础科学突破：研究人员解决了Kannan-Lovász-Simonovits（KLS）猜想——这个持续31年的难题被广泛认为是高维几何领域最重要的未解问题之一，其突破对统计学、优化、算法和计算机科学具有深远影响。

• 普遍几何原理：该成果确立了对数凹分布的普遍几何原理，证明简单平面切割可以在固定比例内捕捉其最狭窄的瓶颈，且与维度无关。

• 人机协作突破：这一突破源于人类主导的智能体研究过程，AI系统探索数学可能性的同时，研究人员进行评估、筛选和调整搜索方向。

• 独立验证：多位独立研究者已验证该研究，确认其核心标准是关键突破，随后进行了机器验证的正式证明。

数十年来，关于高维空间计算难度的基本问题始终未能得到证明。最新研究解决了这个问题，消除了理解随机算法效率的重要理论障碍，这些算法广泛应用于科学和计算领域。

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

图1：正四面体上KLS猜想（简化版）的示意图。

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

Foundry Labs

/think

Foundry Labs 桥接了微软突破与能够将其付诸实践的建造者、科学家和好奇者之间的距离。

Foundry Labs

/.msr-promo__content

/.msr-promo__inner-wrap

在新标签页中打开

注入的促销内容

/.msr-promo

KLS 猜想的重要性在它被解决之前就已经被领域内广泛认可。在 2017-18 年度报告中，数学科学研究所（MSRI）（在新标签页中打开）称其为“高维凸几何中的核心开放问题”。西蒙斯研究所（在新标签页中打开）将其描述为“凸几何中最重要的开放问题之一”。在 2022 年国际数学家大会（ICM）（在新标签页中打开）的会议记录中，Ronen Eldan 指出该猜想对高维凸几何和计算几何具有广泛影响。《Quanta 杂志》（在新标签页中打开）写道，KLS 猜想“是统计学和计算机科学中许多问题的核心”。

技术细节

作者首先改进了 2026 年 7 月的结果，以使数学界限更加精确。他们通过结构化的人类主导流程与 AI 代理合作，探索了 100 多种候选方法，其中许多涉及高阶张量的复杂计算。这产生了一个新的数学标准，成为最终证明的基础。

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

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

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

独立验证

在作者发布完整证明的同一天，另一组领先的专家也发布了他们并行开发的完整证明（在新标签页中打开）。他们的工作基于微软论文第一版（在新标签页中打开）的发现，称其为“证明中的关键步骤”。同一天发布的第三篇证明（在新标签页中打开）依赖于一个密切相关的想法。此外，随后发布了 Lean 4 形式化（在新标签页中打开），将第一篇微软论文中的关键标准与额外研究相结合。

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

人类与AI的协作指导

在证明KLS的过程中，这项研究还展示了研究人员指导AI而非简单地让AI通过单次端到端运行前沿模型或代理来解决复杂问题的强大能力。作者采用了一种智能体搜索过程，结合了迭代的人工协助“修剪”：当多个智能体并行探索某个想法的不同变体时，研究人员会检查它们的中间结果，剔除前景不佳的方向，并将最有希望的结果传递到下一轮。在关键突破出现之前，大约探索了100条研究路径。

在项目的一个独立分支中，作者多次尝试使用几种领先的AI模型在无指导的情况下解决相同的问题，所使用的总token预算与主流程大致相同。那次尝试未能达到目标。最终的成功取决于AI系统的性能和研究人员的数学判断。

结论

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

这项工作还展示了精心指导的人类与AI协作如何有助于真正的科学发现，同时强化而非取代人类的洞察力。它突显了科学判断在识别有前景的方向、识别概念联系以及识别部分见解是否指向更深层结果方面的持续重要性。作者目前正在简化证明并扩展其形式化验证，以便数学和理论计算机科学界能够更轻松地检验该结果并在此基础上进行研究。

致谢

感谢我们的合著者赵松对这项工作的贡献，以及维克多·雷斯（在新标签中打开）和伊沙伊·门内奇在整个项目中提供的有益讨论。

相关出版物

卡片

KLS常数的O(1)界

认识作者

卡片列包装器

卡片主体

张新之

高级研究员

卡片页脚

了解更多

研究领域

• 人工智能

• 数学