‘Huge Breakthrough’ in the Math of Imbalance

不平衡数学的“巨大突破”

2026-08-21 · Quanta Magazine · 原文

One does not need a doctorate in mathematics to split 12 eager trivia buffs into two competitive teams.

不需要数学博士学位就能将 12 名热心问答爱好者分成两支竞争小组。

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.

如果一个问答小组掌握了所有历史知识，而另一方却没有留下任何知识，那就是一个很大的差异。

A recent breakthrough in combinatorial discrepancy theory helps even things out.

组合差异理论最近的一项突破有助于平衡事情。

In the early 1980s, the mathematician János Komlós came up with a counterintuitive prediction.

20 世纪 80 年代初，数学家 János Komlós 提出了一个违反直觉的预测。

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.

密歇根大学理论计算机科学家尼基尔·班萨尔 (Nikhil Bansal) 表示，证明这一点是“差异理论中的圣杯问题之一”。

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.

数学家未能取得多大进展；他们在 1998 年实现的最佳差异上限仍然很大程度上取决于问题的规模。

It was far from constant.

它远非恒定。

Then, in fall 2025, Bansal and Jiang announced the first major advance on the problem in nearly 30 years.

然后，在 2025 年秋天，班萨尔和蒋宣布了近 30 年来在这个问题上的第一个重大进展。

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.

“我过去倾向于认为这个猜想是错误的，”多伦多大学计算机科学家亚历山大·尼科洛夫 (Aleksandar Nikolov) 说。

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.

Bansal 和 Jiang 的解决方案展示了如何将极其复杂的系统转化为更简单、更容易研究的东西，并提供了在数学、物理甚至机器学习中具有潜在应用的见解。

Discrepancy problems like Komlós’ deal with breaking sets of objects into two subsets.

像 Komlós 这样的差异问题涉及将对象集分成两个子集。

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.

科姆洛斯猜想将每个人（或物体）想象成一个长度为 1 的箭头，称为单位向量。

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

马克·贝兰 (Mark Belan)、塞缪尔·贝拉斯科 (Samuel Velasco)/Quanta 杂志

Now assign each vector to a team.

现在将每个向量分配给一个团队。

If you put a vector in Team A, leave its coordinates alone.

如果将矢量放入 A 组，则无需考虑其坐标。

If you put it in Team B, multiply each of its coordinates by −1.

如果将其放入 B 队，则将其每个坐标乘以 -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.)

（值得注意的是，您不需要团队拥有相同数量的人员：您只需将向量分开，根据需要乘以 -1，以便向量相互抵消。）

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.

然而，科姆洛斯有一个特别乐观的假设：无论你考虑多少个向量或属性，总应该有一种方法来分割向量，以便总和低于相同的通用常数。

Samuel Velasco/ Quanta Magazine

塞缪尔·贝拉斯科/广达杂志

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.

这会导致差异随着向量数量 N 的增加而急剧增加。

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 ) ½ .

1985 年，Joel Spencer 发现了一个更好的界限，将差异限制在 N 的对数以下； 1998 年，Wojciech Banaszczyk 将边界改进为 $latex \sqrt{\log N}$，也可以写为 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.

从那时起，计算机科学家开始介入。

In the late 2000s, discrepancy problems started to attract the attention of theoretical computer scientists.

2000 年代末，差异问题开始引起理论计算机科学家的关注。

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 .

2010年，他提出了一个算法的想法。

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.

例如，如果 Alice 的向量是 <1, 0>，他会将 <½, 0> 发送到团队 A，将 <½, 0> 发送到团队 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.

然后，他使用随机程序逐渐调整每个半矢量，以便一个团队最终将原始的 <1, 0> 完全放在他们一边。

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.

他证明了他的算法，如果在计算机上实现，可以分割向量，以便它们的差异被限制在 Spencer 发现的相同 log(N) 界限内。

“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.

“没有人认为这是可能的，”在加州大学洛杉矶分校研究差异算法的计算机科学家拉古·梅卡 (Raghu Meka) 说。

“That was completely out of the box.”

“这完全是开箱即用的。”

In 2016, Bansal adjusted his algorithm to match Banaszczyk’s bound of log( N ) ½ — the standing record.

2016 年，Bansal 调整了他的算法，以匹配 Banaszczyk 的 log( N ) ½ 界限（现有记录）。

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.

他现在想知道是否可以进一步推动这种新方法——不仅要追平旧记录，还要创造新记录。

In 2019, Bansal met Haotian Jiang, then a graduate student at the University of Washington, at a conference.

2019年，班萨尔在一次会议上结识了当时在华盛顿大学读研究生的蒋浩天。

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.”

他也能做到同样的事情。”

Haotian Jiang (left) and Nikhil Bansal made the first major advance on the Komlós conjecture in 30 years.

蒋浩天（左）和尼基尔·班萨尔在科姆洛斯猜想上取得了 30 年来的首次重大进展。

Emily France/University of Michigan

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

In February 2025, Jiang visited Bansal for a week in Ann Arbor.

2025年2月，江泽民在安娜堡访问班萨尔一周。

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.

然而现在，当涉及到随机扰动这些分数以使它们完整时，Bansal 和 Jiang 仔细设计了他们的算法以减少联合影响。

“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 ) ¼ .

How small is log( N ) ¼ ?

log( N ) ¼ 有多小？

For N = 10, it’s 1.

For N = 10 81 — about the number of atoms in the observable universe — it’s 3.

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.

“log(N) 的四次根非常小，”耶鲁大学的 Daniel Spielman 说。

“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.”

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.

匈牙利阿尔弗雷德·雷尼数学研究所的 Rainie Heck 表示，至关重要的是，Bansal 和 Jiang 的算法非常高效。

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.”

“我确实认为，”赫克说，“有人能够证明这一点。”

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。

中文为机器翻译，仅供参考。