8 The question of Dick, Goda and Suzuki
All nets in this paper are \((0,m,s)\)-nets in base \(q\): every elementary box of volume \(q^{-m}\) contains exactly one point (Lemma 1). This is a property of the point set alone, whatever ring the net is digital over, so Niederreiter’s discrepancy bound for \((t,m,s)\)-nets in an integer base [ 46 ] applies: \(D^*_N\le C_{s,q}(\log N)^{s-1}/N+O_{s,q}\bigl((\log N)^{s-2}/N\bigr)\) for \(N=q^m\), with \(C_{s,q}\) independent of \(m\). So all our nets have low discrepancy in the sense of [ 11 , 10 ] , and the question of Dick, Goda and Suzuki reduces, for these nets, to separation. The same holds for digitally shifted nets, which are again \((0,m,s)\)-nets (Lemma 69).
8.1 Digital shifts
Let \(P\) be a graph form over \(\mathbb {Z}/q\mathbb {Z}\) with depths \(\mathbf k\) and blocks \(\Phi \), and \(\tau =(\tau ^{\mathrm{cell}}_c,\tau ^{\mathrm{off}}_c)_c\) a digital shift (Definition 7), split into its digits on the cell digits and on the offset digits of each coordinate. Then \(P\oplus \tau \) is the set of points whose coordinate \(c\) has the digits \(n_c\) followed by \(\sum _d\Phi _{cd}n_d+\gamma _c\), \(n\in \prod _c(\mathbb {Z}/q\mathbb {Z})^{k_c}\), where \(\gamma _c=\tau ^{\mathrm{off}}_c-\sum _d\Phi _{cd}\tau ^{\mathrm{cell}}_d\). In particular \(n\) is the cell of the point, every cell holds one point, \(P\oplus \tau \) is a \((0,m,s)\)-net if \(P\) is, and for two points in the cells \(n,n'\) every offset digit difference is congruent to the corresponding entry of \(\Phi (n'-n)\) modulo \(q\), as for \(P\).
Substitute \(n=\tilde n-\tau ^{\mathrm{cell}}\) and index the shifted point by \(\tilde n\). The shift maps every elementary box of shape \(d\) bijectively onto one of the same shape, since it shifts the first \(d_c\) digits of coordinate \(c\).
Lemma 4 holds verbatim, with the same bound, for every digital shift of a graph form that satisfies (H1) and (H2). Consequently the lower bounds on the separation in Theorems A, 47, 35, 37, 58 and 119 and in Propositions 21 and 118 hold for every digital shift of the respective nets (in Theorem 35(2) the occupied fine cells form a coset of the lattice), and so does the first-order sharpness in Theorem A(2).
By Lemma 69 the shift only adds the constant \(\gamma \) to the offsets. The proofs use the cells (the step and its carries), the residues of digit differences, the facts that a digit difference lies in \((-q,q)\) and vanishes if its residue does, and \(|f'-f|{\lt}1\); the constant cancels in every residue, and in Lemma 4 the deeper digits of a coordinate whose own axis alone moves are still equal, by (H2). Theorem 37 does not even need the re-indexing by the shifted cells: its proof uses only differences of the skeleton digits. The sharpness argument prescribes the cell digits and the first offset digits of a pair; in the shifted net these are digits of the unshifted net prescribed in translated sets of the same size, so the joint uniformity of the digits of the unshifted net, given by its \(t=0\), suffices.
Let \(p\ge 37\) be prime. For every \(m\ge 3\) and every digital shift, the shifted nets of Corollary 59 satisfy its separation bounds, with the same constants \(0.2715\) and \(0.4250\), and its covering bounds; so they are quasi-uniform along every \(N=p^m\), \(m\ge 3\), as the Larcher–Pillichshammer nets in [ 11 , Thm. 3.11 ] . For \(m\ge 4\) the lower bound still tends to \(1\) as \(p\to \infty \). At \(m=3\) the nets are the column nets \(\mathcal C_p\), whose three coordinates share the second and third digits, and the bound depends on whether the shift keeps them shared:
for every shift, \(\delta N^{1/3}{\gt}0.4693\);
if the shift digits of the three coordinates agree at the second and at the third digit, the exact value of Theorem 51(2) holds;
if they agree at the second digit, \(\delta N^{1/3}\ge 1-(7p-3)/(\sqrt3p^2)\);
otherwise \(1/\sqrt3-7/(\sqrt3p)\le \delta N^{1/3}\le 1/\sqrt3+5/(\sqrt3p)\).
A digital shift keeps one point in every cell and keeps \(t=0\) (Lemma 69), which is all the covering bounds use, except for the mesh-ratio constant \(4.264\) of Corollary 59, which comes from Theorem 35(3); at \(m=3\) this gives \(h\le \sqrt3N^{-1/3}\). In the shifted net the occupied fine cells form a coset \(g+\Lambda _A\) (Proposition 70), and the proof of Theorem 35(3) runs with its target residue moved by \(g_z-\sum _d\rho ^dg_{x_d}\); this is not a translation of the unshifted construction, since the target cell must stay in range. For \(m\ge 4\) the separation bounds of Theorems 47, 58 and 35 used in Corollary 59 hold for every shift by Proposition 70. For \(m=3\) Proposition 54 gives the lower bound \(0.4693{\gt}0.4250\), the exact value and the bound for agreeing shift digits, and otherwise the two bounds \(\frac1{\sqrt3}(1-\frac{W+3}p+\frac3{p^2})\) and \(\frac1{\sqrt3}(1+\frac{3+w_{\max }}p-\frac3{p^2})\) with \(W\le 4\) and \(w_{\max }\le 2\), which lie in the stated interval.
8.2 Well-separated families
Let \(s\ge 2\) and \(q\ge 2\) be integers and \(I\subseteq \mathbb {N}\) infinite, and for \(m\in I\) let \(\mathcal P_m\subset [0,1)^s\) be a \((0,m,s)\)-net in base \(q\) whose toroidal minimum distance satisfies \(\delta \ge c\, q^{-m/s}\), with \(c{\gt}0\) independent of \(m\). Then every \(\mathcal P_m\) is \(\kappa _m\)-separated and toroidally \(\kappa _m\)-separated in base \(q\) [ 11 , Def. 3.3 ] , with
so \((\mathcal P_m)_{m\in I}\) is a well-separated and toroidally well-separated family on \(I\) [ 11 , Def. 3.8 ] . In particular:
the nets \(\mathcal P_{k,q}\) of Theorem 47, for every integer \(q\ge 4\), are \((k+1)\)-separated, i.e. \(\kappa _m=m/3+1\) on \(I=\{ 3k:k\ge 2\} \);
the nets of Theorem A(2) are \((k+1)\)-separated on \(I=\{ sk:k\ge 1\} \);
the nets \(\mathcal H^s_{k,p}\) of Theorem 119 are \((k+1)\)-separated for every prime \(p\ge \max (2s,2B_s+4)\) (two more than in Theorem 119; see Step 3 of the proof) and every \(k\ge 1\);
the nets \(\mathcal S^1_{k,p,\rho }\) of Theorem 35, with \(m=sk+s-1\), are \((k+1)\)-separated, i.e. \(\kappa _m=\lceil m/s\rceil \), if \((\rho -1)^2\ge s\) (for \(\rho =\lfloor p^{1/s}\rfloor \) this holds when \(p{\gt}(\lceil \sqrt s\rceil +1)^s\)), and \((k+2)\)-separated otherwise;
for every prime \(p\ge 37\) the nets of Corollary 59 are \((\lfloor m/3\rfloor +1)\)-separated for every \(m\ge 3\).
All of these hold toroidally as well, and for every digital shift (Definition 7) of the respective nets. For prime \(q\) the nets are digital nets over \(\mathbb {F}_q\) in the sense of [ 11 , Def. 2.1 ] ; this covers (3)–(5) entirely and the prime instances of (1) and (2). For composite \(q\) the nets of (1) and (2) are digital over \(\mathbb {Z}/q\mathbb {Z}\), which is not covered by [ 11 , Def. 2.1 ] ; Definitions 3.1 and 3.2 of [ 11 ] are stated for every integer base \(b\ge 2\), and we read Definitions 3.3 and 3.8 in the same generality.
Step 1 ( [ 11 , Lemma 3.7 ] , with strict inequality). Let \(P\subset [0,1)^s\) be finite and \(\kappa \ge 0\), and suppose every two distinct points of \(P\) have toroidal \(\ell ^\infty \)-distance at least \(q^{-\kappa }\). A toroidal shifted elementary interval \(\tilde J_{\mathbf c,a,e}\) with \(\kappa \) digits in every coordinate, \(\mathbf c=(\kappa ,\dots ,\kappa )\) [ 11 , Def. 3.2 ] , is contained in a product of sets \(I_j\bmod 1\), where \(I_j=[\alpha _j,\alpha _j+q^{-\kappa })\) is half-open. If \(x,y\in \tilde J_{\mathbf c,a,e}\), then for each \(j\) there are \(z,z'\in \mathbb {Z}\) with \(x_j+z,\ y_j+z'\in I_j\), so \(\min (|x_j-y_j|,1-|x_j-y_j|)\le |(x_j+z)-(y_j+z')|{\lt}q^{-\kappa }\), and hence \(x=y\). So \(P\) is toroidally \(\kappa \)-separated. A non-toroidal interval \(J_{\mathbf c,a,e}\) gives the same bound for \(|x_j-y_j|\), which is at least the toroidal distance, so \(P\) is also \(\kappa \)-separated. This sharpens the contrapositive of [ 11 , Lemma 3.7 ] to the strict bound \(q_\infty (P){\lt}1/(2q^\kappa )\) for non-separated \(P\), where \(q_\infty (P)\) is the separation radius of [ 11 ] in the maximum norm; the strictness comes from the intervals being half-open.
Step 2. For distinct \(x,y\in \mathcal P_m\) the toroidal coordinate distances \(t_j\) satisfy \(\sum _jt_j^2\ge \delta ^2\), so \(\max _jt_j\ge \delta /\sqrt s\ge (c/\sqrt s)\, q^{-m/s}\ge q^{-\kappa _m}\) by the choice of \(\kappa _m\). Since toroidal distances are at most \(\sqrt s/2\), we have \(c\, q^{-m/s}\le \sqrt s/2\), so \(\kappa _m\ge 1\). Step 1 gives the separation, and \(\kappa _m-m/s\le 1+\log _q(\sqrt s/c)\) is bounded, which is the condition of [ 11 , Def. 3.8 ] .
Step 3 (the families). By Step 2 a net with \(\delta \ge \theta \, q^{-\kappa }\) is \(\kappa \)-separated as soon as \(\theta \ge \sqrt s\). (1) \(m=3k\) and \(\delta \ge c(q)q^{-k}\) (Theorem 48); with \(\kappa =k+1\) we need \(q\, c(q)\ge \sqrt3\), i.e. \(\min \{ (q-1)^2,(q-2)^2+(q-4)^2,3(q-3)^2\} \ge 3\), which holds for \(q\ge 4\) (with equality at \(q=4\)). (2) \(\delta \ge (1-a^*_s/q)q^{-k}\); with \(\kappa =k+1\) we need \(q-a^*_s\ge \sqrt s\). From \(q\ge 5a^*_s+4\) we get \(q-a^*_s\ge \frac45(q+1)\), and from \(\operatorname {lpf}(q)\ge s-1\) we get \(q+1\ge s\), so \(q-a^*_s\ge \frac45s\ge \sqrt s\) for \(s\ge 2\). (3) \(\delta \ge c_p\, p^{-k}\) with \(c_p=\min (\sqrt s(\frac12-\epsilon _p),\sqrt2(1-\epsilon _p))\) and \(\epsilon _p=(B_s+1)/p\); with \(\kappa =k+1\) we need \(p\, c_p\ge \sqrt s\). If \(p\ge 2B_s+4\), then \(\sqrt s(\frac12-\epsilon _p)p=\frac{\sqrt s}2(p-2B_s-2)\ge \sqrt s\) and \(\sqrt2(1-\epsilon _p)p\ge p/\sqrt2\ge \sqrt2\, s\ge \sqrt s\), since \(\epsilon _p\le \frac12\) and \(p\ge 2s\). (4) \(m=sk+s-1\) and \(\delta \ge (\rho -1)p^{-(k+1)}\) (Theorem 35(1)); \(\kappa =k+1\) needs \(\rho -1\ge \sqrt s\), and otherwise \(\kappa =k+2\) needs \((\rho -1)p\ge \sqrt s\), which holds as \(p{\gt}2^s\). If \(p{\gt}(\lceil \sqrt s\rceil +1)^s\), then \(\rho =\lfloor p^{1/s}\rfloor \ge \lceil \sqrt s\rceil +1\). (5) \(m=3\): \(\delta \ge \sqrt{2/3}\, p^{-1}\) (Theorem 50), and \(\kappa =2\) needs \(p\sqrt{2/3}\ge \sqrt3\), i.e. \(p\ge 3/\sqrt2\). \(m=3k\), \(k\ge 2\): part (1). \(m=3k+1\): \(\delta \ge (\rho ^2-4)p^{-(k+1)}\) with \(\rho \) maximal subject to \(\rho ^2(\rho +1)\le p\) (Theorem 58), and \(p\ge 37\) gives \(\rho \ge 3\), so \(\rho ^2-4\ge 5\ge \sqrt3\) and \(\kappa =k+1\). \(m=3k+2\): part (4) with \(s=3\) and \(\rho =\lfloor p^{1/3}\rfloor \ge 3\), so \((\rho -1)^2=4\ge 3\) and \(\kappa =k+1\). In every case \(\kappa _m=\lfloor m/3\rfloor +1\).
Digital shifts. By Proposition 70 the separation bounds used in (1)–(4) and, for \(m\ge 4\), in (5) hold for every digitally shifted net. For \(m=3\), Proposition 54(3) gives \(\delta \ge \frac1{\sqrt3}(1-\frac{W+3}p+\frac3{p^2})\, p^{-1}\) with \(W\le 4\), and \(\kappa =2\) needs \(p^2-(W+6)p+3\ge 0\), which holds for \(p\ge 10\).
Definition 3.8 of [ 11 ] constrains only \(m\in I\), and finitely many further resolutions can be added at no cost. If \(\mathcal Q\subset q^{-m}\mathbb {Z}^s\cap [0,1)^s\) is a \((0,m,s)\)-net in base \(q\), the elementary boxes of shape \((m,0,\dots ,0)\) each hold one point, so the first coordinates of the points are distinct elements of \(q^{-m}\mathbb {Z}\cap [0,1)\) and any two of them have toroidal distance at least \(q^{-m}\); by Step 1 of the proof of Corollary 73, \(\mathcal Q\) is \(m\)-separated and toroidally \(m\)-separated. Adding finitely many such \(m\) to \(I\) changes the \(O(1)\) of [ 11 , Def. 3.8 ] by a constant. In dimension three digital \((0,m,3)\)-nets over \(\mathbb {Z}/q\mathbb {Z}\) exist for every integer \(q\ge 2\) (over \(\mathbb {F}_p\) for every prime \(p\)) and every \(m\ge 1\): by Lemma 11, whose proof does not use \(m\equiv 0\pmod s\), every box minor of the frame of the places \(\infty ,0,1\) is \(\pm 1\), a unit modulo every \(q\), so the frame is one (Lemma 1; see also [ 46 , Thm. 6.2, Cor. 6.3 ] and [ 14 , Sec. 8.2 ] ), and trivially for \(m=0\). Together, Theorems 47 and 51, Corollary 59, Remark 60 and Theorem 66 cover all but finitely many \(m\) in each prime base with a constant independent of \(m\); with the frame nets for the remaining \(m\) they give well-separated families on all of \(\mathbb {N}\), in every prime base. The same holds under every digital shift: the constants survive every shift (Proposition 70, Corollary 71, Remark 135 and Theorem 66(3)), and a digitally shifted \((0,m,s)\)-net is again a \((0,m,s)\)-net on the grid \(q^{-m}\mathbb {Z}^s\) (Lemma 69), so the argument above applies to it.
8.3 The maximum norm
Let \(q\ge 4\), \(k\ge 2\). For every digital shift \(\tau \), any two distinct points of \(\mathcal P_{k,q}\oplus \tau \) have toroidal \(\ell ^\infty \)-distance at least \((1-3/q)\, q^{-k}\). Hence the \(\ell ^\infty \) mesh ratio of \(\mathcal P_{k,q}\oplus \tau \) in the sense of [ 11 ] , toroidal or not, is at most \(2q/(q-3)\), and \(\mathcal P_{k,q}\oplus \tau \) is toroidally \((k+1)\)-separated [ 11 , Def. 3.3 ] .
By Proposition 70 the proof of Theorem 48 applies to \(\mathcal P_{k,q}\oplus \tau \). In its sign analysis every step has a coordinate with \(|\Delta _i|\ge 1-3/q\) (\(=\beta _3\) in that proof): an own-axis step has \(\beta _1\); for \(\nu =2\), (iv) gives a backward coordinate with \(|\sigma |\le 1\) or \(\sigma =0\); for \(\nu =3\), a forward coordinate or a backward one with \(|\sigma |=3\) forces a backward one with \(|\sigma |\le 1\) by (ii), (iii), and otherwise all three are backward with \(|\sigma |\le 2\). One point per cell gives \(h_\infty \le q^{-k}\), and \((1-3/q)q^{-k}\ge q^{-k-1}\) for \(q\ge 4\); the separation statement is Step 1 of the proof of Corollary 73.