From: Gerry Myerson <gerry@mpce.mq.edu.au>
Subject: Frobenius problem (was Re: Horsman's Theorem)
Date: Wed, 07 Feb 2001 09:47:59 +1000
Newsgroups: sci.math
Summary: Maximum number not a positive linear combination of three given ones

In article <95p2kq$4if$1@nnrp1.deja.com>, kfoster5018@my-deja.com 
wrote:

> In article <95o82k$7fp@mcmail.cis.mcmaster.ca>,
>   kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) wrote:
> > In article <h6Nf6.83$Z2.351862@newt.tstonramp.com>,
> > jim horsman <jhorsman@jovanet.com> wrote:
> > :It is easy to show that integer multiples of 3 and 8 can make any
> > :number greater than 13.
> > :Does this generalize? if m and n are relatively prime, there
> > :exist a k, such that a*m +b*n = all integers greater than k.
> > :Does this theorem have a "real"  name? Can someone direct me
> > :to the proof?
> 
> > Sylvester's Theorem. Pedantically, one should talk about
> > "linear combinations with non-negative integer coefficients".
> > The smallest value of k is (m-1)*(n-1)-1. That's how 13 is
> > obtained from 3 and 8.
> 
> > To prove it, to given m and n, you find non-negative integers
> > p, q such that p*m-q*n=1, and use them to attempt proof by
> > induction: if a*m+b*n=r then we can recombine m, n to obtain r+1,
> > provided we started from r=k+1.
> 
>   Curiously, the correponding problem for 3 variables -
> given positive integers a, b, c with gcd(a, b, c) = 1,
> to find the largest integer not representable by
> 
> ax + by + cz
> 
> with x, y, z all positive - was, last I heard, unsolved.

Not clear - have a look at the following. 

58 #27740 10B05 
Selmer, Ernst S.; Beyer, Öyvind 
On the linear Diophantine problem of Frobenius in three variables. 
J. Reine Angew. Math. 301 (1978), 161--170. 

