# Proving non-convexity of a set of lattice points

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!

-
the procedure I suggest does not enumerate points, it only counts them. –  Dima Pasechnik Aug 3 '13 at 16:06

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

-
Hi (and thanks) -- I was afraid of that answer. Actually, how does one go about actually obtaining a description of the convex hull of S? –  simpleperson Aug 3 '13 at 12:48
Two primary options for computing hulls in higher dimensions are Qhull and CGAL. Both require considerable study before you can use them. –  Joseph O'Rourke Aug 3 '13 at 13:03
@Joseph O'Rourke -- I looked a little at CGAL's manual which gave an idea. I want to take any two points x and y of S and show that any lattice point on the line xy is in S. This is a horrid, worse than |S| choose 2 algorithm but might be a quick enough (albeit dirty) way to just check (non)convexity. Is there any problem with that? –  simpleperson Aug 3 '13 at 13:53
one can use Sage to compute the convex hull. It can even be done online, without installing Sage on a local machine, using e.g. cloud.sagemath.org –  Dima Pasechnik Aug 3 '13 at 16:20
e.g. here is a toy example using Sage: l=LatticePolytope([[2,0],[0,2],[1,1]],compute_vertices=True); l; l.npoints() it will output A lattice polytope: 1-dimensional, 2 vertices. 3 –  Dima Pasechnik Aug 3 '13 at 16:34

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$":

-
You're right of course. Thank you. –  simpleperson Aug 3 '13 at 14:27