Listing lattice points in a simplex - MathOverflow

Listing lattice points in a simplex

2011-03-08T04:34:23Z

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!

Answer by Gerry Myerson for Listing lattice points in a simplex

2011-03-08T06:13:51Z

The Reeve tetrahedron http://en.wikipedia.org/wiki/Reeve_tetrahedron shows that there are solids with lattice point corners with arbitrarily great volume and no interior lattice points; the convex hull of $(0, 0, 0)$, $(1, 0, 0)$, $(0, 1, 0)$, and $(1, 1, r)$, where $r$ is a positive integer.

Answer by Steve Huntsman for Listing lattice points in a simplex

2011-03-08T06:18:17Z

Unless I have missed a more recent reference, the state of the art for the computational complexity of problems such as this is detailed in Barvinok, A. "The complexity of generating functions for integer points in polyhedra and beyond". Proc. ICM 2006, v. III (PDF).

Answer by Noam D. Elkies for Listing lattice points in a simplex

2011-07-13T07:20:02Z

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.