‘Huge Breakthrough’ in the Math of Imbalance

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