2025/12/09 by Novak, Erich, Pillichshammer, Friedrich · 1 citation
Mathematics · #11K38 #65C05 #65Y20 #Analytic Number Theory Research #FOS: Mathematics #Mathematical Approximation and Integration #Number Theory (math.NT) #Numerical Analysis (math.NA) #Point processes and geometric inequalities #Probability (math.PR)
paper · doi:10.48550/arxiv.2512.08364
openalex publication_date 2025/12/09 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
We study the Lp-discrepancy of random point sets in high dimensions, with emphasis on small values of p. Although the classical Lp-discrepancy suffers from the curse of dimensionality for all p ∈ (1,∞), the gap between known upper and lower bounds remains substantial, in particular for small p ≥ 1. To clarify this picture, we review the existing results for i.i.d. uniformly distributed points and derive new upper bounds for generalized Lp-discrepancies, obtained by allowing non-uniform sampling densities and corresponding non-negative quadrature weights. Using the probabilistic method, we show that random points drawn from optimally chosen product densities lead to significantly improved upper bounds. For p=2 these bounds are explicit and optimal; for general p ∈ [1,∞) we obtain sharp asymptotic estimates. The improvement can be interpreted as a form of importance sampling for the underlying Sobolev space Fd,q. Our results also reveal that, even with optimal densities, the curse of dimensionality persists for random points when p≥ 1, and it becomes most pronounced for small p. This suggests that the curse should also hold for the classical L1-discrepancy for deterministic point sets.