Let $n \in \mathbf{Z}\_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v\_0,\dots,v\_n \in \mathbf{Z}^n$, computes the set $\Delta \cap \mathbf{Z}^n$ in time $O(\delta^t\mathrm{vol}(\Delta))$ for some explicit $t \in \mathbf{R}$, where $\delta=\max\_{i,j} \log|v\_{ij}|$ is the input size and $\mathrm{vol}(\Delta)$ is the (normalized) volume of $\Delta$? 


Note here that the dimension is fixed. Implicit in this question is that $|\Delta \cap \mathbf{Z}^n|=O(\mathrm{vol}(\Delta))$, which I haven't been able to extract yet from the literature.


This question arises for me after trying to ask the same thing for a polytope $P \subset \mathbf{Z}^n$; the natural way to do this seems to be by computing a triangulation (or do people say tetrahedralization?), such as the Delaunay triangulation, which reduces the problem from $P$ to a bunch of $\Delta$s. 


(And in fact, really what I need is to compute $d\Delta \cap \mathbf{Z}^n$ for $d=O(n)$, but $n$ is constant for now so this doesn't seem to help.)


People often just want to count the set $\Delta \cap \mathbf{Z}^n$ (use short rational generating functions) or to know that it is nonempty (reduces to an integer program), but I need to actually list every lattice point. 


Translating by $v\_0$ we may assume $v\_0=0$ is a vertex, and then we want to compute the set of points $x=a\_1v\_1+\dots+a\_n v\_n$ such that $a\_i \geq 0$ for all $i$ and $a\_1+\dots+a\_n \leq 1$. This should be doable by considering representatives for $\mathbf{Z}^n/\sum \mathbf{Z} v\_i$ via a Hermite normal form, but this gives generators for the whole parallelopiped (wasteful, but perhaps not noticeably so in fixed dimension)? If this makes sense, is there a clean algorithm with a rigorous analysis of the running time (counting the time for integer arithmetic)?


Thanks very much for your help!



Listing lattice points in a simplex
Hermite normal form (HNF) should work much as you suggest.


Translate $v\_0$ to 0. Let $L = \bigoplus\_{i=1}^n {\bf Z} v\_i$. HNF gives an explicit decomposition of $G := {\bf Z}^n / L$ as a direct sum of cyclic groups. Both the computation and the resulting generators take time polynomial in the input size. This lets you run through representatives of the $|G|$ cosets of $L$ in ${\bf Z}^n$. Write each one uniquely as $\sum\_{i=1}^n a\_i v\_i$ for some rational $a\_i \in {\bf Q}$. Replacing each $a\_i$ by its fractional part $\{ a\_i \} = a\_i - \lfloor a\_i \rfloor$ gives the only candidate for the intersection of the coset with $\Delta$, which works iff $\sum\_i \{ a\_i \} \leq 1$. (Exception: the trivial coset has $n+1$ representatives, but you already know them: $0$ and the $v\_i$.) The processing time per coset is again polynomial in the input size, and the number of cosets is $|G| = n! {\rm Vol}(\Delta)$; since for you $n$ is fixed, this answers your question.


Along the way we've obtained $|\Delta \cap {\bf Z}^n| \leq n! {\rm Vol}(\Delta) + n$, giving (again for fixed $n$) the result you "haven't been able to extract yet from the literature", with explicit constants. Equality holds at least when $n! |\Delta| = 1$.


I haven't yet given or cited a proof that HNF can in fact be computed in time polynomial in input size. This seems clear, though the first thing one might try may produce an algorithm that's too slow in practice. A brief Google search indicates that (not surprisingly) there has been considerable work on this question; one article that turns up often is "Asymptotically Fast Computation of the Hermite Normal Form of an Integer Matrix" by
Arne Storjohann and George Labahn (1996), which gives bounds whose dependence on $n$ is polynomial as well (in particular the exponent does not depend on $n$). There's also an HNF implementation in **gp** with several variations, see **mathnf** — that's MATrix HNF, not MATH something :-) — and probably other packages do this too. You might also try Smith normal form (**matsnf**), which seems to do much the same thing for this purpose.


