A Record That Stood Unchanged for 27 Years Has Been Narrowed — A New Bound for the 'Splitting as Evenly as Possible Into Two' Problem

Explanation

"I want to split a large number of items into two groups as evenly as possible." There is a field of mathematics that treats this seemingly simple problem formally, called discrepancy theory. Quanta Magazine reported on August 21, 2026, that the upper bound of a central conjecture in this field has been significantly narrowed for the first time in 27 years.

The problem being addressed is as follows. There are N vectors, each of length at most 1. If a plus or minus sign is assigned to each one and they are all summed together, can the total be kept from being strongly biased in any direction? The size of this bias is called the "discrepancy."

The conjecture put forward by the Hungarian mathematician János Komlós in the early 1980s was a very strong claim: no matter how many vectors there are or how many dimensions exist, the discrepancy never exceeds some fixed number. That is, it claims the bound does not grow with N—it is bounded by a constant independent of N.

By contrast, the upper bounds that have actually been proven grow slowly with N. In 1985, Joel Spencer showed a bound of log N; in 1998, Wojciech Banaszczyk showed √(log N), the square root of log N. This record went unbroken for about 27 years afterward.

Now, Nikhil Bansal of the University of Michigan and Haotian Jiang of the University of Chicago have lowered the bound to the fourth root of log N. The paper is titled "Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk" (arXiv:2508.03961).

The change from square root to fourth root is easier to grasp with actual numbers. Using common logarithms, if N is 10 to the 81st power (roughly the same order as the number of atoms in the observable universe), log N is 81. Its square root is 9, and its fourth root is 3. This is only a rough guide that ignores finer details such as constant factors, but it brings the result considerably closer to the shape of the conjecture, in which the bound barely moves no matter how large N becomes.

The same paper also fully resolves the related Beck–Fiala conjecture under certain conditions.

The problem of splitting things evenly also arises when dividing data into training and validation sets in machine learning, or when assigning experimental subjects into two groups. A proof that appears abstract connects to theoretical guarantees for "how evenly can this be done" in such situations.

Source: Quanta Magazine, "'Huge Breakthrough' in the Math of Imbalance" (August 21, 2026)
https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/
Paper: arXiv:2508.03961 https://arxiv.org/abs/2508.03961