Frobenius Problem and the Covering Radius of a Lattice

Authors

Lenny Fukshansky, Claremont McKenna CollegeFollow
Sinai Robins, Nanyang Technological UniversityFollow

Document Type

Article

Department

Mathematics (CMC)

Publication Date

2007

Abstract

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.

Comments

Previously linked to as: http://ccdl.libraries.claremont.edu/u?/irw,298.

Source: Author's post-print manuscript in pdf.

The original publication is available at www.springerlink.com and may be found at http://www.springerlink.com/content/m3t6n0p17474384q/?p=e5623c5968d5463e82d3872f0f3c9335π=9

Rights Information

© 2007 Springer

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Fukshansky, Lenny, and Sanai Robins. "Frobenius problem and the covering radius of a lattice." Discrete and Computational Geometry 37.3 (March 2007): 471-483.