B Per-prime designs in dimension three

Definition 129

✓

A per-prime design for \((p,r)\) assigns to each prescribed row \(R\) and each coordinate \(d\) integers \(R|d^{(i)}\), \(0\le i{\lt}L_d\). A graph form over \(\mathbb {F}_p\) with depths \(\mathbf k\) carries it if (i) each prescribed row \(R\) has the coefficient \(R|d^{(i)}\bmod p\) on level \(k_d-1-i\) of \(d\) and \(0\) on the higher levels of \(d\), and (ii) each offset row of \(c\) below its prescribed rows has the coefficient \(0\) on the cell of \(c\).

Lemma 130 Invariants

✓

(a) Where defined, \(\chi _1,\chi _2\) and \(J_1,\dots ,J_5\) are unchanged by the moves (a), (c) of Lemma 2 and the block scalings (b). (b) For every prime \(p\), \(\Phi ^F\) has \(\chi _1=\chi _2=-1\) for every \(k\ge 1\) (\(r=2\)), and \((J_1,\dots ,J_5)=(1,-1,2,2,1)\) for every \(k\ge 2\) (\(r=1\)).

Proof ▼

(a) Diagonal blocks are not read. A move (c) scales the last level of a cell and adds to every other level multiples of deeper ones; so \(\tilde x,\tilde y,\tilde\zeta ,\tilde\eta ,\tilde\xi \), each fixed by its leading level and a vanishing condition, are multiplied by units, and \(d_x\) by the product of the factors of \(\xi _0,\xi _1\). \(L_c\) scales the first offset row of \(c\) and replaces the second by a unit multiple of itself plus a multiple of the first; so \(R_Y\), \(R_Z\) (the combinations vanishing on \(\xi _0\)) and \(Z1\) restricted to \(\tilde x,\tilde y\) (where \(Z0\) vanishes) are multiplied by units, and the bracket in \(\chi _2\) is invariant under \(Z1\mapsto Z1+\lambda Z0\) and scales like \(Z1/Z0\). In each quantity every row, column and off-diagonal block occurs equally often in numerator and denominator, so all unit factors, including the block scalings, cancel.

(b) Let \(\varphi _\infty (V)\), \(\varphi _0(V)\), \(\varphi _1(V)\) be the coefficient vectors of \(V\in \mathbb {F}_p[t]_{{\lt}m}\) with respect to \(t^{m-1},t^{m-2},\dots \), resp. \(1,t,\dots \), resp. \(1,(t-1),\dots \). The first \(d\) digits of \([\Psi ^2V]_m\) vanish iff \(\deg V{\lt}m-d\) (as \(\Psi ^2V(t)=(-t)^{m-1}V((t-1)/t)\)), i.e. iff the first \(d\) entries of \(\varphi _\infty (V)\) do; those of \([\Psi V]_m\) vanish iff \((t-1)^d\mid V\) (proof of Proposition 10), i.e. iff those of \(\varphi _1(V)\) do. Invertible matrices whose leading \(d\) rows have equal kernels for every \(d\) differ by a lower-triangular left factor; so the frame readings are \((T_x\varphi _\infty ,\varphi _0,T_z\varphi _1)\), up to the unit \(s_k\), with \(T_x,T_z\) lower-triangular. Multiplying the reading of \(c\) by such a \(T_c\) changes \(\Phi _{cd}\) into \(T''_c\Phi _{cd}(T'_d)^{-1}\) (\(d\ne c\); \(T'_d\), \(T''_c\) the leading \(k_d\times k_d\) block of \(T_d\) and the trailing diagonal block of \(T_c\)) and changes \(\Phi _{cc}\), i.e. it is a combination of moves (a), (c). By (a) we may use the readings \((\varphi _\infty ,\varphi _0,\varphi _1)\). Then the column of level \(j\) of \(d\) is the offset part of the unique \(V\), \(\deg V{\lt}m\), whose cell digits (the top \(k_x\) coefficients, the coefficients of \(t^0,\dots ,t^{k_y-1}\), those of \((t-1)^0,\dots ,(t-1)^{k_z-1}\)) are \(1\) at \((d,j)\) and \(0\) elsewhere; \(X0\) reads the coefficient of \(t^{m-2-k}\), the first offset rows of \(y\) those of \(t^{k_y},t^{k_y+1}\), and \(Z0,Z1\) those of \((t-1)^k,(t-1)^{k+1}\). Let \(\bar t=t-1\), \(\epsilon =(-1)^k\) and \(\beta _i=\binom {k-1+i}{i}\), the coefficients of \((1-t)^{-k}\).

