Low-discrepancy quasi-uniform digital nets in every dimension: blueprint

5 Lattice skeletons: \(m=sk+r\)

5.1 Fine cells and the separation reduction

Lemma 27 Separation reduction
✓

Let \(v\ne w\) be two points, and let \(a_c\) be the centred residue (\(-p^{k+1}/2{\lt}a_c\le p^{k+1}/2\)) of \(P_c(w)-P_c(v)\) modulo \(p^{k+1}\); we call \(a\) the fine difference of \(v\) and \(w\).

  1. The toroidal distance of \(X_c(w)\) and \(X_c(v)\) modulo \(N\) is at least \((|a_c|-1)\varpi \). Hence, if \(|a|_\infty \ge M\) for every pair of distinct points, the toroidal minimum distance satisfies \(\delta N^{1/s}\ge (M-1)\, p^{-\ell /s}\).

  2. If \(|a_c|{\lt}p\) and \(1\le j\le k\), then \(\lfloor P_c(w)/p^j\rfloor -\lfloor P_c(v)/p^j\rfloor \equiv \xi _{c,j}\pmod{p^{k+1-j}}\) with \(\xi _{c,j}\in \{ 0,\operatorname {sgn}a_c\} \), and \(\xi _{c,j}\ne 0\) implies \(\xi _{c,j-1}\ne 0\) for \(j\ge 2\).

Proof ▼

(i) \(N=p^{k+1}\varpi \), so \(X_c(w)-X_c(v)\equiv x:=a_c\varpi +(\theta '-\theta )\pmod N\) with \(|\theta '-\theta |{\lt}\varpi \). If \(|x|\le N/2\), the distance is \(|x|\ge |a_c|\varpi -(\varpi -1)\). Otherwise it is \(N-|x|\ge N-(|a_c|+1)\varpi +1{\gt}(p^{k+1}-|a_c|-1)\varpi \ge (|a_c|-1)\varpi \), as \(|a_c|\le p^{k+1}/2\). So \(\delta N\ge (M-1)\varpi \), and \(\varpi N^{1/s}/N=p^{m/s-k-1}=p^{-\ell /s}\). (ii) Write \(P_c(w)=P_c(v)+a_c+\varepsilon p^{k+1}\) with \(\varepsilon \in \{ -1,0,1\} \). The difference of the floors is \(\lfloor (P_c(v)+a_c)/p^j\rfloor -\lfloor P_c(v)/p^j\rfloor +\varepsilon p^{k+1-j}\). As \(|a_c|{\lt}p\le p^j\), the first part lies in \(\{ 0,\operatorname {sgn}a_c\} \), and it is nonzero only if a multiple of \(p^j\), hence of \(p^{j-1}\), lies between \(P_c(v)\) and \(P_c(v)+a_c\). Neither part uses that \(p\) is odd or prime; \(p\ge 2\) suffices.

5.2 Necessary conditions, forced faults and completion

Lemma 28 Necessary conditions on the skeleton digits
✓

Let a graph form with the depths above be a \((0,m,s)\)-net over \(\mathbb {F}_p\). Let \(A\in \mathbb {F}_p^{\ell \times r}\) hold the coefficients of the skeleton digits on the last levels \(x_{d,k}\), and, for \(k\ge 1\) and \(i\ne j\), let \(g_{ij}\) be the coefficient of \(S_{z_i}\) on \(z_{j,k-1}\).

  1. Every square submatrix of \(A\) is invertible.

  2. (Forced faults.) If \(\ell \ge 2\) and \(k\ge 1\), then \(g_{ij}\ne 0\) for all \(i\ne j\).

  3. For every full coordinate \(x_d\) and every set \(I\) of \(j\) skeleton coordinates, the coefficients of the \(S_{z_i}\), \(i\in I\), on the levels \(x_{d,k},\dots ,x_{d,k-j+1}\) form an invertible matrix; for a skeleton coordinate \(z_e\notin I\) the same holds on the levels \(z_{e,k-1},\dots ,z_{e,k-j}\) (whenever these levels exist).

Proof ▼

All three follow from Lemma 2 for suitable boxes. For (N1) take depth \(k+1\) on the skeleton coordinates of a set \(I\), depth \(k\) on the full coordinates of a set \(J\) with \(|J|=|I|\), and \(k_c\) elsewhere: the over coordinates are those of \(I\), by one digit (their skeleton digits), the under coordinates those of \(J\), by one level (the level \(k\)), and the minor is \(\det A[I,J]\). (N2) is the box with depth \(k+1\) on \(z_i\) and \(k-1\) on \(z_j\); (N3) the box with depth \(k+1\) on \(I\) and \(k_e-j\) on the coordinate \(e\).

Let the frame and \(\Phi ^F\) be as above.

  1. (Normal form.) After the moves of Proposition 13, applied to the restricted frame as described in the proof below, row \(0\) of every block \((z_i,d)\), \(d\ne z_i\), of \(\Phi ^F\) has the generating function \(w_{id}/(1-y_{id}x)\) of Proposition 13, where \(x^n\) marks carry depth \(n\), the level \(k_d-1-n\); this holds for every \(k\). For a column block \(d\) let \(\ell _d\) be the number of skeleton coordinates other than \(d\) (\(\ell _d=\ell \) if \(d\) is full, \(\ell _d=\ell -1\) if \(d\) is a skeleton coordinate). Then Propositions 18 and 14 hold for the skeleton rows, with the \(\ell _d\) skeleton rows \(z_i\ne d\) of block \(d\) in place of the rows \(c\ne d\), and \(\ell _d-1\), \(\ell _d\) in place of \(s-2\), \(s-1\) (the carry depths \(n\le \ell _d-1\)).

  2. (\(\ell =1\).) For every \(k\ge 0\) and all units \(\kappa _1,\dots ,\kappa _r\), the moves of Lemma 2 turn \(\Phi ^F\) into a graph form whose skeleton digit is \(S_z=\sum _d\kappa _dx_{d,k}\) (all other entries of row \(0\) of \(z\), own block included, are \(0\)). It is a \((0,m,s)\)-net over \(\mathbb {F}_p\).

  3. (\(\ell =2\).) Let \(k\ge 1\) and prescribe skeleton digits

    \[ S_{z_i}=\sum _dA_{id}\, x_{d,k}+\sum _d\beta _{id}\, x_{d,k-1}+g_{ij}\, z_{j,k-1}+o_i\, z_{i,k-1}\qquad (\{ i,j\} =\{ 1,2\} ) \]

    satisfying (N1)–(N3), with arbitrary own coefficients \(o_i\). For a suitable choice of the places they are reachable for every \(k\ge 1\), and they complete to a \((0,m,s)\)-net over \(\mathbb {F}_p\).

Proof ▼

(i) Restriction. Let \(m'=s(k+1)\) and \(V\in \mathbb {F}_p[t]_{{\lt}m'}\). The first digit of the reading at a finite skeleton place \(a_z\) vanishes iff \((t-a_z)\mid V\), and at \(\infty \) iff \(\deg V{\lt}m'-1\). So the points of the \(m'\)-frame whose skeleton coordinates have first digit \(0\) are given by \(V=\prod _{z\text{ finite}}(t-a_z)\, V'\) with \(\deg V'{\lt}m\), and their readings are those of \(V'\) times a unit power series, shifted by one digit at a skeleton place. Hence this point set, with the skeleton coordinates rescaled by \(p\), is the \(m\)-frame up to per-coordinate lower-triangular scrambles, i.e. up to the moves of Lemma 2; each new elementary box is an old one with one more leading digit on each skeleton coordinate. In the graph form of the \(m'\)-frame with depths \((k+1,\dots ,k+1)\) the restriction is the vanishing of level \(0\) of the skeleton cells, and the old first offset row of \(z\) becomes its skeleton digit. The move of Proposition 13 is lower-triangular in the levels and only scales level \(0\), so it commutes with deleting the level-\(0\) columns of the skeleton blocks; this gives the normal form, with carry depth \(n\) at level \(k_d-1-n\). The proofs of Propositions 18 and 14 use only this normal form and the distinctness, with unit differences, of the \(y_{cd}\) on the rows involved, so they apply to the \(\ell _d\) skeleton rows of a column.

