内容来源：https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/

内容总结：

数学“失衡”难题获重大突破：近乎完美的平衡如何实现？

想象一下，要把12位知识渊博的 trivia 问答爱好者分成两支实力相当的队伍，这可不是简单的算术题。每个人都有自己的强项和短板：有人精通地理却五音不全，有人是自然百科但对电视一无所知，还有人痴迷电影却不爱读书。如何让两队在每个领域，从希腊神话到大学篮球，都势均力敌？

这听起来像是个趣味数学题，但它背后的“组合差异理论”（combinatorial discrepancy theory）却是数学和计算机科学领域的一个核心难题。该理论研究如何将资源尽可能均匀地分配。如果一支队伍囊括了所有历史知识，而另一支一无所获，这就是巨大的“差异”。

上世纪80年代初，数学家 János Komlós 提出了一个惊人猜想：无论你考虑多少个对象（比如选手）或多少维度（比如知识类别），这种“差异”的数值永远不会超过一个固定的常数。这意味着，总有一种方式能让你把队伍分得足够均匀，差异始终低于某个特定值。

这一猜想被学界视为“圣杯级”难题，但由于其颠覆性，不少数学家曾怀疑它是否正确。然而，在2025年秋季，来自芝加哥大学的理论计算机科学家蒋浩天（Haotian Jiang）与密歇根大学的尼基尔·班萨尔（Nikhil Bansal）合作，取得了近30年来该问题的最重大进展。他们的研究虽未完全证明猜想，但将差异的上限压缩到了一个极小的范围，仅比常数“高出一丝”，即使在维度天文数字般庞大的情况下也几乎可以忽略不计。这一成果被同行评价为“令人兴奋”、“一项美丽的结果”和“巨大的飞跃”。

这项突破的核心在于一种新颖的算法。过去的算法在分割向量（代表选手及其属性）时，难以避免多维属性之间的相互干扰。蒋浩天和班萨尔巧妙地在算法中加入了“依赖度”测量，他们设计了一种方式，使得在对各属性进行随机微调时，能够有效降低各维度之间的“联动效应”。通过这种方式，他们最终将差异上限压低到了 log(N) 的1/4次方（log(N)¼），这已是极小的数值，对于任何实际应用而言，几乎等同于常数。

这一进展不仅巩固了 Komlós 猜想的可信度，也为数学、物理学乃至机器学习领域提供了新的视角和潜在工具。研究者们普遍认为，虽然攻克完整猜想仍需全新的思路，但这项成果已经为最终证明带来了巨大希望。正如一位专家所言：“有人终将证明它。”

中文翻译：

在不平衡数学中迎来“巨大突破”

艾达·泽君·沈 供图/《量子杂志》

要把12位热心的 trivia 问答爱好者分成两支竞技队伍，并不需要有数学博士学位。但试想每个人都有自己的独特优势和短板：有人痴迷地理却对音乐一窍不通，有人是博物爱好者却从不看电视，还有人酷爱电影却从不读书。要在两支队伍之间平衡这些特质就难得多了。

那么，你究竟能把队伍组得多均匀，让它们在从希腊神话到大学篮球的每个类别上都拥有旗鼓相当的实力？

根据研究组合差异理论的学者的说法，你总能让队伍出人意料地均匀。

差异理论是数学的一个分支，研究如何尽可能均匀地分配资源。如果一支 trivia 队伍掌握了全部历史知识，另一支队伍一无所获，那差距就大了。

20世纪80年代初，数学家亚诺什·科姆洛什提出了一个反直觉的预测。他猜想，无论你考虑多少个物体（比如你的队员）或多少个维度（比如 trivia 的类别），这种差异——它是可以量化的——永远不会超过一个常数。总会有一种划分方式，使得差异低于这个精确的数值。

“这确实令人震惊，”芝加哥大学的理论计算机科学家蒋浩天说，“科姆洛什猜想说它与问题的维度无关。这是一个普适常数。”

