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.
Rights Information
© 2010 Lenny Fukshansky
Terms of Use & License Information
Recommended Citation
Fukshansky, Lenny. "On the Frobenius Problem and its Generalization." Colloquium, University of Rostock, Rostock, Germany. 3 November 2010.
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.