Milner 317

Wednesdays, 12:30-1:30 PM

Texas A&M University

**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.