Tight Bounds for Tusnády's Problem in the Plane

We show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $\mathrm{\Theta }({\log }^{3\mathrm{/}2}n)$. The known bounds were $\mathrm{\Omega }(\log n)$ and $O({\log }^{3\mathrm{/}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 }_{2}n{)}^{3\mathrm{/}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 $\mathrm{\Omega }({\log }^{3\mathrm{/}2}n)$ over $\mathrm{\Theta }(\log n)$ digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.