For \(r=2\) the degree bound, the vanishing orders at \(0\) and \(1\) (for \(\tilde x,\tilde y\) one more factor \(\bar t\), as \(Z0=0\)) and one normalization give \(x_k:\, t^{k+1}\bar t^k\), \(\tilde x:\, t^{k+1}\bar t^{k+1}\), \(y_k:\, \epsilon \, t^k\bar t^k\), \(\tilde y:\, -\epsilon \, t^{k-1}\bar t^{k+1}\). So \((Y0,Z0,Z1)|x_k=(\epsilon ,1,k+1)\), \((Y0,Z1)|\tilde x=(-\epsilon ,1)\), \((X0,Z0,Z1)|y_k=(\epsilon ,\epsilon ,k\epsilon )\), \((X0,Z1)|\tilde y=(-\epsilon ,-\epsilon )\), and

\[ \chi _1=\frac{(-\epsilon )(-\epsilon )\, \epsilon \cdot 1}{1\cdot \epsilon \, (-\epsilon )\, \epsilon }=-1,\qquad \chi _2=\bigl((k+1)-k\bigr)\frac{1\cdot (-\epsilon )}{1\cdot \epsilon }=-1. \]

For \(r=1\), inverting \(t^k\) resp. \(\bar t^k\) as a power series at the other finite place, the columns are

\[ \xi _j:\ t^k\bar t^k\textstyle \sum _{i\le j}\beta _it^{j-i},\qquad \eta _j:\ \epsilon \, \bar t^kt^{k-1-j}\sum _{i\le j}\beta _it^i,\qquad \zeta _j:\ t^k\bar t^{k-1-j}\sum _{i\le j}(-1)^i\beta _i\bar t^i, \]

with the entries

	\(X0\)	\(Y0\)	\(Y1\)	\(Z0\)	\(Z1\)
\(\xi _0\)		\(\epsilon \)	\(-k\epsilon \)	\(1\)	\(k\)
\(\xi _1\)		\(k\epsilon \)	\(-(k^2-1)\epsilon \)	\(k+1\)	\(k^2+k+1\)
\(\xi _2\)		\(\epsilon \binom {k+1}2\)	\(-\epsilon k(k-1)(k+2)/2\)	\(\binom {k+2}2\)	\((k+2)(k^2+k+2)/2\)
\(\eta _0\), \(\eta _1\)	\(\epsilon \), \(k\epsilon \)			\(\epsilon \), \((k+1)\epsilon \)	\((k-1)\epsilon \), \((k^2-2)\epsilon \)
\(\zeta _0\), \(\zeta _1\)	\(1\), \(-k\)	\(-\epsilon \), \((k+1)\epsilon \)	\((k-1)\epsilon \), \((2-k^2)\epsilon \)

Hence \(d_x=\epsilon \), \(R_Y=Y1+kY0\), \(R_Z=Z1-kZ0\), \(\tilde\zeta =\zeta _1+k\zeta _0\), \(\tilde\eta =\eta _1-k\eta _0\), \(\tilde\xi =\xi _2-(k+1)\xi _1+\binom {k+1}2\xi _0\),

\[ R_Y|(\xi _1,\zeta _0,\tilde\zeta ,\tilde\xi )=(\epsilon ,-\epsilon ,2\epsilon ,-\epsilon ),\qquad R_Z|(\xi _1,\eta _0,\tilde\eta ,\tilde\xi )=(1,-\epsilon ,-2\epsilon ,1),\qquad Y0|\tilde\zeta =Z0|\tilde\eta =\epsilon , \]

and substituting gives \((J_1,\dots ,J_5)=(1,-1,2,2,1)\). All entries are integers and all divisors are \(\pm 1\), so this holds for every \(k\) and every \(p\).

Proposition 131 Existence, \(m\equiv 2\)

✓

Let \(D\) be a per-prime design for \((p,2)\) with

\(Z0|x_{k-1}=Z0|x_{k-2}=Z0|y_{k-1}=Z0|y_{k-2}=0\) and \(X0|z_{k-3}=Y0|z_{k-3}=0\);
the following are nonzero modulo \(p\): the entries \(Z0|x_k\), \(Z0|y_k\), \(Y0|x_k\), \(Y0|x_{k-1}\), \(Z1|x_{k-1}\), \(X0|y_k\), \(X0|y_{k-1}\), \(X0|z_{k-1}\), \(Y0|z_{k-1}\) and the brackets \([Y0,Z1\, |\, x_{k-2},x_{k-1}]\), \([X0,Z1\, |\, y_{k-2},y_{k-1}]\), \([X0,Y0\, |\, z_{k-2},z_{k-1}]\);
\(\chi _1(D)=\chi _2(D)=-1\) in \(\mathbb {F}_p\).

Then for every \(k\ge 2\) the moves of Lemma 2 turn \(\Phi ^F\) into a digital \((0,3k+2,3)\)-net over \(\mathbb {F}_p\) that carries \(D\).

Proof ▼

All moves are moves (a)–(c), so every intermediate graph form has unit box minors; each pivot below is nonzero because, given the entries already normalized, it is a box minor or a quotient of two (box in brackets). An entry is set when it is made equal to its value in \(D\).

