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

We study the number of lattice points in integer dilates of the rational polytope [GRAPHICS] 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 This is equivalent to the problem of finding the largest dilate tP such that the facet {Sigma(k=1)(n) x(k)a(k) = t} contains no lattice point. We present two methods for computing the Ehrhart quasipolynomials L((P) over bar, t) := #(tP boolean AND Z") and L(Pdegrees, t) := #(tPdegrees boolean AND Z"). 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. (C) 2002 Elsevier Science (USA).