The L₁-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality

2026/07/27 by Josef Dick
#math.NA #cs.NA #math.PR

paper · pdf

Abstract

We prove that the L₁-discrepancy with arbitrary nonnegative weights suffers from the curse of dimensionality. More precisely, for every ε ∈ (0,1) and d ∈ ℕ, the inverse of the L₁-discrepancy satisfies N_1,+(ε, d) ≥ ((1-ε)²)/(1 + ε) ( (3+2 √(3))/(6))^d, where (3+2√(3))/6 = 1.07735…. 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.

Citations

• Generalized Discrepancy of Random Points
• Intractability results for integration in tensor product spaces
• The L_p-discrepancy for finite p>1 suffers from the curse of dimensionality
• An elementary proof of a lower bound for the inverse of the star discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets

Related

• The L_p-discrepancy for finite p>1 suffers from the curse of dimensionality
• Generalized Discrepancy of Random Points
• On the Discrepancy Function in Arbitary Dimension, Close to L ¹
• An elementary proof of a lower bound for the inverse of the star discrepancy
• The discrepancy of (n_kx) with respect to certain probability measures