\(L_2\) discrepancy of generalized Zaremba point sets (Q449693)

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.