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

DOI10.1006/JNTH.2002.2786MaRDI QIDQ1864844zbMATH OpenOpenAlexFDO

Authors Matthias Beck, Sinai Robins, Ricardo L. Diaz

Publication date 23 March 2003

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 437624 (Why is no real title available?)
• scientific article; zbMATH DE number 3176160 (Why is no real title available?)
• scientific article; zbMATH DE number 148667 (Why is no real title available?)
• scientific article; zbMATH DE number 681084 (Why is no real title available?)
• scientific article; zbMATH DE number 847806 (Why is no real title available?)
• scientific article; zbMATH DE number 3396015 (Why is no real title available?)
• A Linear Diophantine Problem
• Computing the Ehrhart polynomial of a convex lattice polytope
• Counting lattice points by means of the residue theorem
• Das Verhalten der Kleinschen Funktionen log(w1, w2) gegenüber Modultransformationen und verallgemeinerte Dedekindsche Summen.
• Generating functions and generalized Dedekind sums.
• Higher dimensional Dedekind sums
• Lattice translates of a polytope and the Frobenius problem
• Notes on generalized Dedekind sums
• On a linear Diophantine problem of Frobenius.
• On a linear Diophantine problem of Frobenius. II.
• On a linear diophantine problem of Frobenius
• On the linear diophantine problem of Frobenius
• On the linear diophantine problem of Frobenius.
• Points entiers dans les polyèdres convexes
• Polynomials Associated with Finite Gell-Complexes
• Residue formulae, vector partition functions and lattice points in rational polytopes
• Riemann-Roch for toric orbifolds
• Some remarks on certain generalized Dedekind sums
• Sur un probl?me de g?om?trie diophantienne lin?aire. I. Poly?dres et r?seaux.
• The Ehrhart polynomial of a lattice polytope
• The polynomial part of a restricted partition function related to the Frobenius problem
• Ü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
• A discrete Farkas lemma
• Some consequences of the polynomial Freiman-Ruzsa conjecture
• On a Diophantine equation
• 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
• Lattice translates of a polytope and the Frobenius problem
• The Hilbert series and \(a\)-invariant of circle invariants
• 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)