12 One point per cube: cube tilings and the value 1
Let \(q\ge 2\), \(j\ge 1\), \(\beta _0,\dots ,\beta _{j-1}\in \mathbb {Z}/q\mathbb {Z}\), and \(\phi (P)=\sum _{i{\lt}j}\beta _i\, d_i(P)\) for \(P\in \mathbb {Z}/q^j\mathbb {Z}\) (digits of the representative in \([0,q^j)\)). Then \(\phi \) is a homomorphism \(\mathbb {Z}/q^j\mathbb {Z}\to \mathbb {Z}/q\mathbb {Z}\) if and only if \(\beta _i=0\) for every \(i\ge 1\).
If \(\beta _i=0\) for \(i\ge 1\), then \(\phi (P)=\beta _0\, (P\bmod q)\), a homomorphism. Conversely, a homomorphism on the cyclic group \(\mathbb {Z}/q^j\mathbb {Z}\) satisfies \(\phi (P)=P\, \phi (1)=\beta _0P=\beta _0\, d_0(P)\) in \(\mathbb {Z}/q\mathbb {Z}\); at \(P=q^i\), \(i\ge 1\), this gives \(\beta _i=\phi (q^i)=\beta _0\, d_0(q^i)=0\).
Let \(q\ge 2\).
One level. Let a set of integer vectors \(Y\in \mathbb {Z}^s\) consist of all \(Y\) whose lowest base-\(q\) digits \((Y_c\bmod q)_c\) satisfy a system of linear equations over \(\mathbb {Z}/q\mathbb {Z}\), with solution set \(y_0+C\) for a linear code \(C\subset (\mathbb {Z}/q\mathbb {Z})^s\), all higher digits being free. Then the set is the coset \(y_0+C+q\mathbb {Z}^s\) of the Construction A lattice \(C+q\mathbb {Z}^s\).
Two levels. For an \(s\times s\) matrix \(B\) over \(\mathbb {Z}/q\mathbb {Z}\) let \(\mathcal D_B=\{ q\ell +(B\ell \bmod q):\ell \in \{ 0,\dots ,q-1\} ^s\} \subset (\mathbb {Z}/q^2\mathbb {Z})^s\) (the two-digit set of \(B\); \(\ell \) plays the part of the last cell digits), with \(B\ell \bmod q\) taken in \([0,q)^s\). Then \(\mathcal D_B\) is a subgroup if and only if \(Bc\equiv 0\pmod q\) for every carry vector \(c=(\lfloor (v_i+v'_i)/q\rfloor )_i\) of two vectors \(v,v'\in \{ B\ell \bmod q\} \). If \(B\) is invertible, \(\mathcal D_B\) is not a subgroup.
Locally a lattice. Let a digital net over \(\mathbb {Z}/q\mathbb {Z}\) be in graph form with depths \((k,\dots ,k)\) and geometric layer \(\tilde M\), and let the cells \(n\), \(n'\) differ only in their last level, by \(n'-n=E\in \mathbb {Z}^s\) (no carry). If the geometric digits \(r\) of \(n\) satisfy \(r+\tilde ME\in [0,q)^s\), then in cell units the points of \(n'\) and \(n\) differ by \((I+\tilde M/q)E+(f'-f)/q\), with \(f,f'\in [0,1)^s\) the contributions of the deeper digits.
(a) The set of \(Y\in \mathbb {Z}^s\) with \(Y\bmod q\in y_0+C\) is \(y_0+C+q\mathbb {Z}^s\). (b) Let \(Y=q\ell +v\) and \(Y'=q\ell '+v'\) be in \(\mathcal D_B\), and let \(c\) be the carry vector of \(v,v'\). Then \(Y+Y'=q(\ell +\ell '+c)+(v+v'-qc)\) with \(v+v'-qc\in [0,q)^s\), and \(v+v'\equiv B(\ell +\ell ')\); so \(Y+Y'\in \mathcal D_B\) if and only if \(Bc\equiv 0\). A nonempty finite subset of a group that is closed under addition is a subgroup. If \(B\) is invertible, its image contains \(v=v'=\lceil q/2\rceil \mathbf{e}_i\), whose carry vector is \(\mathbf{e}_i\); then \(B\mathbf{e}_i\equiv 0\) would be needed, which is false. (c) Only the last digits of the cells change, so \(r\) changes by \(\tilde ME\) modulo \(q\), and \(r'=r+\tilde ME\) exactly since both sides lie in \([0,q)^s\); the cell digits change by \(E\).
Let \(p\) be a prime and consider a graph form over \(\mathbb {F}_p\) with depths \((1,\dots ,1)\): coordinate \(c\) of the point with index \(n\in \mathbb {F}_p^s\) has the digits \(n_c\), \(r_c(n)=(Bn)_c\) and deeper digits, with \(B\in \mathbb {F}_p^{s\times s}\). For \(E\in \mathbb {Z}^s\) let \(\beta =BE\bmod p\in \{ 0,\dots ,p-1\} ^s\) and \(n'\equiv n+E\). Then \(r(n')=r(n)+\beta -p\omega \) with \(\omega _c=[r_c(n)+\beta _c\ge p]\), and \(\omega _c=0\) whenever \(\beta _c=0\). If \(B\) is invertible, then every \(\omega \in \{ 0,1\} ^s\) with \(\omega _c=0\) whenever \(\beta _c=0\) is the wrap vector of some cell \(n\).
Let a digital \((0,sk,s)\)-net over \(\mathbb {Z}/q\mathbb {Z}\), \(k\ge 1\), be in graph form with depths \((k,\dots ,k)\) and geometric layer \(\tilde M\). For disjoint \(T,Z\subset \{ 1,\dots ,s\} \) with \(|T|=|Z|\), \(\det \tilde M_{T,Z}\) is a unit of \(\mathbb {Z}/q\mathbb {Z}\). In particular \(\tilde M\) has rank at least \(\lfloor s/2\rfloor \) modulo every prime factor of \(q\).
(i) \(r(n')\equiv B(n+E)\equiv r(n)+\beta \), and \(r(n')\in [0,p)^s\), which gives \(\omega \); if \(\beta _c=0\), then \(r_c(n)+\beta _c{\lt}p\). If \(B\) is invertible, take \(n=B^{-1}y\) with \(y_c=p-1\) if \(\omega _c=1\) (then \(\beta _c\ge 1\) and \(y_c+\beta _c\ge p\)) and \(y_c=0\) if \(\omega _c=0\). (ii) The box with depths \(k+1\) on \(T\), \(k-1\) on \(Z\) and \(k\) elsewhere has total depth \(sk\); by Lemma 2 its minor is, up to sign, the determinant of the first offset rows of \(T\) on the last level of \(Z\), which is \(\det \tilde M_{T,Z}\) modulo \(q\), and by Lemma 1 it is a unit. Disjoint \(T\), \(Z\) of size \(\lfloor s/2\rfloor \) exist.
A coordinate with \(E_c=0\) and \(\beta _c\ne 0\) contributes \(\min (b_c,1-b_c)\le \frac12\) to the fully folded length, with equality only for \(b_c=\frac12\): a step keeps its full length under free wraps only if its glue in each coordinate that does not move is \(\frac12\), the only value that is its own negative modulo \(1\). So half-integer layers do not need the wraps of different coordinates to be correlated: for odd \(s\) the differences between the two cosets of \(D_s^+\) fill \((\mathbb {Z}+\frac12)^s\), a set that free wraps (integer changes of single coordinates) map to itself, so these steps keep a length of at least \(\sqrt s/2\), and the relaxation of Proposition 118 at \(k=1\), which allows every wrap, tends to \(\min (\sqrt s/2,\sqrt2)\) for dominant layers. The glue \(\frac13\mathbf1\) of the reflected cube does not survive: with free wraps the step \(E=\mathbf{e}_1\) of the layer \(\frac p3\mathbf1\mathbf1^{\! \top }\) would have fully folded length \(1/\sqrt3=.5773\ldots \), and bounded perturbations of the equal rows \(\mathbf1a^{\! \top }\) of the column nets make the wraps independent (computed instance: Figure fig:arcwhylat(b)). Wraps that are correlated across coordinates because the layer is singular (locked wraps, Section 13.3) are needed otherwise: the column nets (Theorem 51) share one geometric digit among all three coordinates, Proposition 106 between two, and in Proposition 107 a layer of rank one locks all three, one coordinate reading half of the digit of the others; literally equal rows exist only at \((s,m)=(3,3)\) (Lemma 52). Locked wraps are what produces the coherent phases defined before Proposition 102. The half-integer rule concerns coordinates whose wraps are free: a coordinate whose wraps are locked to those of the others can carry other glue and a step longer than one cell along its own axis (in the net \(\mathcal W_p\) of Section 13.3, the glue \(\frac12+3\varepsilon \) and the step \(1+2\varepsilon \) along \(\mathbf{e}_z\), with \(\varepsilon =\rho /(2p)\)). The rule concerns the length of a single step under free wraps; it is a heuristic for the choice of glue, not an optimality statement for the minimum, even for free coordinates (the remark on \(\sqrt{233}/15\) in Section 13.3).
Let \(S\) be a periodic one-per-cube set in \(\mathbb {R}^s\) with period lattice \(\Pi \).
If \(S=L\) is a lattice and \(\mathbb {Z}^s+L\) is dense in \(\mathbb {R}^s\), then \(L\) contains a unit vector \(\mathbf{e}_c\); so \(\mu (L)\le 1\).
If \(S=L\subset \mathbb Q^s\) is a lattice whose phase group \(Y\) equals \(\pi _1(Y)\times \dots \times \pi _s(Y)\), the product of its projections to the coordinate circles, then \(L\) contains a unit vector \(\mathbf{e}_c\); so \(\mu (L)\le 1\).
If \(s\le 7\) and \(\mathbb {Z}^s+\Pi \) is dense in \(\mathbb {R}^s\), then two points of \(S\) differ by a unit vector; so \(\mu (S)\le 1\).
If \(S-x\subset \mathbb Q^s\) for some \(x\), all squared distances in \(S\) are rational. Hence \(\mu (S){\lt}(4/3)^{1/4}\) for \(s=2\) and \(\mu (S){\lt}2^{1/6}\) for \(s=3\), the optimal packing values at density \(1\); and for \(4\le s\le 7\), \(\mu (S)\) differs from the value of the densest known packing at density \(1\) (\(D_4\), \(D_5\), \(E_6\), \(E_7\), with squared minima \(\sqrt2\), \(2^{3/5}\), \(2\cdot 3^{-1/6}\), \(2^{6/7}\)).
Lean: assuming classical theorems. Uses Hajós’s theorem, Keller’s conjecture for \(s\le 7\) and the optimal packing bounds in dimensions two and three as explicit hypotheses.
Let \(f(x)=\# \bigl(S\cap (x+[0,1)^s)\bigr)\). Then \(f(x+\pi )=f(x)\) for \(\pi \in \Pi \) and \(f(n)=1\) for \(n\in \mathbb {Z}^s\), so \(f=1\) on \(\mathbb {Z}^s+\Pi \). For every \(x\) there is \(\varepsilon {\gt}0\) such that \(f\) is constant on \(x-[0,\varepsilon )^s\): \(S\) is locally finite, so we may choose \(\varepsilon \) below every positive difference \(x_c-\sigma _c\) and \(x_c+1-\sigma _c\) for the finitely many \(\sigma \in S\) near the cube, and then shifting the cube by \(-t\), \(t\in [0,\varepsilon )^s\), neither adds nor removes a point. If \(f\equiv 1\), the cubes \(\sigma +(-1,0]^s\), \(\sigma \in S\), tile \(\mathbb {R}^s\), since \(x\in \sigma +(-1,0]^s\) if and only if \(\sigma \in x+[0,1)^s\). (i) Density gives a point of \(\mathbb {Z}^s+L\) in every \(x-[0,\varepsilon )^s\), so \(f\equiv 1\), and the cubes form a lattice tiling. By Hajós’s theorem (Minkowski’s conjecture) [ 22 ] two of them share a facet, so \(L\) contains some \(\mathbf{e}_c\). (ii) For each \(c\), \(\pi _c(L)+\mathbb {Z}\) is a finitely generated subgroup of \(\mathbb Q\) containing \(\mathbb {Z}\), hence equal to \(\frac1{e_c}\mathbb {Z}\) for an integer \(e_c\ge 1\). For \(x_c\in (\frac{j-1}{e_c},\frac j{e_c}]\) and \(\sigma \in L\) the condition \(x_c\le \sigma _c{\lt}x_c+1\) is equivalent to \(\frac j{e_c}\le \sigma _c\le \frac{j-1}{e_c}+1\), which does not depend on \(x_c\); so \(f\) is constant on every box \(\prod _c(\frac{j_c-1}{e_c},\frac{j_c}{e_c}]\), and its value there is that at the corner \((j_c/e_c)_c\). By hypothesis the corner lies in \(\mathbb {Z}^s+L\), so \(f\equiv 1\), and Hajós’s theorem applies as in (i). (iii) As in (i), \(f\equiv 1\) and the cubes \(\sigma +(-1,0]^s\) tile \(\mathbb {R}^s\). Keller’s conjecture holds for \(s\le 7\) (Perron [ 49 ] for \(s\le 6\), Brakensiek, Heule, Mackey and Narváez [ 1 ] for \(s=7\)): two cubes of the tiling share a complete facet, so their corners differ by some \(\mathbf{e}_c\). (iv) The differences are rational vectors. As \(S\) is a finite union of \(\Pi \)-cosets, \(\mu (S)\) is a minimum over the finitely many \(\Pi \)-orbits of pairs, so it is attained and \(\mu (S)^2\) is rational. A periodic set of density \(1\) with minimum \(\mu \) is a packing of balls of radius \(\mu /2\) with density \(\mathrm{vol}(B_{\mu /2})\), so \(\mu ^2\) is at most \(4\vartheta _s^{2/s}\) with \(\vartheta _s\) the optimal centre density; this is \(2/\sqrt3\) for \(s=2\) [ 9 , Ch. 1 ] and \(2^{1/3}\) for \(s=3\) [ 23 ] , both irrational. The four squared minima for \(4\le s\le 7\) are \(4\vartheta _s^{2/s}\) with the centre densities \(\frac18\), \(\frac1{8\sqrt2}\), \(\frac1{8\sqrt3}\), \(\frac1{16}\) [ 9 ] , and they are irrational.
The largest minimum of a periodic one-per-cube set is not known. In dimension three an exhaustive enumeration of the lattices of covolume \(1\) in \(\frac1e\mathbb {Z}^3\), \(e\le 11\), finds one-per-cube lattices with minimum up to \(\sqrt{29/25}=1.0770\ldots \) (computed), for instance the lattice with basis \(\tfrac 1{5}(3,-4,-2)\), \(\tfrac 1{10}(6,2,-9)\), \(\tfrac 1{2}(1,0,2)\). It has covolume \(1\); its Gram matrix \(100^{-1}\left(\begin{smallmatrix} 116 & 56 & -10 \\ 56 & 121 & -60 \\ -10 & -60 & 125 \end{smallmatrix}\right)\) is Minkowski-reduced, so its minimum is \(\sqrt{116/100}\); and a finite check over one period shows that every unit cube holds exactly one of its points. So the largest minimum lies between \(1.0770\) and \(2^{1/6}=1.1224\ldots \) [ 23 ] . The maximizers found have offsets that are not affine modulo \(1\) in the cell, so no digital net realizes them through its geometric digit (Corollary 99(c)); the best digital value at \(m=3\) in this paper is \(\sqrt{281}/16=1.0476\ldots \) (Proposition 107). For \(s\le 9\), restricting to lattices is not known to lose anything: lattices hold the packing records there and are optimal for \(s=3\), \(8\) [ 9 , 23 , 67 ] . The constraints visible here are the cube constraint (one point in every cube of side \(q^{-k}\), at \(m\equiv 0\pmod s\)), the linearity of the offsets and, in the frame orbit, Lemma 19. The skeleton regime (\(m\not\equiv 0\pmod s\)), whose cells are not cubes, is not bound by the cube constraint (Table 105).