10
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I don't know what you mean by "the basis-and-origin simplex". $\endgroup$ May 8, 2013 at 6:12
  • $\begingroup$ In two dimensions the "basis and origin triangle" is $\{(0,0), (1,0), (0,1)\}$. $\endgroup$
    – Ben Barber
    May 8, 2013 at 7:21
  • 2
    $\begingroup$ 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. $\endgroup$ May 8, 2013 at 8:34
  • $\begingroup$ @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. $\endgroup$ May 8, 2013 at 13:46
  • $\begingroup$ @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? $\endgroup$
    – Lee Mosher
    May 8, 2013 at 14:12

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ OK, I think I believe you, but let me check this... $\endgroup$ May 9, 2013 at 1:44
  • $\begingroup$ I also want to say that this really is quite beautiful. Thanks! $\endgroup$ 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$ May 9, 2013 at 12:06
2
$\begingroup$

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

$\endgroup$
3
  • $\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$ 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$ 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$ May 9, 2013 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.