







Frobenius Numbers by Toric Gröbner Bases






Organization:  Wolfram Research, Inc. 






ACA 2005






Nara Women's University, Nara, Japan






A talk from the Conference on Applications of Computer Algebra (ACA) 2005 on a method of computing of Frobenius numbers that uses Gröbner bases. Abstract: Given a set A = {a_{1}...a_{n}} of positive integers with gcd 1, it is not hard to show that all "sufficiently large" integers can be represented as a nonnegative integer combination of elements of A. The Frobenius number of the set is defined as the largest integer not so representable. The Frobenius instance problem (also called the money changing or postage stamp problem) is to determine, given a positive integer M, a set of nonnegative integers X={x_{1}...x_{n}} such that X.A=n, or else show no such set exists. We will briefly recall how this can be addressed via toric Gröbner bases. It is known that the Frobenius number problem is NPhard in general. For dimension 2 it is trivial (Sylvester solved in two decades before Frobenius publicized the problem). In dimension 3 a very efficient method was found independently by Greenberg and Davison. For higher dimensions some quite effective methods are known for the case where one element of A is not too large (say, less than 10^{7}). Recent work has given rise to methods that are effective when the above restrictions do not hold, although the dimension must be bounded by 10 or so. It turns out that there is a way to recast this work using toric Gröbner bases, wherein the "fundamental domain" for the set A is given by the staircase of the basis with respect to a particular ordering. It is reasonably efficient in dimensions 4 to 7, when the elements in the set are as large as 10^{40} or so. We will illustrate this.












Frobenius numbers, Toric Gröbner Bases






http://www.jssac.org/Conference/ACA






 ACA2005_Frobenius.pdf (96.9 KB)  PDF Document   ACA2005_Frobenius.nb (326.9 KB)  Mathematica Notebook 