Step 1 (windows). \(Y0,Z0,Z1\) on \(x_{k-2},x_{k-1},x_k\) form an invertible matrix (box \((k-2,k+2,k+2)\)); subtracting combinations of these levels from the levels \(x_l\), \(l{\lt}k-2\), clears the three rows there. Likewise \(X0,Z0,Z1\) on \(y_{k-2},y_{k-1},y_k\) (box \((k+2,k-2,k+2)\)), and \(X0,Y0\) on \(z_l\), \(l{\lt}k-2\), with \(z_{k-2},z_{k-1}\) (box \((k+2,k+2,k-2)\)). Then subtract multiples of \(x_k\) from \(x_{k-1},x_{k-2}\) to clear \(Z0\) there (pivot \(Z0|x_k\), box \((k,k+1,k+1)\)), and likewise in \(y\) (box \((k+1,k,k+1)\)); now \(x_{k-1}=\tilde x\), \(y_{k-1}=\tilde y\).

Step 2. Scale \(\Phi _{yx}\) to set \(Y0|x_k\) (box \((k,k+2,k)\)) and the level \(x_{k-1}\) to set \(Y0|x_{k-1}\) (box \((k-1,k+2,k+1)\)); apply \(L_z\): \(Z0\mapsto \ell Z0\), \(Z1\mapsto \ell 'Z1+\lambda Z0\), to set \(Z0|x_k\), \(Z1|x_{k-1}\) (box \((k-1,k+1,k+2)\)) and \(Z1|x_k\).

Step 3. Scale \(\Phi _{xy}\) to set \(X0|y_k\) (box \((k+2,k,k)\)), the level \(y_{k-1}\) to set \(X0|y_{k-1}\) (box \((k+2,k-1,k+1)\)), and \(\Phi _{zy}\) to set \(Z0|y_k\) (box \((k+1,k,k+1)\)).

Step 4 (forced entries). This is where the invariants enter. All entries read by \(\chi _1,\chi _2\) are now set except \(Z1|y_{k-1}\), \(Z1|y_k\). By Lemma 130 and (I2) the current \(\chi _1,\chi _2\) equal those of \(D\); as \(\chi _1\) is a nonzero multiple of \(Z1|y_{k-1}\) and \(\chi _2\) is affine with nonzero slope in \(Z1|y_k\), these entries already have their values in \(D\), and no move is needed (or possible) to set them.

Step 5. Replace \(x_{k-2}\) by \(a\, x_{k-2}+b\, x_{k-1}\) so as to set \(Y0|x_{k-2}\), \(Z1|x_{k-2}\); the matrix \([Y0,Z1\, |\, x_{k-2},x_{k-1}]\) is invertible (box \((k-2,k+2,k+2)\), divided by \(Z0|x_k\)), and \(Z0\) stays \(0\) on \(x_{k-2}\). Afterwards the bracket is \(a\) times its old value and equals that of \(D\), nonzero by (U2); so \(a\ne 0\) and this is a move (c). The same for \(y_{k-2}\) (box \((k+2,k-2,k+2)\)).

Step 6. Scale \(\Phi _{xz}\), \(\Phi _{yz}\) to set \(X0|z_{k-1}\), \(Y0|z_{k-1}\) (boxes \((k+2,k+1,k-1)\), \((k+1,k+2,k-1)\)), and replace \(z_{k-2}\) by \(a\, z_{k-2}+b\, z_{k-1}\) to set \(X0|z_{k-2}\), \(Y0|z_{k-2}\) (box \((k+2,k+2,k-2)\); \(a\ne 0\) as in Step 5).

Step 7. By move (a), give each coordinate’s prescribed rows their values in \(D\) on the window of its own cell (\(0\) above it) and its other offset rows the value \(0\) on its own cell.

Steps 2–6 only combine window levels, so the prescribed rows still vanish above the windows (as Definition 129(i) requires), and the graph form carries \(D\). Lemma 1 completes the proof.

Proposition 132 Existence, \(m\equiv 1\)

✓

Let \(D\) be a per-prime design for \((p,1)\) with

\(Y0,Z0\) vanish on \(x_{k-2},x_{k-3}\); \(X0,Z0\) on \(y_{k-3}\); \(X0,Y0\) on \(z_{k-3}\);
the following are nonzero modulo \(p\): the entries \(Y0|x_k\), \(Z0|x_k\), \(X0|y_{k-1}\), \(Z0|y_{k-1}\), \(X0|z_{k-1}\), \(Y0|z_{k-1}\), \(Y1|x_{k-2}\), \(Z1|y_{k-3}\), \(Y1|z_{k-3}\) and the brackets

\[ [Y0,Z0\, |\, x_{k-1},x_k],\quad [X0,Z0\, |\, y_{k-2},y_{k-1}],\quad [X0,Y0\, |\, z_{k-2},z_{k-1}], \]

\[ [Y1,Z1\, |\, x_{k-3},x_{k-2}],\quad [Y1,Y0\, |\, x_k,z_{k-1}],\quad [Z1,Z0\, |\, x_k,y_{k-1}]; \]
\((J_1,\dots ,J_5)(D)=(1,-1,2,2,1)\) in \(\mathbb {F}_p\).

Then for every \(k\ge 3\) the moves of Lemma 2 turn \(\Phi ^F\) into a digital \((0,3k+1,3)\)-net over \(\mathbb {F}_p\) that carries \(D\).

Proof ▼

As for Proposition 131; in each solve below, \(a\ne 0\) because the corresponding bracket of \(D\) is nonzero (U1).

Step 1 (windows). Clear \(Y0,Y1,Z0,Z1\) on \(x_l\), \(l{\lt}k-3\) (box \((k-3,k+2,k+2)\)), \(X0,Z0,Z1\) on \(y_l\), \(l{\lt}k-3\) (box \((k+2,k-3,k+2)\)), and \(X0,Y0,Y1\) on \(z_l\), \(l{\lt}k-3\) (box \((k+2,k+2,k-3)\)). Then clear \(Y0,Z0\) on \(x_{k-2},x_{k-3}\) with \(x_{k-1},x_k\) (box \((k-1,k+1,k+1)\)), \(X0,Z0\) on \(y_{k-3}\) with \(y_{k-2},y_{k-1}\) (box \((k+2,k-2,k+1)\)), and \(X0,Y0\) on \(z_{k-3}\) with \(z_{k-2},z_{k-1}\) (box \((k+2,k+1,k-2)\)).

Step 2 (\(X0,Y0,Z0\)). Scale \(\Phi _{yx}\), \(\Phi _{zx}\) to set \(Y0|x_k\), \(Z0|x_k\) (boxes \((k,k+1,k)\), \((k,k,k+1)\)) and replace \(x_{k-1}\) by \(a\, x_{k-1}+b\, x_k\) to set \(Y0|x_{k-1}\), \(Z0|x_{k-1}\) (box \((k-1,k+1,k+1)\)). In the same way set \(X0|y_{k-1}\), \(Z0|y_{k-1}\) by \(\Phi _{xy}\), \(\Phi _{zy}\) and \(X0|y_{k-2}\), \(Z0|y_{k-2}\) by \(y_{k-2}\mapsto a\, y_{k-2}+b\, y_{k-1}\) (boxes \((k+2,k-1,k)\), \((k+1,k-1,k+1)\), \((k+2,k-2,k+1)\)), and \(X0|z_{k-1}\), \(Y0|z_{k-1}\), \(X0|z_{k-2}\), \(Y0|z_{k-2}\) by \(\Phi _{xz}\), \(\Phi _{yz}\) and \(z_{k-2}\) (boxes \((k+2,k,k-1)\), \((k+1,k+1,k-1)\), \((k+2,k+1,k-2)\)).

Step 3 (\(Y1,Z1\)). Apply \(L_y\): \(Y1\mapsto aY1+bY0\) to set \(Y1|x_k\), \(Y1|z_{k-1}\) (matrix \([Y1,Y0\, |\, x_k,z_{k-1}]\), box \((k,k+2,k-1)\)), and \(L_z\): \(Z1\mapsto cZ1+dZ0\) to set \(Z1|x_k\), \(Z1|y_{k-1}\) (box \((k,k-1,k+2)\)).

Step 4 (forced entries). All entries read by \(J_1,\dots ,J_4\) are now set except \(Y1|x_{k-1}\), \(Z1|x_{k-1}\), \(Y1|z_{k-2}\), \(Z1|y_{k-2}\), and \(J_1,\dots ,J_4\) are affine with nonzero slope in one of them each (through \(R_Y|\xi _1\), \(R_Z|\xi _1\), \(R_Y|\tilde\zeta \), \(R_Z|\tilde\eta \)). By Lemma 130 and (I1) they already have their values in \(D\).

Step 5. Scale the levels \(z_{k-3}\), \(y_{k-3}\), \(x_{k-2}\) to set \(Y1|z_{k-3}\), \(Z1|y_{k-3}\), \(Y1|x_{k-2}\) (boxes \((k+2,k+2,k-3)\), \((k+2,k-3,k+2)\), \((k-2,k+2,k+1)\)). Now \(\tilde\xi =\xi _2\), as \(Y0,Z0\) vanish on \(x_{k-2}\), and \(J_5\) is affine with nonzero slope in \(Z1|x_{k-2}\); by Lemma 130 and (I1) this entry has its value in \(D\). Finally replace \(x_{k-3}\) by \(a\, x_{k-3}+b\, x_{k-2}\) to set \(Y1|x_{k-3}\), \(Z1|x_{k-3}\) (box \((k-3,k+2,k+2)\)).

Step 6 is Step 7 of Proposition 131.

Definition 133 Per-prime relaxation

✓

Let \(D\) be a per-prime design for \((p,r)\) and \(B\in \mathbb {Z}_{{\gt}0}^3\) a search radius. A configuration is a pair \((E,j)\) of a cell difference \(E\in \mathbb {Z}^3\setminus \{ 0\} \), \(|E_c|\le B_c\), and carry depths \(j_c\in \{ 0,\dots ,L_c-1\} \), with \(j_c=0\) if \(E_c=0\). Put \(\Delta _{d,0}=E_d\), \(\Delta _{d,i}=\operatorname {sgn}(E_d)\, [i\le j_d]\) for \(1\le i{\lt}L_d\), and let \(\sigma _c\) resp. \(\iota _c\in \{ 0,\dots ,p-1\} \) be the residue of \(\sum _{d,i}R|d^{(i)}\Delta _{d,i}\), where \(R\) is the skeleton row resp. the row of the inner digit of \(c\). With \(\mathcal A(v)=\{ v,v-p\} \) for \(v\ne 0\), \(\mathcal A(0)=\{ 0\} \), and \(\varepsilon _c=0\) if \(E_d=0\) for all \(d\ne c\), \(\varepsilon _c=1\) otherwise, let

\[ t_c=\min _{\beta \in \mathcal A(\iota _c)}\bigl(|pE_c+\beta |-\varepsilon _c\bigr)^+\ \ (c\text{ full}),\qquad t_c=\min _{\alpha \in \mathcal A(\sigma _c),\, \beta \in \mathcal A(\iota _c)}\bigl(|p(pE_c+\alpha )+\beta |-\varepsilon _c\bigr)^+\ \ (c\text{ skeleton}). \]

A certificate is a pair \((T,B)\) with \(T\le t_x^2+t_y^2+t_z^2\) for every configuration, \(B_c{\lt}p\) for all \(c\), \(T\le p^2B_c^2\) for full \(c\), and \(B_c=1\), \(T\le p^4\) for skeleton \(c\).

Proposition 134 Separation

✓

Let \(p\) be odd, \(D\) a per-prime design for \((p,r)\) with a certificate \((T,B)\), and \(k\ge 3\) (\(r=1\)) resp. \(k\ge 2\) (\(r=2\)). Every graph form over \(\mathbb {F}_p\) with depths \(\mathbf k\) carrying \(D\), net or not, has \(\| X(w)-X(v)\| ^2_{\mathrm{torus}}\ge Tg_0^2\) for all indices \(v\ne w\) (integer coordinates on the torus of side \(N\)). Hence \(\delta N^{1/3}\ge \sqrt T\, p^{-5/3}\) (\(r=1\)) resp. \(\sqrt T\, p^{-4/3}\) (\(r=2\)).

Proof ▼

Let \(E_c\) be the centred residue of \(n_c(w)-n_c(v)\) modulo \(p^{k_c}\); as the cells are the index, \(E\ne 0\). The proof of Lemma 27(i) only uses \(X_c=g\, n_c+\theta \), \(0\le \theta {\lt}g\), \(N=g\, p^{k_c}\) and the centring; with \(g=pg_0\) (full) resp. \(p^2g_0\) (skeleton) the toroidal distance in coordinate \(c\) is at least \((|E_c|-1)g\). So if \(|E_c|{\gt}B_c\) for a full \(c\), or \(|E_c|\ge 2\) for a skeleton \(c\), the claim follows from \(T\le p^2B_c^2\) resp. \(T\le p^4\).

Otherwise \(|E_c|\le B_c{\lt}p\) for all \(c\). For \(E_c\ne 0\) the digits of \(n_c(w)\) and \(n_c(v)\) differ, modulo \(p\), by \(E_c\) on the last level, by \(\operatorname {sgn}E_c\) on the next \(j'_c\ge 0\) levels (a carry chain, cf. Lemma 27(ii)), and not above; with \(j_c=\min (j'_c,L_c-1)\), \((E,j)\) is a configuration. As the prescribed rows have the coefficients of \(D\) on the windows and \(0\) above, the skeleton and inner digits of \(c\) change by \(\sigma _c\) resp. \(\iota _c\) modulo \(p\), and since they lie in \([0,p)\), \(S_c(w)-S_c(v)\in \mathcal A(\sigma _c)\) and \(\rho _c(w)-\rho _c(v)\in \mathcal A(\iota _c)\). Further \(|\theta _c(w)-\theta _c(v)|{\lt}g_0\), with equality \(\theta _c(w)=\theta _c(v)\) if \(\varepsilon _c=0\): the deeper digits of \(c\) have coefficient \(0\) on the cell of \(c\) (Definition 129(ii)), and no other cell changes. Hence \(X_c(w)-X_c(v)\equiv g_0y_c+\theta _c(w)-\theta _c(v)\pmod N\) with \(y_c=pE_c+\beta \) resp. \(p(pE_c+\alpha )+\beta \) for some \(\alpha \in \mathcal A(\sigma _c)\), \(\beta \in \mathcal A(\iota _c)\); as \(|y_c|{\lt}3p^2\) and \(N/g_0=p^{k+2}\ge p^4\), the toroidal distance is at least \(g_0(|y_c|-\varepsilon _c)^+\ge g_0t_c\). Summing squares gives \(\| X(w)-X(v)\| ^2_{\mathrm{torus}}\ge g_0^2\sum _ct_c^2\ge Tg_0^2\). Finally \(\delta N^{1/3}\ge \sqrt T\, g_0N^{-2/3}=\sqrt T\, p^{(m-3k-6)/3}\).

