From a Pub Team-Division Problem
Imagine organizing a trivia night at a pub with twenty people, each with different knowledge—sports, history, anime. You need to split them into two teams so that in every knowledge dimension the teams are roughly balanced.
Replace people with vectors and this becomes the discrepancy problem in combinatorics: given n unit vectors, assign each either as-is to team A or multiplied by −1 to team B, so that the coordinate-wise sums stay as close to zero as possible. The measure of "how bad the split is" is called the discrepancy.
How old is the problem? In the early 1980s, Hungarian mathematician János Komlós conjectured that no matter how many objects or dimensions, the discrepancy can always be bounded by a universal constant. The conjecture was so bold that he later joked: "I was young and reckless; it was an irresponsible conjecture."
Forty years passed without a proof of the constant. But per an August Quanta Magazine report, Nikhil Bansal (University of Michigan) and Haotian Jiang (University of Chicago) slashed the bound from sqrt(log N) to the fourth root of log N—the first crack in this wall in thirty years. Yale's Daniel Spielman put it plainly: the fourth root never exceeds 5 at realistic scales, so it's "practically a constant."
Forty Years of Attack and Defense
- 1981: Komlós conjectures the discrepancy can be pressed into a constant.
- 1985: Spencer proves a bound of log N.
- 1998: Banaszczyk improves to sqrt(log N) (existential only).
- 2010: Bansal gives an algorithmic version matching log N.
- 2016: Algorithms catch up to sqrt(log N).
- 2022: Constant proven under special conditions.
- 2025: Fourth root—the wall cracks.
- Operations research: scheduling and balanced partitioning
- Numerical computation: quadrature rules and sampling
- Machine learning: LLM-related research
- Financial engineering: cousins of quasi-Monte Carlo
- Physical simulation: uniform sampling
- Quanta report: https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/
- Paper: arXiv:2508.03961 (Bansal & Jiang)
A few milestones deserve detail. Spencer's 1985 log N bound covered most intuitions—many thought the story ended there. Banaszczyk's 1998 sqrt(log N) was purely existential; making it constructive took Bansal six full years, finishing in 2016. In 2022, Bansal, Jiang, and Raghu Meka (UCLA) proved the constant under special conditions as a warm-up.
Then in February 2025, Jiang visited Bansal in Ann Arbor. They planned to grind for a week, but found the key lead on day two. The paper (arXiv:2508.03961) went up in the fall, and after a few quiet months the field erupted. Aleksandar Nikolov of the University of Toronto, who had sided with "the conjecture is false," revised his confidence upward substantially after reading it.
What Does a Fourth Root Mean?
| Objects N | Fourth root of log N | |---|---| | 10 | 1 | | 10^9 (world population) | ~2.1 | | 10^81 (atoms in observable universe) | 3 |
A logarithm raised to the fourth power grows extremely slowly. From N = 10 to the number of atoms in the universe, the bound only rises from 1 to 3. That's what Spielman means by "practically a constant"—formally one step away from Komlós's true constant, practically indistinguishable.
What They Actually Did Differently
Bansal's celebrated 2010 technique: split each vector in half, give each team one half, then randomly perturb these halves, gradually pushing each whole vector to one side while keeping discrepancy in check.
The new result instruments this perturbation process. They introduced a measure and control of dependency: when one dimension moves, how much is the discrepancy of other dimensions dragged along? Dimensions were previously highly entangled; by carefully designing the direction and step size of perturbations, the collateral damage cancels out—effectively excavating a layer of hidden independence.
Crucially, this is not a purely existential proof but an efficient algorithm. The same dependency-control technique may transfer to other open problems—several stubborn questions in optimization, operations research, and numerical integration belong to the same family.
What Is This Math Good For?
Two examples in depth:
Machine learning. Rainie Heck of Hungary's Rényi Institute is already applying discrepancy theory tools to large language models—uniformity control problems surface in many stages of training and inference.
Quant finance's relative. Numerical integration has a branch on "low-discrepancy sequences"—uniformity of lattice points is also called discrepancy, and quasi-Monte Carlo (QMC) methods in quant trading rely on it. It shares a surname but not a lineage with combinatorial discrepancy, yet shares the aesthetic of "pressing unevenness to the extreme." QMC practitioners won't be entirely indifferent to upgraded discrepancy algorithms.
The Wall Still Stands
Bansal remains clear-eyed: "We've hit a wall at the fourth root; going lower will certainly require something completely new." Spielman adds that fourth roots are rarely the final answer in mathematical history, so this is likely not the end. Heck is more optimistic: someone will eventually prove the constant.
Forty years—from log N to the square root to the fourth root, each step taking roughly a decade. The next step is replacing that 3 with a true constant. The pub team-splitting problem is one step from the finish line, and the road within that step has never been brighter.
References: