arXiv preprint ·
Resolving Tusnády's Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Classical Analysis & ODEs
On the gradient conjecture at infinity: Finite spherical length for gradient trajectories of definable potentials
Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
A Computationally-Efficient Closed-Form $C^{s,1}$-Extension Formula
The double descent and Runge phenomena in overparametrized polynomial interpolation
Why Directly Learning Periodic Trajectories Can Fail
Get the few papers worth your time in Classical Analysis & ODEs every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.