On the Frobenius problem and its generalization

10/07/2014 - 12:15pm
10/07/2014 - 1:10pm
Lenny Fukshansky (CMC)

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, dates back to the 19-th century lectures of G. Frobenius and work of J. Sylvester, and has been studied extensively by many prominent mathematicians of the 20-th century, including P. Erdos. While this problem is now known to be NP-hard, there has been a number of successful efforts by various authors producing bounds and asymptotic estimates on the Frobenius number and its generalization. I will discuss some of these results, which are obtained by an application of techniques from Discrete Geometry.

Mudd Science Library 126, Pomona College