8
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I am not sure what you mean by $| \Delta \cap \mathbb{Z}^n | = O(\vol(\Delta)).$ There are certainly simplices of volume zero which contain (infinitely) many lattice points (and the hyperplanes defining them do not need many bits to define). $\endgroup$
    – Igor Rivin
    Commented Mar 8, 2011 at 4:44
  • $\begingroup$ To expand on Igor's comment, I think it makes sense to look for an output-sensitive bound, like Theta(N), where N is the number of lattice points in your simplex. (Obviously, you can't beat that.) $\endgroup$
    – Darsh Ranjan
    Commented Mar 8, 2011 at 5:15
  • $\begingroup$ Igor, simplices of volume zero with lattice point vertices? $\endgroup$
    – Gerry Myerson
    Commented Mar 8, 2011 at 6:07
  • $\begingroup$ Igor, by definition an $(n+1)$-simplex in $\mathbf{R}^n$ is required to have the $\mathbf{R}$ span of $v_0,\dots,v_n$ equal to $\mathbf{R}^n$, so in particular $\mathrm{vol}(\Delta)>0$. If not, I will add this hypothesis. Is then there still a counterexample? JV $\endgroup$
    – John Voight
    Commented Mar 8, 2011 at 16:30
  • $\begingroup$ It is enough to have a good algorithm in the case where the boundary of the simplex intersects the integer lattice $\mathbb Z^n$ only in its vertices since one can cut it into a union of smaller simplices otherwise. $\endgroup$
    – Roland Bacher
    Commented Jun 1, 2011 at 6:29

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ $|\Delta \cap {\bf Z^n}| = n! {\rm Vol}(\Delta) + n$ holds also if $\Delta$ is in the ${\rm GL}_n({\bf Z})$ orbit of the simplex with $v_i = a_i e_i$ where $e_i$ is the $i$-th unit vector and $a_i=1$ for all $i$ except $i=1$, or except $a_1=a_2=2$. $\endgroup$
    – Noam D. Elkies
    Commented Jul 13, 2011 at 16:49
  • $\begingroup$ To make this work for a general polytope, one can modify the proof of Lagarias and Ziegler ("Bound for lattice polytopes containing a fixed number of interior points in a sublattice", Can. J. Math. 43 (1991), 1022-1035) to show that any polytope is $GL_n(\mathbb{Z})$-equivalent to a polytope contained in a lattice orthotope (box) with side lengths $b_1,\dots,b_n$ satisfying $b_1\cdots b_n\leq n^nv$ where $v$ is the normalized (integral) volume. It follows that the number of lattice points in a polytope is at most $(2n)^n v$; probably one can do better, but not better than $O(v)$ for fixed $n$. $\endgroup$
    – John Voight
    Commented Jul 15, 2011 at 1:01
  • $\begingroup$ Fantastic explanation! I love knowing how to do this now. A small consolation is that one doesn't need to compute all n ai's for every candidate: for a given candidate, just compute the ai's one by one and stop when the sum exceeds 1, which happens immediately for the vast majority of candidates. That speeds the whole thing up by a factor of n. $\endgroup$
    – Don Hatch
    Commented Oct 19, 2013 at 15:29
  • $\begingroup$ Recently needed to do this with n=7, vol=24 million so approx 24 million points. Unfortunately there's 7!=5040 times that many in the parallelotope: that's 125 billion candidates to sift through. The previously mentioned "small consolation" of computing ai's one by one sped it up by a factor of 7, so it took 7 hours instead of 2 days. Sure would love to know how to systematically run through reps in just the simplex rather than the whole parallelotope, which would make it take 5 seconds instead of 7 hours! $\endgroup$
    – Don Hatch
    Commented Oct 19, 2013 at 15:33
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, but how does Barvinok's short generating functions allow you to actually enumerate the lattice points? Multiplying these functions out may explode the complexity. And every reference I found says "polynomial time", which is problematic for me for two reasons: (1) the analysis does not take into account the time in arithmetic in the integers, and (2) there is no precise degree bound on the polynomial time (as asked above, what is $t$?). JV $\endgroup$
    – John Voight
    Commented Mar 8, 2011 at 16:33
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sure! But I do not require the volume to be bounded above in terms of the number of interior lattice points--rather the other way around. (This example already appears in $\mathrm{R}^2$: there are triangles of arbitrarily large area with no interior lattice points.) JV $\endgroup$
    – John Voight
    Commented Mar 8, 2011 at 17:06
  • $\begingroup$ I think I see now how to get a bound in the other direction, at least crudely. There is a result of Lagarias and Ziegler which says that any polytope of usual volume $V$ (so $[0,1]^n$ has volume $1$) is integrally equivalent under $\mathrm{GL}_n(\mathbf{Z})$ to a polytope contained in a lattice cube of side length at most $n(n!V)=n\mathrm{vol}(\Delta)$. So $|\Delta \cap \mathbf{Z}^n| = O( \mathrm{vol}(\Delta)^n)$. But surely one can do better. JV $\endgroup$
    – John Voight
    Commented Mar 8, 2011 at 17:10
  • $\begingroup$ Those triangles with large area and no interior lattice points have lots of lattice points on the boundary (Pick's Theorem); the Reeve tetrahedra have only the four lattice points on the boundary. $\endgroup$
    – Gerry Myerson
    Commented Mar 8, 2011 at 22:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .