‘重大突破’在差异理论数学中

# “不平衡数学的重大突破” | Quanta 杂志 来源：https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/ 30年来，计算机科学家首次找到了更优的方法，将物体均匀分配到两个组别中。 将12位热衷于知识竞赛的爱好者分成两支对抗性队伍，并不需要数学博士学位。但考虑到每个人都带着独特的优势与短板：有人可能是地理通却对音乐毫无感觉，有人可能是自然爱好者却从不看电视，还有人可能是影迷却从不阅读书籍。要在两个阵营间平衡各种特质，难度会大大增加。 那么，如何才能让队伍在希腊神话到大学篮球的各类知识上，都达到势均力敌的程度？ 研究组合差异理论的学者们表示：你总能组建出出人意料地均衡的队伍。 差异理论是数学的一个分支，研究如何尽可能均匀地分配资源。如果一支知识竞赛队伍包揽了所有历史知识，另一支一无所获，这就是巨大的差异。 20世纪80年代初，数学家亚诺什·科姆洛什提出了一个反直觉的预测。他猜想：无论考虑多少对象或维度，差异——这个可量化的数值——都不会超过某个常数。总能找到一种分组方式，使差异低于该常数。 芝加哥大学理论计算机科学家江浩天表示：“这确实令人震惊。科姆洛什猜想表明这与问题维度无关，而是一个普适常数。” 虽然从未有人推翻该猜想，但因其过于惊人，部分数学家认为它必然错误。密歇根大学理论计算机科学家尼基尔·班萨尔指出，证明此猜想是“差异理论中的圣杯问题之一”。 即便猜想的提出者也认为这有些荒谬。现已退休的科姆洛什在邮件中调侃道：“提出这个猜想时我年轻无知。这个不负责任的猜想给组合差异理论添了堵。” 若科姆洛什猜想成立，将为差异理论及其他领域（如运筹学）的诸多问题提供答案。 但数十年来，证明似乎希望渺茫。数学家们进展甚微；1998年取得的最佳上界仍强烈依赖问题维度，远非常数。 转折出现在2025年秋季，班萨尔与江浩天宣布了该问题近30年来的首个重大进展。他们发现了一种极限，其随维度的增长速度极其缓慢，即便在天文数字的维度下也仅略偏离常数。其他研究者用“非常激动人心”“美妙的结果”“巨大飞跃”等词评价这项采用全新算法的研究。 虽然这一意外发现尚未彻底解决问题，但它为科姆洛什猜想提供了迄今为止最有力的证据。多伦多大学计算机科学家亚历山大·尼科洛夫表示：“我曾倾向于认为猜想错误，但这项新工作让我相当确信猜想可能成立。” 班萨尔与江浩天的解法展示了如何将极其复杂的系统简化为更易研究的形式，并为数学、物理学乃至机器学习提供了潜在应用洞见。 ## **分而治之** 科姆洛什等人研究的差异问题，核心是将物体集合分为两个子集。这好比将人分成知识竞赛队伍，或将二手车分配到不同场地，亦或将临床试验参与者分为治疗组与安慰剂组。 科姆洛什猜想将每个对象抽象为长度为1的单位向量。该向量由一组坐标定义，每个坐标衡量特定属性的强度。 假设你只关注图书和电影两类知识，每人可表示为下图中的向量（图略）： 马克·贝兰，塞缪尔·贝拉斯科/《Quanta 杂志》 现在为每个向量分配队伍：若归入A队，保持坐标不变；若归入B队，则将所有坐标乘以-1（相当于翻转向量方向）。 若能完美划分——使两队在图书和电影知识总量相等——则所有向量之和应为零，达到完美平衡。 但完美通常难以实现。问题转化为：你能多接近零？ 在四人示例中，穷举所有可能性很容易。若这样做，你会发现爱丽丝和鲍勃应归一队，卡拉和戴夫归另一队。（值得注意的是，队伍人数无需相等：只需通过向量加减，使其相互抵消。） 当向量数量和待平衡属性增多时，任务难度将急剧上升。然而科姆洛什提出了特别乐观的假说：无论向量或属性有多少，总存在一种划分方式，使向量和始终低于同一普适常数。 实践中该假说似乎远非如此。考虑一种简单策略：随机分配向量。这会导致差异随向量数量N的增长急剧上升。1985年，乔尔·斯宾塞提出了更优上界，将差异限制在N的对数之下；1998年，沃伊切赫·巴纳什奇克改进至√(log N)，也可写作(log N)¹⁄²。尽管这是重要进步，但差异仍随向量数量增长。科姆洛什提出的常数界限似乎遥不可及。 正因如此，计算机科学家开始介入。 ## **分割场景** 21世纪00年代末，差异问题开始吸引理论计算机科学家关注。班萨尔便是其中之一，他希望通过编写一系列逻辑步骤（即算法），在理论上让计算机执行以推进科姆洛什问题。 许多研究者认为此类算法不可能存在，他们认为精确求解问题无法实现。但班萨尔当时不知情，他认为这种无知是种幸运：“否则我不敢违背学界共识。” 2010年，他构想出一种算法。他首先将每个向量二分：例如将爱丽丝的向量<1, 0>拆分为A队的<½, 0>和B队的<½, 0>。“我可以把一个人劈成两半，”班萨尔解释道。随后通过随机过程逐步调整半向量，最终使一队获得完整的<1, 0>向量，同时控制每一步的差异增量。 他证明该算法（若在计算机上实现）能将差异控制在斯宾塞提出的log N界限内。加州大学洛杉矶分校研究差异算法的计算机科学家拉古·梅卡表示：“当时无人认为这可能实现，这完全跳出传统思维框架。” 2016年，班萨尔调整算法以达到巴纳什奇克的(log N)¹⁄²界限——当时的最佳纪录。 这项研究启发了其他学者以新视角思考差异问题。梅卡评价：“它为此前束手无策的问题提供了全新方法。” 班萨尔坦言：“作为计算机科学家，我们曾追赶那些聪明的数学家已证明的结论。”他开始思考能否将此新方法进一步推进——不仅匹配旧纪录，更要创造新纪录。 ## **关联起因** 2019年，班萨尔与当时在华盛顿大学读研的江浩天在会议上相遇。两人因对差异算法的共同兴趣结缘，数年后与梅卡等研究者共同证明了特定条件下的科姆洛什猜想。班萨尔与江浩天愉快合作，决定继续攻克完整猜想。 “我们合作默契，”班萨尔说，“我能抛出半成品想法，他能心领神会，反之亦然。” 2025年2月，江浩天到安娜堡拜访班萨尔。第二天他们便找到降低上界的突破口。 此前的算法着重控制差异随时间累积的增长。现在他们加入了额外限制。 差异本质上取决于多个维度。若两家车商分配新车库存时确保各颜色车辆数量相等，但某家获得更多敞篷车，后续再平衡敞篷车就会破坏颜色维度的均衡。差异效应无法局限在特定维度，班萨尔强调：“它们高度交织。” 班萨尔与江浩天试图挖掘隐藏的独立性。“最初讨论时觉得这想法很疯狂，”班萨尔回忆，“但尝试后发现并非如此。” 数月内他们实现了突破。新算法不仅衡量整体差异，还引入“依赖性”度量：随机扰动某属性时，其他属性的差异会如何变化？他们沿用班萨尔旧算法将向量二分，但新算法精心设计了调整半向量的过程以降低复合影响。“虽然属性表面相关，”班萨尔解释，“但我们可以调整它们使彼此不互相干扰。” 这使两人能更精确控制差异演化。最终算法保证：对于N个向量，差异最多为(log N)¹⁄⁴。 这是科姆洛什问题数十年来的首个改进。尼科洛夫表示：“我原以为已知上界就是最优解，只需证明无法突破。所以这个改进确实让我惊讶。” 耶鲁大学的丹尼尔·斯皮尔曼指出：“log N的四次方根非常小。在生活中你几乎找不到使(log N)¹⁄⁴超过5的数……对所有实际应用而言，这已相当接近常数。” ## **负责任的进展** 班萨尔与江浩天的改进验证了差异理论的核心洞见：即使完美平衡不可能，接近平衡不仅可行且具实用性。 差异理论可能迎来更多突破。匈牙利阿尔弗雷德·雷尼数学研究所的蕾妮·赫克强调，班萨尔与江浩天的算法具有高效性，这意味着研究者或可利用该算法解决差异理论的其他开放问题，以及优化理论、物理学、金融学等领域的难题。例如赫克正研究如何应用差异理论改进大型语言模型及其他机器学习系统。 此进展有望重燃对科姆洛什“不负责任”常数界限的探索。尼科洛夫与斯皮尔曼都表示对猜想成立有了新的信心。普适常数在数学问题中屡见不鲜，√(log N)也时而出现，但四次方根则罕见，这暗示当前界限并非最终答案。斯皮尔曼表示：“这类结果作为问题的最终答案极为罕见。” 班萨尔认为其自2010年起使用的算法策略可能无法彻底解决问题。“我们在四次方根处碰壁，”他坦言，“突破它必然需要全新方法。” 但这给研究者带来了希望。赫克表示：“我坚信终将有人证明此猜想。”