On the number of integer points in translated and expanded polyhedra

Abstract

We prove that the problem of minimizing the number of integer points inparallel translations of a rational convex polytope in ${\mathbb{R}}^6$ is NP-hard. We apply this result to show that given a rational convex polytope $P\subset {\mathbb{R}}^6$, finding the largest integer $t$ s.t. the expansion $tP$ contains fewer than $k$ integer points is also NP-hard. We conclude that the Ehrhart quasi-polynomials of rational polytopes can have arbitrary fluctuations.