The 𝐿_{𝑝}-discrepancy for finite 𝑝>1 suffers from the curse of dimensionality

Novak, Erich; Pillichshammer, Friedrich

doi:10.1090/proc/17100

The $L_p$-discrepancy for finite $p>1$ suffers from the curse of dimensionality
HTML articles powered by AMS MathViewer

by Erich Novak and Friedrich Pillichshammer;

Proc. Amer. Math. Soc. 153 (2025), 1447-1459

DOI: https://doi.org/10.1090/proc/17100

Published electronically: February 14, 2025

HTML | PDF | Request permission

Abstract:

We prove that the $L_p$-discrepancy suffers from the curse of dimensionality for all $p$ in $(1,\infty )$ and hence only the case $p=1$ is still open.

References

József Beck and William W. L. Chen, Irregularities of distribution, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR 903025, DOI 10.1017/CBO9780511565984
Dmitriy Bilyk, Michael T. Lacey, and Armen Vagharshakyan, On the small ball inequality in all dimensions, J. Funct. Anal. 254 (2008), no. 9, 2470–2502. MR 2409170, DOI 10.1016/j.jfa.2007.09.010
Josef Dick, Peter Kritzer, and Friedrich Pillichshammer, Lattice rules—numerical integration, approximation, and discrepancy, Springer Series in Computational Mathematics, vol. 58, Springer, Cham, [2022] ©2022. With an appendix by Adrian Ebert. MR 4472208, DOI 10.1007/978-3-031-09951-9
Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
Michael Gnewuch, Hendrik Pasing, and Christian Weiss, A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy, Math. Comp. 90 (2021), no. 332, 2873–2898. MR 4305372, DOI 10.1090/mcom/3666
Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279–302. MR 1814282, DOI 10.4064/aa96-3-7
Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477–483. MR 2068153, DOI 10.1016/j.jco.2004.01.001
David Krieg, Tractability of sampling recovery on unweighted function classes, Proc. Amer. Math. Soc. Ser. B 11 (2024), 115–125. MR 4746436, DOI 10.1090/bproc/216
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 419394
Jiří Matoušek, Geometric discrepancy, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 1999. An illustrated guide. MR 1697825, DOI 10.1007/978-3-642-03942-3
Erich Novak, Optimal algorithms for numerical integration: recent results and open problems, Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat., vol. 460, Springer, Cham, [2024] ©2024, pp. 105–131. MR 4774917, DOI 10.1007/978-3-031-59762-6_{5}
Erich Novak and Friedrich Pillichshammer, The curse of dimensionality for the $L_ p$-discrepancy with finite $p$, J. Complexity 79 (2023), Paper No. 101769, 19. MR 4605397, DOI 10.1016/j.jco.2023.101769
Erich Novak and H. Woźniakowski, Intractability results for integration and discrepancy, J. Complexity 17 (2001), no. 2, 388–441. 3rd Conference of the Foundations of Computational Mathematics (Oxford, 1999). MR 1843427, DOI 10.1006/jcom.2000.0577
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79. MR 66435, DOI 10.1112/S0025579300000541
Henryk Woźniakowski, Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 2000, pp. 114–136. MR 1849846

AMS Website Down

Proceedings of the American Mathematical Society

The $L_p$-discrepancy for finite $p>1$ suffers from the curse of dimensionality
HTML articles powered by AMS MathViewer

Abstract: