PORTUGALIAEMATHEMATICA Vol. 55, No. 4, pp. 425-449 (1998)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

On the Diophantine Frobenius Problem

Y.O. Hamidoune

Université Pierre et Marie Curie, E. Combinatoire, CASE 189,
4 Place Jussieu, 75005 Paris - FRANCE

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:

Electronic version published on: 29 Mar 2001. This page was last modified: 27 Nov 2007.