7 Bases two and three: the deep-shift lift
A \((0,m,s)\)-net in base \(2\) with \(m\ge 2\) requires \(s\le 3\) [ 46 , Cor. 5.11 ] ; for digital nets over rings see [ 39 , Thm. 2 ] . So \(s=3\) is the largest dimension in which one set of integer generator matrices can give \(t=0\) in every base (for dimension \(s\) see the text after Lemma 11). In the frame language of Section 3: \(t=0\) in every base needs places whose pairwise differences are \(\pm 1\); \(\{ 0,1\} \) is the largest set of integers with this property (in the language of exceptional units [ 36 ] ), and the place \(\infty \) gives the third coordinate.
Let \(P\) be as above, \(0\le D\), and let \(s_A,s_B\in \mathbb {F}_b^{3m_0}\) vanish on the first \(D\) digits of each coordinate, i.e. change only the deep digits, those of index \({\gt}D\). They are separating if, for every \(1\le e\le m_0\),
where \(s^{cc'}\) is the restriction of \(s\) to the coordinates \(c,c'\). The lift \(L_D(P)\) is the set of \(b^{m_0+3}\) points with index \((n,\alpha ,\beta _1,\beta _2)\in \mathbb {F}_b^{m_0+3}\) whose coordinates have the \(m_0+3\) digits
one top digit, \(m_0\) block digits and two jitter digits. The shift \(\tau \) of \(P\) stays in the block digits, so \(L_D(P)\) is again a digitally shifted digital net over \(\mathbb {F}_b\).
Let \(P\) be a digitally shifted digital \((0,m_0,3)\)-net over \(\mathbb {F}_b\).
If \(s_A,s_B\) are separating, then \(L_D(P)\) is a digitally shifted digital \((0,m_0+3,3)\)-net over \(\mathbb {F}_b\).
If \(2D\le m_0\), separating \(s_A,s_B\) exist.
(A) Let \((d_x,d_y,d_z)\) be a box shape with \(\sum _cd_c=m_0+3\); by Lemma 1 it suffices that the box map, from the index to the prescribed digits, is injective. All \(d_c\ge 1\). The top digits \((\alpha ,\alpha +\beta _1,\alpha +\beta _1+\beta _2)\) determine \((\alpha ,\beta )\). The remaining depths \(d_c-1\) sum to \(m_0\) and are at most \(m_0\) each, so no jitter digit is prescribed, and what remains is an \(m_0\)-box of the shifted net \(P+s_\beta \), which is injective. Exactly one \(d_c=0\), say \(d_x=0\) (the cases \(d_y=0\), \(d_z=0\) are the same with the pairs \(xz\) and \(xy\)). The top digits of \(y\) and \(z\) fix \(\alpha +\beta _1\) and \(\beta _2\), and the remaining index is \((n,t)\) with \(t=\beta _1\); the block digits of \((y,z)\) are those of \(P_{yz}+\text{const}+t\, s_A^{yz}\). If \(d_y-1=e\) and \(d_z-1=m_0+1-e\) with \(1\le e\le m_0\), injectivity on \((n,t)\) is injectivity of the projection to the first \(e\) resp. \(m_0+1-e\) digits on \(P_{yz}+\mathbb {F}_bs_A^{yz}\); it holds on \(P_{yz}\) by the \((e,m_0-e)\) box, and for \(t\ne 0\) a collision would put \(s_A^{yz}\) in \(H_e=\ker \lambda ^{yz}_e\), which the separating condition excludes. If \(d_y=1\) or \(d_z=1\), the other coordinate reads all of its block and one jitter digit, \(\beta _1\) for \(z\) and \(\beta _1+\beta _2\) for \(y\), which determines \(t\), and then the block determines \(n\). For \(d_y=0\) the pair is \((x,z)\) with the line \(s_B-s_A\) and the jitter digits \(\beta _2\), \(\beta _1\); for \(d_z=0\) it is \((x,y)\) with \(s_B\) and \(\beta _2\), \(\beta _1+\beta _2\). Two \(d_c=0\). One coordinate carries all \(m_0+3\) digits: its top digit, its block (a bijection in \(n\) for fixed \(\beta =(\beta _1,\beta _2)\)) and its two jitter digits, which are a bijection of \(\mathbb {F}_b^2\) onto \((\beta _1,\beta _2)\) in every coordinate.
(B) The functional \(\lambda _e=\lambda ^{cc'}_e\) vanishes on \(Z_e\), so it is supported on the first \(e\) digits of \(c\) and the first \(m_0+1-e\) digits of \(c'\). Its coefficient on digit \(e\) of \(c\) is nonzero: otherwise \(\lambda _e\) would live on a window of \(e-1\) plus \(m_0+1-e\) digits, onto which \(P_{cc'}\) projects bijectively (the \((e-1,m_0+1-e)\) box), and vanish on \(P_{cc'}\), hence be \(0\). Likewise its coefficient on digit \(m_0+1-e\) of \(c'\) is nonzero. If \(e{\gt}D\), digit \(e\) of \(c\) is deep (index \({\gt}D\)); if \(e\le D\), digit \(m_0+1-e\ge m_0+1-D{\gt}D\) of \(c'\) is deep. So each \(\lambda _e\) has a nonzero coefficient on a deep digit, its own: digit \(e\) of \(c\) if \(e{\gt}D\), digit \(m_0+1-e\) of \(c'\) if \(e\le D\). In any vanishing linear combination, the term with the largest \(e{\gt}D\) (or, if there is none, the smallest \(e\)) is the only one that sees its own digit, so its coefficient is \(0\); by induction all coefficients are \(0\). Hence the restrictions of \(\lambda _1,\dots ,\lambda _{m_0}\) to the deep digits are linearly independent, and the deep parts of \(s_A^{yz}\) can be chosen with \(\lambda ^{yz}_e(s_A^{yz})=1\) for all \(e\), those of \(s_B^{xy}\) with \(\lambda ^{xy}_e(s_B^{xy})=1\); the conditions on \((s_B-s_A)^{xz}\) involve the still free deep digits of \((s_A)_x\) and \((s_B)_z\), and are solved in the same way.
Let \(P_L\to P_{L+3}\to \cdots \) be lifts whose depth parameters satisfy \(D_{L+3j'}\ge \lfloor L/2\rfloor +j'\) for every \(j'\ge 0\) (for instance the canonical continuation). Then for every \(j\ge 0\) the toroidal (hence also Euclidean) minimum distance of \(P_{L+3j}\) satisfies
Freezing. By induction on \(j\), \(P_{L+3j}\) is the set of points whose coordinate \(c\) has the digits \(\pi _c(u)\, |\, (p+\eta (u))_c\, |\, \mathrm{low}_c(u)\), where \(u\in \mathbb {F}_b^{3j}\) collects the new index digits, \(u\mapsto \pi (u)=(\pi _c(u))_c\in \mathbb {F}_b^{3j}\) is a bijection (\(j\) top digits per coordinate), \(p\) runs over \(P_L\), \(\eta (u)\) is a digitwise shift of the \(L\) block digits, and \(\mathrm{low}(u)\) has \(2j\) digits per coordinate. The lift at resolution \(\ell =L+3j'\) shifts only digits of index \({\gt}D_\ell \) of its own block, in which the block of \(P_L\) occupies the indices \(j'+1,\dots ,j'+L\); so it touches block digits of index \({\gt}D_\ell -j'\ge \lfloor L/2\rfloor \) only, and never the \(j'\) top digits before them. Hence \(\eta (u)\) vanishes on the top \(\lfloor L/2\rfloor \) digits of every coordinate: these are frozen, equal to those of \(p\).
Separation. Measure in units of \(b^{-(L+3j)}b^{2j}\), so that the torus has period \(b^{L+j}\) and a point has coordinates \(\pi _c(u)b^L+t_c(p)W+\varepsilon _c\) with \(\varepsilon _c\in [0,W)\). Two points with different \(p\ne p'\): reducing modulo \(b^L\), which divides the period, does not increase toroidal distances, and modulo \(b^L=AW\) the difference in coordinate \(c\) is \((t_c(p)-t_c(p'))W+(\varepsilon _c-\varepsilon '_c)\), of toroidal size more than \(W(|t_c(p)-t_c(p')|_A-1)\); so their distance is at least \(W\sqrt{v^*_L}\). Two points with the same \(p\) and different \(u\): some \(\pi _c\) differ, while \(t_c\) agree, so coordinate \(c\) differs by \((\pi _c-\pi '_c)b^L+(\varepsilon _c-\varepsilon '_c)\) with \(\pi _c\not\equiv \pi '_c\pmod{b^j}\), of toroidal size more than \(b^L-W\). A distance of \(x\) units is \(x\, b^{-L-j}\) in \([0,1)^3\), and \(N^{1/3}=b^{L/3+j}\), so \(\delta N^{1/3}\) is the distance in units times \(b^{-2L/3}\).
For \(\mathbf d\in \mathbb {F}_b^n\) let \(\mu _n(\mathbf d)\) be the least toroidal distance \(|X'-X|_{b^n}\) (the distance to the nearest multiple of \(b^n\)) over the integers \(X\in [0,b^n)\), where \(X'\) has the digits of \(X\) plus \(\mathbf d\), digit by digit modulo \(b\). Let \(H=\lfloor L/2\rfloor \).
Under the hypothesis of Lemma 64, for every \(j\ge 0\) and every digital shift \(\tau \) of \(P_{L+3j}\) (Definition 7),
\[ \delta (P_{L+3j}\oplus \tau )\, N^{1/3}\ \ge \ \min \bigl(W\sqrt{v^\circ _L}\, b^{-2L/3},\ b^{L/3}-W\, b^{-2L/3}\bigr), \]where \(v^\circ _L=\min _\Delta \sum _c\max \bigl(0,\mu _H(\Delta _c)-1\bigr)^2\), the minimum over the differences \(\Delta =(\Delta _x,\Delta _y,\Delta _z)\) of the top \(H\) digits of two distinct points of \(P_L\) (\(\Delta =0\) allowed, with weight \(0\)).
For every digitally shifted digital \((0,m,3)\)-net \(P\) over \(\mathbb {F}_b\),
\[ \min _\tau \delta (P\oplus \tau )^2=b^{-2m}\min _\Delta \textstyle \sum _c\mu _m(\Delta _c)^2, \]the minimum over the digital shifts \(\tau \) and over the nonzero digit differences \(\Delta \) of two points of \(P\) (toroidal distances).
For a pair of points with digit difference \(\Delta \), coordinate \(c\) of the shifted pair has the digits \(X_c\) and \(X_c+\Delta _c\), where \(X_c\) is coordinate \(c\) of the first point plus \(\tau _c\). As \(\tau \) varies, \((X_x,X_y,X_z)\) runs over all triples of digit vectors, independently in the three coordinates, so the minimum over \(\tau \) of the squared distance of the pair is \(\sum _c\min _{X_c}|X'_c-X_c|^2\). This gives (b). Since \(t\mapsto \max (0,t-1)^2\) is nondecreasing, the same argument gives \(v^\circ _L=\min _{\tau '}v^*_L(P_L\oplus \tau ')\) over the digital shifts \(\tau '\) of \(P_L\). For (a), write the points of \(P_{L+3j}\) as in the proof of Lemma 64. A digital shift \(\tau \) keeps \(u\mapsto \pi (u)+\tau _\pi \) a bijection, where \(\tau _\pi \) are its digits on the top \(j\) digits, and adds the same vector \(\tau _{\mathrm{blk}}\) to the block digits of every point. So \(P_{L+3j}\oplus \tau \) has the structure used in that proof, with \(P_L\) replaced by the digitally shifted copy \(P_L\oplus \tau _{\mathrm{blk}}\): the top \(H\) block digits of every point are those of a point of \(P_L\oplus \tau _{\mathrm{blk}}\), and the proof applies verbatim. The first term is then \(W\sqrt{v^*_L(P_L\oplus \tau _{\mathrm{blk}})}\, b^{-2L/3}\ge W\sqrt{v^\circ _L}\, b^{-2L/3}\), and the second term does not involve the shift.
Let \(b\in \{ 2,3\} \). For every \(m\ge 1\) there is an explicit digital \((0,m,3)\)-net \(P_m\) over \(\mathbb {F}_b\) and a digital shift \(\tau _m\in (\mathbb {F}_b^m)^3\) (Definition 7) such that the toroidal (hence also Euclidean) minimum distances satisfy
\(\delta (P_m\oplus \tau _m)\, N^{1/3}\ge 0.4129\) for \(b=2\) and \(\ge 0.3538\) for \(b=3\);
\(\delta (P_m)\, N^{1/3}\ge 0.1718\) for \(b=2\) and \(\ge 0.0770\) for \(b=3\);
\(\delta (P_m\oplus \tau )\, N^{1/3}\ge 0.1718\) for \(b=2\) and \(\ge 0.0770\) for \(b=3\), for every digital shift \(\tau \in (\mathbb {F}_b^m)^3\).
Per residue \(m\equiv 0,1,2\pmod3\) the constants are those of Table tab:base23. For \(m\ge 9\) (\(b=2\)) resp. \(m\ge 6\) (\(b=3\)) the nets come from a finite seed by deep-shift lifts: along a fixed chain up to the certificate resolution of Table tab:base23, then by any continuation with \(D_\ell =\lfloor \ell /2\rfloor \). For smaller \(m\) they are explicit nets with exactly computed minimum distances.
For the lifted resolutions: Lemma 63(A) gives the net property at every resolution, Lemma 63(B) the existence of the continuation, and Lemma 64 the bound \(\delta N^{1/3}\ge g_L\) for every \(m\ge L\) in the residue class of a certificate resolution \(L\), once the finite certificate \(v^*_L\) is known and the proviso \(g_L\le b^{L/3}-Wb^{-2L/3}\) holds. The finite part is an exact computation on explicitly given nets: the \(t=0\) property of the seeds and of the nets at the certificate resolutions, the integers \(v^*_L\) (with the proviso, which holds by a wide margin), the exact minimum distances at the finitely many resolutions between the seed and \(L\), and, for \(m\) below the seed resolutions, explicit digital \((0,m,3)\)-nets with their exact minimum distances (all above the stated constants). The constants are the minima of these exact values, truncated. Without the shift the same matrices are used: Lemmas 63 and 64 never use the shift, and only the certificates change. For (3), Lemma 65(a) gives the bound for every digital shift and every \(m\ge L\) from one integer \(v^\circ _L\), computed at the same certificate resolution \(L\) (the proviso holds again); at the finitely many resolutions below \(L\), and for the explicit nets below the seed, the exact minimum of \(\delta (P_m\oplus \tau )N^{1/3}\) over all \(\tau \) is computed by Lemma 65(b).
Along the chains the every-shift certificate \(v^\circ _L\) vanishes at many resolutions (for \(b=3\), \(m\equiv 0\), at every resolution below \(18\); computed), and it is positive at the six certificate resolutions of Table tab:base23, all of them even. Two facts explain the pattern. (i) Parity. If \(L\) is even and \(v^\circ _L=0\), then \(v^\circ _{L+3}=0\) for every lift \(P_{L+3}\) of \(P_L\). Indeed, the indices \((n,0,0,0)\) of the lift (Definition 62) give points with top digit \(0\), block digits those of \(P_L\) and jitter digits \(0\), so the top \(\lfloor (L+3)/2\rfloor =H+1\) digits of their differences are \(0\) followed by the top \(H\) digits of the differences of \(P_L\). For such differences the toroidal \(\mu _{H+1}\) of the extended vector is at most the plain (non-toroidal) value of the original one, and a vector \(\pm (0,\dots ,0,1,\dots ,1)\) has plain value \(1\); so a vanishing certificate at \(L\) gives one at \(L+3\). For odd \(L\) the window of \(P_{L+3}\) gains one more block digit, so a certificate can first become positive only at an even resolution. (ii) Dichotomy. If \(v^\circ _L=0\), then along every lift chain from \(P_L\) every \(m\ge L\) in the class has \(\min _\tau \delta (P_m\oplus \tau )N^{1/3}{\lt}2\sqrt3\, b^{\lceil L/2\rceil -2L/3}\). Indeed, the indices whose new digits are all \(0\) embed \(P_L\) into \(P_m\) with top and jitter digits \(0\), and a difference whose top window is \(0\) or \(\pm (0,\dots ,0,1,\dots ,1)\) in each coordinate can be shifted to have each coordinate below \(2W\) in the units \(b^{-(L+j)}\) of the proof of Lemma 64, \(m=L+3j\). So, for a chain frozen from every resolution, a floor \(\kappa N^{-1/3}\), \(\kappa {\gt}0\), that holds for every shift from some resolution on exists if and only if \(v^\circ _L{\gt}0\) for some \(L\); if the certificate vanished at infinitely many \(L\), the every-shift separation would tend to \(0\). For the nets of Theorem 66 the certificate is positive at every certificate resolution (Table tab:base23), so no shift makes their separation decay.