从来没有人找到反驳这一猜想的方法。然而它如此惊人，以至于有些数学家认为它一定是错误的。证明它“是差异理论中的圣杯问题之一”，密歇根大学的理论计算机科学家尼基尔·班萨尔说。

甚至连猜想的提出者本人都觉得它有些荒谬。“我提出它的时候又年轻又愚蠢，”现已退休的科姆洛什在电子邮件中开玩笑说，“我用这个不负责任的猜想给组合差异理论扔了一个难题。”

如果科姆洛什猜想成立，它可能解开许多其他问题的答案，不仅在差异理论内部，也包括运筹学等领域。

但几十年来，证明看起来希望渺茫。数学家们未能取得太大进展；他们在1998年达到的最佳差异上限仍然严重依赖于问题的维度，远非常数。

然后，在2025年秋天，班萨尔和蒋浩天宣布了该问题近30年来的第一个重大进展。他们找到了一个随维度变化极其缓慢的上限，即使维度数量达到天文数字，也与常数仅有一线之差。其他研究者将这项采用了新颖算法方法的工作描述为“非常令人兴奋”“一个漂亮的结果”和“巨大的进步”。

虽然这一出人意料的发现尚未完全解决该问题，但它提供了迄今最有说服力的证据，表明科姆洛什的猜想毕竟没有那么不负责任。“我以前倾向于认为这个猜想是错的，”多伦多大学的计算机科学家亚历山大·尼古洛夫说，“这项新工作‘现在让我更有信心地认为，这个猜想实际上很可能是真的。’”

班萨尔和蒋浩天的解法展示了如何将深不可测的复杂系统驯服为更简单、更易于研究的东西——并提供了在数学、物理甚至机器学习中具有潜在应用价值的见解。

分而治之

像科姆洛什问题这样的差异问题处理的是将一组物体分成两个子集。你可以想象把人分成 trivia 队伍、把二手车分成批次，或者把临床试验参与者分成治疗组和安慰剂组。

科姆洛什猜想将每个人（或物体）想象为一支长度为1的箭头，称为单位向量。这个向量由一串坐标定义，每个坐标衡量该人拥有某一特定属性的程度。

假设你只关心两个 trivia 知识领域——书籍和电影。你可以这样把每个人想象成一个向量：

马克·贝兰、塞缪尔·贝拉斯科/《量子杂志》

现在把每个向量分配到一支队伍。如果你把一个向量放入A队，就保留它的坐标不变。如果你把它放入B队，就将每个坐标乘以−1。（这会把向量翻转过来。）

如果你能做到完美分割，把人分成两队，使每队在书籍和电影方面拥有等量的知识，那么所有这些向量加起来应该等于零。完美和谐。

但完美通常是不可能的。所以问题变成了：你能多接近零？

在我们的四人例子中，穷举所有选项很容易。如果你这么做，你会发现爱丽丝和鲍勃应该在一队，卡拉和戴夫在另一队。（值得注意的是，你不需要两队人数相同：你只需要把向量分开，根据需要给其中一些乘以−1，使向量相互抵消。）

当你面对更多向量和更多需要平衡的属性时，这项任务就变得困难得多。然而科姆洛什有一个特别乐观的假设：无论你考虑多少向量或属性，总应该有一种方式将向量分开，使得总和低于同一个普适常数。

在实践中，这个假设看起来远非成立。考虑一种天真的策略：简单地将向量随机分配到两队。这会导致差异随着向量数量N的增加而急剧上升。1985年，乔尔·斯宾塞找到了一个更好的界限，将差异限制在N的对数以下；1998年，沃伊切赫·巴纳什奇克将该界限改进为$latex \sqrt{\log N}$，也可以写成log(N)½。两者都是有意义的进步，但不平衡的量仍然随着向量数量的增加而增长。科姆洛什的常数似乎遥不可及。

就在这时，计算机科学家开始介入。

分割场景

2000年代末，差异问题开始引起理论计算机科学家的关注。班萨尔就是其中之一。他希望写下计算机理论上可以执行的一系列逻辑步骤——即一种算法——来推进科姆洛什问题。

