# Discrete disjoint covering of integer lattices

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.

-
I don't know what you mean by "the basis-and-origin simplex". –  Gerry Myerson May 8 '13 at 6:12
In two dimensions the "basis and origin triangle" is $\{(0,0), (1,0), (0,1)\}$. –  Ben Barber May 8 '13 at 7:21
I did something related in $\mathbb R^d$ and found a family of tilings there (see <a href="mathoverflow.net/questions/77952/… question</a>). It turned out that the tilings had been previously studied under the name <i>notched cube tilings</i>. It's quite plausible that some version of Stein's ideas can be applied in your situation. –  Anthony Quas May 8 '13 at 8:34
@Gerry, Ben has it right; I should have said "minimal $n$-simplex", because they're all $SL_n$-the same... in fact, I think I will. –  some guy on the street May 8 '13 at 13:46
@Some guy: This change, from "basis-and-origin simplex" to "minimal integer simplex", changes the mathematical content of your question and confuses the issue. For example, {(0,0),(34,21),(21,13)} is a "minimal integer" simplex, but it is not a translate of the basis-and-origin simplex. Was that your intent? –  Lee Mosher May 8 '13 at 14:12

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$).

-
OK, I think I believe you, but let me check this... –  some guy on the street May 9 '13 at 1:44
I also want to say that this really is quite beautiful. Thanks! –  some guy on the street May 9 '13 at 1:50
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. –  some guy on the street May 9 '13 at 12:06

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}.$$

-
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? – some guy on the street May 9 '13 at 15:34 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$. – Richard Stanley May 9 '13 at 17:29 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! –  some guy on the street May 9 '13 at 18:26