Abstract
The L p -discrepancy is a quantitative measure for the irregularity of distribution modulo one of infinite sequences. In 1986, Proinov proved for all p > 1 a lower bound for the L p -discrepancy of general infinite sequences in the d-dimensional unit cube, but it remained an open question whether this lower bound is best possible in the order of magnitude until recently. In 2014, Dick and Pillichshammer gave a first construction of an infinite sequence whose order of L 2-discrepancy matches the lower bound of Proinov. Here we give a complete solution to this problem for all finite p > 1. We consider so-called order 2 digital (t, d)-sequences over the finite field with two elements and show that such sequences achieve the optimal order of L p -discrepancy simultaneously for all p ∈ (1,∞).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Beck and W. W. L. Chen, Irregularities of Distribution, Cambridge University Press, Cambridge, 1987.
R. Béjian, Minoration de la discrépance d’une suite quelconque sur T, Acta Arith. 41 (1982), 185–202.
D. Bilyk, M. T. Lacey, I. Parissis and A. Vagharshakyan, Exponential squared integrability of the discrepancy function in two dimensions, Mathematika 55 (2009), 2470–2502.
D. Bilyk, M. T. Lacey and A. Vagharshakyan, On the small ball inequality in all dimensions, J. Funct. Anal. 254 (2008), 2470–2502.
D. Bilyk and L. Markhasin, BMO and exponential Orlicz space estimates of the discrepancy function in arbitrary dimension, J. d’Analyse Mathématique, to appear. arXiv:1411.5794.
W. W. L. Chen, On irregularities of distribution, Mathematika 27 (1981), 153–170.
W. W. L. Chen, On irregularities of distribution II, Quart. J. Math. Oxford 34 (1983), 257–279.
W. W. L. Chen and M. M. Skriganov, Explicit constructions in the classical mean squares problem in irregularities of point distribution, J. Reine Angew. Math. 545 (2002), 67–95.
H. Davenport, Note on irregularities of distribution, Mathematika 3 (1956), 131–135.
J. Dick, Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions, SIAM J. Numer. Anal. 45 (2007), 2141–2176.
J. Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), 1519–1553.
J. Dick, On Quasi-Monte Carlo rules achieving higher order convergence, in Monte Carlo and Quasi-Monte Carlo Methods 2008 (P. L’Ecuyer and A. Owen, eds.), Springer, Berlin, 2009, pp. 73–96.
J. Dick, Discrepancy bounds for infinite-dimensional order two digital sequences over F2, J. Number Theory 136 (2014), 204–232.
J. Dick and J. Baldeaux, Equidistribution properties of generalized nets and sequences, in Monte Carlo and Quasi-Monte Carlo Methods 2008 (P. L’Ecuyer and A. Owen, eds.), Springer, Berlin, 2009, pp. 305–323.
J. Dick, A. Hinrichs, L. Markhasin and F. Pillichshammer, Discrepancy bounds for higher order digital sequences in function spaces with dominating mixed smoothness, Mathematika, to appear. arXiv:1604.08713.
J. Dick and F. Pillichshammer, On the mean square weighted L 2 discrepancy of randomized digital (t, m, s)-nets over Z2, Acta Arith. 117 (2005), 371–403.
J. Dick and F. Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010.
J. Dick and F. Pillichshammer, Optimal L 2 discrepancy bounds for higher order digital sequences over the finite field F 2, Acta Arith. 162 (2014), 65–99.
J. Dick and F. Pillichshammer, Explicit constructions of point sets and sequences with low discrepancy, in Uniform Distribution and Quasi-Monte Carlo Methods — Discrepancy, Integration and Applications (P. Kritzer, H. Niederreiter, F. Pillichshammer and A. Winterhof, eds.), Radon Series of Computational and Applied Mathematics, De Gruyter, Berlin, 2014, pp. 63–86.
N. M. Dobrovol’skiĭ, An effective proof of Roth’s theorem on quadratic dispersion (Russian), Uspekhi Mat. Nauk 39 (1984), 155–156; English translation: Russian Math. Surv. 39 (1984), 117–118.
M. Drmota and R.F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics 1651, Springer-Verlag, Berlin, 1997.
H. Faure, P. Kritzer and F. Pillichshammer, From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules, Indag. Math. (N.S.) 26 (2015), 760–822.
K. K. Frolov, Upper bound of the discrepancy in metric L p, 2 ≤ p < ∞, Dokl. Akad. Nauk SSSR 252 (1980), 805–807.
G. Halász, On Roth’s method in the theory of irregularities of point distributions, in Recent Progress in Analytic Number Theory, Vol. 2, Academic Press, London–New York, 1981, pp. 79–94.
F. J. Hickernell and R.-X. Yue, The mean square discrepancy of scrambled (t, s)-sequences, SIAM J. Numer. Anal. 38 (2000), 1089–1112.
A. Hinrichs, Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness, Math. Nachr. 283 (2010), 478–488.
E. Hlawka, Über die Diskrepanz mehrdimensionaler Folgen mod 1, Math. Z. 77 (1961), 273–284.
R. Kritzinger, L p- and S p,q r B-discrepancy of the symmetrized van der Corput sequence and modified Hammersley point sets in arbitrary bases, J. Complexity 33 (2016), 145–168.
R. Kritzinger and F. Pillichshammer, L p-discrepancy of the symmetrized van der Corput sequence, Arch. Math. 104 (2015), 407–418.
L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, John Wiley, New York, 1974; Reprint, Dover Publications, Mineola, NY, 2006.
G. Larcher, On the star discrepancy of sequences in the unit interval, J. Complexity 31 (2015), 474–485.
G. Leobacher and F. Pillichshammer, Introduction to Quasi-Monte Carlo Integration and Applications, Compact Textbooks in Mathematics, Birkhäuser/Springer, Cham, 2014.
L. Markhasin, Discrepancy of generalized Hammersley type point sets in Besov spaces with dominating mixed smoothness, Unif. Distrib. Theory 8 (2013), 135–164.
L. Markhasin, Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension, J. Complexity 29 (2013), 370–388.
L. Markhasin, Discrepancy and integration in function spaces with dominating mixed smoothness, Dissertationes Math. 494 (2013), 1–81.
L. Markhasin, L p- and S p,q r B-discrepancy of (order 2) digital nets, Acta Arith. 168 (2015), 139–159.
J. Matoušek, Geometric Discrepancy. An Illustrated Guide, Algorithms and Combinatorics, 18, Springer-Verlag, Berlin, 1999.
H. Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), 273–337.
H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, No. 63 in CBMS-NSF Series in Applied Mathematics, SIAM, Philadelphia, 1992.
H. Niederreiter and C.P. Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl. 2 (1996), 241–273.
E. Novak and H. Woźniakowski, Tractability of Multivariate Problems. Volume I: Linear Information, European Mathematical Society Publishing House, Zürich, 2008.
P. D. Proinov, On irregularities of distribution, C. R. Acad. Bulgare Sci. 39 (1986), 31–34.
K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79.
K. F. Roth, On irregularities of distribution. IV, Acta Arith. 37 (1980), 67–75.
W. M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45–50.
W. M. Schmidt, Irregularities of Distribution. X, Number Theory and Algebra, Academic Press, New York, 1977, pp. 311–329.
M. M. Skriganov, Lattices in algebraic number fields and uniform distribution mod 1 (Russian), Algebra i Analiz 1 (1989), 207–228; English translation: Leningrad Math. J. 1 (1990), 535–558.
M. M. Skriganov, Constructions of uniform distributions in terms of geometry of numbers (Russian), Algebra i Analiz 6 (1994), 200–230; English translation: St. Petersburg Math. J. 6 (1995), 635–664.
M. M. Skriganov, Harmonic analysis on totally disconnected groups and irregularities of point distributions, J. Reine Angew. Math. 600 (2006), 25–49.
I. M. Sobol’, The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. i Mat. Fiz. 7 (1967), 784–802.
S. Tezuka, Polynomial arithmetic analogue of Halton sequences, ACM Trans. Model. Computer Simul. 3 (1993), 99–107.
H. Triebel, Bases in Function Spaces, Sampling, Discrepancy, Numerical Integration, European Mathematical Society Publishing House, Zürich, 2010.
H. Triebel, Numerical integration and discrepancy. A new approach, Math. Nachr. 283 (2010), 139–159.
H. Weyl, Über die Gleichverteilung mod. Eins, Math. Ann. 77 (1916), 313–352.
S. C. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85–96.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported under Australian Research Council’s Discovery Projects funding scheme (project number DP150101770).
F.P. is 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”.
Rights and permissions
About this article
Cite this article
Dick, J., Hinrichs, A., Markhasin, L. et al. Optimal L p -discrepancy bounds for second order digital sequences. Isr. J. Math. 221, 489–510 (2017). https://doi.org/10.1007/s11856-017-1555-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-017-1555-2