Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
Abstract
The inverse of the star discrepancy n∗(d, ε) satisfies d ε−1 ≲ n∗(d,ε)≲ dε−2 for all d ∈ ℕ and 0 < ε < ε0. The upper bound was established by Heinrich, Novak, Wasilkowski and Woźniakowski (2001), while the lower bound is due to Hinrichs (2004). Steinerberger (2023) subsequently gave an elementary proof of the latter result. These bounds imply that the inverse of the star discrepancy depends linearly on the dimension, but the exact exponent of ε−1 had remained open. In this paper we prove a lower bound which shows that the exponent $2$ of ε−1 in the upper bound cannot be improved. More precisely, for every 0<α<1 and fixed 0<A≤ B, there exist constants cα,B>0 and εα,A>0 such that, for every 0<ε<εα,A and every integer d satisfying Aε−α≤ d≤ Bε−α, one has n∗(d,ε) ≥ cα,B d ε−(2−α). Along these polynomial strips the right-hand side is of order ε−2. Consequently, every uniform polynomial upper estimate n∗(d,ε)≤ C dqε−p must satisfy p≥2. Together with the lower bound of Hinrichs (2004), which forces q≥1, this proves that the exponents p=2 and q=1 in the Heinrich--Novak--Wasilkowski--Woźniakowski upper bound are individually optimal. In particular, the optimal exponent p∗ = 2.
Related
- Early stopping of stochastic variance reduced gradient for linear inverse problems by the discrepancy principle
- Wallis-type products with polynomial exponents and the Dirichlet beta function at negative integers
- Optimal discrepancy for triangles
- PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
- Optimal Decay Exponents for Fractional Burgers Rarefaction Waves
BibTeX
@misc{dick2026optimal,
title = {{Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy}},
author = {Josef Dick},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.23571},
eprint = {2607.23571},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.23571},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
AU - Josef Dick
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2607.23571
UR - https://arxiv.org/abs/2607.23571
AB - The inverse of the star discrepancy n^∗(d, ε) satisfies d ε^−1 ≲ n^∗(d,ε)≲ dε^−2 for all d ∈ ℕ and 0 < ε < ε_0. The upper bound was established by Heinrich, Novak, Wasilkowski and Woźniakowski (2001), while the lower bound is due to Hinrichs (2004). Steinerberger (2023) subsequently gave an elementary proof of the latter result. These bounds imply that the inverse of the star discrepancy depends linearly on the dimension, but the exact exponent of ε^−1 had remained open. In this paper we prove a lower bound which shows that the exponent $2$ of ε^−1 in the upper bound cannot be improved. More precisely, for every 0<α<1 and fixed 0<A≤ B, there exist constants c_α,B>0 and ε_α,A>0 such that, for every 0<ε<ε_α,A and every integer d satisfying Aε^−α≤ d≤ Bε^−α, one has n^∗(d,ε) ≥ c_α,B d ε^−(2−α). Along these polynomial strips the right-hand side is of order ε^−2. Consequently, every uniform polynomial upper estimate n^∗(d,ε)≤ C d^qε^−p must satisfy p≥2. Together with the lower bound of Hinrichs (2004), which forces q≥1, this proves that the exponents p=2 and q=1 in the Heinrich--Novak--Wasilkowski--Woźniakowski upper bound are individually optimal. In particular, the optimal exponent p^∗ = 2.
ER -