The $L_1$-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality

Abstract

We prove that the $L_1$-discrepancy with arbitrary nonnegative weights suffers from the curse of dimensionality. More precisely, for every $\varepsilon \in (0,1)$ and $d \in \mathbb{N}$, the inverse of the $L_1$-discrepancy satisfies \[ N_{1,+}(\varepsilon, d) \ge \frac{(1-\varepsilon)^2}{1 + \varepsilon} \left( \frac{3+2 \sqrt{3}}{6}\right)^d, \] where $(3+2\sqrt{3})/6 = 1.07735\ldots$. The proof combines a change to a volume-biased probability measure with a fractional-moment estimate for the normalized discrepancy function. The lower bound applies, in particular, to equally weighted point sets. The argument uses the nonnegativity of the weights in an essential way and does not cover arbitrary signed weights.

Disclosure

“bound in d up to a positive constant independent of d. Hence, for every 1 < C < Cθ , one has N1,+ (ε, d) ≥ C d for all sufficiently large d. This is the curse of dimensionality and completes the proof of Theorem 1.1. 3 Declaration of generative AI use The author used ChatGPT 5.6 Sol for literature search, during the exploratory development and in preparing portions of the exposition and LaTeX source. All mathematical arguments, calculations, references, and conclusions were independ”

PDF page 6

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:08:47.297808Z

Structural counts