Asymptotically optimal bracketing covers for anchored boxes

Abstract

Bracketing covers and $\hat{I}´$-covers provide finite discretizations of the anchored boxes that define the star discrepancy. Let $N_{[]}(d,\hat{I}´)$ and $N(d,\hat{I}´)$ 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 also construct, for every fixed $d$, bracketing covers which, together with the lower bound, show that $N_{[]}(d,\hat{I}´)=(1+o_d(1))\hat{I}{´}^{-d}$ as $\hat{I}´\downarrow 0$. The construction combines a coarse partition with box-dependent anisotropic local grids. Its shared vertices yield $\hat{I}´$-covers with asymptotic upper coefficient one. Explicit upper bounds are obtained for both quantities.