A Sharp Upper Bound for the Frobenius Number
Abstract
Let 0<a1<⋯<an be integers with n≥ 2 and gcd(a1,…,an)=1. Their Frobenius number F(a1,…,an) is the largest integer that cannot be expressed as a nonnegative integer combination of a1,…,an. Erdős and Graham proved the classical bound F(a1,…,an)≤ 2an−1⌊ an/n⌋−an, which depends on the two largest generators. Dixmier subsequently proved their conjecture F(a1,…,an)≤ an2/(n−1), a bound depending only on an and n that removes the factor $2$ from the corresponding quadratic estimate. Following the Erdős--Graham approach, we remove the factor $2$ while retaining the dependence on an−1, and prove F(a1,…,an)≤ an−1⌈ an/(n−1)⌉−an−1. This bound can be substantially smaller than Dixmier's when an−1 is small relative to an. For every n≥3, we also construct infinitely many instances satisfying the reverse inequality, which shows that the bound is sharp.
Related
- A sharp upper bound on the number of spanning forests of regular graphs
- A double-logarithmic upper bound on the chromatic number of the associahedron
- An upper bound of 61 for the Ramsey number $R(3,3,3,3)$
- The Tight Upper Bound on the Number of Distinct Squares in Circular Words
- A sharp almost sure upper bound for partial sums of random multiplicative functions
BibTeX
@misc{chen2026sharp,
title = {{A Sharp Upper Bound for the Frobenius Number}},
author = {Lin Chen and Tingwei Hu and Yuchen Mao and Guochuan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32219},
eprint = {2610.32219},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32219},
}
RIS
TY - UNPB
TI - A Sharp Upper Bound for the Frobenius Number
AU - Lin Chen
AU - Tingwei Hu
AU - Yuchen Mao
AU - Guochuan Zhang
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32219
UR - https://arxiv.org/abs/2610.32219
AB - Let 0<a_1<⋯<a_n be integers with n≥ 2 and gcd(a_1,…,a_n)=1. Their Frobenius number F(a_1,…,a_n) is the largest integer that cannot be expressed as a nonnegative integer combination of a_1,…,a_n. Erdős and Graham proved the classical bound F(a_1,…,a_n)≤ 2a_n−1⌊ a_n/n⌋−a_n, which depends on the two largest generators. Dixmier subsequently proved their conjecture F(a_1,…,a_n)≤ a_n^2/(n−1), a bound depending only on a_n and n that removes the factor $2$ from the corresponding quadratic estimate. Following the Erdős--Graham approach, we remove the factor $2$ while retaining the dependence on a_n−1, and prove F(a_1,…,a_n)≤ a_n−1⌈ a_n/(n−1)⌉−a_n−1. This bound can be substantially smaller than Dixmier's when a_n−1 is small relative to a_n. For every n≥3, we also construct infinitely many instances satisfying the reverse inequality, which shows that the bound is sharp.
ER -