Imagine a scatter of points on a map. Give each one a plus or a minus sign, then draw any rectangle aligned with the map’s edges. Inside some rectangles, pluses and minuses will nearly cancel; inside others, one sign may dominate. The challenge is to choose the signs so that every rectangle stays as balanced as possible. A new mathematical approach shows why, once points occupy two or more dimensions, perfect balance has a stubborn limit.
This problem, known as Tusnády’s problem, asks how large the worst imbalance must be in the best possible coloring of a point set. The family of rectangles is enormous: their edges can slide across the plane, or across a higher-dimensional space, in countless ways. Yet the coloring must work for all of them at once. Earlier work had established an upper limit on the imbalance; a matching lower limit had remained elusive beyond two dimensions.
In a recent paper, mathematician Yuhao Lei closes that gap. For every fixed dimension of two or more, the largest unavoidable imbalance among a collection of N points grows like the logarithm of N raised to the power “dimension minus one-half.” The result matches the earlier upper bound, pinning down the exact rate of growth. The dimension must stay fixed as the number of points increases; the theorem does not claim the same rate when the dimension itself grows.
The key move is not to try every possible coloring. Instead, imagine assigning each point a random weight drawn from a bell-shaped, Gaussian distribution. For any chosen rectangle, add the weights of the points it contains. The researchers ask a different question: how likely is it that all those rectangle totals stay in a narrow band around zero? For a typical random point set, they show that this event is extraordinarily unlikely—even after focusing on a large portion of the possible weight patterns.
Why should that say anything about plus-and-minus colorings? Because the Gaussian test can be connected to the discrete problem: if too many sign assignments kept every rectangle’s total small, their geometry would force a relatively large region of Gaussian weight patterns to pass the test. The small-probability estimate rules that out. Turning a continuous random probe into a statement about discrete color choices is a crucial step in the proof.
To get a strong enough estimate, the argument takes advantage of how a rectangle can be assembled across scales. Split space into progressively smaller dyadic boxes—pieces formed by repeatedly halving intervals along each coordinate. Large pieces capture the coarse structure of a query; smaller pieces reveal its fine edges. The researchers separate the coarse patterns from the remaining, finer ones, then show that the fine patterns retain substantial variation across random points.
There is a second obstacle: two rectangles can overlap, so their weighted totals are correlated. The proof measures how much their fine pieces overlap and tracks these relationships through increasingly high moments. Those estimates sharpen the Gaussian test until it detects an extra square-root-of-a-logarithm amount of unavoidable imbalance. In everyday terms, the geometry of many overlapping rectangles makes it hard for one coloring to hide its excess everywhere.
The lower bound is robust, too. With very high probability, a uniformly random cloud of points still resists low-imbalance colorings even if someone removes a small fixed fraction of the points first. The claim holds simultaneously for every such remaining subset and every coloring of it. Deleting a few troublesome points, then recoloring the rest, does not make the geometric obstruction disappear.
The same ideas also illuminate a real-time version of the balancing game. Suppose two independent streams of observations come from the same unknown distribution. As each observation arrives, an algorithm must decide immediately whether to keep it or discard it; it cannot revise that choice later. The goal is to keep the two retained samples’ counts close inside every lower-left region, not just at the end but after every arrival. With an expected allowance of ρn deletions from the two samples, the paper proves that the smallest achievable worst-case prefix imbalance grows like the logarithm of n raised to “dimension plus one-half,” in every fixed dimension.
For the matching upper bound, the algorithm first uses a pilot batch to lay down a grid, then organizes its cells into nested dyadic boxes. Each new point proposes a signed change across the boxes containing it. A stationary Metropolis rule—adapted from earlier work—accepts or rejects that change, keeping the running bookkeeping state controlled while limiting how often points must be discarded. Small cell limits handle the leftover slivers between a query and the grid. The method works without knowing the underlying distribution.
But the moment when you measure matters. In one dimension, the best possible final imbalance is only on the scale of the logarithm of the logarithm of n, raised to the three-halves power—far smaller than the imbalance that must be tolerated while monitoring every prefix. Later arrivals can undo earlier mismatches. In two or more dimensions, the paper narrows the final-count bounds, but they still differ by a logarithmic factor. Closing that gap remains open.
The broader lesson is methodological: when a problem seems to demand a search across too many choices, change what you measure. Here, a Gaussian shadow of the point set reveals a geometric obstruction that direct color-by-color reasoning could not reach. It turns an abstract question about signs into a study of overlapping regions, scales, and the randomness of a probe—and carries that insight into algorithms that must make decisions before the data are even fully seen.
