A Proof of the Novak--Woźniakowski Conjecture: Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Abstract

The inverse of the star discrepancy $n^\ast(d, \varepsilon)$ satisfies \[ d \varepsilon^{-1} \lesssim n^{\ast}(d,\varepsilon)\lesssim d\varepsilon^{-2} \] for all $d \in \mathbb{N}$ and $0 < \varepsilon < \varepsilon_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 $\varepsilon^{-1}$ had remained open. In this paper we prove a lower bound which shows that the exponent $2$ of $\varepsilon^{-1}$ in the upper bound cannot be improved. More precisely, for every $0<α<1$ and fixed $0<A\le B$, there exist constants $c_{α,B}>0$ and $\varepsilon_{α,A}>0$ such that, for every $0<\varepsilon<\varepsilon_{α,A}$ and every integer $d$ satisfying \[ A\varepsilon^{-α}\le d\le B\varepsilon^{-α}, \] one has \[ n^\ast(d,\varepsilon) \ge c_{α,B}\,d\,\varepsilon^{-(2-α)}. \] Along these polynomial strips the right-hand side is of order $\varepsilon^{-2}$. Consequently, every uniform polynomial upper estimate $n^{\ast}(d,\varepsilon)\le C d^q\varepsilon^{-p}$ must satisfy $p\ge2$. Together with the lower bound of Hinrichs (2004), which forces $q\ge1$, 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^\ast = 2$, thereby proving the Novak--Woźniakowski conjecture.

Disclosure

“n∗ (dε , ε) ≥ cα ε−2 , whereas the assumed upper estimate gives n∗ (dε , ε) ≤ C2q ε−(p+αq) . This is impossible as ε ↓ 0, because p + αq < 2. Therefore p∗ ≥ 2, and the theorem follows. Declaration of generative AI use The author used ChatGPT 5.6 Sol for literature searches, exploratory development, and the preparation of portions of the exposition and LaTeX source. All mathematical arguments, calculations, references, and conclusions were independen”

PDF page 10

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:07:05.353278Z

Structural counts