On the Diophantine Frobenius Problem

Y.O. Hamidoune

Abstract: Let $X\subset \N$ be a finite subset such that $\gcd (X)=1$. The Frobenius number of $X$ (denoted by $G(X)$) is the greatest integer without an expression as a sum of elements of $X$. We write $f(n,M)=\max \{G(X)$; $\gcd(X)=1$, $|X|=n$\ \,&\,\ $\max(X)=M\}$.
We shall define a family ${\cal F}_{n,M}$, which is the natural extension of the known families having a large Frobenius number. Let $A$ be a set with cardinality $n$ and maximal element $M$. Our main results imply that for $A\notin {\cal F}_{n,{M}}$, $ G (A)\leq({M}-n/2)^2/{n}-1$. In particular we obtain the value of $f(n,M)$, for $M\geq n(n-1)+2$. Moreover our methods lead to a precise description for the sets $A$ with $G(A)=f(n,M)$.
The function $f(n,M)$ has been calculated by Dixmier for $M\equiv 0,1,2$ modulo $n-1$. We obtain in this case the structure of sets $A$ with $G(A)=f(n,M)$. In particular, if $M\equiv 0$ mod $n-1$, a result of Dixmier, conjectured by Lewin, states that $G(A)\leq G(N)$, where $N=\{M/(n-1),\,2M/(n-1),\,...,\,M,M-1\}$. We show that for $n\geq6$ and $M\geq3n-3$, $G(A)<G(N)$, for $A\neq N$.

Full text of the article:

• Compressed PostScript file (104 kilobytes)
• PDF file (216 kilobytes)