The curse of dimensionality for geometric $L_1$-discrepancies with nonnegative weights

Abstract

We prove that the normalized star, extreme, and periodic $L_1$-discrepancies with arbitrary nonnegative weights suffer from the curse of dimensionality. A single elementary lemma is used in all three cases: after normalizing the target and every one-dimensional kernel to probability densities, a uniform square-root-affinity gap tensorizes over the coordinates. For every $d\in \mathbb{N}$ and $0<\epsilon <1$, the normalized information complexities have lower bounds of the form \[ \frac{(1-\varepsilon)^2}{1+\varepsilon}\,q^d, \] with \[ q_{\mathrm{star}}=\frac12+\frac1{\sqrt3},\qquad q_{\mathrm{ext}}=\frac{75(9+4\sqrt2)}{784},\qquad q_{\mathrm{per}}=\frac{25}{16}. \] All three constants are larger than one. The argument uses only nonnegativity, product integration, the elementary inequalities for the square root, and Cauchy--Schwarz.

11 pages