Abstract. Let N ≥ 2 and let 1 < a(1) < ... < a(N) be relatively prime integers. The Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be expressed as Sigma(N)(i=1) 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 a number exists. The general problem of determining the Frobenius number given N and a(1),..., a(N) is NP-hard, but there have 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 the 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.
© 2007 Springer
Fukshansky, Lenny, and Sanai Robins. "Frobenius problem and the covering radius of a lattice." Discrete and Computational Geometry 37.3 (March 2007): 471-483.