The Frobenius problem, rational polytopes, and Fourier-Dedekind Sums

Abstract

We study the number of lattice points in integer dilates of the rational polytope $P=(x_1,...,x_n)\in {\mathbb{R}}_{\ge 0}^n:{\sum }_{k=1}^n{x}_k{a}_k\le 1$, where $a_1,...,a_n$ are positive integers. This polytope is closely related to the linear Diophantine problem of Frobenius: given relatively prime positive integers $a_1,...,a_n$, find the largest value of t (the Frobenius number) such that $m_1{a}_1+...+m_n{a}_n=t$ has no solution in positive integers $m_1,...,m_n$. This is equivalent to the problem of finding the largest dilate tP such that the facet ${\sum }_{k=1}^n{x}_k{a}_k=t$ contains no lattice point. We present two methods for computing the Ehrhart quasipolynomials of P which count the integer points in the dilated polytope and its interior. Within the computations a Dedekind-like finite Fourier sum appears. We obtain a reciprocity law for these sums, generalizing a theorem of Gessel. As a corollary of our formulas, we rederive the reciprocity law for Zagier's higher-dimensional Dedekind sums. Finally, we find bounds for the Fourier-Dedekind sums and use them to give new bounds for the Frobenius number.

Added journal reference