Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number

2025

Read Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08560.txt.

Introduction

Aled Williams studies the classic Frobenius problem in number theory. Given a set of whole numbers with no shared factor, some totals can be built from them and some cannot. The Frobenius number is the largest total that cannot be built. Many upper bounds for that number exist, and the study asks how tight each bound is.

Williams weighs the bounds with both proofs and random computer trials. The tests show how close each bound comes to the true value in practice. He then asks whether a bound with growth slower than quadratic could hold in all cases. He proves that no such gain is possible. The result sets a hard limit on how much future bounds can improve.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08560

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number Abstract In this paper we study the (classical) Frobenius problem, namely the problem of finding the largest integer that cannot be represented as a nonnegative integral combination of given relatively prime (strictly) positive integers (known as the Frobenius number). We firstly compare several upper bounds on the Frobenius number, assessing their relative tightness through both theoretical arguments and Monte Carlo simulations. We then explore whether a general upper bound with a worst-case exponent strictly less than quadratic can exist, and formally demonstrate that such an improvement is impossible. These findings offer new insights into the structural properties of established bounds and underscore inherent constraints for future refinement. Keywords : Frobenius problem, Frobenius number, Diophantine equations, knapsack problems, knapsack polytopes, integer programming. Aled Williams Department of Mathematics London School of Economics and Political Science London, UK [email protected] 1 Introduction Let \boldsymbol{a} be a positive integral n -dimensional primitive vector, i.e. \boldsymbol{a}=(a_{1},\ldots,a_{n})^{T}\in\mathbb{Z}^{n}_{>0} with \gcd(\boldsymbol{a}):=\gcd(a_{1},\ldots,a_{n})=1 . In what follows, we exclude the case n=1 and assume that the dimension n\geq 2 . In particular, without loss of generality, we assume the following conditions: \boldsymbol{a}=(a_{1},\ldots,a_{n})^{T}\in\mathbb{Z}^{n}_{>0}\,,n\geq 2\text{ and }\gcd(\boldsymbol{a}):=\gcd(a_{1},\ldots,a_{n})=1. (1) The Frobenius number of \boldsymbol{a} , denoted by F(\boldsymbol{a}) , is the largest integer that cannot be represented as a nonnegative integral combination of the a_{i} ’s, i.e. F(\boldsymbol{a}):=\max\left\{b\in\mathbb{Z}:b\neq\boldsymbol{a}^{T}\boldsymbol{z}\text{ for all }\boldsymbol{z}\in\mathbb{Z}^{n}_{\geq 0}\right\}, where \boldsymbol{a}^{T} denotes the transpose of \boldsymbol{a} . Note for completeness that the Frobenius problem, namely the problem of finding the Frobenius number F(\boldsymbol{a}) given \boldsymbol{a} , is also known by other names within the literature including the money-changing problem (or the money-changing problem of Frobenius, or the coin-exchange problem of Frobenius) [ 19 , 17 , 3 ] , the coin problem (or the Frobenius coin problem) [ 4 , 15 ] and the Diophantine problem of Frobenius [ 14 , 13 ] . From a geometric viewpoint, F(\boldsymbol{a}) is the maximal right-hand side such that the knapsack polytope P(\boldsymbol{a},b)=\left\{\boldsymbol{x}\in\mathbb{R}^{n}_{\geq 0}:\boldsymbol{a}^{T}\boldsymbol{x}=b\right\} does not contain integral points. It should be noted that ( 1 ) are indeed necessary and sufficient conditions for the existence of the Frobenius number. Note that instead of the conditions ( 1 ), some authors instead assume the stronger condition that all the entries of the vector are pairwise coprime, i.e. \boldsymbol{a}=(a_{1},\ldots,a_{n})^{T}\in\mathbb{Z}^{n}_{>0}\,,n\geq 2\text{ and }\gcd(a_{i},a_{j})=1\text{ for any }i,j\in\{1,2,\ldots,n\}\text{ with }i\neq j. (2) It should be noted that not all integral vectors satisfying ( 1 ) also satisfy the stronger conditions ( 2 ). For example, the vector \boldsymbol{a}=(6,10,15)^{T} satisfies ( 1 ) but does not satisfy ( 2 ). There is a very rich history on Frobenius numbers and the book [ 1 ] provides a very good survey of the problem. Note that computing the Frobenius number in general is \mathcal{NP} -hard [ 12 ] (which was proved via a reduction to the integer knapsack problem), however, if the number of integers n is fixed, then a polynomial time algorithm to calculate F(\boldsymbol{a}) exists [ 10 ] . If n=2 , it is well-known (most likely due to Sylvester [ 16 ] ) that \displaystyle F(a_{1},a_{2}) \displaystyle=a_{1}a_{2}-a_{1}-a_{2} (3) \displaystyle=(a_{1}-1)(a_{2}-1)-1\,. In contrast to the case when n=2 , it was shown by Curtis [ 6 ] that no general closed formula exists for the Frobenius number if n>2 . In light of this, there has been a great deal of research into producing upper bounds on F(\boldsymbol{a}) . These bounds share the property that in the worst-case they are of quadratic order with respect to the maximum absolute valued entry of \boldsymbol{a} , which will be denoted by \|\boldsymbol{a}\|_{\infty}=\max_{i}|a_{i}| . Further, let \|\cdot\|_{2} denote the \ell_{2} -norm (or Euclidean norm). In particular, upon assuming that ( 1 ) and a_{1}\leq a_{2}\leq\cdots\leq a_{n} hold, such bounds include the classical bound by Erdős and Graham [ 7 , Theorem 1] F(\boldsymbol{a})\leq 2a_{n-1}\left\lfloor\frac{a_{n}}{n}\right\rfloor-a_{n}, by Schur (according to Brauer [ 5 ] ) F(\boldsymbol{a})\leq(a_{1}-1)(a_{n}-1)-1, by Selmer [ 14 ] (for a_{1}\geq n ) F(\boldsymbol{a})\leq 2a_{n}\left\lfloor\frac{a_{1}}{n}\right\rfloor-a_{1}, by Vitek [ 18 , Theorem 5] (for n\geq 3 ) F(\boldsymbol{a})\leq\frac{1}{2}(a_{2}-1)(a_{n}-2)-1, and by Fukshansky and Robins [ 9 , Equation 29] F(\boldsymbol{a})\leq\left\lfloor\frac{(n-1)^{2}\,\Gamma(\frac{n+1}{2})}{\pi^{(n-1)/2}}\sum_{i=1}^{n}a_{i}\sqrt{\|\boldsymbol{a}\|_{2}^{2}-a_{i}^{2}}+1\right\rfloor, where \Gamma(\cdot) and \lfloor\,\cdot\,\rfloor denote Euler’s gamma and the standard floor functions, respectively. It should be noted that the bound of Selmer [ 14 ] F(\boldsymbol{a})\leq 2a_{n}\left\lfloor\frac{a_{1}}{n}\right\rfloor-a_{1}, (4) with a_{1}\geq n , is widely referenced in books and papers, but is frequently misstated. In particular, many sources give insufficient attention to the underlying assumptions on the vector \boldsymbol{a} . Notably, this upper bound does not necessarily hold under the weaker conditions ( 1 ). Proposition 1 . The upper bound ( 4 ) of Selmer [ 14 ] does not necessarily hold unless the stronger conditions ( 2 ) hold. This requirement remains even if the weaker conditions ( 1 ) are met. Recall that the above bounds share the property that in the worst-case they are of quadratic order and depend on the maximum entry of \boldsymbol{a} . It was shown by Williams and Haijima [ 20 ] that any upper bound on the Frobenius number F(\boldsymbol{a}) must inherently depend on \|\boldsymbol{a}\|_{\infty} if the integral vector \boldsymbol{a} satisfies only the (weaker) conditions ( 1 ). Later in this paper (in Section 4), we investigate whether a general upper bound on F(\boldsymbol{a}) can be obtained under these weaker conditions with a worst-case exponent strictly lower than quadratic. If the entries of \boldsymbol{a} satisfy the stronger conditions ( 2 ) that they are pairwise coprime, then, following an argument closely related to Beck et al. [ 2 ] , Williams and Haijima [ 20 ] establish the bound F(\boldsymbol{a})\leq\frac{1}{2}\left(\sqrt{\frac{1}{3}\left(a_{1}+a_{2}+a_{3}\right)\left(a_{1}+a_{2}+a_{3}+2a_{1}a_{2}a_{3}\right)+\frac{8}{3}\left(a_{1}a_{2}+a_{2}a_{3}+a_{3}a_{1}\right)}-a_{1}-a_{2}-a_{3}\right). (5) Notably, the original proof of Beck et al. [ 2 ] contained a subtle error, which altered the value of their initially claimed upper bound of F(\boldsymbol{a})\leq\frac{1}{2}\left(\sqrt{a_{1}a_{2}a_{3}\left(a_{1}+a_{2}+a_{3}\right)}-a_{1}-a_{2}-a_{3}\right). (6) It was shown by Williams and Haijima [ 20 ] that despite the subtle error, the original bound ( 6 ) remains valid assuming the stronger conditions ( 2 ) hold, although it turns out that ( 5 ) is tighter than ( 6 ) in all but a relatively “small” (finite) number of cases. Furthermore, it was shown by Williams and Haijima [ 20 ] that provided the stronger conditions ( 2 ) hold, then for any i,j\in\{1,2,\ldots,n\} with i\neq j we have F(\boldsymbol{a})\leq(a_{i}-1)(a_{j}-1)-1. It should be noted that the above bound tells us that the well-known result ( 3 ) of Sylvester [ 16 ] naturally extends to provide an upper bound for the Frobenius number F(\boldsymbol{a}) under the (stronger) conditions ( 2 ), i.e. that the entries of \boldsymbol{a} are pairwise coprime. 2 Comparison of Bounds Under the GCD Conditions In this section, we compare bounds that are valid under the (weaker) conditions ( 1 ) on \boldsymbol{a} . In particular, we examine the bounds by Erdős and Graham [ 7 , Theorem 1] F(\boldsymbol{a})\leq 2a_{n-1}\left\lfloor\frac{a_{n}}{n}\right\rfloor-a_{n}, (7) by Schur (according to Brauer [ 5 ] ) F(\boldsymbol{a})\leq(a_{1}-1)(a_{n}-1)-1, (8) by Vitek [ 18 , Theorem 5] (for n\geq 3 ) F(\boldsymbol{a})\leq\frac{1}{2}(a_{2}-1)(a_{n}-2)-1, (9) and by Fukshansky and Robins [ 9 , Equation 29] F(\boldsymbol{a})\leq\left\lfloor\frac{(n-1)^{2}\,\Gamma(\frac{n+1}{2})}{\pi^{(n-1)/2}}\sum_{i=1}^{n}a_{i}\sqrt{\|\boldsymbol{a}\|_{2}^{2}-a_{i}^{2}}+1\right\rfloor, (10) where \Gamma(\cdot) and \lfloor\,\cdot\,\rfloor denote Euler’s gamma and the standard floor functions, respectively. It should be noted that in several

Read the complete text