Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy
Abstract
Bracketing covers and δ-covers provide finite discretizations of the anchored boxes that define the star discrepancy. Let N[](d,δ) and N(d,δ) denote the corresponding bracketing and covering numbers. We prove the lower bounds N[](d,δ)≥ ⌈ δ−d⌉, N(d,δ)≥ ⌈ d!/dd δ−d⌉. We give two explicit constructions of bracketing covers. For every fixed d, together with the lower bound they imply N[](d,δ)=(1+od(1))δ−d as δ↓0. A first construction uses box-dependent anisotropic local grids and gives simple explicit bounds. A second, homothetic logarithmic-shell construction again attains this coefficient and gives limsupd→∞N[](d,δ)1/d≤δ−1+e+O(δ) as δ↓0. Combining these finite estimates with Gnewuch's general bracketing bound and a Hoeffding--Bernstein chaining argument shows that, for every d,n∈ℕ, there exists an n-point set with star discrepancy at most 2.3463√(d/n). Consequently, ⌈5.5052dε−2⌉ points suffice for star discrepancy at most ε.
Related
- Optimal discrepancy for triangles
- Negative controls for bias detection within exposure-anchored self-controlled designs: applications and considerations
- A class of asymptotically optimal authentication codes with secrecy
- A set of points with optimal L2 spherical cap discrepancy
- Strichartz estimates for Klein-Gordon equations on asymptotically hyperbolic manifolds with applications
BibTeX
@misc{suzuki2026asymptotically,
title = {{Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy}},
author = {Kosuke Suzuki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.00899},
eprint = {2608.00899},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.00899},
}
RIS
TY - UNPB
TI - Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy
AU - Kosuke Suzuki
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2608.00899
UR - https://arxiv.org/abs/2608.00899
AB - Bracketing covers and δ-covers provide finite discretizations of the anchored boxes that define the star discrepancy. Let N_[](d,δ) and N(d,δ) denote the corresponding bracketing and covering numbers. We prove the lower bounds N_[](d,δ)≥ ⌈ δ^−d⌉, N(d,δ)≥ ⌈ d!/d^d δ^−d⌉. We give two explicit constructions of bracketing covers. For every fixed d, together with the lower bound they imply N_[](d,δ)=(1+o_d(1))δ^−d as δ↓0. A first construction uses box-dependent anisotropic local grids and gives simple explicit bounds. A second, homothetic logarithmic-shell construction again attains this coefficient and gives limsup_d→∞N_[](d,δ)^1/d≤δ^−1+e+O(δ) as δ↓0. Combining these finite estimates with Gnewuch's general bracketing bound and a Hoeffding--Bernstein chaining argument shows that, for every d,n∈ℕ, there exists an n-point set with star discrepancy at most 2.3463√(d/n). Consequently, ⌈5.5052dε^−2⌉ points suffice for star discrepancy at most ε.
ER -