许多研究者认为这样的算法不可能存在；他们说，计算该问题的精确解是不可能的。但班萨尔当时并不知道这一点。他觉得自己的无知是一种福气。“否则我就不敢违背那种共识了，”他说。

2010年，他想出了一个算法的构思。他首先将每个向量分成两半。例如，如果爱丽丝的向量是<1，0>，他会把<½，0>发给A队，把<½，0>发给B队。“我可以把人切成两半，”班萨尔说。然后他用一个随机过程逐步调整每个半向量，使某支队伍最终获得完整的原始<1，0>。在整个过程中，他确保每一步都不会让差异膨胀太多。

他证明，他的算法如果在计算机上实现，可以将向量分开，使差异被限制在与斯宾塞发现的相同的log(N)界限内。“当时没有人认为这是可能的，”加州大学洛杉矶分校从事差异算法研究的计算机科学家拉古·梅卡说，“这完全是突破常规的。”

2016年，班萨尔调整了他的算法，以达到巴纳什奇克的log(N)½界限——这是当时的纪录。

这项工作启发了其他研究者以新的方式思考差异问题。“它为一个人们几乎没有方法的问题提供了一种新方法，”梅卡说。

尽管如此，“作为计算机科学家，我们是在追赶那些我们知道聪明的数学家已经证明的结果，”班萨尔说。他现在想知道能否将这种新方法推得更远——不仅要追平旧纪录，还要创造新纪录。

依赖的根源

2019年，班萨尔在一次会议上遇到了当时是华盛顿大学研究生的蒋浩天。这两位计算机科学家因对差异算法的共同兴趣而结缘，几年后，他们与梅卡和另外两位研究者一起，在特定条件下证明了科姆洛什猜想。班萨尔和蒋浩天喜欢一起工作，决定继续合作攻克完整的猜想。

“[我们]合作很有默契，”班萨尔说，“我可以把半成熟的想法丢给他，他能接住。他也可以这样做。”

艾米丽·弗朗斯/密歇根大学

2025年2月，蒋浩天到安娜堡拜访班萨尔一周。到第二天，他们就找到了可能降低顽固上限的线索。

在他们之前的算法中，他们专注于约束随着时间推移不可避免积累的差异。现在，他们加入了额外的限制条件。

差异本质上同时依赖于许多维度。如果两家汽车经销商分一批新库存，使每种颜色的汽车数量相同，但其中一家经销商的敞篷车更多，那么在不打乱颜色维度平衡的情况下让敞篷车数量均等就很棘手。你不能把差异效应限制在任何特定维度上。“它们真的高度交织在一起，”班萨尔说。

他和蒋浩天想尝试揭示一种隐藏的独立性。“我们第一次交换想法时觉得这像个疯狂的主意，”他说，“但后来我们摆弄它的时候，觉得它并没有听起来那么疯狂。”

在接下来的几个月里，他们弄清楚了如何让它奏效。他们的新算法不仅会衡量整体差异，还会衡量“依赖性”——如果你随机扰动一个属性，其他属性之间的差异会变化多少？两人像班萨尔之前的算法那样，将向量的一半分配到每组。但现在，在随机扰动这些分数使其完整化时，班萨尔和蒋浩天精心设计了算法以减少联合影响。“不知怎的，尽管表面上看[这些属性]是相关的，”班萨尔说，“你可以以一种它们互不干扰的方式来移动。”

这让他和蒋浩天能在每一步更强地控制差异的演化方式。最终，他们的算法保证了对于N个向量，差异最多可以限制在log(N)¼。

这是几十年来科姆洛什问题的第一次改进。“我以前认为已知的那个界限很可能就是正确的界限，我们只需要找到一种方法来证明我们无法做得更好，”多伦多大学的计算机科学家尼古洛夫说，“所以我当然很惊讶我们能做得好得多。”

