Digital nets in dimension two with the optimal order of $L_p$ discrepancy

Kritzinger, Ralph; Pillichshammer, Friedrich

Journal de théorie des nombres de Bordeaux, Tome 31 (2019) no. 1, pp. 179-204.

Nous étudions la discrépance $L_p$ ($p\in [1,\infty )$) de réseaux digitaux de dimension $2.$ En 2001, Larcher et Pillichshammer ont identifié une classe de $(0,n,2)$-réseaux pour lesquels la version symétrisée au sens de Davenport a une discrépance $L_2$ d’ordre $\sqrt{logN}/N$, qui est optimal grâce au résultat célèbre de Roth. Cependant la question de savoir si la même borne s’applique à la discrépance des réseaux originaux est restée ouverte.

Dans cet article, nous identifions les réseaux digitaux de la classe susmentionnée pour lesquels la symétrisation n’est pas nécessaire pour obtenir l’ordre optimal de la discrépance $L_p$ pour $p\in [1,\infty )$.

Ce résultat est dans l’esprit d’un article de Bilyk de 2013, qui a étudié la discrépance $L_2$ des ensembles des points de la forme $(k/N,\{k\alpha \left\}\right)$ pour $k=0,1,...,N-1$ et a donné des propriétés diophantiennes de $\alpha$ qui garantissent l’ordre optimal de la discrépance $L_2$.

We study the $L_p$ discrepancy of two-dimensional digital nets for finite $p$. In the year 2001 Larcher and Pillichshammer identified a class of digital nets for which the symmetrized version in the sense of Davenport has $L_2$ discrepancy of the order $\sqrt{logN}/N$, which is best possible due to the celebrated result of Roth. However, it remained open whether this discrepancy bound also holds for the original digital nets without any modification.

In the present paper we identify nets from the above mentioned class for which the symmetrization is not necessary in order to achieve the optimal order of $L_p$ discrepancy for all $p\in [1,\infty )$.

Our findings are in the spirit of a paper by Bilyk from 2013, who considered the $L_2$ discrepancy of lattices consisting of the elements $(k/N,\{k\alpha \left\}\right)$ for $k=0,1,...,N-1$, and who gave Diophantine properties of $\alpha$ which guarantee the optimal order of $L_2$ discrepancy.

Classification : 11N06, 11K38
Mots clés : $L_p$ discrepancy, digital nets, Hammersley net

[1] Bilyk, Dmitriy The $L^2$-discrepancy of irrational lattices, Monte Carlo and Quasi-Monte Carlo Methods 2012 (Springer Proceedings in Mathematics & Statistics), Volume 65, Springer, 2013, pp. 289-296 | DOI | MR | Zbl

[2] Davenport, Harold Note on irregularities of distribution, Mathematika, Volume 3 (1956), pp. 131-135 | DOI | MR | Zbl

[3] Dick, Josef; Pillichshammer, Friedrich Digital nets and sequences. Discrepancy theory and quasi-Monte Carlo integration, Cambridge University Press, 2010 | Zbl

[4] Faure, Henri; Pillichshammer, Friedrich $L_p$ discrepancy of generalized two-dimensional Hammersley point sets, Monatsh. Math., Volume 158 (2009) no. 1, pp. 31-61 | DOI | Zbl

[5] Halász, Gabor On Roth’s method in the theory of irregularities of point distributions, Recent progress in analytic number theory, Academic Press Inc., 1981, pp. 79-94 | Zbl

[6] Halton, John H.; Zaremba, Stanislaw K. The extreme and $L^2$ discrepancies of some plane sets, Monatsh. Math., Volume 73 (1969), pp. 316-328 | DOI | MR | Zbl

[7] Hinrichs, Aicke Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness, Math. Nachr., Volume 283 (2010) no. 3, pp. 478-488 | DOI | MR | Zbl

[8] Hinrichs, Aicke; Kritzinger, Ralph; Pillichshammer, Friedrich Optimal order of $L_p$ discrepancy of digit shifted Hammersley point sets in dimension 2, Unif. Distrib. Theory, Volume 10 (2015) no. 1, pp. 115-133 | Zbl

[9] Kritzinger, Ralph Finding exact formulas for the $L_2$ discrepancy of digital $(0,n,2)$-nets via Haar functions, Acta Arith., Volume 187 (2018) no. 2, pp. 151-187 | DOI | MR | Zbl

[10] Kuipers, L.; Niederreiter, Harald Uniform distribution of sequences, Pure and Applied Mathematics, John Wiley & Sons, 1974 | Zbl

[11] Larcher, Gerhard; Pillichshammer, Friedrich Walsh series analysis of the $L_2$ discrepancy of symmetrisized point sets, Monatsh. Math., Volume 132 (2001) no. 1, pp. 1-18 | DOI | Zbl

[12] Larcher, Gerhard; Pillichshammer, Friedrich Sums of distances to the nearest integer and the discrepancy of digital nets, Acta Arith., Volume 106 (2003) no. 4, pp. 379-408 | DOI | MR | Zbl

[13] Leobacher, Gunther; Pillichshammer, Friedrich Introduction to Quasi-Monte Carlo Integration and Applications, Compact Textbooks in Mathematics, Birkhäuser, 2014 | DOI | Zbl

[14] Lerch, Matyáš Question 1547, L’Intermédiaire des Mathématiciens, Volume 11 (1904), pp. 144-145

[15] Niederreiter, Harald Point sets and sequences with small discrepancy, Monatsh. Math., Volume 104 (1987), pp. 273-337 | DOI | MR | Zbl

[16] Niederreiter, Harald Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, 63, Society for Industrial and Applied Mathematics, 1992 | MR | Zbl

[17] Pillichshammer, Friedrich On the $L_p$ discrepancy of the Hammersley point set, Monatsh. Math., Volume 136 (2002) no. 1, pp. 67-79 | DOI | Zbl

[18] Roth, Klaus F. On irregularities of distribution, Mathematika, Volume 1 (1954), pp. 73-79 | DOI | Zbl

[19] Schmidt, Wolfgang M. Irregularities of distribution. VII., Acta Arith., Volume 21 (1972), pp. 45-50 | DOI | MR | Zbl

[20] Schmidt, Wolfgang M. Irregularities of distribution. X, Number Theory and Algebra, Academic Press Inc., 1977, pp. 311-329 | Zbl

[21] Vilenkin, I. V. Plane nets of integration, Zh. Vychisl. Mat. Mat. Fiz., Volume 7 (1967) no. 1, pp. 189-196 | MR | Zbl

[22] Warnock, Tony T. Computational investigations of low discrepancy point sets, Applications of Number Theory to Numerical Analysis, Academic Press Inc., 1972 | MR | Zbl