Remark 135 Digital shifts

✓

Proposition 134 holds verbatim, with the same certificate \((T,B)\), for every digital shift (Definition 7) of every graph form carrying \(D\). So the constants of Table tab:perprime hold for every digitally shifted per-prime net.

Proof ▼

By Lemma 69 the shifted point set is indexed by its own cells \(n\), one point per cell, and its offsets are \(\Phi n+\gamma \), with the blocks \(\Phi \) of the unshifted graph form and a constant \(\gamma \). Each coordinate still has the form \(X_c=g_0(pn_c+\rho _c)+\theta _c\) resp. \(g_0(p(pn_c+S_c)+\rho _c)+\theta _c\) with \(S_c,\rho _c\in [0,p)\) and \(0\le \theta _c{\lt}g_0\). So the first paragraph of the proof of Proposition 134 applies, and \(E\) and the carry chains are those of the shifted cells, so \((E,j)\) is a configuration. The prescribed rows applied to \(n(w)-n(v)\) give \(S_c(w)-S_c(v)\equiv \sigma _c\) and \(\rho _c(w)-\rho _c(v)\equiv \iota _c\pmod p\), since \(\gamma \) cancels. As both digits lie in \([0,p)\), the differences lie in \(\mathcal A(\sigma _c)\) resp. \(\mathcal A(\iota _c)\). A shift may change which of the two representatives occurs, but \(t_c\) is the minimum over both. If \(\varepsilon _c=0\), the deeper digits of \(c\) are given by rows with coefficient \(0\) on the cell of \(c\) (Definition 129(ii)) plus the same constants, so \(\theta _c(w)=\theta _c(v)\); otherwise \(|\theta _c(w)-\theta _c(v)|{\lt}g_0\) as before. The rest of the proof is unchanged.

