no. 14 · Friday 13 November 2026
Resolving Tusnády's Problem
Abstract
We prove a lower bound of $Ω_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$. Together with Nikolov's upper bound of the same order and Wei's planar lower bound, this settles Tusnády's problem: the discrepancy of axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$ in every fixed dimension $d\ge2$. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors. The matching upper and lower bounds are also formalized in Lean 4.
- comments
- 35 pages. Brownian sheet application. Lean 4 formalization at https://doi.org/10.5281/zenodo.24000482
- fields
- Classical Analysis and ODEs, Combinatorics