(ii) For each full \(x_d\), the entry of \(S_z\) on \(x_{d,k}\) is the box minor with depth \(k+1\) on \(z\) and \(k\) on \(x_d\), hence a unit. Subtract multiples of level \(k\) from the levels \(l{\lt}k\) (move (c) with \(U_{x_d}\) lower-triangular) so that \(S_z\) vanishes there, scale level \(k\) to \(\kappa _d\), and set all diagonal blocks to \(0\) (move (a)). By Lemma 2 every box minor stays a unit, and Lemma 1 applies. This is the recipe of Definition 55(\(\mathcal B^2\)) in \(s\) dimensions; it needs no normal form.

(iii) By (i), the only constraints are these. On a full column \(d\) (\(\ell _d=2\)): at carry depth \(0\), \(A_{id}=\lambda _i\mu _dw_{id}\) (a generalized Cauchy column); at carry depth \(1\) Proposition 18 only asks that the interpolating polynomial have a unit leading coefficient, and for two rows this is the determinant \(\det [A_{\cdot d},\beta _{\cdot d}]\), which is (N3). On a skeleton column (\(\ell _d=1\)): \(g_{ij}\ne 0\), which is (N2). Larger carry depths are set to \(0\) by Proposition 14, for every \(k\), and the own terms by move (a). It remains to realize the ratios \(A_{2d}/A_{1d}\). Put \(z_1\) at \(\infty \) and \(z_2\) at a finite place \(a_2\); then \(w_{1d}=1\) and \(w_{2d}=1/(a_2-b_d)\), with \(b_d\) the place of \(x_d\), and the condition is \(b_d=a_2-\Lambda A_{1d}/A_{2d}\) with \(\Lambda =\lambda _2/\lambda _1\). Take \(\Lambda =1\), \(\lambda _1=1\) and \(\mu _d=A_{1d}\). The \(b_d\) are finite, differ from \(a_2\) because \(A_{1d}\ne 0\), and are pairwise distinct because the \(2\times 2\) minors of \(A\) are nonzero (N1). The net property follows as in (ii).

Corollary 30 Reachable skeletons with two skeleton coordinates
✓

Let \(\ell =2\), and fix skeleton digits of the form in Proposition 29(iii), with coefficients that do not depend on \(k\). For a suitable choice of the places they are reachable from the frame for every \(k\ge 1\) if and only if they satisfy (N1)–(N3). The necessity holds for each single \(k\ge 1\): every graph form with these skeleton digits that is a \((0,m,s)\)-net over \(\mathbb {F}_p\) satisfies (N1)–(N3).

Proof ▼

For skeleton digits of this form, (N1)–(N3) say: every entry and every \(2\times 2\) minor of \(A\) is nonzero (N1, which contains (N3) for \(j=1\) on a full coordinate); \(g_{12}\ne 0\) and \(g_{21}\ne 0\) (N2, which is also (N3) for \(j=1\) on a skeleton coordinate); and \(\det [A_{\cdot d},\beta _{\cdot d}]\ne 0\) for every full coordinate \(x_d\) ((N3) for \(j=2\); for \(\ell =2\) no skeleton coordinate lies outside a set \(I\) of size \(2\)). These conditions involve only the coefficients, not \(k\). If: Proposition 29(iii). Only if: let \(k\ge 1\), and let a graph form with the given skeleton digits be reachable from the frame for some choice of the places. All box minors of \(\Phi ^F\) are units (Lemma 11, over \(\mathbb {F}_p\)), and the moves multiply every box minor by a unit (Lemma 2), so the graph form is a \((0,m,s)\)-net over \(\mathbb {F}_p\) (Lemma 1). Lemma 28 applies to every such net and gives (N1)–(N3).

5.3 Lattices

