The Frobenius Problem, Rational Polytopes, and Fourier–Dedekind Sums
By Matthias Beck, Ricardo Diaz, Sinai Robins. 2002
90 citations recorded by the source corpus.
We study the number of lattice points in integer dilates of the rational polytope P={(x1,…,xn)∈R⩾0n:∑k=1nxkak⩽1}, where a1,…,an are positive integers. This polytope is closely related to the linear Diophantine problem of Frobenius: given relatively prime positive integers a1,…,an, find the largest value of t (the Frobenius number) such that m1a1+···+mnan=t has no solution in positive integers m1,…,mn. This is equivalent to the problem of finding the largest dilate tP such that the facet {∑k=1nxkak=t} contains no lattice point. We present two methods for computing the Ehrhart quasipolynomials L(P,t)≔#(tP∩Zn) and L(P°,t)≔#(tP°∩Zn). 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.
Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/3b885b69e4f5e651be81958ff422fe9d4b2b3df8
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algebra and Number Theory
In Geometry and Topology
Citations in the corpus
- An optimal lower bound for the Frobenius problem (2005, result): “by Erd¨os and Graham [5] gN ≤ 2aN ha 1 N i −a1 , by Selmer [19] gN ≤ 2aN−1 ha N N i −aN , 1 and by Vitek [21] gN ≤ (a2 − 1)(aN − 2) 2 − 1, as well as more recent results by Beck, Diaz, and Robins [2] gN ≤ 1 2 p a1a2a3(a1 +a2 +a3)−a1 − a2 −a3 , and by Fukshansky and Robins [7], who produced an upp”