Computing the period of an Ehrhart quasi-polynomial (Q2571277)

For an \(m\)-dimensional convex polytope \(P\) in \({\mathbf R}^d\) with rational vertices, the integer-point counting function \(L_P(t) := \# ( tP \cap {\mathbf Z}^d )\) is a quasi-polynomial in the positive integer variable \(t\), by Ehrhart's fundamental theorem [\textit{E. Ehrhart}, C. R. Acad. Sci., Paris 254, 616--618 (1962; Zbl 0100.27601)]. A quasi-polynomial is a function \(Q\) defined on the integers for which there exists a positive integer \(p\) such that for each \(0 \leq m < p\), \(Q(m+np)\) is a polynomial in \(n\). Any such \(p\) is a period of the quasi-polynomial. The main theorem in the article states that in fixed dimension \(d\), one can decide in polynomial time if a given positive integer is a period of the Ehrhart quasi-polynomial \(L_P\) of a given rational polytope \(P\). It also gives a corollary that there is a polynomial-time reduction of finding the minimum such period to the problem of factoring a positive integer.