arXiv · Oct 6, 2026
Tight Bounds for Tusn'ady's Problem in the Plane
By Zhewei Wei
We show that the worst-case combinatorial discrepancy of n points in the plane with respect to axis-parallel rectangles is Θ(log^(3/2)n). The known bounds were Ω(log n) and O(log^(3/2)n); we prove the matching lower bound. It holds for random point sets: for every A>0, there is a constant c_A>0 such that, with probability at least 1-e^(-An), every coloring of n independent uniform points in the unit square has an anchored rectangle with imbalance at least c_A(log₂n)^(3/2). The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to Ω(log^(3/2)n) over Θ(log n) digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.