Title

On the Frobenius Problem and its Generalization

Document Type

Lecture

Department

Mathematics (CMC)

Publication Date

11-3-2010

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 represented as a linear combination of a_1,...,a_N with non-negative integer coefficients. More generally, the s-Frobenius number is defined to be the largest positive integer that has precisely s distinct representations like this, so that the classical Frobenius number can be thought of as the 0-Frobenius number. The condition that a_1,...,a_N are relatively prime implies that s-Frobenius numbers exist for every non-negative integer s. 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 an upper bound on the Frobenius number in terms of the covering radius of the null-lattice of the linear form with coefficients a_1,...,a_N. More generally, we are able to obtain upper and lower bounds on the s-Frobenius number for any nonnegative integer s. In this talk, we will discuss these and some related results on the Frobenius problem and its generalizations, as time allows.

Comments

This lecture was given during the Colloquium at California State University Dominguez Hills in September 2011, and during the Colloquium at the University of Rostock in November 2010.

Rights Information

© 2010 Lenny Fukshansky

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.