Wednesday, October 19
Milner 317, 12:30 PM
Title: The Frobenius problem and the covering radius of a lattice
Abstract: Let N > 1 be an integer, 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 a linear combination of a_1,...,a_N with non-negative integer coefficients. The condition that a_1,...,a_N are relatively prime implies that such number exists. The general problem of determining the Frobenius number given N and a_1,...,a_N 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 a_1,...,a_N. 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.