Gr{ö}bner basis. a "pseudo-polynomial" algorithm for computing the Frobenius number

Abstract

Let consider $n$ natural numbers $a\_1,\dots ,a\_n$. Let $S$ be the numerical semigroup generated by $a\_1,\dots ,a\_n$. Set $A=K[t^{a\_1},\dots ,t^{a\_n}]=K[x\_1,\dots ,x\_n]/I$. The aim of this paper is: \begin{enumerate}\item Give an effective pseudo-polynomial algorithm on $a\_1$, which computes The Ap{é}ry set and the Frobenius number of $S$. As a consequence it also solves in pseudo-polynomial time the integer knapsack problem : given a natural integer b, b belongs to $S$?\item The \gbb of $I$ for the reverse lexicographic order to $x\_n,\dots ,x\_1$, without using Buchberger's algorithm. \item $\ini{I} $ for the reverse lexicographic order to $x\_n,\dots ,x\_1$.\item $A$ as a $K[t^{a\_1}]$-module. \end{enumerate} We dont know the complexity of our algorithm. We need to solve the "multiplicative" integer knapsack problem: Find all positive integer solutions $(k\_1,\dots ,k\_n)$ of the inequality $\prod \_{i=2}^n(k\_i+1)\le a\_1+1$. This algorithm is easily implemented. The implementation of this algorithm "frobenius-number-mm", for $n=17$, can be downloaded in \hfill\breakhttps://www-fourier.ujf-grenoble.fr/~morales/frobenius-number-mm