Refined upper bounds for the linear Diophantine problem of Frobenius

2003/05/31 by Matthias Beck, Shelemyahu Zacks
Mathematics · #math.NT #math.CO #msc:11D04 #msc:05A15 #msc:11Y16

paper · pdf

published as Adv. Appl. Math. 32, no. 3 (2004), 454-467 · 12 pages, 5 figures

arxiv created 2005/01/02 · arxiv updated 2009/11/30

Abstract

We study the Frobenius problem: given relatively prime positive integers a₁,...,a_d, find the largest value of t (the Frobenius number g(a₁,...,a_d)) such that m₁ a₁ + ... m_d a_d = t has no solution in nonnegative integers m₁,...,m_d. We introduce a method to compute upper bounds for g(a₁,a₂,a₃), which seem to grow considerably slower than previously known bounds. Our computations are based on a formula for the restricted partition function, which involves Dedekind-Rademacher sums, and the reciprocity law for these sums.

Related

• Some experimental results on the Frobenius problem
• Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number
• Considering a Classical Upper Bound on the Frobenius Number
• The generalized Frobenius problem via restricted partition functions
• An Optimal Lower Bound for the Frobenius Problem