arXiv:2611.06998 · v1

Resolving Tusnády's Problem

首次提交 2026-11-05 02:58

版本更新 2026-11-05 02:58

雷达观测 2026-11-06 10:04

摘要

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.

作者备注：33 pages