Let $a\sb 1,a\sb 2,\cdots,a\sb k$ be relatively prime integers $>1$. 
The problem of Frobenius consists in determining the largest integer 
$g(a\sb 1,a\sb 2,\cdots,a\sb k)$ with no integral representation $a\sb 
1x\sb 1+a\sb 2x\sb 2+\cdots+a\sb kx\sb k$, $x\sb i\geq 0$. Also the 
number $n(a\sb 1,a\sb 2,\cdots,a\sb k)$ with no such representation has 
been studied. Here a complete solution is found for both when $k=3$. 
The arguments involve tedious work using continued fractions. (See 
\#27741 below.)

Reviewed by E. L. Cohen 


58 #27741 10B05 
Rödseth, Öystein J. 
On a linear Diophantine problem of Frobenius. 
J. Reine Angew. Math. 301 (1978), 171--178. 

The author simplifies the proof of Selmer and Beyer [see \#27740 above] 
in determining $g(a\sb 1,a\sb 2,a\sb 3)$ and $n(a\sb 1,a\sb 2,a\sb 3)$ 
in the Frobenius problem. The results in both these works are given 
explicitly.

Reviewed by E. L. Cohen 


82d:10046 10F20 (10F30 90C10) 
Selmer, Ernst S. 
On the postage stamp problem with three stamp denominations. 
Math. Scand. 47 (1980), no. 1, 29--71. 

Given enough stamps of $k$ integral denominations $1=a\sb 1<a\sb 
2<\cdots<a\sb k$, what is the largest consecutive range of postal rates 
which can be formed if no more than $h$ stamps may be used? This is the 
so-called "postage stamp problem" which, stated formally, asks for the 
largest integer $n\sb h(A\sb k)$ such that for any integer $m$, $0\leq 
m\leq n\sb h(A\sb k)$, there are $x\sb i\geq 0$ such that $m=\sum\sb 
{i=1}\sp kx\sb ia\sb i$, $\sum\sb {i=1}\sp kx\sb i\leq h$, where $A\sb 
k=\{a\sb 1,\cdots,a\sb k\}$ is a given basis of integers, $1=a\sb 
1<a\sb 2<\cdots<a\sb k$. This is the local problem. The "global 
problem" is to find an "extremal basis" $A\sb k\sp *$ which gives the 
maximal extremal $h$-range $n\sb h(A\sb k\sp *)=n\sb h(k)$. 

This paper is concerned with the local problem for $k=3$. G. R. 
Hofmeister [J. Reine Angew. Math. 232 (1968), 77--101; MR 38 #1068] has 
solved the global problem for $k=3$. H. Salie [Math. Ann. 165 (1966), 
196--203; MR 33 #7295] and later O. J. Rodseth [J. Reine Angew. Math. 
301 (1978), 171--178; MR 58 #27741] gave procedures to determine $n\sb 
h(A\sb 3)$. Rodseth's method does not estimate, a priori, the number of 
steps required to determine $n\sb h(A\sb 3)$. Salie gave explicit 
formulas to determine $n\sb h(A\sb 3)$, albeit under restrictive 
conditions on $a\sb 2,a\sb 3$. The author's aim in the present paper is 
to apply Rodseth's method to improve the results of Salie and to obtain 
more general explicit formulas to determine $n\sb h(A\sb 3)$.

Reviewed by P. K. Subramanian 


89f:11039 11D04 (11P99 90C10) 
Hujter, Mihaly(H-AOS-C); Vizvári, Béla(H-AOS-C) 
The exact solutions to the Frobenius problem with three variables. 
J. Ramanujan Math. Soc. 2 (1987), no. 2, 117--143. 

Let $a\sb 1,\cdots,a\sb n$ be positive integers. The famous classical 
problem of Frobenius is to find the maximal nonnegative integer that 
cannot be represented in the form $\sum\sb {i=1}\sp na\sb ix\sb i$ with 
$0\le x\sb i\in\bold Z$, $i=1,\cdots,n$. The problem is quite easy for 
$n=1, 2$, but is not completely solved for any larger $n$. In the paper 
the authors give a survey of many known formulas for special cases of 
the problem, especially in the case $n=3$. For $n=3$ they give some new 
special formulas, which, together with the old ones, give the Frobenius 
number for $a\sb 1\le10$ and $a\sb 1=12$. Further, in the appendix a 
useful list of the Frobenius numbers is given for several triples 
$(a\sb 1, a\sb 2, a\sb 3)$ that are not covered by the known special 
formulas.

Reviewed by Istvan Gaal 


89j:11122 11Y50 (11D04 90C10) 
Greenberg, Harold(1-CUNY2-S) 
Solution to a linear Diophantine equation for nonnegative integers. 
J. Algorithms 9 (1988), no. 3, 343--353. 

The paper contains a fundamental improvement in the theory of linear 
Diophantine equations with three variables. Let $1<a<b<c$ and $L$ be 
positive integers. Following the results of O. J. Rodseth [J. Reine 
Angew. Math. 301 (1978), 171--178; MR 58 #27741] the author gives an 
algorithm using only $O(\log a)$ steps to generate a nonnegative 
solution of the linear Diophantine equation $ax+by+cz=L$. Applying this 
algorithm the author provides us with another algorithm, requiring 
$O(\log a)$ steps as well, to solve the Frobenius problem with three 
variables, i.e., to determine the number $\max\{L\in\bold Z\:\nexists 
(x,y,z)\in\bold Z\sb +\sp 3, ax+by+cz=L\}$ assuming that 
$\roman{gcd}(a,b,c)=1$.

Reviewed by Bela Vizvari 


99k:11043 11D04 
Morikawa, Ryozo 
On the linear Diophantine problem of Frobenius in three variables. 
Bull. Fac. Liberal Arts Nagasaki Univ. 38 (1997), no. 1, 1--17. 

The version of the Frobenius problem discussed in this paper is as 
follows. Let $a$, $b$, $c$ be relatively prime positive integers. Let 
$G=\{u\vert \exists (x,y,z)\in\bold N\sp 3$, $u=ax+by+cz\}$. The 
problem is to determine the greatest integer which is not an element of 
the set $G$. The author gives some exact formulas and investigates the 
order of magnitude of the Frobenius number. The author seems not to be 
aware of the literature dealing with the same problem [e.g. H. 
Greenberg, J. Algorithms 9 (1988), no. 3, 343--353; MR 89j:11122; M. 
Hujter and B. Vizvari, J. Ramanujan Math. Soc. 2 (1987), no. 2, 
117--143; MR 89f:11039].

Reviewed by Bela Vizvari 

Gerry Myerson (gerry@mpce.mq.edu.au)