math.NA — Numerical Analysis

Low-discrepancy quasi-uniform digital nets in every dimension

Contributed by Leonhard Gruenschloss

Dick, Goda and Suzuki asked for low-discrepancy digital nets that are quasi-uniform, with minimum distance $\delta$ and covering radius both of the optimal order $N^{-1/s}$, and stated the problem as open in dimension $s\ge3$. We construct such nets in every dimension. For every $s\ge3$, every base $q$ whose prime factors are at least $s-1$, and every $k\ge1$, we give explicit digital $(0,sk,s)$-nets over $\Z/q\Z$ with $N=q^{sk}$ points, covering radius at most $\sqrt s\,N^{-1/s}$, and $\delta N^{1/s}\ge1-a^*_s/q$ once $q\ge5a^*_s+4$. The constant $a^*_s\le e^{s\log s+O(s)}$ is computed from $s$ by a deterministic polynomial-time lattice algorithm. In dimension three every $N=p^m$, $m\ge3$, is covered for each prime $p\ge37$, and, with computer assistance, every $N=2^m$ and $N=3^m$. In prime bases these families are well separated in the sense of Dick, Goda and Suzuki, and they stay so under every digital shift. One mechanism underlies all constructions. For $N=q^{sk}$ it reads as follows. The first $k$ base-$q$ digits of a point's coordinates select a cube of side $q^{-k}$, and a $(0,sk,s)$-net has exactly one point in each such cube. Digit $k+1$ of each coordinate is a linear function of the first $k$ digits of all coordinates, because the net is digital. We choose this linear function so that, between the planes where this digit wraps around modulo $q$ or where a carry occurs among the first $k$ digits, the points lie on a translate of one lattice; for the main theorem this lattice is a slightly distorted copy of $\Z^s$. All later digits move a point by less than $1/q$ of the cube side. Part~II studies the constant $K$ in $\delta N^{1/s}=1-K/q+O(q^{-2})$. We prove lower bounds on $K$ when the linear maps have bounded coefficients. At $N=q^3$ we find the optimal $K$ among nets whose points lie on lines parallel to the main diagonal. With the cube-tiling theorems of Haj\'os and Keller we show that idealized lattices with one point per cube, whose points sit independently inside their cubes, cannot exceed $\delta N^{1/s}=1$. When the positions inside the cubes are coupled, the value $1$ can be exceeded: $\delta N^{1/3}\to\sqrt{281}/16$ at $N=p^3$, $\delta N^{1/5}>1$ for $(0,5,5)$-nets from $p=37$ on, and $\delta N^{1/s}\to\min(\sqrt s/2,\sqrt2)$ at $N=p^{sk}$, which is the $E_8$ value at $s=8$ (limits as $p\to\infty$). The results are formalized in Lean~4, apart from some finite computations, which are checked by scripts.