“log(N)的四次方根非常小，”耶鲁大学的丹尼尔·斯皮尔曼说，“就像在你的一生中，你不会看到一个数的log(N)四次方根超过5……从任何实际目的来看，它都已经非常接近常数了。”

不负责任的进展

班萨尔和蒋浩天的改进再次印证了差异理论核心中那个令人惊讶的优雅洞见：即使完美平衡不可能，接近平衡是可行的，甚至是切合实际的。

差异理论的更多进展可能就在眼前。关键在于，班萨尔和蒋浩天的算法是高效的，匈牙利阿尔弗雷德·雷尼数学研究所的雷尼·赫克说。这种高效意味着研究者有可能利用这一算法来帮助解决差异理论中的其他开放问题，以及优化理论、物理、金融等领域的问题。例如，赫克研究如何应用差异理论来改进大型语言模型和其他机器学习系统。

而最近的进展可能最终重新激发人们对科姆洛什那个“不负责任的”常数界限的探索。尼古洛夫和斯皮尔曼都表达了对该猜想成立的新信心。普适常数经常出现在数学问题中，甚至log(N)的平方根偶尔也会出现。四次方根则不那么常见，这表明它不会是最终极限。“在任何问题中，那很少是正确的答案，”斯皮尔曼说。

班萨尔怀疑他从2010年以来一直使用的算法策略能完成这项任务。“我们在四分之一次方处碰壁了，”他说，“要超越它肯定需要全新的东西。”

但它给了研究者希望。“我确实认为，”赫克说，“有人能够证明它。”

英文来源：

