Proving non-convexity of a set of lattice points

Question

I have a set of lattice points S in R^n (listed in memory in a computer for n=8 say). I want to computationally certify that they do not form the lattice points of a convex polytope P in R^n. (Ex. S={-1,1} in R^1.) Is there an easy (and hopefully efficient enough) way to do this?

Remarks:

• I don't have much feel for the (many) points themselves at the moment. For instance, I don't know what are vertices of the convex hull of S (or how to find that).

• Assuming I could find a description of the convex hull, I get scared about a solution that says "now figure out what the lattice points are and compare with S", because of efficiency concerns.

Thank you!

Answer 1

You can compute the convex hull $P$ of these points, and then apply, say, Barvinok's algorithm for counting $|P\cap\mathbb{Z}^n|$. Comparing the latter with $|S|$ would give you the needed certificate. Although $n=8$ might be a bit too high for an existing implementation (e.g. LattE) to handle.

Another trick might be to compute the volume of $P$ - it will give you some bound on the number of integer vectors in $P$.

On can use Sage to compute the convex hull etc (note that it does not do integer points count efficiently, though). Here is a toy example:

l=LatticePolytope([[2,0],[0,2],[1,1]],compute_vertices=True); l; l.npoints()

A lattice polytope: 1-dimensional, 2 vertices.

3

Answer 2

To respond to your suggestion in your comment to Dima's answer: This set $S$ of four points in $\mathbb{Z}^2$ does "not form the lattice points of a convex polytope," and yet, for "any two points $x$ and $y$ of $S$," every "lattice point on the line [segment] $xy$ is in $S$":