\(L_2\) discrepancy of generalized Zaremba point sets. (English. French summary) Zbl 1277.11081

Faure, Henri; Pillichshammer, Friedrich

J. Théor. Nombres Bordx. 23, No. 1, 121-136 (2011).

The authors of this paper study the \(L_2\) discrepancy of finite point sets in the half-open unit square \([0,1)^2\). It is known due to a result by Roth that any point set \(P_N\) of \(N\) points in \([0,1)^2\) satisfies a lower bound of order \(\sqrt{\log N}\) for its \(L_2\) discrepancy. Several results on how to find point sets satisfying an upper bound on the \(L_2\) discrepancy of the same order have been obtained during the past decades.
This paper also deals with the explicit construction of such point sets. To be more precise, it is shown in the paper that certain modifications of the two-dimensional Hammersley point set with \(N\) points have an \(L_2\) discrepancy of order \(\sqrt{\log N}\). To obtain their results, the authors study special digital shifts of Hammersley point sets in an arbitrary base \(b\), a modification which they refer to as generalized Zaremba point sets. The main result of the paper states how the frequency of certain permutations in the construction of a generalized Zaremba point set can be related to its \(L_2\) discrepancy. In particular, this yields explicit constructions of generalized Zaremba point sets with an \(L_2\) discrepancy of optimal order in the sense of Roth’s result. The findings in the paper generalize and extend earlier results by Halton and Zaremba, White, and Kritzer and Pillichshammer.

Reviewer: Peter Kritzer (Linz)

MSC:

11K38	Irregularities of distribution, discrepancy
11K06	General theory of distribution modulo \(1\)

Keywords:

Discrepancy; \(L_2\) discrepancy; Hammersley point sets, Zaremba point sets; digitally shifted point sets

References:

[1]	H. Chaix and H. Faure, Discrépance et diaphonie en dimension un. Acta Arith. 63 (1993), 103-141. · Zbl 0772.11022
[2]	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. · Zbl 1083.11049
[3]	W .W .L .Chen and M. M. Skriganov, Orthogonality and digit shifts in the classical mean squares problem in irregularities of point distribution. In Diophantine approximation, Dev. Math. 16, 141-159, Springer, New York Vienna, 2008. · Zbl 1233.11082
[4]	H. Davenport, Note on irregularities of distribution. Mathematika 3 (1956), 131-135. · Zbl 0073.03402
[5]	J. Dick and F. Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge, 2010. · Zbl 1282.65012
[6]	H. Faure, Discrépance de suites associées à un système de numération (en dimension un). Bull. Soc. Math. France 109 (1981), 143-182. · Zbl 0488.10052
[7]	H. Faure and F. Pillichshammer, \(L_p\) discrepancy of generalized two-dimensional Hammersley point sets. Monatsh. Math. 158 ( 2009), 31-61. · Zbl 1175.11042
[8]	H. Faure and F. Pillichshammer, \(L_2\) discrepancy of two-dimensional digitally shifted Hammersley point sets in base \(b\). In Monte Carlo and Quasi-Monte Carlo Methods 2008, P. L’Ecuyer and A. Owen (eds.), 355-368, Springer-Verlag, Berlin Heidelberg, 2009. · Zbl 1228.11122
[9]	H. Faure, F. Pillichshammer, G. Pirsic and W. Ch. Schmid, \(L_2\) discrepancy of generalized two-dimensional Hammersley point sets scrambled with arbitrary permutations. Acta. Arith. 141 (2010), 395-418. · Zbl 1198.11072
[10]	J.H. Halton and S.K. Zaremba, The extreme and the \({L}^2\) discrepancies of some plane sets. Monatsh. Math. 73 (1969), 316-328. · Zbl 0183.31401
[11]	P. Kritzer and F. Pillichshammer, An exact formula for the \(L_2\) discrepancy of the shifted Hammersley point set. Uniform Distribution Theory 1 (2006), 1-13. · Zbl 1147.11041
[12]	L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences. John Wiley, New York, 1974; reprint, Dover Publications, Mineola, NY, 2006. · Zbl 0281.10001
[13]	G. Larcher and F. Pillichshammer, Walsh series analysis of the \(L_2\)-discrepancy of symmetrisized point sets. Monatsh. Math. 132 (2001), 1-18. · Zbl 1108.11309
[14]	F. Pillichshammer, On the \(L_p\)-discrepancy of the Hammersley point set. Monatsh. Math. 136 (2002), 67-79. · Zbl 1010.11043
[15]	P. D. Proinov, Symmetrization of the van der Corput generalized sequences. Proc. Japan Acad. 64 (1988), Ser. A, 159-162. · Zbl 0654.10049
[16]	K.F. Roth, On irregularities of distribution. Mathematika 1 (1954), 73-79. · Zbl 0057.28604
[17]	I.V. Vilenkin, Plane nets of Integration. Ž. Vyčisl. Mat. i Mat. Fiz. 7 (1967), 189-196. (English translation in: U.S.S.R. Computational Math. and Math. Phys. 7 (1) (1967), 258-267.) · Zbl 0187.10701
[18]	B.E. White, Mean-square discrepancies of the Hammersley and Zaremba sequences for arbitrary radix. Monatsh. Math. 80 (1975), 219-229. · Zbl 0322.65002