Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy

Abstract

Bracketing covers and $\delta$-covers provide finite discretizations of the anchored boxes that define the star discrepancy. Let $N_{[]}(d,\delta )$ and $N(d,\delta )$ denote the corresponding bracketing and covering numbers. We prove the lower bounds \[ N_{[]}(d,δ)\ge \lceil δ^{-d}\rceil, \qquad N(d,δ)\ge \left\lceil \frac{d!}{d^d}\,δ^{-d}\right\rceil. \] We give two explicit constructions of bracketing covers. For every fixed $d$, together with the lower bound they imply $N_{[]}(d,\delta )=(1+o_d(1)){\delta }^{-d}$ as $\delta \downarrow 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 ${\mathrm{limsup}}_{d\to \infty }{N}_{[]}(d,\delta {)}^{1/d}\le {\delta }^{-1}+e+O(\delta )$ as $\delta \downarrow 0$. Combining these finite estimates with Gnewuch's general bracketing bound and a Hoeffding--Bernstein chaining argument shows that, for every $d,n\in \mathbb{N}$, there exists an $n$-point set with star discrepancy at most $2.3463\sqrt{d/n}$. Consequently, $\lceil 5.5052d{\epsilon }^{-2}\rceil$ points suffice for star discrepancy at most $\epsilon$.