betaFeedback

WorksMathematics

A Sharp Upper Bound for the Frobenius Number

Abstract

Let 0<a1<⋯<an0<a_1<\cdots<a_n be integers with n≥2n\ge 2 and gcd⁡(a1,…,an)=1\gcd(a_1,\ldots,a_n)=1. Their Frobenius number F(a1,…,an)F(a_1,\ldots,a_n) is the largest integer that cannot be expressed as a nonnegative integer combination of a1,…,ana_1,\ldots,a_n. Erdős and Graham proved the classical bound F(a1,…,an)≤2an−1⌊an/n⌋−anF(a_1,\ldots,a_n)\le 2a_{n-1}\lfloor a_n/n\rfloor-a_n, which depends on the two largest generators. Dixmier subsequently proved their conjecture F(a1,…,an)≤an2/(n−1)F(a_1,\ldots,a_n)\le a_n^2/(n-1), a bound depending only on ana_n and nn that removes the factor 22 from the corresponding quadratic estimate. Following the Erdős–Graham approach, we remove the factor 22 while retaining the dependence on an−1a_{n-1}, and prove F(a1,…,an)≤an−1⌈an/(n−1)⌉−an−1F(a_1,\ldots,a_n)\le a_{n-1}\lceil a_n/(n-1)\rceil-a_n-1. This bound can be substantially smaller than Dixmier's when an−1a_{n-1} is small relative to ana_n. For every n≥3n\ge3, we also construct infinitely many instances satisfying the reverse inequality, which shows that the bound is sharp.

Paper details

vlnc:W_rvcwq36d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…