Abstract
We present an explicit construction of infinite sequences of points \((x_{0}, x_{1}, x_{2}, \ldots)\) in the d-dimensional unit-cube whose periodic L2-discrepancy satisfies
where the factor \(C_d > 0\) depends only on the dimension d. The construction is based on higher order digital sequences as introduced by J. Dick in the year 2008. The result is best possible in the order of magnitude in N according to a Roth-type lower bound shown first by P.D. Proinov. Since the periodic L2-discrepancy is equivalent to P. Zinterhof's diaphony the result also applies to this alternative quantitative measure for the irregularity of distribution.
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).
H. Chaix and H. Faure, Discr´epance et diaphonie en dimension un, Acta Arith., 63 (1993), 103–141.
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, A. Hinrichs, L. Markhasin, and F. Pillichshammer, Optimal \(L_p\)-discrepancy bounds for second order digital sequences, Israel J. Math., 221 (2017), 489–510.
J. Dick, A. Hinrichs, and F. Pillichshammer, A note on the periodic \(L_2\)L2 discrepancy of Korobov’s p-sets, Arch. Math., 115 (2020), 67–78.
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 \(\mathcal{L}_{2}\) discrepancy bounds for higher order digital sequences over the finite field \(\mathbb{F}_{2}\), Acta Arith., 16 (2014), 65–99.
M. Drmota and R.F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, 1651, Springer Verlag (Berlin, 1997).
H. Faure, Discrepancy and diaphony of digital (0, 1)-sequences in prime base, Acta Arith., 117 (2005), 125–148.
H. Faure, P. Kritzer, and F. Pillichshammer, From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules, Indag. Math., 26 (2015), 760–822.
V.S. Grozdanov, On the diaphony of one class of one-dimensional sequences, Int. J. Math. Math. Sci., 19 (1996), 115–124.
V.S. Grozdanov, On the diaphony and star-diaphony of the semisymmetrical net of Roth, C. R. Acad. Bulgare Sci., 52(9-10) (1999), 19–22.
A. Hinrichs, R. Kritzinger, and F. Pillichshammer, Extreme and periodic \(L_2\) discrepancy of plane point sets, Acta Arith., 199 (2021), 163–198.
A. Hinrichs, L. Markhasin, J. Oettershagen, and T. Ullrich, Optimal quasi-Monte Carlo rules on order 2 digital nets for numerical integration of multivariate periodic functions, Numer. Math., 134 (2016), 163–196.
A. Hinrichs and J. Oettershagen, Optimal point sets for quasi-Monte Carlo integration of bivariate periodic functions with bounded mixed derivatives, in: Monte Carlo and Quasi-Monte Carlo Methods, Springer Proc. Math. Stat., 163, Springer (Cham, 2016), pp. 385–405,
A. Hinrichs and H. Weyhausen, Asymptotic behavior of average \(L_p\)-discrepancies, J. Complexity, 28 (2012), 425–439.
W. Hornfeck and Ph. Kuhn, Diaphony, a measure of uniform distribution, and the Patterson function, Acta Crystallogr. Sect. A, 71 (2015), 382–391.
N. Kirk, On Proinov’s lower bound for the diaphony, Uniform Distribution Theory, 15 (2020), 39–72.
R. Kritzinger and F. Pillichshammer, Exact order of extreme Lp discrepancy of infinite sequences in arbitrary dimension, Arch. Math., 118 (2022), 169–179.
R. Kritzinger and F. Pillichshammer, Point sets with optimal order of extreme and periodic discrepancy, Acta Arith., 204 (2022), 191–223.
L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, John Wiley (New York, 1974).
V.F. Lev, On two versions of \(L_2\)-discrepancy and geometrical interpretation of diaphony, Acta Math. Hungar., 69(4) (1995), 281–300.
V.F. Lev, The exact order of generalized diaphony and multidimensional numerical integration, J. Austral. Math. Soc. Ser. A, 66 (1999), 1–17.
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, CBMS-NSF Series in Applied Mathematics, 63, 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.
G. Pagés, Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration, J. Comput. Appl. Math., 44 (1992), 21–39.
F. Pausinger and W. Ch. Schmid, A good permutation for one-dimensional diaphony, Monte Carlo Methods Appl., 16 (2010), 307-–322.
P. D. Proinov, Quantitative Theory of Uniform Distribution and Integral Approximation, University of Plovdiv (Bulgaria, 2000) (in Bulgarian).
P. D. Proinov, Symmetrization of the van der Corput generalized sequences, Proc. Japan Acad. Ser. A Math. Sci., 64 (1988), 159–162.
P. D. Proinov and V. S. Grozdanov, On the diaphony of the van der Corput-Halton sequence, J. Number Theory, 30 (1988), 94–104.
K. F. Roth, On irregularities of distribution, Mathematika, 1 (1954), 73–79.
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.
H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins, Math. Ann., 77 (1916), 313–352.
P. Zinterhof, Über einige Absch¨atzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden, ¨Osterr. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II, 185 (1976), 121–132.
Author information
Authors and Affiliations
Corresponding author
Additional information
The author is supported by the Austrian Research Foundation (FWF), Project F5509-N26, that is part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Pillichshammer, F. Optimal periodic L2-discrepancy and diaphony bounds for higher order digital sequences. Acta Math. Hungar. 169, 252–271 (2023). https://doi.org/10.1007/s10474-023-01307-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-023-01307-9