The Frobenius Problem and the Covering Radius of a Lattice
Document Type
Lecture
Department
Mathematics (CMC)
Publication Date
12-2005
Abstract
Let N > 1 be an integer, and let 1 < a1 < ... < 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.
Rights Information
© 2005 Lenny Fukshansky
Terms of Use & License Information
Recommended Citation
Fukshansky, Lenny. "The Frobenius Problem and the Covering Radius of a Lattice." West Coast Number Theory, Pacific Grove, CA. December 2005.
Comments
This lecture is related to an article written by Lenny Fukshansky and Sinai Robins, "Frobenius Problem and the Covering Radius of a Lattice" in Discrete and Computational Geometry Volume 37, Issue 3, pages 471-483.
The lecture was given during West Coast Number Theory in Pacific Grove, CA, December 2005. It was also given during the Colloquium at Temple University in February 2006, the Combinatorics Seminar at UCLA in May 2010, and the Number Theory Seminar at Texas A&M University in October 2005.