Let \(\Lambda _A\) be as above.

  1. (\(\ell =1\).) If \(\rho \ge 2\), \(\rho ^s{\lt}p\) and \(A=(\rho ,\rho ^2,\dots ,\rho ^{s-1})\), then \(\lambda _\infty (\Lambda _A)=\rho \). For \(\rho =\lfloor p^{1/s}\rfloor \) this is the largest minimum of any lattice of index \(p\).

  2. (\(r=1\).) If \(\rho \ge 2\), \(\rho ^\ell (\rho +1)\le p\) and \(A=(\rho ,\rho ^2,\dots ,\rho ^\ell )^{\! \top }\), then \(\lambda _\infty (\Lambda _A)=\rho ^\ell \).

  3. (\(\ell =r=2\).) If \(\rho \ge 2\), \(\rho ^2-4{\lt}p\) and \(A=\left(\begin{smallmatrix} \rho & 1 \\ 1 & \rho \end{smallmatrix}\right)\), then \(\lambda _\infty (\Lambda _A)\ge \rho -1\).

  4. (\(\ell =2\), \(r\ge 3\).) Let \(B\ge 1\) and let \(\nu _1{\gt}\sqrt2\, B\) and \(\nu _2,\dots ,\nu _{r-1}\) be integers with \(\nu _l^2+1{\gt}B\). Put \(\zeta _l=\nu _l+i\) and \(\Omega _l=\zeta _1\cdots \zeta _l\in \mathbb {Z}[i]\), and define \(A\in \mathbb {Z}^{2\times r}\) by

    \[ A_1x+i\, A_2x=\sum _{l=1}^{r-2}x_l\, \Omega _l+(x_{r-1}+ix_r)\, \Omega _{r-1}. \]

    If \(B(1+\| A_j\| _1){\lt}p\) for \(j=1,2\), then \(\lambda _\infty (\Lambda _A)\ge B+1\).

Proof ▼

(L) If \(0{\lt}|u|_\infty \le \rho -1\), then \(|z-\sum _d\rho ^dx_d|\le (\rho -1)(1+\rho +\dots +\rho ^{s-1})=\rho ^s-1{\lt}p\), so \(z=\rho (x_1+\rho x_2+\cdots )\) exactly. Then \(\rho \mid z\) and \(|z|{\lt}\rho \) give \(z=0\), then \(|x_1|{\lt}\rho \) and \(\rho \mid x_1\) give \(x_1=0\), and so on: \(u=0\). The vector \(x=e_1\), \(z=\rho \) shows equality, and \(\rho =\lfloor p^{1/s}\rfloor \) attains the pigeonhole bound. (L1) Let \(u=(x,z_1,\dots ,z_\ell )\ne 0\) and \(B=|u|_\infty \). If \(B(\rho +1)\ge p\), then \(B\ge p/(\rho +1)\ge \rho ^\ell \). Otherwise \(|z_1-\rho x|\le B(1+\rho ){\lt}p\) gives \(z_1=\rho x\), and for \(i{\lt}\ell \), \(z_{i+1}-\rho z_i\equiv \rho ^{i+1}x-\rho ^{i+1}x=0\) with \(|z_{i+1}-\rho z_i|{\lt}p\) gives \(z_{i+1}=\rho z_i\); so \(z_\ell =\rho ^\ell x\). As \(u\ne 0\), \(x\ne 0\), so \(B\ge |z_\ell |\ge \rho ^\ell \); the vector \((1,\rho ,\dots ,\rho ^\ell )\) shows equality. (T) If \(0{\lt}|u|_\infty \le \rho -2\), then \(|z_1-\rho x_1-x_2|\le (\rho -2)(\rho +2){\lt}p\), so \(z_1=\rho x_1+x_2\), and likewise \(z_2=x_1+\rho x_2\). If \(x=0\) then \(z=0\). Otherwise, say \(|x_1|\ge |x_2|\), and \(|z_1|\ge (\rho -1)|x_1|\ge \rho -1\), a contradiction. (G) Let \(0{\lt}|u|_\infty \le B\). Since \(|z_j-A_jx|\le B(1+\| A_j\| _1){\lt}p\), the relations are exact. Then \(Z=z_1+iz_2\) is divisible by \(\zeta _1\) in \(\mathbb {Z}[i]\), and \(|Z|\le \sqrt2B{\lt}|\zeta _1|\), so \(Z=0\). Dividing by \(\zeta _1\) shows that \(\zeta _2\) divides the rational integer \(x_1\). For a rational integer \(n\), \(n/\zeta _2=n(\nu _2-i)/(\nu _2^2+1)\), so \(\zeta _2\mid n\) iff \(\nu _2^2+1\mid n\); as \(|x_1|\le B{\lt}\nu _2^2+1\), \(x_1=0\). Continuing with \(\zeta _3,\dots ,\zeta _{r-1}\) gives \(x_1=\dots =x_{r-2}=0\) and then \(x_{r-1}+ix_r=0\), so \(u=0\).

Definition 32
✓
#

Let \(s\ge 5\), \(r=s-2\) and \(B\ge 1\). Let \(A(B)\) be the matrix of Lemma 31(G) with \(\nu _1=\lfloor \sqrt2B\rfloor +1\) and \(\nu _l=\lfloor \sqrt B\rfloor +1\) for \(2\le l\le r-1\), and, for a prime \(p\), let \(B(p)\) be the largest integer \(\beta \ge 1\) with \(\beta \, (1+\max _j\| A_j(\beta )\| _1){\lt}p\). This \(B(p)\) is nondecreasing in \(p\).

Lemma 33 (N1) for the Gaussian matrix
✓
#

Let \(s\ge 5\), \(B\ge 1\), \(A=A(B)\) and \(B(1+\max _j\| A_j\| _1){\lt}p\). Then:

  1. \(\nu _j^2+1{\lt}p\) for every \(j\);

  2. if \(\sum _{j=1}^{r-1}\arctan (1/\nu _j){\lt}\pi /2\), every entry and every \(2\times 2\) minor of \(A\) is nonzero modulo \(p\), i.e. \(A\) satisfies (N1);

  3. the hypothesis of (b) holds if \(s\le 8\) and \(B\ge g^*+1\), where \(g^*=1+\lceil r/2\rceil \), and, for every \(s\), if \(B{\gt}(2(r-1)/\pi )^2\).

Proof ▼

