The Frobenius Problem, Rational Polytopes, and Fourier–Dedekind Sums
✍ Scribed by Matthias Beck; Ricardo Diaz; Sinai Robins
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 195 KB
- Volume
- 96
- Category
- Article
- ISSN
- 0022-314X
No coin nor oath required. For personal study only.
✦ Synopsis
We study the number of lattice points in integer dilates of the rational polytope
x k a k 41 ( )
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
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 f P n k¼1 x k a k ¼ tg contains no lattice point. We present two methods for computing the Ehrhart quasipolynomials Lð % P P; tÞ :¼ #ðtP \ Z n Þ and LðP8; tÞ :¼ #ðtP8 \ Z n Þ: 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.