From Splitting Trivia Teams to a 40-Year Mathematical Wall
Imagine organizing a trivia night at a bar. Twenty people, each with different knowledge — sports, history, anime. You must split them into two teams so that on every knowledge dimension the teams are roughly balanced, or the contest gets boring and people feel cheated.
Replace people with vectors and this becomes discrepancy theory in combinatorics: given n unit vectors, assign each either as-is to team A or multiplied by −1 to team B, so that every coordinate sum stays close to zero. The quantity measuring how badly balanced the split is, is 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 pushed inside 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 proving the constant. But per an August Quanta Magazine feature, Nikhil Bansal of the University of Michigan and Haotian Jiang of the University of Chicago cut the bound from √(log N) down to the fourth root of log N — the first crack in that wall in three decades. Yale colleague Daniel Spielman put it plainly: the fourth root never exceeds 5 at realistic scales — "it's essentially a constant."
Four Decades of Attacks
- 1981: Komlós conjectures the discrepancy can be pressed into a constant.
- 1985: Spencer proves a log N bound.
- 1998: Banaszczyk improves it to √(log N) — purely as an existence result.
- 2010: Bansal gives an algorithmic version matching log N.
- 2016: Algorithms catch up to √(log N), six years of work by Bansal.
- 2022: Bansal, Jiang, and Raghu Meka (UCLA) prove the constant under special conditions — a warm-up.
- 2025: Fourth root of log N — the wall cracks.
- Operations research / optimization: scheduling and balanced partitioning.
- Numerical computation: quadrature rules and sampling.
- Machine learning: LLM-related research.
- Financial engineering: close cousin of quasi-Monte Carlo methods.
- Physics simulation: uniformized sampling.
- Quanta Magazine report: https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/
- Paper: arXiv:2508.03961 (Bansal & Jiang)
Then in February 2025, Jiang visited Bansal in Ann Arbor. They planned a week of grinding; they found the lead on day two. The paper (arXiv:2508.03961) appeared in the fall, and after months of quiet the field erupted. Aleksandar Nikolov of the University of Toronto, previously on the "conjecture is false" side, said his confidence shifted "considerably" after reading it.
What Does Fourth Root of log N Mean Numerically?
| Number of objects N | Fourth root of log N | |---|---| | 10 | 1 | | 10^9 (world population scale) | ≈ 2.1 | | 10^81 (atoms in the observable universe) | 3 |
A fourth root of a logarithm grows extremely slowly. From N = 10 to the number of atoms in the universe, the bound only rises from 1 to 3. That is what Spielman means by "essentially a constant" — formally one step short of 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 apply random perturbations to these half-chunks, gradually pushing each whole vector toward one team while keeping the discrepancy from blowing up. The new result adds instrumentation to the perturbation process — they introduce a measure and control of dependency: when one dimension is moved, how much is the discrepancy of other dimensions dragged along? The dimensions are highly entangled, but by carefully designing the direction and step size of perturbations, the collateral damage cancels out — equivalent to excavating a layer of hidden independence.
Critically, this is not a pure existence proof but an efficient algorithm. The same dependency-control craftsmanship could be transplanted to other open problems — several long-standing difficulties in optimization, operations research, and numerical integration belong to the same structural family.
Why This Math Matters
Two examples in detail:
Machine learning. Rainie Heck of the Rényi Institute in Hungary is already applying discrepancy theory tools to large language models — uniformity-control problems surface at many stages of training and inference.
A relative in quant finance. Numerical integration has a branch of "low-discrepancy sequences" — the uniformity measure of lattice points is also called discrepancy, and quasi-Monte Carlo (QMC) methods in quantitative trading use exactly that. It is a different branch from combinatorial discrepancy, but they share the aesthetic of "compressing unevenness to the extreme." Practitioners of QMC should not 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 further will definitely need something entirely new." Spielman adds that fourth roots are rarely the final answer in mathematical history, so this is probably not the end. Heck is more optimistic: someone will eventually prove the constant.
Forty years — from log N to square root to fourth root, each step taking roughly a decade. The next step is replacing that 3 with a true constant. The trivia-night problem is one step from a period, but the road within that step has never been so well lit.
References: