Is there a covering of $\mathbb{Z}^n$ by disjoint translates of the basis-and-origin minimal integer $n$-simplex? By haphazard I have such coverings for $\mathbb{Z}$, $\mathbb{Z}^2$ and $\mathbb{Z}^3$, where the wanted translations are lattices spanned by $\{2\}$, $\{(2,-1),(-1,2)\}$, and $\{(1,1,-1),(1,-1,1),(-1,1,1)\}$, but rhyme nor reason can I see in this sequence of families to extend.
$\begingroup$
$\endgroup$
7
asked May 7, 2013 at 16:20
2 Answers
$\begingroup$
$\endgroup$
3
Let $S$ be the set of integer points $(x_1,x_2,\dots,x_n)$ satisfying
$$x_1+2x_2+3x_3+\dots+nx_n \equiv 0 \mod n+1,$$
and $T$ be the basis-and-origin simplex as described in Ben's comment.
Then translates of $T$ by $S$ disjointly cover $\mathbb{Z}^n$ (since decreasing the $x_i$ coordinate by $1$ changes the left hand side of the above relation by $i$, for any point not in $S$ there's exactly one direction we can move in to reach $S$).
answered May 8, 2013 at 19:11
-
$\begingroup$ OK, I think I believe you, but let me check this... $\endgroup$ Commented May 9, 2013 at 1:44
-
$\begingroup$ I also want to say that this really is quite beautiful. Thanks! $\endgroup$ Commented May 9, 2013 at 1:50
-
$\begingroup$ And it turns out that the Cartan matrix for $A_n$ is always a solution; this explains the bases already in the $n=1,2$ case; the haphazard found base for $n=3$ I suspect has the noncyclic group of order $4$ as quotient. $\endgroup$ Commented May 9, 2013 at 12:06
$\begingroup$
$\endgroup$
3
For fixed dimension $n$ there is an algorithm to find all such lattice tilings. Namely, let $S_n$ be the set of all $n\times n$ matrices $A$ of determinant $n+1$ that are in Hermite normal form over $\mathbb{Z}$. If the columns of $A$ are $v_1,\dots,v_n$, then there are $n$ nonzero integer column vectors $u_1,\dots,u_n$ for which there exist $0\leq a_i<1$ satisfying $\sum a_i v_i=u_i$. If the determinant of the matrix $M$ with columns $u_i$ is $\pm 1$, then the translates by the lattice generated by $v_1,\dots,v_n$ of the origin and the vectors $u_i$ gives a tiling of $\mathbb{Z}^n$. By a unimodular integral change of basis we can convert the $u_i$'s to the unit coordinate vectors. This construction gives all the desired lattice tilings, and is easy to implement algorithmically. For $n=4$ there are exactly two Hermite normal forms such that $\det M=\pm 1$, namely, $$ \begin{bmatrix} 1 & 0 & 0 & 2\\\ 0 & 1 & 0 & 3\\\ 0 & 0 & 1 & 4\\\ 0 & 0 & 0 & 5\end{bmatrix}, \qquad \begin{bmatrix} 1 & 0 & 0 & 1\\\ 0 & 1 & 0 & 0\\\ 0 & 0 & 1 & 1\\\ 0 & 0 & 0 & 5\end{bmatrix}. $$
answered May 9, 2013 at 14:53
-
$\begingroup$ could you explain the "$\Sigma a_i v_i=u_i"? I can see that there are finitely many HNFs to check, and that they're enough... are we basically trying to see if the cube spanned by an HNF contains enough independent integer points? $\endgroup$ Commented May 9, 2013 at 15:34
-
$\begingroup$ For any $n\times n$ integer matrix $M$ with determinant $d\neq 0$ and columns $v_1,\dots,v_n$, there are exactly $|d|-1$ nonzero integer vectors $u_1,\dots,u_{d-1}$ of the form $u_i=\sum a_i v_i$, where $0\leq a_i<1$. The point here is that these nonzero $u_i$'s should form a basis for the lattice $\mathbb{Z}^n$. $\endgroup$ Commented May 9, 2013 at 17:29
-
$\begingroup$ I think that's what I was trying to say... but I'd have quibbled $\Sigma a_{ij} v_j$; and now I'm convinced that there are always exactly $n$ such $[a_{i\dot}]$; and so the interest is in how might this fail to give a basis for $\mathbb{Z}^n$... I'm now convinced this gives a list of all solutions in every case; I still like that Kevin's answer gives a specific solution in all dimensions, which is closer to what I was wondering about, but this is really nifty! $\endgroup$ Commented May 9, 2013 at 18:26
$\{(0,0), (1,0), (0,1)\}$. $\endgroup$