Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918019049979904 |
|---|---|
| author | Williams, Aled |
| author_facet | Williams, Aled |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number Williams, Aled Number Theory Optimization and Control 11D04, 11D07, 90C10, 11D45 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. |
| title | Evaluating the Sharpness and Limitations of Bounds on the Frobenius Number |
| topic | Number Theory Optimization and Control 11D04, 11D07, 90C10, 11D45 |
| url | https://arxiv.org/abs/2505.08560 |