(a) Columns \(r-1\) and \(r\) of \(A\) are \((\operatorname {Re}\Omega _{r-1},\operatorname {Im}\Omega _{r-1})\) and \((-\operatorname {Im}\Omega _{r-1},\operatorname {Re}\Omega _{r-1})\), so \(\| A_j\| _1\ge |\Omega _{r-1}|=\prod _j(\nu _j^2+1)^{1/2}\ge \sqrt5\, (\nu _1^2+1)^{1/2}\), as \(r\ge 3\) and \(\nu _l\ge 2\). Hence \(p{\gt}B\sqrt5\, (\nu _1^2+1)^{1/2}\). Since \(\nu _1\le \sqrt2B+1\), we have \(\nu _1^2+1\le 2B^2+2\sqrt2B+2\le 5B^2\) for \(B\ge 2\), and \(\nu _1^2+1=5=5B^2\) for \(B=1\). So \(p{\gt}\nu _1^2+1\ge \nu _j^2+1\). (b) The arguments of all \(\Omega _l\) lie in \((0,\pi /2)\), so the entries are nonzero integers, of absolute value \({\lt}p\) by the hypothesis. The \(2\times 2\) minor of the columns \(l{\lt}l'\le r-1\) is \(\operatorname {Im}(\overline{\Omega _l}\, \Omega _{l'})=|\Omega _l|^2\operatorname {Im}(\zeta _{l+1}\cdots \zeta _{l'})\), and that of the columns \(l\le r-1\) and \(r\) is \(|\Omega _l|^2\operatorname {Re}(\zeta _{l+1}\cdots \zeta _{r-1})\). Here \(|\Omega _l|^2\) is a product of the factors \(\nu _j^2+1{\lt}p\), so it is prime to \(p\). The second factor is a nonzero integer of absolute value at most \(|\zeta _2\cdots \zeta _{r-1}|{\lt}|\Omega _{r-1}|{\lt}p\). (c) The \(\nu _j\) are nondecreasing in \(B\). At \(B=g^*+1\) they are \((6,3)\), \((6,3,3)\), \((8,3,3,3)\), \((8,3,3,3,3)\) for \(s=5,6,7,8\), with arctangent sums below \(0.487\), \(0.809\), \(1.090\), \(1.412\), all \({\lt}\pi /2\). For every \(B\), \(\nu _j{\gt}\sqrt B\) (Definition 32), so the sum is \({\lt}(r-1)/\sqrt B\).

The lattices of this section are Construction A lattices [ 9 , Ch. 5 ] (stated there for binary codes; the \(p\)-ary version is the same): with the systematic \([s,r]\) code \(C_A=\{ (x,Ax):x\in \mathbb {F}_p^r\} \subset \mathbb {F}_p^s\) of the skeleton digits, \(\Lambda _A=C_A+p\mathbb {Z}^s\). For every prime \(p\) the nonzero vectors of \(p\mathbb {Z}^s\) have maximum and Euclidean norm at least \(p\), and the centred lift of a codeword is a shortest lift in every coordinate. So \(\lambda _\infty (\Lambda _A)\) is the least largest centred entry of a nonzero codeword, and \(\lambda _2(\Lambda _A)^2=\min (p^2,w_E(C_A))\), with \(w_E\) the least Euclidean (squared Lee) weight. We call skeleton digits pure if they depend only on the last levels \(x_{d,k}\) of the full coordinates (as in Definition 36). For pure skeleton digits, \(P_{x_d}\equiv x_{d,k}\) and \(P_z\equiv S_z\pmod p\) constrain only the lowest fine digit, so the occupied fine cells lie in \(\Lambda _A\) (for \(\ell =1\) they fill it, Theorem 35(2)); the faults shift \(C_A\) to cosets that vary between coarse blocks. In this language:

(a) Condition (N1) of Lemma 28 says that \(C_A\) is MDS [ 45 , Ch. 11, Thm. 8 ] , which says nothing about the Lee or Euclidean minimum: \(A=(1,\dots ,1)\) is MDS with \(\lambda _\infty (\Lambda _A)=1\).

(b) Inside the frame orbit the layer at carry depth \(0\) is a generalized Cauchy matrix in the places (Proposition 29(i)), so \(C_A\) is a generalized Reed–Solomon code [ 51 ] (doubly extended if \(s=p+1\)). This restricts the code only if \(r\ge 3\) and \(\ell \ge 3\), since every MDS code of dimension or codimension at most two is generalized Reed–Solomon; for \(r\le 2\) or \(\ell \le 2\) the restriction comes instead from the faults: the code and the faults must be realized with the same row scalars \(\lambda '\) (Proposition 18), which ties their values together. Lemma 40 is the Plücker relation (Lemma 19(X)) applied jointly to the code and the faults; Corollary 41 concerns the Korobov column with bounded faults, not other codes.

(c) For \(\ell =1\), \(\Lambda _A=\{ a\in \mathbb {Z}^s:h\cdot a\equiv 0\pmod p\} \) with the (parity-)check vector \(\mathbf h=(\kappa _1,\dots ,\kappa _r,-1)\) is the dual of the rank-\(1\) lattice \(\mathbb {Z}^s+\mathbb {Z}\mathbf h/p\) [ 55 ] , and \(\lambda _2(\Lambda _A)\) is its spectral test [ 5 ] , [ 32 , Sec. 3.3.4 ] ; for \(\kappa _d=\rho ^d\) (Definition 36) it is Knuth’s spectral-test lattice of the multiplier \(\rho \) in dimension \(s\), after \(a_z\mapsto -a_z\). For \(\rho =\lfloor p^{1/s}\rfloor \) the normalized minimum \(\lambda _2(\Lambda _A)p^{-1/s}\) lies between \(\rho p^{-1/s}\) and \(\sqrt{\rho ^2+1}\, p^{-1/s}\) and tends to \(1\), against the upper bound \(\sqrt{\gamma _s}\) valid for every \(\mathbf h\) (Remark 127). So \(\kappa _d=\rho ^d\) is optimal in the maximum norm but not for the spectral test, which Proposition 104 (Part II) exploits.

5.4 One skeleton coordinate

Let \(s\ge 3\), let \(p\) be a prime, let \(\rho \ge 2\) be an integer with \(\rho ^s{\lt}p\) (one exists iff \(p{\gt}2^s\)), and let \(k\ge 0\). The net \(\mathcal S^1_{k,p,\rho }\) of Definition 36, whose skeleton digit is \(S_z=\sum _d\rho ^dx_{d,k}\), with \(N=p^{sk+s-1}\) points, is a digital \((0,sk+s-1,s)\)-net over \(\mathbb {F}_p\), and:

  1. its toroidal (hence also Euclidean) minimum distance satisfies \(\delta N^{1/s}\ge (\rho -1)\, p^{-1/s}\); for \(\rho =\lfloor p^{1/s}\rfloor \) the bound exceeds \((\rho -1)/(\rho +1)\), so it is \({\gt}1/3\) for every prime \(p{\gt}2^s\), \({\gt}1/2\) for \(p{\gt}3^s\), and tends to \(1\);

  2. its occupied fine cells are exactly the cells of a lattice of index \(p\) with minimum \(\lambda _\infty =\rho \), which for \(\rho =\lfloor p^{1/s}\rfloor \) is the largest minimum of any lattice of index \(p\);

  3. for \(\rho =\lfloor p^{1/s}\rfloor \) its covering radius satisfies \(hN^{1/s}\le \sqrt s\, (\mu +1)\, p^{-1/s}\) with \(\mu =\lceil p/\rho ^{s-1}\rceil {\lt}\rho (1+1/\rho )^s+1\), so the mesh ratio \(h/\delta \le \sqrt s\, (\mu +1)/(\rho -1)\) is bounded uniformly in \(p\) and \(k\), and is at most \(\sqrt s\, (1+o(1))\) as \(p\to \infty \).

Proof of Theorem 35 ▼

Net. Proposition 29(ii): \(p{\gt}2^s\ge s-1\), and the prescribed coefficients \(\rho ^d\) are units since \(\rho ^{s-1}{\lt}p\).

(1) Since \(x_{d,k}\equiv P_{x_d}\) and \(P_z\equiv S_z\pmod p\), every point satisfies \(P_z\equiv \sum _d\rho ^dP_{x_d}\pmod p\). This congruence passes to the differences modulo \(p^{k+1}\), so every difference \(a\ne 0\) lies in \(\Lambda _A\) of Lemma 31(L), and \(|a|_\infty \ge \rho \). Lemma 27(i) gives \(\delta N^{1/s}\ge (\rho -1)p^{-1/s}\). There are no faults. With \(\rho =\lfloor p^{1/s}\rfloor \) we have \(p{\lt}(\rho +1)^s\), so the bound exceeds \((\rho -1)/(\rho +1)\), which is \(\ge 1/3\) for \(\rho \ge 2\) (\(p{\gt}2^s\)) and \(\ge 1/2\) for \(\rho \ge 3\) (\(p{\gt}3^s\)).

(2) There are \(N=p^{s(k+1)-1}\) points with distinct \(P\), all in \(\Lambda _A\), and \(\Lambda _A\) has \(p^{s(k+1)}/p=N\) classes modulo \(p^{k+1}\mathbb {Z}^s\). So the occupied fine cells are exactly the cells of \(\Lambda _A\). Optimality is Lemma 31(L).

(3) Let \(Q\in \{ 0,\dots ,p^{k+1}-1\} ^s\) be the fine cell of a point \(y\in [0,1)^s\). We look for a cell \(a=Q-v\in \Lambda _A\) in the same range with \(|v|_\infty \le \mu :=\lceil p/\rho ^{s-1}\rceil \). Prescribe the sign \(\epsilon _c\) of \(v_c\): \(-1\) if \(Q_c{\lt}p^{k+1}/2\), else \(+1\). Since \(\mu \le p/4+1\le p^{k+1}/2\), any \(v\) with these signs and \(|v|_\infty \le \mu \) keeps \(a\) in range. With \(T\equiv Q_z-\sum _d\rho ^dQ_{x_d}\pmod p\), the vector \(a\) lies in \(\Lambda _A\) iff \(v_z-\sum _d\rho ^dv_{x_d}\equiv T\). Choose the representative \(T'\) of \(T\) in \([0,p)\) or in \((-p,0]\), and expand \(T'=\sum _{i=0}^{s-1}t_i\rho ^i\) in base \(\rho \) with signed digits: \(t_0,\dots ,t_{s-2}\) are taken one at a time from the window \([0,\rho -1]\) or \([-(\rho -1),0]\), according to the sign of \(T'\), and \(t_{s-1}\) is the rest. Put \(v_z=t_0\) and \(v_{x_i}=-t_i\); the windows give the required signs of \(v_z,v_{x_1},\dots ,v_{x_{s-2}}\). The lower digits contribute less than \(\rho ^{s-1}\) in absolute value, so \(t_{s-1}\) has the sign of \(T'\) (which we choose) and \(|t_{s-1}|{\lt}p/\rho ^{s-1}+1\). So \(|v|_\infty \le \mu \), since also \(\rho -1{\lt}p/\rho ^{s-1}\). The point in the cell \(a\) differs from \(y\) by less than \((\mu +1)p^{-(k+1)}\) in every coordinate, so

\[ hN^{1/s}\le \sqrt s\, (\mu +1)\, p^{-1/s},\qquad \frac h\delta \le \frac{\sqrt s\, (\mu +1)}{\rho -1}. \]

For \(\rho =\lfloor p^{1/s}\rfloor \), \(\mu {\lt}\rho (1+1/\rho )^s+1\), so both bounds are bounded in \(p\) for fixed \(s\), and \(h/\delta \le \sqrt s\, (1+o(1))\) as \(p\to \infty \).

Definition 36
✓

Let \(s\ge 3\), \(\rho \ge 2\) with \(\rho ^s{\lt}p\), \(k\ge 0\) and \(m=sk+s-1\). Take the frame that assigns the places \(\infty ,0,1,\dots ,s-2\) to the coordinates \(x_1,\dots ,x_{s-1},z\), respectively, the depths \((k+1,\dots ,k+1,k)\) with the skeleton coordinate \(z\) last, and the recipe of Proposition 29(ii) with \(\kappa _d=\rho ^d\). The result is the digital net \(\mathcal S^1_{k,p,\rho }\) over \(\mathbb {F}_p\). Its skeleton digit is

\[ S_z=\sum _{d=1}^{s-1}\rho ^d\, x_{d,k}. \]

5.5 Two skeleton coordinates

Let \(s\ge 4\), let \(p\) be a prime and \(k\ge 1\), and let \(\mathcal S^2_{k,p}\) be the net of Definition 38, with \(N=p^{sk+s-2}\) points.

  1. (\(s=4\).) For every prime \(p\ge 5\), \(\mathcal S^2_{k,p}\) is a digital \((0,4k+2,4)\)-net over \(\mathbb {F}_p\) with \(\delta N^{1/4}\ge (\rho -4)\, p^{-1/2}\), where \(\rho =\max \{ \rho :\rho ^2{\lt}p+4\} \); the bound is positive for every prime \(p\ge 23\) and tends to \(1\).

  2. (\(5\le s\le 8\).) For every prime \(p\ge 137\), \(443\), \(2179\), \(6101\) (\(s=5,6,7,8\)), \(\mathcal S^2_{k,p}\) is a digital \((0,sk+s-2,s)\)-net over \(\mathbb {F}_p\) with \(\delta N^{1/s}\ge (B(p)-g^*)\, p^{-2/s}{\gt}0\), where \(g^*=1+\lceil (s-2)/2\rceil \) and \(B(p)\asymp p^{2/s}\) is defined in Definition 32.

  3. (\(s\ge 9\).) The same holds for every prime \(p\) with \(B(p){\gt}g^*\) and \(\sum _{j=1}^{s-3}\arctan (1/\nu _j){\lt}\pi /2\) for the \(\nu _j\) of Definition 32 at \(B=B(p)\); this holds if \(B(p){\gt}\max \{ g^*,(2(s-3)/\pi )^2\} \), in particular for all sufficiently large \(p\).

Proof of Theorem 37 ▼

(N1). For \(s=4\) the entries \(\rho \), \(1\) are units, and \(\det A=\rho ^2-1=(\rho -1)(\rho +1)\) with \(0{\lt}\rho -1{\lt}\rho +1{\lt}p\), since \(\rho ^2{\lt}p+4\) and \(p\ge 5\). For \(s\ge 5\) use Lemma 33: in (2), \(B(p)\ge g^*+1\) exactly for \(p{\gt}132\), \(440\), \(2170\), \(6095\) (\(s=5,\dots ,8\)), which gives the primes \(137\), \(443\), \(2179\), \(6101\). These four numbers are \(\Gamma (g^*+1)\) for \(\Gamma (B)=B(1+\max _j\| A_j(B)\| _1)\), and \(\Gamma \) is increasing on \(B\ge g^*+1\) (below), so some \(B\ge g^*+1\) has \(\Gamma (B){\lt}p\) iff \(\Gamma (g^*+1){\lt}p\). In (3) the hypothesis is that of Lemma 33(b), and the closed-form sufficient condition is that of Lemma 33(c). Net. Proposition 29(iii).

Monotonicity of \(\Gamma \). Let \(5\le s\le 8\) and \(g^*+1\le B{\lt}B'\). The \(\nu _j\) do not decrease from \(B\) to \(B'\), and \(\sum _j\arctan (1/\nu _j){\lt}\pi /2\) at \(B\) by Lemma 33(c). The absolute values of the entries of \(A(B)\) are the real and imaginary parts of \(\Omega _1,\dots ,\Omega _{r-1}\) (proof of Lemma 33(a)). Raise the \(\nu _j\) one at a time from their values at \(B\) to those at \(B'\). If \(\nu _j\) is a factor of \(\Omega _l=P\, (\nu _j+i)\), the other factors have arctangents no larger than at \(B\), so \(P=a+ib\) with \(\arg P\in [0,\pi /2)\), i.e. \(a{\gt}0\), \(b\ge 0\); and \(P(\nu _j+i)=(a\nu _j-b)+i(b\nu _j+a)\), so raising \(\nu _j\) by \(\Delta \ge 0\) raises the real part by \(a\Delta \) and the imaginary part by \(b\Delta \). All parts stay positive, so every \(|A_{jd}|\) is nondecreasing, \(\| A_j(B')\| _1\ge \| A_j(B)\| _1\), and \(\Gamma (B'){\gt}\Gamma (B)\). (The thresholds are also verified in Lean, by a different route: \(\Gamma \) is evaluated exactly for \(g^*+1\le B{\lt}B_1\), \(B_1=7,7,9,9\), and \((B\max _j\| A_j(B)\| _1)^2\ge 2B^s\), from \(\| A_j\| _1\ge |\Omega _{r-1}|\), covers \(B\ge B_1\).)

Separation. Let \(a\ne 0\) be a difference and \(M=|a|_\infty \). If \(M\ge p-1\), then \(M\ge \lambda _\infty (\Lambda _A)-g^*\) below holds, since \(\lambda _\infty (\Lambda _A)\le \lfloor p^{2/s}\rfloor \le p-1\). Otherwise let \(\xi _c=\xi _{c,1}\) be the floor changes of Lemma 27(ii); they give the changes of the level-\((k-1)\) digits modulo \(p\). Put

\[ u=\Bigl(a_x,\ a_{z_1}-\sum _{d\in I_1}\xi _{x_d}-\xi _{z_2},\ a_{z_2}-\sum _{d\in I_2}\xi _{x_d}+\xi _{z_1}\Bigr). \]

By the skeleton digits, the change of \(S_{z_i}\) is \(A_ia_x\) plus the contributions of the level-\((k-1)\) changes \(\xi \); subtracting these, as in \(u\), leaves a vector of \(\Lambda _A\). So \(u\in \Lambda _A\), and \(|u|_\infty \le M+g^*\) with \(g^*=1+\lceil r/2\rceil \). If \(u\ne 0\), then \(M\ge \lambda _\infty (\Lambda _A)-g^*\). If \(u=0\), then \(a_x=0\), so every \(\xi _{x_d}=0\), and \(a_{z_1}=\xi _{z_2}\), \(a_{z_2}=-\xi _{z_1}\). If \(\xi _{z_2}=1\) then \(a_{z_2}{\gt}0\) and \(a_{z_1}=1\), so \(\xi _{z_1}\in \{ 0,1\} \) and \(a_{z_2}=-\xi _{z_1}\le 0\), a contradiction. The case \(\xi _{z_2}=-1\) is symmetric, and \(\xi _{z_2}=0\) gives \(a_{z_1}=0\), \(\xi _{z_1}=0\), \(a_{z_2}=0\), contradicting \(a\ne 0\). Here the opposite signs of \(g_{12}\) and \(g_{21}\) give the contradiction, so no dependence of \(S_{z_i}\) on its own cell is needed. So \(M\ge \lambda _\infty (\Lambda _A)-g^*\), and Lemma 27(i) gives \(\delta N^{1/s}\ge (\lambda _\infty (\Lambda _A)-g^*-1)p^{-2/s}\). With \(\lambda _\infty \ge \rho -1\) and \(g^*=2\) (\(s=4\)), resp. \(\lambda _\infty \ge B+1\) (Lemma 31), this is the claim. For \(s=4\), \(\rho \ge 5\) iff \(p\ge 23\), and \((\rho -4)/\sqrt p\to 1\).

Definition 38
✓

Let \(s\ge 4\), \(r=s-2\), \(k\ge 1\), \(m=sk+s-2\). For \(s=4\) let \(A\) be the matrix of Lemma 31(T) with \(\rho \) maximal such that \(\rho ^2-4{\lt}p\), and put \(I_1=\{ 2\} \), \(I_2=\{ 1\} \). For \(s\ge 5\) let \(A=A(B(p))\) (Definition 32), and let \(I_1\sqcup I_2=\{ 1,\dots ,r\} \) with \(|I_1|=\lfloor r/2\rfloor \). The net \(\mathcal S^2_{k,p}\) is the completion (Proposition 29(iii)) of the skeleton digits

\[ S_{z_1}=A_1x_{\cdot ,k}+\sum _{d\in I_1}x_{d,k-1}+z_{2,k-1},\qquad S_{z_2}=A_2x_{\cdot ,k}+\sum _{d\in I_2}x_{d,k-1}-z_{1,k-1}, \]

with no dependence of \(S_{z_i}\) on the cell of \(z_i\) itself (own coefficients \(0\)), and \(x_{\cdot ,k}=(x_{1,k},\dots ,x_{r,k})\).

Remark 39 Comparison with \(m\equiv 0\)

Seen one digit deeper, the case \(m=sk\) fits this picture as the case \(\ell =s\): every coordinate is a skeleton coordinate whose skeleton digit is its geometric digit, the occupied fine cells are a translate of all of \(p\mathbb {Z}^s\), and the geometric layer \(\tilde M\) plays the role of the faults; so \(1-K/q\) is the analogue of “\(\lambda _\infty \) minus faults” (up to the one fine cell more that Lemma 27 loses). Since \(p\mathbb {Z}^s\) attains the pigeonhole bound, only the scale of the faults differs: \(K/q\) at \(r=0\) against \(g^*\, p^{-\ell /s}\) for \(r\ne 0\). This is why the thresholds (\(p{\gt}2^s\) for \(r=s-1\); \(p\ge 23\), \(137\), \(443\), \(2179\), \(6101\) for \(r=s-2\), \(s=4,\dots ,8\)) are far below the threshold \(5a^*_s+4\le e^{s\log s+O(s)}\) of Theorem A, while at a fixed large \(p\) the constants for \(r=0\) are larger: the skeletons gain in the range of \(p\), not in the constant (heuristic comparison).

5.6 Three or more skeleton coordinates

Lemma 40 A Plücker identity for skeleton digits
✓
#

Let \(\ell \ge 3\), let a graph form be obtained from a frame over \(\mathbb {F}_p\) by the moves of Lemma 2, and let \(d\) be a full coordinate. Let \(\kappa _i\) be the coefficient of \(S_{z_i}\) on \(x_{d,k}\), \(g_{ij}\) that on \(z_{j,k-1}\), and \(\psi _i=1/\kappa _i\). Then, for distinct \(i,j,l\),

\[ g_{ji}\, g_{lj}\, \psi _j+g_{ij}\, g_{li}\, \psi _i=g_{li}\, g_{lj}\, \psi _l . \]
Proof ▼

The moves only scale the entries of the first offset rows on the last cell level, so by Proposition 29(i) these entries form a Cauchy layer \(W_{ce}=\lambda _c\mu _e/D_{ce}\) in the places (Section 3), with \(W_{z_iz_j}=g_{ij}\) and \(W_{z_ix_d}=\kappa _i\). Lemma 19(X) for the coordinates \(z_i,z_j,z_l,x_d\) reads \(g_{ji}\kappa _l/(\kappa _jg_{li})+g_{ij}\kappa _l/(\kappa _ig_{lj})=1\); multiplying by \(g_{li}g_{lj}/\kappa _l\) gives the identity.

Corollary 41 Korobov skeleton digits need large faults
✓
#

Let \(\ell \ge 3\), \(k\ge 1\), let \(d\) be a full coordinate, and let \(\rho ,G\ge 1\) be integers with \(G^2{\lt}\rho \) and \(p{\gt}G^2(2\rho ^2+1)\). Then no graph form obtained from a frame over \(\mathbb {F}_p\) by the moves of Lemma 2 has, in the notation of Lemma 40, \(\kappa _1,\kappa _2,\kappa _3\equiv \rho ,\rho ^2,\rho ^3\) and centred \(g_{ij}\) with \(|g_{ij}|\le G\) for \(i\ne j\le 3\).

Proof ▼

Suppose such a graph form exists. The moves multiply every box minor by a unit, so it is a \((0,m,s)\)-net, and \(g_{ij}\ne 0\) by (N2). Multiply the identity for \((i,j,l)=(1,2,3)\) by \(\rho ^3\): \(g_{21}g_{32}\rho +g_{12}g_{31}\rho ^2\equiv g_{31}g_{32}\pmod p\). The difference of the two sides is at most \(G^2(\rho ^2+\rho +1){\lt}p\) in absolute value, so the congruence is an equality of integers. Hence \(\rho \mid g_{31}g_{32}\). But \(0{\lt}|g_{31}g_{32}|\le G^2{\lt}\rho \), a contradiction.

Proposition 42 A Korobov skeleton with faults \(\pm 1\); computer-assisted
✓

Let \(p=13\), \(s=4\) and \(m=4k+1\) with \(k\ge 1\), with one full coordinate \(x\) of depth \(k+1\) (we write \(x_l\) for its level \(l\)) and three skeleton coordinates \(z_1,z_2,z_3\) of depth \(k\), and take the frame with the place \(\infty \) for \(x\) and the places \(0\), \(1\), \(3\) for \(z_1\), \(z_2\), \(z_3\). The skeleton digits

\begin{align*} S_{z_1}& =4x_k-2x_{k-1}+x_{k-2}-z_{1,k-1}-z_{2,k-1}+z_{2,k-2}-z_{3,k-1}+z_{3,k-2},\\ S_{z_2}& =7x_k-x_{k-1}-z_{1,k-1}+z_{1,k-2}-z_{3,k-1},\\ S_{z_3}& =8x_k-x_{k-1}-z_{1,k-1}+z_{2,k-1} \end{align*}

(terms with nonexistent levels omitted) are reachable from the frame for every \(k\ge 1\), so they complete to digital \((0,4k+1,4)\)-nets over \(\mathbb {F}_{13}\). Every graph form over \(\mathbb {F}_{13}\) with the depths \((k+1,k,k,k)\) and these skeleton digits, net or not, satisfies \(\delta N^{1/4}\ge 3\cdot 13^{-3/4}{\gt}0.438\) (toroidal).

Proof ▼

Write \(\kappa =(4,7,8)\), \(\beta =(-2,-1,-1)\) and \(\eta =(1,0,0)\) for the coefficients of the \(S_{z_i}\) on \(x_k\), \(x_{k-1}\), \(x_{k-2}\), \(g_{ij}\) and \(H_{ij}\) for those of \(S_{z_i}\) on \(z_{j,k-1}\) and \(z_{j,k-2}\) (\(i\ne j\)), and \(\alpha =(0,1,3)\) for the places of \(z_1,z_2,z_3\); all faults \(g_{ij}\) are \(\pm 1\).

Reachability. By Proposition 29(i), Propositions 18 and 14 hold for the skeleton rows: column \(x\) carries the three rows \(S_{z_i}\) and the levels \(k\), \(k-1\), \(k-2\) (the carry depths \(0,1,2\)), and column \(z_j\) carries the two rows \(S_{z_i}\), \(i\ne j\), and the levels \(k-1\), \(k-2\); one vector \(\lambda '\) of row scalars is shared by all columns. The coefficients of \(S_{z_i}\) on its own cell are diagonal entries, free by move (a). By Proposition 18 (with \(w=1\), \(y=\alpha _i\) on the column at \(\infty \), and \(w=y=1/(\alpha _i-\alpha _j)\) on the column \(z_j\)), the digits are reachable, with all deeper levels \(0\), if there are units \(\lambda '_i\), \(\mu _x\), \(\mu _{z_j}\) such that, modulo \(13\): (R1) \(\kappa _i=\lambda '_i\mu _x\); \(\kappa _i+\beta _i=\lambda '_i(c_0+c_1\alpha _i)\) with \(c_1\ne 0\); and \(\kappa _i+\beta _i+\eta _i=\lambda '_iG(\alpha _i)\) with \(\deg G=2\); (R2) \(g_{ij}=\lambda '_i\mu _{z_j}/(\alpha _i-\alpha _j)\), and \(g_{ij}+H_{ij}=\lambda '_i(\alpha _i-\alpha _j)^{-1}\bigl(c'_0+c'_1/(\alpha _i-\alpha _j)\bigr)\) with \(c'_1\ne 0\), for each \(j\) and the two \(i\ne j\). Take \(\lambda '=\kappa \) and \(\mu _x=1\). For (R2) at level \(k-1\) each column must give one value of \(\mu _{z_j}=g_{ij}(\alpha _i-\alpha _j)/\kappa _i\) for both \(i\ne j\): column \(z_1\) needs \(7\mu =-1\) and \(8\mu =-3\), column \(z_2\) needs \(4\mu =1\) and \(8\mu =2\), column \(z_3\) needs \(4\mu =3\) and \(7\mu =2\), and indeed \((\mu _{z_1},\mu _{z_2},\mu _{z_3})=(-2,-3,4)\) solves all six. For (R1), \((\kappa _i+\beta _i)/\kappa _i=(2/4,6/7,7/8)=(7,12,9)=c_0+c_1\alpha _i\) with \((c_0,c_1)=(7,5)\). The remaining conditions say that leading coefficients of interpolation polynomials are nonzero: three values \(\lambda '_iG(\alpha _i)\) at distinct \(\alpha _i\) always come from a \(G\) of degree at most \(2\), and since \(\det [\lambda ',\lambda '\odot (c_0+c_1\alpha ),\lambda '\odot G(\alpha )]\) is \(\lambda '_1\lambda '_2\lambda '_3\, c_1\) times the leading coefficient of \(G\) times a Vandermonde determinant, \(\deg G=2\) is equivalent to \(\det [\kappa ,\beta ,\eta ]\ne 0\); here \(\det [\kappa ,\beta ,\eta ]=7\cdot (-1)-8\cdot (-1)=1\). Likewise \(c'_1\ne 0\) in column \(z_j\) is equivalent to \(g_{ij}H_{lj}-H_{ij}g_{lj}\ne 0\) for \(\{ i,l\} =\{ 1,2,3\} \setminus \{ j\} \), and these are \(1\), \(-1\), \(1\) for \(j=1,2,3\). The places \(\infty ,0,1,3\) are distinct modulo \(13\). So Proposition 14 gives, for every \(k\ge 1\), moves of Lemma 2 that turn the graph form \(\Phi ^F\) of the frame into one with these skeleton digits (truncated for \(k=1\)). The box minors of \(\Phi ^F\) are units (Lemma 11), the moves multiply them by units, and Lemma 1 gives the net property.

Separation. Let \(a\) be the centred difference of the fine positions of two distinct points (Lemma 27). If some \(|a_c|\ge 13/2\), then \(|a|_\infty \ge 7\). Otherwise, as \(P_x\equiv x_k\) and \(P_{z_i}\equiv S_{z_i}\pmod{13}\), Lemma 27(ii) gives

\[ a_{z_i}\equiv \kappa _ia_x+\beta _i\xi _{x,1}+\eta _i\xi _{x,2}+\sum _{j\ne i}\bigl(g_{ij}\xi _{z_j,1}+H_{ij}\xi _{z_j,2}\bigr)-[i=1]\, \xi _{z_1,1}\pmod{13}, \]

with sign-consistent prefix patterns \((\xi _{c,1},\xi _{c,2})\in \{ (0,0),(\operatorname {sgn}a_c,0),(\operatorname {sgn}a_c,\operatorname {sgn}a_c)\} \) (and \(\xi =0\) for missing levels). We enumerate \(|a_x|\le 6\) and all patterns (\(4625\) combinations, with both signs for the patterns of the \(z_i\) before the sign check; rerun by the scripts of Appendix app:verify), take the centred \(a_{z_i}\) and keep the sign-consistent solutions: the least \(|a|_\infty \) of a nonzero solution is \(M_{13}=4\). Lemma 27(i) gives \(\delta N^{1/4}\ge (M_{13}-1)\, 13^{-3/4}=0.4381\ldots \).