The Frobenius Problem and the Covering Radius of a Lattice

Let N \u3e 1 be an integer, and let 1 \u3c a1 \u3c ... \u3c aN be relatively prime integers. Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be expressed as a linear combination of a1, ..., aN with non-negative integer coefficients. The condition that a1, ..., aN are relatively prime implies that such a number exists. The general problem of determining the Frobenius number given N and a1, ..., aN is known to be 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 the linear form with coefficients a1, ..., aN. In case when this lattice has equal successive minima, our bound is better than the previously known ones. This is joint work with Sinai Robins