Asymptotically optimal bracketing covers for anchored boxes

2026/08/01 by Kosuke Suzuki
Mathematics · #math.CO #msc:52C17 #msc:11K38 #msc:65C05

paper · pdf

arxiv created 2026/08/01 · arxiv updated 2026/08/04

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,δ)≥ \lceil δ^-d\rceil, N(d,δ)≥ \lceil (d!)/(d^d) δ^-d\rceil. We also construct, for every fixed d, bracketing covers which, together with the lower bound, show that N_[](d,δ)=(1+o_d(1))δ^-d as δ\downarrow0. The construction combines a coarse partition with box-dependent anisotropic local grids. Its shared vertices yield δ-covers with asymptotic upper coefficient one. Explicit upper bounds are obtained for both quantities.

Citations

• The L₁-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality
• A Proof of the Novak--Woźniakowski Conjecture: Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
• Hammersley Point Sets and Inverse of Star-Discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets