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

DOI10.1006/JNTH.2002.2786zbMATH Open1038.11026arXivmath/0204035OpenAlexW1971718614MaRDI QIDQ1864844FDOQ1864844

Authors: Matthias Beck, Sinai Robins, Ricardo L. Diaz 

Publication date: 23 March 2003

Published in: Journal of Number Theory (Search for Journal in Brave)

Abstract: We study the number of lattice points in integer dilates of the rational polytope $P=(x_1,\mathrm{...},x_n)in{R}_{geq0}^n:su{m}_{k=1}^n{x}_k{a}_{k}leq1$, where $a_1,\mathrm{...},a_n$ are positive integers. This polytope is closely related to the linear Diophantine problem of Frobenius: given relatively prime positive integers $a_1,\mathrm{...},a_n$, find the largest value of t (the Frobenius number) such that $m_1{a}_1+\mathrm{...}+m_n{a}_n=t$ has no solution in positive integers $m_1,\mathrm{...},m_n$. This is equivalent to the problem of finding the largest dilate tP such that the facet $su{m}_{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.

Full work available at URL: https://arxiv.org/abs/math/0204035

Recommendations

• Arithmetic of higher dimensional Dedekind-Rademacher sums
• scientific article; zbMATH DE number 2156407
• Fourier-Dedekind sums and an extension of Rademacher reciprocity
• On reciprocity formulae for inhomogeneous and homogeneous Dedekind sums
• scientific article; zbMATH DE number 1014797

zbMATH Keywords

lattice pointsEhrhart quasipolynomialrational polytopesDedekind sums.linear Diophantine problem of Frobenius

Mathematics Subject Classification ID

Dedekind eta function, Dedekind sums (11F20) Lattice points in specified regions (11P21) Linear Diophantine equations (11D04)

Cites Work

• Title not available (Why is that?)
• Residue formulae, vector partition functions and lattice points in rational polytopes
• Points entiers dans les polyèdres convexes
• Das Verhalten der Kleinschen Funktionen log(w1, w2) gegenüber Modultransformationen und verallgemeinerte Dedekindsche Summen.
• On the linear diophantine problem of Frobenius
• A Linear Diophantine Problem
• Title not available (Why is that?)
• On the linear diophantine problem of Frobenius.
• Title not available (Why is that?)
• The Ehrhart polynomial of a lattice polytope
• Generating functions and generalized Dedekind sums.
• Title not available (Why is that?)
• Sur un probl?me de g?om?trie diophantienne lin?aire. I. Poly?dres et r?seaux.
• Higher dimensional Dedekind sums
• Lattice translates of a polytope and the Frobenius problem
• On a linear Diophantine problem of Frobenius.
• On a linear Diophantine problem of Frobenius. II.
• Title not available (Why is that?)
• Some remarks on certain generalized Dedekind sums
• Notes on generalized Dedekind sums
• Polynomials Associated with Finite Gell-Complexes
• Riemann-Roch for toric orbifolds
• Computing the Ehrhart polynomial of a convex lattice polytope
• The polynomial part of a restricted partition function related to the Frobenius problem
• Counting lattice points by means of the residue theorem
• On a linear diophantine problem of Frobenius
• Title not available (Why is that?)
• Über einige Anwendungen Dedekindscher Summen.

Cited In (27)

• Commutative algebra of generalised Frobenius numbers
• An optimal lower bound for the Frobenius problem
• Asymptotics for the partial fractions of the restricted partition generating function. I
• On a Diophantine equation
• A discrete Farkas lemma
• Some consequences of the polynomial Freiman-Ruzsa conjecture
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• The index of the spin\(^c\) Dirac operator on the weighted projective space and the reciprocity law of the Fourier-Dedekind sum
• Analogues of the Frobenius problem
• Modular factorization of superconformal indices
• On the GLY conjecture of upper estimate of positive integral points in real right-angled simplices
• Counting lattice points in certain rational polytopes and generalized Dedekind sums
• Euler-Maclaurin with remainder for a simple integral polytope
• Operational state complexity of unary NFAs with finite nondeterminism
• Refined upper bounds for the linear Diophantine problem of Frobenius
• Algebraic capacities
• The Hilbert series and \(a\)-invariant of circle invariants
• Lattice translates of a polytope and the Frobenius problem
• Spectral invariants, analysis of the Floer moduli space, and geometry of the Hamiltonian diffeomorphism group
• Frobenius problem and dead ends in integers
• Some identities and reciprocity relations of unipoly-Dedekind type DC sums
• Fourier-Dedekind sums and an extension of Rademacher reciprocity
• Ehrhart theory of polytopes and Seiberg-Witten invariants of plumbed 3-manifolds
• Exact evaluations and reciprocity theorems for finite trigonometric sums
• Exact Euler-Maclaurin formulas for simple lattice polytopes
• An algebraic approach to \(q\)-partial fractions and Sylvester denumerants
• Partitions and Sylvester waves

This page was built for publication: The Frobenius problem, rational polytopes, and Fourier-Dedekind sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1864844)