Paperlane

no. 14 · Friday 13 November 2026

Resolving Tusnády's Problem

Nicola Wengiel

math.CA · v2 · □ lean · 35 pp

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
pdf ↗ page arXiv:2611.06998 ↗