Tusnády's problem asks for the order of magnitude of the worst-case combinatorial discrepancy of N-point sets with respect to axis-parallel boxes in fixed dimension d. A matching lower bound to Nikolov's upper bound O((log N)^{d-1/2}) was missing for d≥3.

The proof builds smoothed product test functions from localized Walsh functions on dyadic shell boxes. It uses sampling discretization to choose a weighted point set. An entropy argument for Gaussian vectors conditioned on small weighted box counts then bounds the hereditary discrepancy from below. The main theorem, Nikolov's upper bound, and the inclusion–exclusion comparison between anchored and general boxes are formalized in Lean 4, reusing Wei's Lean formalization for the planar case.

The paper proves a lower bound of Ω_d((log N)^{d-1/2}) for anchored boxes in every d≥3. Combined with prior work, this gives discrepancy Θ_d((log N)^{d-1/2}) for every d≥2. Extensions cover homothetic copies of convex polytopes and an efficient coloring algorithm that attains the upper bound.