×

On the mean square weighted \({\mathcal L}_2\) discrepancy of randomized digital \((t,m,s)\)-nets over \({\mathbb Z}_2\). (English) Zbl 1080.11058

For a set \(P_N=\{\mathbf{x}_0, \ldots , \mathbf{x}_{N-1}\}\) of points in the \(s\)-dimensional unit cube \([0,1)^s\) the discrepancy function is defined as \(\Delta(t_1,\dots , t_s)=A_N([0,t_1)\times \cdots \times [0,t_s))/N-t_1\cdots t_s\), where \(0\leq t_j\leq 1\) and \(A_N([0,t_1)\times \cdots \times [0,t_s))\) denotes the number of indices \(n\) with \(\mathbf{x}_n\in [0,t_1)\times \cdots \times [0,t_s)\). Let \(D=\{1, \ldots , s\}\). For \({\mathfrak u}\subseteq D\) let \(\gamma_{{\mathfrak u}}\) be a nonnegative real number, \(| {\mathfrak u}| \) the cardinality of \({\mathfrak u}\) and for a vector \(\mathbf{x}\in [0,1)^s\) let \(\mathbf{x}_{{\mathfrak u}}\) denote the vector from \([0,1)^{| {\mathfrak u}| }\) containing all components of \(\mathbf{x}\) whose indices are in \({\mathfrak u}\). Let \(d\mathbf{x}_{{\mathfrak u}}=\prod_{j\in {\mathfrak u}}dx_j\) and let \((\mathbf{x}_{{\mathfrak u}},1)\) be the vector from \([0,1)^s\) with all components whose indices are not in \({\mathfrak u}\) replaced by 1. The authors define the weighted \({\mathcal L}_2\) discrepancy of \(P_N\) as follows: \[ {\mathcal L}_{2,N,\gamma}(P_N)= \biggl( \sum_{\substack{ {\mathfrak u}\subseteq D\\ {\mathfrak u}\neq \emptyset}} \gamma_{{\mathfrak u}}\int_{{[0,1]}^{| {\mathfrak u} | }} \Delta ((\mathbf{x}_{{\mathfrak u}},1))^2\, d\mathbf{x}_{{\mathfrak u}}\biggr)^{1/2}. \] In this paper the weighted \({\mathcal L}_2\) discrepancy of randomized digital \((t,m,s)\)-nets over \(\mathbb{Z}_2\) is investigated. The randomization method considered here is a digital shift of depth \(m\), i.e., for each coordinate the first \(m\) digits of each point are shifted by the same shift whereas the remaining digits in each coordinate are shifted independently for each point.
Theorem 1 gives a formula for the mean square weighted \({\mathcal L}_2\) discrepancy \(\mathbf{E}[{\mathcal L}_{2,2^m,\gamma}^2(\widetilde{P}_{2^m})]\) of randomized digital nets \(\widetilde{P}_{2^m}\). In Theorem 2 the authors derive an exact formula for the mean square weighted \({\mathcal L}_2\) discrepancy of radomized digital \((0,m,s)\)-nets in dimensions \(s=2\) and \(s=3\). Theorem 3 gives an upper bound of the mean square weighted \({\mathcal L}_2\) discrepancy of randomized digital \((t,m,s)\)-nets over \(\mathbb{Z}_2\). The convergence order in Theorem 3 is best possible.
The authors also consider the classical \({\mathcal L}_2\) discrepancy, i.e., \(\gamma_D=1\) and \(\gamma_{{\mathfrak u}}=0\) for \({\mathfrak u}\subset D\), of certain shifted \((t,m,s)\)-nets. By using Theorem 4 and a result of H. Niederreiter and C. P. Xing [Rational points on curves over finite fields. Theory and Applications. Cambridge University Press, Cambridge (2001; Zbl 0971.11033)], Corollary 3 follows. Corollary 3 says that there exists a shifted digital \((5s,m,s)\)-net over \(\mathbb{Z}_2\) such that the upper bound of the classical \({\mathcal L}_2\) discrepancy is \[ \frac{(\log N)^{(s-1)/2}}{N}\frac{22^s}{(\log 2)^{(s-1)/2}((s-1)!)^{1/2}} +O\left(\frac{(\log N)^{(s-2)/2}}{N}\right). \] Here the constant \(22^s(\log 2)^{-(s-1)/2}((s-1)!)^{-1/2}\) improves Hickernell’s considerably.
In Theorem 5 the authors finally give an upper bound on the classical \({\mathcal L}_2\) discrepancy of shifted Niederreiter-Xing nets [H. Niederreiter and C. Xing, Acta Arith. 102, 189–197 (2002; Zbl 0988.11032)], where the number of points is relatively small compared to the dimension. This shows that Roth’s lower bound is in the dimension \(s\) of the best possible form.

MSC:

11K38 Irregularities of distribution, discrepancy
11K06 General theory of distribution modulo \(1\)
PDFBibTeX XMLCite
Full Text: DOI