2:00 pm Tuesday, February 28, 2006
Number Theory Seminar: Frobenius number of ESM lattices by L. Fukshansky (Texas A&M) in RLM 9.166
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. Our bound is frequently better than the previously known ones, in particular when this lattice has equal successive minima (ESM); we show that this happens infinitely often. This is joint work with Sinai Robins. Submitted by
|
|