Optimal periodic \(L_2\)-discrepancy and diaphony bounds for higher order digital sequences. (English) Zbl 07672148
Summary: We present an explicit construction of infinite sequences of points \((x_0,x_1,x_2, \dots)\) in the \(d\)-dimensional unit-cube whose periodic \(L_2\)-discrepancy satisfies \[L^{\text{per}}_{2,N} (\{x_0, x_1, \dots , x_{N-1}\}) \le C_dN^{-1}(\log N)^{d/2} \;\;\text{ for all}\; N \ge 2,\] 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 [SIAM J. Numer. Anal. 46, No. 3, 1519–1553 (2008; Zbl 1189.42012)]. The result is best possible in the order of magnitude in N according to a Roth-type lower bound shown first by P. D. Projnov [Proc. Japan Acad., Ser. A 64, No. 5, 159–162 (1988; Zbl 0654.10049)]. Since the periodic \(L_2\)-discrepancy is equivalent to diaphony of P. Zinterhof [Österr. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II 185, 121–132 (1976; Zbl 0356.65007)], the result also applies to this alternative quantitative measure for the irregularity of distribution.
MSC:
| 11K38 | Irregularities of distribution, discrepancy |
| 11K06 | General theory of distribution modulo \(1\) |
| 11K45 | Pseudo-random numbers; Monte Carlo methods |
Keywords:
periodic \(L_2\)-discrepancy; diaphony; explicit construction; digital sequence; higher order sequenceReferences:
| [1] | J. Beck and W. W. L. Chen, Irregularities of Distribution, Cambridge University Press (Cambridge, 1987). · Zbl 0617.10039 |
| [2] | H. Chaix and H. Faure, Discr´epance et diaphonie en dimension un, Acta Arith., 63 (1993), 103-141. · Zbl 0772.11022 |
| [3] | 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. · Zbl 1158.65007 |
| [4] | J. Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal., 46 (2008), 1519-1553. · Zbl 1189.42012 |
| [5] | 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. · Zbl 1394.11060 |
| [6] | 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. · Zbl 1448.11148 |
| [7] | J. Dick and F. Pillichshammer, Digital Nets and Sequences - Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press (Cambridge, 2010). · Zbl 1282.65012 |
| [8] | 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. · Zbl 1294.11127 |
| [9] | M. Drmota and R.F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, 1651, Springer Verlag (Berlin, 1997). |
| [10] | H. Faure, Discrepancy and diaphony of digital (0, 1)-sequences in prime base, Acta Arith., 117 (2005), 125-148. · Zbl 1080.11054 |
| [11] | 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. · Zbl 1335.11063 |
| [12] | V.S. Grozdanov, On the diaphony of one class of one-dimensional sequences, Int. J. Math. Math. Sci., 19 (1996), 115-124. · Zbl 0841.11038 |
| [13] | 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. · Zbl 0947.65004 |
| [14] | A. Hinrichs, R. Kritzinger, and F. Pillichshammer, Extreme and periodic \(L_2\) discrepancy of plane point sets, Acta Arith., 199 (2021), 163-198. · Zbl 1483.11158 |
| [15] | 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. · Zbl 1358.65004 |
| [16] | 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, · Zbl 1356.65007 |
| [17] | A. Hinrichs and H. Weyhausen, Asymptotic behavior of average \(L_p\)-discrepancies, J. Complexity, 28 (2012), 425-439. · Zbl 1268.11101 |
| [18] | W. Hornfeck and Ph. Kuhn, Diaphony, a measure of uniform distribution, and the Patterson function, Acta Crystallogr. Sect. A, 71 (2015), 382-391. · Zbl 1390.11095 |
| [19] | N. Kirk, On Proinov’s lower bound for the diaphony, Uniform Distribution Theory, 15 (2020), 39-72. · Zbl 1485.11117 |
| [20] | R. Kritzinger and F. Pillichshammer, Exact order of extreme Lp discrepancy of infinite sequences in arbitrary dimension, Arch. Math., 118 (2022), 169-179. · Zbl 1496.11101 |
| [21] | R. Kritzinger and F. Pillichshammer, Point sets with optimal order of extreme and periodic discrepancy, Acta Arith., 204 (2022), 191-223. · Zbl 1503.11107 |
| [22] | L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, John Wiley (New York, 1974). · Zbl 0281.10001 |
| [23] | V.F. Lev, On two versions of \(L_2\)-discrepancy and geometrical interpretation of diaphony, Acta Math. Hungar., 69(4) (1995), 281-300. · Zbl 0845.11026 |
| [24] | V.F. Lev, The exact order of generalized diaphony and multidimensional numerical integration, J. Austral. Math. Soc. Ser. A, 66 (1999), 1-17. · Zbl 0926.11054 |
| [25] | J. Matoušek, Geometric Discrepancy - An Illustrated Guide, Algorithms and Combinatorics, 18, Springer-Verlag (Berlin, 1999). · Zbl 0930.11060 |
| [26] | H. Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math., 104 (1987),273-337. · Zbl 0626.10045 |
| [27] | H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Series in Applied Mathematics, 63, SIAM (Philadelphia, 1992). · Zbl 0761.65002 |
| [28] | H. Niederreiter and C.P. Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl., 2 (1996), 241-273. · Zbl 0893.11029 |
| [29] | G. Pagés, Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration, J. Comput. Appl. Math., 44 (1992), 21-39. · Zbl 0765.41033 |
| [30] | F. Pausinger and W. Ch. Schmid, A good permutation for one-dimensional diaphony, Monte Carlo Methods Appl., 16 (2010), 307-322. · Zbl 1206.11096 |
| [31] | P. D. Proinov, Quantitative Theory of Uniform Distribution and Integral Approximation, University of Plovdiv (Bulgaria, 2000) (in Bulgarian). |
| [32] | P. D. Proinov, Symmetrization of the van der Corput generalized sequences, Proc. Japan Acad. Ser. A Math. Sci., 64 (1988), 159-162. · Zbl 0654.10049 |
| [33] | P. D. Proinov and V. S. Grozdanov, On the diaphony of the van der Corput-Halton sequence, J. Number Theory, 30 (1988), 94-104. · Zbl 0654.10050 |
| [34] | K. F. Roth, On irregularities of distribution, Mathematika, 1 (1954), 73-79. · Zbl 0057.28604 |
| [35] | 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. |
| [36] | H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins, Math. Ann., 77 (1916), 313-352. · JFM 46.0278.06 |
| [37] | 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. · Zbl 0356.65007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