Remark 136 Formalized statements of this section without a result label

✓

The 17 resp. 20 per-prime designs of Appendix B satisfy (S2), (N2), (K) resp. (S1), (N1), (J).

1: J. Brakensiek, M. Heule, J. Mackey, D. Narváez, The resolution of Keller’s conjecture, J. Automat. Reason. 66 (2022) 277–300, doi:10.1007/s10817-022-09623-5; conference version in: IJCAR 2020, Lecture Notes in Comput. Sci. 12166, Springer, 2020, 48–65, doi:10.1007/978-3-030-51074-9_4; arXiv:1910.03740.
2: E. S. Barnes, N. J. A. Sloane, New lattice packings of spheres, Canad. J. Math. 35 (1983) 117–130, doi:10.4153/cjm-1983-008-1.
3: H. Cohn, N. Elkies, New upper bounds on sphere packings I, Ann. of Math. 157 (2003) 689–714, doi:10.4007/annals.2003.157.689; arXiv:math/0110009.
4: H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, The sphere packing problem in dimension \(24\), Ann. of Math. 185 (2017) 1017–1033, doi:10.4007/annals.2017.185.3.8; arXiv:1603.06518.
5: R. R. Coveyou, R. D. MacPherson, Fourier analysis of uniform random number generators, J. ACM 14 (1967) 100–119, doi:10.1145/321371.321379.
6: R. L. Cook, Stochastic sampling in computer graphics, ACM Trans. Graph. 5 (1986) 51–72, doi:10.1145/7529.8927.
7: L. Clozel, H. Oh, E. Ullmo, Hecke operators and equidistribution of Hecke points, Invent. Math. 144 (2001) 327–351, doi:10.1007/s002220100126.
8: R. Cranley, T. N. L. Patterson, Randomization of number theoretic methods for multiple integration, SIAM J. Numer. Anal. 13 (1976) 904–914, doi:10.1137/0713071.
9: J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, 1999.
10: J. Dick, T. Goda, G. Larcher, F. Pillichshammer, K. Suzuki, On the quasi-uniformity properties of quasi-Monte Carlo point sets and sequences, Part I: lattices and Kronecker sequences, Math. Comp. (2026), doi:10.1090/mcom/4264; arXiv:2502.06202 (theorem numbers cited from arXiv v2).
11: J. Dick, T. Goda, K. Suzuki, On the quasi-uniformity properties of quasi-Monte Carlo point sets and sequences, Part II: digital nets and sequences, Math. Comp. (2026), doi:10.1090/mcom/4263; arXiv:2501.18226 (theorem numbers cited from arXiv v2).
12: C.-J. de la Vallée Poussin, Recherches analytiques sur la théorie des nombres premiers, Ann. Soc. Sci. Bruxelles 20 B (1896) 183–256.
13: L. de Moura, S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction – CADE 28, Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625–635, doi:10.1007/978-3-030-79876-5_37.
14: J. Dick, F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge Univ. Press, 2010.
15: A. Eskin, H. Oh, Ergodic theoretic proof of equidistribution of Hecke points, Ergodic Theory Dynam. Systems 26 (2006) 163–167, doi:10.1017/s0143385705000428; arXiv:math/0409507.
16: H. Faure, Discrépance de suites associées à un système de numération (en dimension \(s\)), Acta Arith. 41 (1982) 337–351, doi:10.4064/aa-41-4-337-351.
17: H. Faure, C. Lemieux, Generalized Halton sequences in 2008: a comparative study, ACM Trans. Model. Comput. Simul. 19 (2009), Art. 15, 1–31, doi:10.1145/1596519.1596520.
18: T. Goda, R. Hofer, K. Suzuki, Disproving the quasi-uniformity of the Halton sequences and of some Halton-type sequences, J. Complexity 95 (2026) 102047, doi:10.1016/j.jco.2026.102047; arXiv:2511.21153 (theorem numbers cited from arXiv v2).
19: L. GrünschloSS, J. Hanika, R. Schwede, A. Keller, \((t,m,s)\)-nets and maximized minimum distance, in: A. Keller, S. Heinrich, H. Niederreiter (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, 2008, 397–412, doi:10.1007/978-3-540-74496-2_23.
20: L. GrünschloSS, A. Keller, \((t,m,s)\)-nets and maximized minimum distance, Part II, in: P. L’Ecuyer, A. B. Owen (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer, 2009, 395–409, doi:10.1007/978-3-642-04107-5_25.
21: J. Hadamard, Sur la distribution des zéros de la fonction \(\zeta (s)\) et ses conséquences arithmétiques, Bull. Soc. Math. France 24 (1896) 199–220, doi:10.24033/bsmf.545.
22: G. Hajós, Über einfache und mehrfache Bedeckung des \(n\)-dimensionalen Raumes mit einem Würfelgitter, Math. Z. 47 (1942) 427–467, doi:10.1007/bf01180974.
23: T. C. Hales, A proof of the Kepler conjecture, Ann. of Math. 162 (2005) 1065–1185, doi:10.4007/annals.2005.162.1065.
24: J. M. Hammersley, Monte Carlo methods for solving multivariable problems, Ann. New York Acad. Sci. 86 (1960) 844–874, doi:10.1111/j.1749-6632.1960.tb42846.x.
25: G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., revised by D. R. Heath-Brown and J. H. Silverman, Oxford Univ. Press, 2008.
26: X. He, Rotated sphere packing designs, J. Amer. Statist. Assoc. 112 (2017) 1612–1622, doi:10.1080/01621459.2016.1222289.
27: X. He, Interleaved lattice-based maximin distance designs, Biometrika 106 (2019) 453–464, doi:10.1093/biomet/asy069; arXiv:1807.02289.
28: X. He, Lattice-based designs with quasi-optimal separation distance on all projections, Biometrika 108 (2021) 443–454, doi:10.1093/biomet/asaa057; arXiv:1709.02062.
29: M. Hall, L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 5 (1955) 541–549, doi:10.2140/pjm.1955.5.541.
30: R. Hofer, K. Suzuki, A complete classification of digital \((0,m,3)\)-nets and digital \((0,2)\)-sequences in base \(2\), Unif. Distrib. Theory 14 (2019) 43–52, doi:10.2478/udt-2019-0004; arXiv:1807.04383.
31: R. Kannan, A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979) 499–507, doi:10.1137/0208040.
32: D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.
33: W. Kositwattanarerk, F. Oggier, Connections between Construction D and related constructions of lattices, Des. Codes Cryptogr. 73 (2014) 441–455, doi:10.1007/s10623-014-9939-3; arXiv:1308.6175.
34: N. M. Korobov, The approximate computation of multiple integrals, Dokl. Akad. Nauk SSSR 124 (1959) 1207–1210.
35: R. Kritzinger, Dispersion of digital \((0,m,2)\)-nets, Monatsh. Math. 195 (2021) 155–171, doi:10.1007/s00605-021-01525-9; arXiv:2004.14760.
36: H. W. Lenstra, Jr., Euclidean number fields of large degree, Invent. Math. 38 (1976/77) 237–254, doi:10.1007/bf01403131.
37: C. Lemieux, Tractability using periodized generalized Faure sequences, J. Complexity 31 (2015) 42–56, doi:10.1016/j.jco.2014.08.001.
38: C. Lemieux, H. Faure, New perspectives on \((0,s)\)-sequences, in: P. L’Ecuyer, A. B. Owen (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer, 2009, 113–130, doi:10.1007/978-3-642-04107-5_7.
39: G. Larcher, H. Niederreiter, W. Ch. Schmid, Digital nets and sequences constructed over finite rings and their application to quasi-Monte Carlo integration, Monatsh. Math. 121 (1996) 231–253, doi:10.1007/bf01298952.
40: G. Larcher, F. Pillichshammer, Walsh series analysis of the \(L_2\)-discrepancy of symmetrisized point sets, Monatsh. Math. 132 (2001) 1–18, doi:10.1007/s006050170054.
41: J. C. Lagarias, P. W. Shor, Keller’s cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. (N.S.) 27 (1992) 279–283, doi:10.1090/s0273-0979-1992-00318-x; arXiv:math/9210222.
42: J. Mackey, A cube tiling of dimension eight with no facesharing, Discrete Comput. Geom. 28 (2002) 275–279, doi:10.1007/s00454-002-2801-9.
43: J. Matoušek, On the \(L_2\)-discrepancy for anchored boxes, J. Complexity 14 (1998) 527–556, doi:10.1006/jcom.1998.0489.
44: The mathlib Community, The Lean mathematical library, in: Proc. 9th ACM SIGPLAN Int. Conf. on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367–381, doi:10.1145/3372885.3373824.
45: F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
46: H. Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987) 273–337, doi:10.1007/bf01294651.
47: A. B. Owen, Randomly permuted \((t,m,s)\)-nets and \((t,s)\)-sequences, in: H. Niederreiter, P. J.-S. Shiue (eds.), Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Lecture Notes in Statist. 106, Springer, 1995, 299–317, doi:10.1007/978-1-4612-2552-2_19.
48: L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 1 (1951) 111–116, doi:10.2140/pjm.1951.1.111.
49: O. Perron, Über lückenlose Ausfüllung des \(n\)-dimensionalen Raumes durch kongruente Würfel, Math. Z. 46 (1940) 1–26, doi:10.1007/bf01181421; II, Math. Z. 46 (1940) 161–180, doi:10.1007/bf01181436.
50: L. Panek, M. Firer, M. M. S. Alves, Symmetry groups of Rosenbloom–Tsfasman spaces, Discrete Math. 309 (2009) 763–771, doi:10.1016/j.disc.2008.01.013.
51: R. M. Roth, G. Seroussi, On generator matrices of MDS codes (Corresp.), IEEE Trans. Inform. Theory 31 (1985) 826–830, doi:10.1109/tit.1985.1057113.
52: M. Yu. Rosenbloom, M. A. Tsfasman, Codes for the \(m\)-metric, Probl. Inf. Transm. 33 (1997) 45–52.
53: L. Rudolph, The even-order GrünschloSS–Keller permutation nets are \((0,m,2)\)-nets, preprint, Zenodo, version 1.0.0, 2026, doi:10.5281/zenodo.22264675.
54: N. Sakai, T. Goda, Space-filling lattice designs for computer experiments, arXiv:2602.15390 (2026).
55: I. H. Sloan, S. Joe, Lattice Methods for Multiple Integration, Oxford Univ. Press, 1994.
56: M. M. Skriganov, Coding theory and uniform distributions, Algebra i Analiz 13 (2001) 191–239; English transl. St. Petersburg Math. J. 13 (2002) 301–337; arXiv:math/9909163 (theorem numbers cited from the arXiv version).
57: I. M. Sobol’, On the distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. Mat. Fiz. 7 (1967) 784–802; English transl. USSR Comput. Math. Math. Phys. 7 (1967) 86–112, doi:10.1016/0041-5553(67)90144-9.
58: I. M. Sobol’, B. V. Shukhman, Quasi-random points keep their distance, Math. Comput. Simulation 75 (2007) 80–86, doi:10.1016/j.matcom.2006.09.004.
59: K. Suzuki, Exact \(\ell ^\infty \)-separation radius of Sobol’ sequences in dimension \(2\), arXiv:2508.14803 (2025).
60: K. Suzuki, Separation properties of scrambled digital nets and related random point sets, arXiv:2607.29063 (2026).
61: S. Tezuka, Polynomial arithmetic analogue of Halton sequences, ACM Trans. Model. Comput. Simul. 3 (1993) 99–107, doi:10.1145/169702.169694.
62: S. Tezuka, Uniform Random Numbers: Theory and Practice, Kluwer, 1995.
63: R. Tavildar, P. Viswanath, Approximately universal codes over slow-fading channels, IEEE Trans. Inform. Theory 52 (2006) 3233–3258, doi:10.1109/tit.2006.876226; arXiv:cs/0512017.
64: E. R. van Dam, B. Husslage, D. den Hertog, H. Melissen, Maximin Latin hypercube designs in two dimensions, Oper. Res. 55 (2007) 158–169, doi:10.1287/opre.1060.0317.
65: E. R. van Dam, G. Rennen, B. Husslage, Bounds for maximin Latin hypercube designs, Oper. Res. 57 (2009) 595–608, doi:10.1287/opre.1080.0604.
66: P. O. Vontobel, A. Ganesan, On universally decodable matrices for space-time coding, Des. Codes Cryptogr. 41 (2006) 325–342, doi:10.1007/s10623-006-9019-4; arXiv:cs/0601075.
67: M. S. Viazovska, The sphere packing problem in dimension \(8\), Ann. of Math. 185 (2017) 991–1015, doi:10.4007/annals.2017.185.3.7.