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

DOI10.5802/JTNB.1074MaRDI QIDQ2199494zbMATH OpenOpenAlexFDO

Authors Ralph Kritzinger, Friedrich Pillichshammer

Publication date 11 September 2020

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://arxiv.org/abs/1804.04891

zbMATH Keywords

\(L_p\) discrepancy digital nets Hammersley net

Mathematics Subject Classification ID

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

Abstract: 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

s q r t l o g N / 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 i n [1, i n f t y)

. 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 a l p h a)

for

k = 0, 1, l d o t s, N - 1

, and who gave Diophantine properties of

a l p h a

which guarantee the optimal order of

L_{2}

discrepancy.

Review text

The paper deals with digital \((0,m,2)\)-nets over \(\mathbb{Z}_2\). Such nets are point sets with \(2^m\), \(m\in\mathbb{N}\), points in the unit square with very regular distribution properties. The points of a \((0,m,2)\)-net are generated by means of linear algebra, and are characterized by two generating matrices \(C_1\) and \(C_2\) of size \(m\times m\) over \(\mathbb{Z}_2\). Digital nets are frequently studied in the theory of uniform distribution modulo one, where one considers to which extent the points are evenly distributed. The level of uniform distribution can be assessed by studying the so-called discrepancy function, which compares the number of points of a given point set in axes-parallel boxes to the volumes of these boxes. Taking \(L_p\)-norms of the discrepancy function then yields the notions of \(L_p\)-discrepancy for \(p\in[1,\infty]\). Given a point set of \(N\) points in the unit square, it is an intriguing question what the order of magnitude with respect to \(N\) of the \(L_p\)-discrepancy of the point set is. The authors consider a particular choice of the generating matrices \(C_1\) and \(C_2\) of a digital \((0,m,2)\)-net over \(\mathbb{Z}_2\), namely \[ C_1= \begin{pmatrix} 0 & 0 & \ldots & 0 & 1\\ 0 & 0 & \ldots & 1 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 1 & \ldots & 0 & 0\\ 1 & 0 & \ldots & 0 & 0\\ \end{pmatrix},\ \ \ C_2=\begin{pmatrix} 1 & a_1 & a_1 & \ldots & a_1 & a_1\\ 0 & 1 & a_2 & \ldots & a_2 & a_2\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0 &\ldots & 1 & a_{m-1}\\ 0 & 0 & 0 &\ldots & 0 & 1\\ \end{pmatrix}, \] i.e., \(C_2\) is an upper-triangular matrix with a special structure. Previously, it was known that one can obtain point sets with optimal order of \(L_2\)-discrepancy by applying a symmetrization method to digital \((0,m,2)\)-nets. The present paper shows further progress on this question by proving that by choosing the matrices \(C_1\) and \(C_2\) as above, and making a suitable assumption on the \(a_i\) in the matrix \(C_2\), one can also obtain digital nets with optimal order of \(L_p\)-discrepancy for \(p\in [1,\infty)\), but without the need to symmetrize the net anymore. Indeed, the main result of the paper implies that the \(L_p\)-discrepancy of a digital \((0,m,2)\)-net generated by \(C_1\) and \(C_2\) of the above form, and with \(N=2^m\) points, is of order \[ \mathcal{O} \left(\frac{\max (\sqrt{\log N}, h_m (\boldsymbol{a}))}{N}\right), \] where \(h_m (\boldsymbol{a})\) is defined as \(h_m (\boldsymbol{a})=\sum_{i=1}^m (1-a_i)\), i.e., \(h_m (\boldsymbol{a})\) counts how many of the \(a_i\) in \(C_2\) are zero. In particular, if \(h_m (\boldsymbol{a})\) is of order \(\mathcal{O} (\sqrt{\log N})\), the order of magnitude of the \(L_p\)-discrepancy of the corresponding digital net is \(\mathcal{O} (\sqrt{\log N} /N)\), which is optimal due to classical results in discrepancy theory.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Digital nets in dimension two with the optimal order of \(L_p\) discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2199494)