Computing the Period of an Ehrhart Quasi-Polynomial

Abstract

If $P\subset {\Bbb R}^d$ is a rational polytope, then $i_P(t):=\#(tP\cap {\Bbb Z}^d)$ is a quasi-polynomial in $t$, called the Ehrhart quasi-polynomial of $P$. A period of $i_P(t)$ is ${\cal D}(P)$, the smallest ${\cal D}\in {\Bbb Z}_+$ such that ${\cal D}\cdot P$ has integral vertices. Often, ${\cal D}(P)$ is the minimum period of $i_P(t)$, but, in several interesting examples, the minimum period is smaller. We prove that, for fixed $d$, there is a polynomial time algorithm which, given a rational polytope $P\subset{\Bbb R}^d$ and an integer $n$, decides whether $n$ is a period of $i_P(t)$. In particular, there is a polynomial time algorithm to decide whether $i_P(t)$ is a polynomial. We conjecture that, for fixed $d$, there is a polynomial time algorithm to compute the minimum period of $i_P(t)$. The tools we use are rational generating functions.