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

Simple item page
dc.creatorBeck, Matthias
dc.creatorDiaz, Ricardo
dc.creatorRobins, Sinai
dc.date2002-04-02
dc.date2003-05-28
dc.date.accessioned2026-07-07T04:47:24Z
dc.date.available2026-07-07T04:47:24Z
dc.descriptionWe study the number of lattice points in integer dilates of the rational polytope $P = (x_1,...,x_n) \in \R_{\geq 0}^n : \sum_{k=1}^n x_k a_k \leq 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.
dc.descriptionAdded journal reference
dc.identifierhttps://arxiv.org/abs/math/0204035
dc.identifierhttp://arxiv.org/abs/math/0204035
dc.identifierJournal of Number Theory 96 (2002), 1--21
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/63703
dc.subjectNumber Theory
dc.subjectCombinatorics
dc.subject11D04, 05A15, 11H06
dc.titleThe Frobenius problem, rational polytopes, and Fourier-Dedekind Sums
dc.typetext

Files

Collections

arXiv