PreprintarXiv licencearXiv
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≥3. 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≥2. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors.
Related
- Tusnády's problem and online two-sample thinning
- Resolving a Problem of Lv and Koolen on the Smallest Eigenvalue of Distance-Regular Graphs
- Resolving the “ontogeny problem” in vertebrate paleontology
- One internal stabilization is enough for resolving self-referential tubes
- Resolving Erdős-Ulam Monochromatic Union-Closed Family Conjectures
BibTeX
@misc{wengiel2026resolving,
title = {{Resolving Tusnády's Problem}},
author = {Nicola Wengiel},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06998},
eprint = {2611.06998},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06998},
}
RIS
TY - UNPB
TI - Resolving Tusnády's Problem
AU - Nicola Wengiel
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06998
UR - https://arxiv.org/abs/2611.06998
AB - 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≥3. 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≥2. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors.
ER -