Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 
 

 

The weighted star discrepancy of Korobov's $ p$-sets


Authors: Josef Dick and Friedrich Pillichshammer
Journal: Proc. Amer. Math. Soc. 143 (2015), 5043-5057
MSC (2010): Primary 11K38, 65C05
DOI: https://doi.org/10.1090/proc/12636
Published electronically: May 7, 2015
MathSciNet review: 3411125
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze the weighted star discrepancy of so-called $ p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these sets have largely been ignored since a number of other constructions have been discovered which achieve a better convergence rate. However, it has recently been discovered that the $ p$-sets perform well in terms of the dependence on the dimension.

We prove bounds on the weighted star discrepancy of the $ p$-sets which hold for any choice of weights. For product weights, we give conditions under which the discrepancy bounds are independent of the dimension $ s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.


References [Enhancements On Off] (What's this?)

  • [1] Christoph Aistleitner, Tractability results for the weighted star-discrepancy, J. Complexity 30 (2014), no. 4, 381-391. MR 3212778, https://doi.org/10.1016/j.jco.2013.12.004
  • [2] Josef Dick, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, J. Approx. Theory 183 (2014), 14-30. MR 3209579, https://doi.org/10.1016/j.jat.2014.03.015
  • [3] Josef Dick, Gunther Leobacher, and Friedrich Pillichshammer, Construction algorithms for digital nets with low weighted star discrepancy, SIAM J. Numer. Anal. 43 (2005), no. 1, 76-95 (electronic). MR 2177135 (2006h:11090), https://doi.org/10.1137/040604662
  • [4] Josef Dick, Harald Niederreiter, and Friedrich Pillichshammer, Weighted star discrepancy of digital nets in prime bases, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 77-96. MR 2208703 (2007b:11113), https://doi.org/10.1007/3-540-31186-6_6
  • [5] Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394 (2012b:65005)
  • [6] Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593-623. MR 2086942 (2005h:65008), https://doi.org/10.1016/j.jco.2003.06.002
  • [7] Benjamin Doerr, Michael Gnewuch, and Anand Srivastav, Bounds and constructions for the star-discrepancy via $ \delta $-covers, J. Complexity 21 (2005), no. 5, 691-709. MR 2170868 (2006d:11087), https://doi.org/10.1016/j.jco.2005.05.002
  • [8] Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • [9] N. M. Korobov, Approximate calculation of repeated integrals by number-theoretical methods, Dokl. Akad. Nauk SSSR (N.S.) 115 (1957), 1062-1065 (Russian). MR 0098714 (20 #5169)
  • [10] N. M. Korobov, On number-theoretic methods in approximate analysis, Probl. Numer. Math. Comp. Techn. (Russian), Gosudarstv. Naučno-Tehn. Izdat. Mašinostr. Lit., Moscow, 1963, pp. 36-44 (Russian). MR 0189241 (32 #6668)
  • [11] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394 (54 #7415)
  • [12] Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbook in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176
  • [13] 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 (2002b:11103), https://doi.org/10.4064/aa96-3-7
  • [14] Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477-483. MR 2068153 (2005e:11098), https://doi.org/10.1016/j.jco.2004.01.001
  • [15] Aicke Hinrichs, Friedrich Pillichshammer, and Wolfgang Ch. Schmid, Tractability properties of the weighted star discrepancy, J. Complexity 24 (2008), no. 2, 134-143. MR 2400312 (2009g:11102), https://doi.org/10.1016/j.jco.2007.08.002
  • [16] Loo Keng Hua and Yuan Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR 617192 (83g:10034)
  • [17] Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394 (97i:11115)
  • [18] Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • [19] Erich Novak and Henryk Woźniakowski, When are integration and discrepancy tractable?, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 211-266. MR 1836619 (2002h:68083)
  • [20] Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266 (2009m:46037)
  • [21] 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 (2011h:46093)
  • [22] Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170
  • [23] Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1-33. MR 1617765 (99d:65384), https://doi.org/10.1006/jcom.1997.0463
  • [24] Xiaoqun Wang, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18 (2002), no. 3, 683-701. MR 1928803 (2003m:65008), https://doi.org/10.1006/jcom.2002.0641
  • [25] Xiaoqun Wang, Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp. 72 (2003), no. 242, 823-838 (electronic). MR 1954970 (2003m:65009), https://doi.org/10.1090/S0025-5718-02-01440-0
  • [26] André Weil, On some exponential sums, Proc. Nat. Acad. Sci. U. S. A. 34 (1948), 204-207. MR 0027006 (10,234e)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11K38, 65C05

Retrieve articles in all journals with MSC (2010): 11K38, 65C05


Additional Information

Josef Dick
Affiliation: School of Mathematics and Statistics, The University of New South Wales, Sydney, Australia
Email: josef.dick@unsw.edu.au

Friedrich Pillichshammer
Affiliation: Institut für Analysis, Universität Linz, Altenbergerstraße 69, A-4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

DOI: https://doi.org/10.1090/proc/12636
Received by editor(s): March 31, 2014
Received by editor(s) in revised form: September 11, 2014
Published electronically: May 7, 2015
Additional Notes: The first author was supported by a QEII Fellowship of the Australian Research Council DP1097023.
The second author was supported by the Austrian Science Fund (FWF): Project F5509-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
Communicated by: Walter Van Assche
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society