Frobenius problem and the covering radius of a lattice
| dc.creator | Fukshansky, Lenny | |
| dc.creator | Robins, Sinai | |
| dc.date | 2005-12-06 | |
| dc.date | 2006-07-13 | |
| dc.date.accessioned | 2026-07-07T08:12:19Z | |
| dc.date.available | 2026-07-07T08:12:19Z | |
| dc.description | Let $N \geq2$ and let $1 < a_1 < ... < a_N$ be relatively prime integers. Frobenius number of this $N$-tuple is defined to be the largest positive integer that cannot be expressed as $\sum_{i=1}^N a_i x_i$ where $x_1,...,x_N$ are non-negative integers. The condition that $gcd(a_1,...,a_N)=1$ implies that such number exists. The general problem of determining the Frobenius number given $N$ and $a_1,...,a_N$ is NP-hard, but there has been a number of different bounds on the Frobenius number produced by various authors. We use techniques from the geometry of numbers to produce a new bound, relating Frobenius number to the covering radius of the null-lattice of this $N$-tuple. Our bound is particularly interesting in the case when this lattice has equal successive minima, which, as we prove, happens infinitely often. | |
| dc.description | 12 pages; minor revisions; to appear in Discrete and Computational Geometry | |
| dc.identifier | https://arxiv.org/abs/math/0512134 | |
| dc.identifier | http://arxiv.org/abs/math/0512134 | |
| dc.identifier | Discrete Comput. Geom. 37 (2007), no. 3, 471--483 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132414 | |
| dc.subject | Number Theory | |
| dc.subject | Combinatorics | |
| dc.subject | 11D04, 11H06, 52C07 | |
| dc.title | Frobenius problem and the covering radius of a lattice | |
| dc.type | text |