# existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to check existence of a lattice point inside this polytope. I realize that this is not a very precise request but any kind of input would be nice. I'm not sure if it matters but $A$ is a sparse matrix.

• What precisely do you mean by the expression $Ax \leq b$? Jul 21, 2013 at 13:02
• This is integer programming (feasibility); NP-hard in general. See en.wikipedia.org/wiki/Integer_programming Jul 21, 2013 at 13:41
• I doubt this would help (because computing the volume is difficult), but you may be interested in Minkowski's lattice-point theorem, which infers the existence of a lattice point from the volume. Jul 21, 2013 at 14:24
• Note that while the general problem is hard, it is often easy to solve specific instances, so if you tell us more about your problem, you might get more useful info. Jul 21, 2013 at 16:52
• Without the symmetry requirement, a convex polytope can have arbitrarily large volume and no lattice point. Jul 21, 2013 at 23:44