4 Cubic cells, \(m\equiv 0\pmod s\): designs from short lattice vectors
4.1 Diagonal dominance
Let \(F\) be a reachable design whose diagonal vanishes at every carry depth \(n\ge 1\), with \(F_0[c][c]=-\alpha _c\) and
Then \(\mathrm{LB}\ge 1-a/q\) for every \(q\ge 5a+4\) (and every \(k\ge 1\)).
Since the diagonal vanishes at every carry depth \(n\ge 1\), the own term of every moving coordinate \(i\) is \(-\alpha _i\) for every carry depth \(j_i\), and dominance gives \(e_i\sigma _i\le -\alpha _i+\alpha _i=0\) and \(|\sigma _i|\le 2a{\lt}q\): every moving coordinate is backward, so \(b_i\ge q-|\sigma _i|-\mathrm{jit}_i\). An own-axis step along \(c\) has \(b_c=q-\alpha _c\ge q-a\) (no jitter). A step with at least two moving axes has \(\sum b_i^2\ge 2(q-2a-1)^2\), and \(\sqrt2(q-2a-1)\ge q-a\) holds for \(q\ge (2\sqrt2-1)a/(\sqrt2-1)+\sqrt2/(\sqrt2-1)\), in particular for \(q\ge 5a+4\). A truncated design is dominant with the same \(a\), and at \(k=1\) the configurations are a subset of those for \(k\ge 2\) (after Lemma 4).
4.2 Admissible design columns form a lattice
For \(E\in \Lambda _j\) the polynomial of \(E\) has coefficients in \(R_S\).
\(\operatorname {lc}_j(\Lambda _j)=\gamma _j\mathbb {Z}\) for a positive \(S\)-unit \(\gamma _j\).
An integer column is admissible at carry depth \(j\) if and only if it lies in \(\Lambda _j\) and \(\operatorname {lc}_j(E)\) is an \(S\)-unit; in particular every \(E\in \Lambda _j\) with \(\operatorname {lc}_j(E)=\gamma _j\) is admissible.
If \(E_i\in \Lambda _i\) and \(\operatorname {lc}_i(E_i)=\gamma _i\) for \(i=0,\dots ,j\), then \(E_0,\dots ,E_j\) is a basis of \(\Lambda _j\), and \(\{ E\in \Lambda _j:\operatorname {lc}_j(E)=\gamma _j\} =E_j+\Lambda _{j-1}\).
(i) Lagrange interpolation at any \(j+1\) rows \(J\) recovers \(g=\sum _{b\in J}(E_b/w_b)\prod _{b'\in J\setminus b}(X-y_{b'})/(y_b-y_{b'})\), and all denominators are \(S\)-units. (ii) \(\operatorname {lc}_j(\Lambda _j)\) is a finitely generated subgroup of \(\mathbb Q\), nonzero because \(\Lambda _j\) spans \(V_j\), so it is \(\gamma _j\mathbb {Z}\) with \(\gamma _j{\gt}0\); by (i), \(\gamma _j\in R_S\). The vector \((w_cy_c^j)_c\) of \(g=X^j\) has \(S\)-unit or zero entries, so some product \(P\) of primes in \(S\) makes \(P(w_cy_c^j)_c\) integral, with \(\operatorname {lc}_j=P\); hence \(P\in \gamma _j\mathbb {Z}\), and \(\gamma _j\) has no prime factor outside \(S\) in its numerator either. (iii) is (i) together with the definition. (iv) If \(v\in \Lambda _j\) has \(\operatorname {lc}_j(v)=t\gamma _j\), then \(v-tE_j\in \Lambda _j\cap \ker \operatorname {lc}_j=\Lambda _{j-1}\); induction on \(j\).
Let \(\pi _j\) be the orthogonal projection of \(\mathbb {R}^{s-1}\) onto the line \(V_j\cap V_{j-1}^\perp \). Then \(\pi _j(\Lambda _j)\) is generated by a vector of length
Every \(E\in \Lambda _j\setminus V_{j-1}\) has \(\| E\| _2\ge \eta _j\).
The \(p\)-adic places, \(p\in S\). If \(E\in V_j\) has \(\operatorname {lc}_j(E)=1\) and \(\max _c|E_c|_p=p^e\), then \(p^eE\) is \(p\)-integral, and \(D'p^eE\in \Lambda _j\) for an integer \(D'\) prime to \(p\); so \(D'p^e\in \gamma _j\mathbb {Z}\) and \(v_p(\gamma _j)\le e\). Conversely, for \(v\in \Lambda _j\) with \(\operatorname {lc}_j(v)=\gamma _j\) the vector \(v/\gamma _j\) has \(\operatorname {lc}_j=1\) and \(\max _c|v_c/\gamma _j|_p\le p^{v_p(\gamma _j)}\). So \(A_{j,p}=p^{v_p(\gamma _j)}\), and as \(\gamma _j{\gt}0\) is an \(S\)-unit, \(\gamma _j=\prod _{p\in S}A_{j,p}\). The archimedean place. On \(V_j\), \(\operatorname {lc}_j(E)=\langle \theta ,E\rangle \) for a unique \(\theta \in V_j\), and \(\theta \perp V_{j-1}\). Hence \(\| \pi _j(E)\| =|\operatorname {lc}_j(E)|/\| \theta \| \), and the least norm with \(\operatorname {lc}_j=1\) is \(A_{j,\mathbb {R}}=1/\| \theta \| \), attained at \(\theta /\| \theta \| ^2\). So \(\pi _j(\Lambda _j)=\gamma _j\mathbb {Z}\, \theta /\| \theta \| ^2\), generated by a vector of length \(\gamma _jA_{j,\mathbb {R}}=\eta _j\), and \(\| E\| \ge \| \pi _j(E)\| \ge \eta _j\) if \(\operatorname {lc}_j(E)\ne 0\).
Let \(E_i\in \Lambda _i\) with \(\operatorname {lc}_i(E_i)=\gamma _i\) for \(i{\lt}j\), and let \(v\in \Lambda _j\) with \(\operatorname {lc}_j(v)=\gamma _j\). Write the orthogonal projection of \(v\) onto \(V_{j-1}\) as \(\sum _{i{\lt}j}c_iE_i\) and put \(E_j=v-\sum _{i{\lt}j}\lfloor c_i+\frac12\rfloor E_i\). Then \(E_j\in \Lambda _j\), \(\operatorname {lc}_j(E_j)=\gamma _j\), and
Consequently, if \(E_0,\dots ,E_j\) are all obtained in this way and \(\eta _i\le H\) for every \(i\le j\), then \(\| E_i\| _2\le (3/2)^iH\) for every \(i\le j\).
\(E_j-v\in \Lambda _{j-1}=\ker \operatorname {lc}_j\cap \Lambda _j\), and \(E_j=\pi _j(v)+\sum _{i{\lt}j}\bigl(c_i-\lfloor c_i+\frac12\rfloor \bigr)E_i\) with \(\| \pi _j(v)\| =\eta _j\) (Lemma 23) and every coefficient in \([-\frac12,\frac12]\). For the consequence let \(T_i=\sum _{i'\le i}\| E_{i'}\| \). Then \(T_0=\eta _0\le H\) and \(T_i\le \frac32T_{i-1}+H\), so \(T_i\le 2H((3/2)^{i+1}-1)\) by induction, and \(\| E_i\| \le H+\frac12T_{i-1}\le (3/2)^iH\).
4.3 The design \(U^*_s\) and the proof of Theorem A
Let \(s\ge 3\), \(\nu =s-2\), and take the places \(\infty ,0,1,\dots ,\nu \) and \(\lambda '\equiv 1\). For each column \(d\) let \(E_{d,0}\) be the generator of \(\Lambda _0\) with \(\operatorname {lc}_0{\gt}0\), and for \(1\le j\le \nu \) let \(E_{d,j}\) be the unique \(E\in \Lambda _j\) with \(\operatorname {lc}_j(E)=+\gamma _j\) whose orthogonal projection onto \(V_{j-1}\) has all its coefficients in the basis \(E_{d,0},\dots ,E_{d,j-1}\) in \([-\frac12,\frac12)\). The design \(U^*_s=(F_0,\dots ,F_\nu )\) has the partial sums \(M^{(j)}[c][d]=E_{d,j}[c]\) (\(c\ne d\), \(j\le \nu \)), the diagonal \(F_0[c][c]=-\alpha _c\) at carry depth \(0\) with \(\alpha _c=\sum _{d\ne c}\max _j|E_{d,j}[c]|\), and zero diagonal at the carry depths \(n\ge 1\). Let \(a^*_s=\max _c\alpha _c\).
The every-dimension theorem also holds with the monomial design \(U_s\): put \(L_s=\operatorname {lcm}(1,\dots ,s-2)^{s-1}\), \(\lambda '_c=L_s\) for finite \(c\), \(\lambda '_\infty =1\), and \(F_n[c][d]=L_s/(c-d)^{n+1}\) for finite \(c,d\), \(F_n[\infty ][d]=[n=0]\), \(F_n[c][\infty ]=L_s\binom cn\), with a diagonal that is dominant in the sense of Proposition 21. Its increments are monomials in the nodes, and the proof of Theorem A applies verbatim with its constant \(a_s=\max _c\alpha _c\) in place of \(a^*_s\) (for \(k\ge 2\) the net property, the separation bound for \(q\ge 5a_s+4\) and the sharpness are formally verified for this design). But \(\log a_s=(1+o(1))s^2\): for finite \(c\), \(\alpha _c\ge |F_0[c][\infty ]|=L_s\), and \(\log L_s=(s-1)\psi (s-2)\) with Chebyshev’s function \(\psi \), while \(a_s\le L_s(s^2+2^{s-2})\); so \(a_s=e^{\Theta (s^2)}\) already by Chebyshev’s bounds \(\psi (x)\asymp x\), and the constant \(1\) uses the prime number theorem [ 21 , 12 ] . In the language above the reason is \(p\)-adic: a monomial has all its roots at \(0\), so at a collision of nodes it is as large as possible, \(|y^j|_p=p^{j\, v_p(c-d)}\), at every carry depth and in every column, and the single row scalar \(\lambda '\) must clear all of it. Theorem A puts the roots near the colliding nodes, separately for each prime, and so replaces \(e^{\Theta (s^2)}\) by the upper bound \(e^{s\log s+O(s)}\) (Table tab:astar: \(a_5=17407\) against \(a^*_5=16\)).
Lean: assuming classical theorems. The growth statement \(\log a_s=(1+o(1))s^2\) uses the prime number theorem as an explicit hypothesis (PNTpsi); everything else is unconditional.