Frobenius problem and the covering radius of a lattice

Abstract

Let $N\ge 2$ 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.

12 pages; minor revisions; to appear in Discrete and Computational Geometry