‘Huge Breakthrough’ in the Math of Imbalance
Ada Zejun Shen for Quanta Magazine
One does not need a doctorate in mathematics to split 12 eager trivia buffs into two competitive teams. But consider that each person arrives with unique strengths and liabilities: One may be a geography obsessive with no ear for music, another could be a naturalist who doesn’t own a television, and another could be a cinephile who never reads. Balancing traits between two camps becomes a lot harder.
So, how evenly can you assemble the teams so that they have matching firepower in every category, from Greek mythology to college basketball?
You can always make the teams surprisingly even, according to researchers studying combinatorial discrepancy theory.
Discrepancy theory is a branch of mathematics concerned with allocating resources as evenly as possible. If one trivia team gets all the history knowledge, leaving none for the other, that’s a big discrepancy.
In the early 1980s, the mathematician János Komlós came up with a counterintuitive prediction. He conjectured that no matter how many objects (your players) or dimensions (trivia categories) you consider, the discrepancy — which you can quantify — will never exceed a constant amount. There will always be a way to divide the teams with a discrepancy below that exact amount.
“This is really astonishing,” said Haotian Jiang, a theoretical computer scientist at the University of Chicago. “The Komlós conjecture says it has nothing to do with the dimension of the problem. It’s a universal constant.”
No one has ever found a way to contradict the conjecture. Yet it is so astonishing that some mathematicians thought it must be false. Proving it is “one of these holy-grail problems in discrepancy theory,” said Nikhil Bansal, a theoretical computer scientist from the University of Michigan.
Even the conjecture’s creator thinks it’s somewhat absurd. “I was young and foolish when I made it,” the now retired Komlós joked in an email. “I threw a wrench into combinatorial discrepancy theory with this irresponsible conjecture.”
If the Komlós conjecture is true, it could unlock answers to many other problems, both within discrepancy theory and in fields like operations research.
But for decades, a proof looked like a long shot. Mathematicians weren’t able to make much progress; their best upper limit on the discrepancy, achieved in 1998, still depended strongly on the dimension of the problem. It was far from constant.
Then, in fall 2025, Bansal and Jiang announced the first major advance on the problem in nearly 30 years. They found a limit that changes so slowly with the dimension that it is only a hair away from constant, even with an astronomical number of dimensions. Other researchers described the work, which used a novel algorithmic approach, as “very exciting,” “a beautiful result,” and “a huge step forward.”
While the unexpected finding has not fully resolved the problem, it offers the most compelling evidence yet that Komlós’ conjecture wasn’t so irresponsible after all. “I used to lean toward thinking the conjecture is false,” said Aleksandar Nikolov, a computer scientist at the University of Toronto. The new work “is now making me quite a bit more confident that probably the conjecture actually is true.”
Bansal and Jiang’s solution shows how unfathomably complex systems can be wrangled into something much simpler and easier to study — and offers insights that have potential applications in math, physics, and even machine learning.
Divide and Conquer
Discrepancy problems like Komlós’ deal with breaking sets of objects into two subsets. You can think of splitting people into trivia teams, or used cars into lots, or clinical trial participants into treatment and placebo groups.
The Komlós conjecture imagines each person (or object) as an arrow of length 1 called a unit vector. This vector is defined by a list of coordinates, where each coordinate measures how much of a particular attribute that person has.
Say you only care about two areas of trivia knowledge — books and movies. Here’s how you might imagine each person as a vector:
Mark Belan, Samuel Velasco/Quanta Magazine
Now assign each vector to a team. If you put a vector in Team A, leave its coordinates alone. If you put it in Team B, multiply each of its coordinates by −1. (This flips the vector around.)
If you’re able to make a perfect split, dividing people into two teams so that each team has an equal amount of knowledge across books and movies, then all of these vectors should add up to zero. Perfect harmony.
But perfection usually isn’t possible. So the question becomes: How close to zero can you get?
In our four-player example, it’s easy to run through all the options. If you do so, you’ll find that Alice and Bob should be on one team, and Carla and Dave on the other. (Notably, you don’t need the teams to have the same number of people: You just want to split the vectors up, multiplying as many by −1 as you need to, so that the vectors cancel each other out.)
This task gets much harder when you have more vectors and more attributes you want to balance out. Yet Komlós had a particularly optimistic hypothesis: that no matter how many vectors or attributes you consider, there should always be a way to split the vectors up so that the sum falls below the same universal constant.
In practice, that hypothesis appears to be far from true. Consider one naïve strategy: Simply assign vectors to teams at random. This leads to a discrepancy that skyrockets as the number of vectors, N, increases. In 1985, Joel Spencer found a better bound, capping discrepancy below the logarithm of N; in 1998, Wojciech Banaszczyk improved the bound to $latex \sqrt{\log N}$, which can also be written as log(N)½. Both were meaningful strides, but the amount of imbalance still grew as the number of vectors did. Komlós’ constant felt out of reach.
That’s when computer scientists started to get involved.
Split Scene
In the late 2000s, discrepancy problems started to attract the attention of theoretical computer scientists. Bansal was among them. He hoped to make progress on the Komlós problem by writing down a series of logical steps — an algorithm — that a computer could theoretically execute.
Many researchers thought that no such algorithm could exist; instead, they said, calculating an exact solution to the problem would be impossible. But Bansal didn’t know this at the time. He feels his ignorance was a blessing. “Otherwise I wouldn’t have dared to go against that wisdom,” he said.
In 2010, he came up with an idea for an algorithm. He started by splitting each vector in half. For example, if Alice’s vector is <1, 0>, he’d send <½, 0> to Team A and <½, 0> to Team B. “I could chop a person into two,” Bansal said. He then used a random procedure to gradually massage each half-vector so that one team ended up with the original <1, 0> fully on their side. All the while, he made sure not to let the discrepancy balloon too much at every step.
He proved that his algorithm, if implemented on a computer, could split the vectors up so that their discrepancy was capped at the same log(N) bound that Spencer had found. “Nobody had even thought it was possible,” said Raghu Meka, a computer scientist who works on discrepancy algorithms at the University of California, Los Angeles. “That was completely out of the box.”
In 2016, Bansal adjusted his algorithm to match Banaszczyk’s bound of log(N)½ — the standing record.
The work inspired other researchers to think about discrepancy problems in a new way. “It also gave a new method on a problem that people had kind of no approaches for,” Meka said.
Still, “as computer scientists, we were catching up to these results that we know smart math people already proved,” Bansal said. He now wondered whether he could push this new method further — to not just match old records but set new ones.
Dependent Cause
In 2019, Bansal met Haotian Jiang, then a graduate student at the University of Washington, at a conference. The computer scientists bonded over their interest in discrepancy algorithms, and a few years later, together with Meka and two other researchers, they proved the Komlós conjecture, but only under specific conditions. Bansal and Jiang enjoyed working together and resolved to continue collaborating on the full conjecture.
“[We] have a nice chemistry,” Bansal said. “I can throw half-baked ideas at him, and he picks it up. And he can do the same.”
Emily France/University of Michigan
In February 2025, Jiang visited Bansal for a week in Ann Arbor. By the second day, they had a lead on how they might lower the stubborn upper bound.
In their previous algorithms, they’d focused on constraining the discrepancy that inevitably accumulates over time. Now, they built in additional restrictions.
Discrepancy inherently depends on many dimensions at once. If two car dealerships split a new batch of inventory so that they have the same number of cars in each color, but one dealer has more convertibles, it’s tricky to later equalize the convertibles without upsetting the balance in the color dimension. You can’t confine discrepancy effects to any particular dimension. “They’re really so highly intertwined,” Bansal said.
He and Jiang wanted to try to uncover a hidden independence. “It felt like a crazy idea when we first bounced off each other,” he said. “But then when we were playing with it, we thought it’s not as crazy as it sounds.”
Over the next few months, they figured out how to make it work. Their new algorithm would measure not just the overall discrepancy but also “dependency” — if you randomly perturb one attribute, how much will the discrepancy among the other attributes change? The pair assigned halves of vectors to each group, as Bansal’s previous algorithms had done. Now, however, when it came to randomly perturbing those fractions to make them whole, Bansal and Jiang carefully designed their algorithm to reduce joint impacts. “Somehow, even though superficially [the attributes] are related,” Bansal said, “you can move in such a way that they don’t really bother each other.”
This allowed him and Jiang to exert greater control over how discrepancy evolved at each step. In the end, their algorithm guaranteed that for N vectors, the discrepancy could be at most log(N)¼.
It’s the first improvement on the Komlós problem in decades. “I used to think that it’s likely that the bound that was known before was just the right bound, and we just had to find a way to prove that we cannot do any better,” said Nikolov, the University of Toronto computer scientist. “So I was definitely surprised that we could do a lot better.”
“The fourth root of log(N) is very small,” said Daniel Spielman of Yale University. “Like in your life, you will not see a number for which the fourth root of log(N) is more than 5. … It’s getting pretty close to constant for every practical purpose.”
Irresponsible Progress
Bansal and Jiang’s improvement reaffirms the surprisingly elegant insight that lies at the heart of discrepancy theory: Even when perfect balance is impossible, getting close is feasible, and even practical.
More progress in discrepancy theory may be around the corner. Crucially, Bansal and Jiang’s algorithm is efficient, according to Rainie Heck of the Alfréd Rényi Institute of Mathematics in Hungary. This efficiency means that researchers could potentially use the algorithm to help tackle other open problems in discrepancy theory, as well as questions in optimization theory, physics, finance, and more. Heck, for instance, studies how discrepancy theory can be applied to improve large language models and other machine learning systems.
And the recent advance might reinvigorate the search for Komlós’ “irresponsible” constant bound at last. Nikolov and Spielman both expressed newfound confidence that the conjecture is true. Universal constants arise often in math problems, and even the square root of log(N) rears its head once in a while. A fourth root, not so much, which suggests that this won’t be the final limit. “It’s very rare that that’s the right answer to any problem,” Spielman said.
Bansal doubts that the algorithmic strategy he’s been using since 2010 will finish the job. “We hit a wall at a quarter root,” he said. “Going beyond that will definitely require something very new.”
But it’s given researchers hope. “I do think,” Heck said, “that someone will be able to prove it.”