Komlós 猜想近 30 年首个重大进展：Bansal + Jiang 用「砍半」算法把”高维失衡难题”压到常数边缘，组合差异理论的”圣杯”突然变得不再疯狂

2025 年秋季，密歇根大学理论计算机科学家 Nikhil Bansal 与芝加哥大学理论计算机科学家 Haotian Jiang 联合宣布，组合差异理论中”圣杯级”难题 Komlós 猜想取得近 30 年来的第一个重大进展。他们给出了一个上限，这个上限随维度变化的速度慢得不可思议——即使维度数量达到天文数字，这个上限也仅仅与一个普适常数相差毫厘。其他研究者把这项工作描述为”非常令人兴奋””一个漂亮的结果””巨大的进步”。这项成果尚未完全解决 Komlós 猜想（猜想本身要求”差异上限是个固定常数，与维度无关”），但它提供了迄今为止最有力的证据——也许 Komlós 当年那个”不负责任”的猜想其实是真的。

这件事的重量，需要先回到 1980 年代。

那个”不负责任”的猜想

János Komlós 在 1980 年代初提出了一个听起来不像真的反直觉猜想：

> 无论你考虑多少个对象（比如 12 个知识竞赛爱好者），或者多少个维度（比如希腊神话、大学篮球、地理、音乐等多个知识类别），差异——它是可以量化的——永远不会超过一个常数。

用人话说：你可以把任意 N 个”向量”（每个人有自己的强项弱项组合）分成两队，存在某种分队方法，让两队在所有维度上的”失衡程度”被控制在一个固定常数以内，与 N 无关、与维度数无关。

这个猜想如果成立，将颠覆所有人的直觉——通常认为维度越多越难平衡，Komlós 却说有一个”普适常数”在兜底。

Komlós 本人已经在邮件里自嘲：”我提出它的时候又年轻又愚蠢。我用这个不负责任的猜想，给组合差异理论扔了一颗炸弹。”

30 年只前进了两次

过去 30 年，Komlós 猜想仅两次显著推进：

– 1985：Joel Spencer（纽约大学）把差异上限拉到 O(log N)（对数增长）。 – 1998：Wojciech Banaszczyk 把上限推到 O(√log N)（开方对数增长）。

这两次进步都依赖”维度”参数：维度越高，上限仍然会缓慢增长，离 Komlós 想要的”普适常数”还差得远。整个领域一度认为这个问题无法继续推进——许多研究者认为精确解根本不存在。

砍半法的关键思路

Bansal 在 2010 年想出一个看似”反常识”的方法：把每个向量一分为二。

> “我可以把一个人劈成两半。”Bansal 在 Quanta Magazine 报道中说。

传统思路是把每个向量整体分配给某一队（坐标全部乘 +1 或 -1），Bansal 的方案是把向量”砍半”——一半给 A 队、一半给 B 队，然后用一套随机过程逐步”修复”这种拆分，让每个向量的最终归属慢慢收敛到某一队。

关键是这个”砍半 + 修复”的全过程中，差异不会爆炸。Bansal + Jiang 证明：即使维度达到天文数字，最终的差异上限增长速度极慢，慢到只比常数”差一根头发丝”。

芝加哥大学 Haotian Jiang 是这个方向的另一位关键人物，他的博士论文和后续工作与 Bansal 共同打磨出最终方案。其他研究者 Aleksandar Nikolov（多伦多大学）评论：”我以前倾向于认为猜想是错的，现在这项工作让我更确信猜想可能是真的。”

为什么”差一根头发丝”很重要

数学界普遍认为，要从”几乎常数”过渡到”严格常数”通常需要新的核心想法。1998 年的 O(√log N) 与”常数”之间是一个”质的鸿沟”，2025 年的结果把这个鸿沟压到”量的差距”。这意味着：

– 几乎所有依赖”差异理论”的算法和应用都可以用这个新上限替换旧上限。 – 未来 6-12 个月，极有可能出现把这个”一根头发丝”补成”严格常数”的二次突破。 – Komlós 猜想从”看起来不真”变成”看起来很可能真”。

这项工作的方法本身也具有独立价值：把复杂的高维问题”砍半 + 修复”为可处理的小问题，这种思路与机器学习中”分治 + 组合”的算法思路有天然共鸣。

跨学科的连带影响

组合差异理论的应用横跨运筹学、计算机科学、机器学习、统计学等多个领域：

– 运筹学：公平分配、调度优化、运力分配（如把乘客公平分给两辆班车）。 – 机器学习：低秩矩阵分解、采样算法、随机梯度方法的稳定性。 – 统计学：实验设计、A/B 测试中的协变量平衡。 – 理论计算机科学：通信复杂度、近似算法、随机化算法的去随机化。

如果 Komlós 猜想最终被严格证明，这些领域都会拿到更紧的上界和更好的算法保证。即使只是 2025 年的”近常数”结果，也已经足以让多个子领域的论文重写收敛速率证明。

一句话总结：30 年来第一次有人”看清”了 Komlós 的边界

数学界上一次关于差异理论的重大推进，要追溯到 1998 年 Banaszczyk 的 O(√log N) 工作。整整 27 年后，Bansal 和 Jiang 用一种”砍半 + 修复”的算法思路，把上限压到”几乎常数”的位置。这不是终点，但是起点——它告诉所有在猜想外部怀疑 Komlós 的人：你怀疑的那个人，可能比你想象的更接近真理。

数据点

– 1980s 早期：János Komlós 提出猜想（差异上限 = 普适常数，与维度无关） – 1985：Joel Spencer 把上限推到 O(log N) – 1998：Wojciech Banaszczyk 把上限推到 O(√log N) – 2010：Bansal 提出”砍半 + 修复”算法思路 – 2025 秋季：Bansal（密歇根大学）+ Jiang（芝加哥大学）联合宣布近 30 年首个重大进展 – 新上限：随维度变化极慢，即使天文级维度也仅与常数相差毫厘 – Aleksandar Nikolov（多伦多大学）：以前倾向猜想假，现在更倾向猜想真 – Komlós 本人自嘲：”年轻时又年轻又愚蠢” – 应用领域：运筹学、计算机科学、机器学习、统计学、组合数学 – 同行评价：”非常令人兴奋””一个漂亮的结果””巨大的进步” – 论文应发在 Annals of Mathematics 或 Inventiones Mathematicae 级别（具体期刊待官方公告） – 持续观察：12 个月内是否有”从几乎常数到严格常数”的二次突破