Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following linear Diophantine Equation::

  ax + by + cz = d  ------------ (1)

for all, a,b,c and d positive integers, and relatively prime, and assume a>b>c without loss of generality.

Can we find a lower bound on d which ensures at least one non-negative solution to this equation?

I know we can solve this problem easily for

     ax+by = c. -------- (2)

The answer is

c>=ab, ------------(3)

which derives from the fact that the distance between two consecutive solutions of this equation is

     $D = (\sqrt(a^2 + b^2))$  ----------(4)

and c>=ab ensures that the length of line in x-y plane is large enough to include at least one solution).

Since equation (1) is a plane in the xyz coordinate system, and the distance between consecutive solution can be shown to be DD = sqrt(b^2+c^2) (though this may not be smallest distance between solutions). I was thinking that if we can show that an inscribed circle with diameter DD can be enclosed within the triangle formed by x,y and z intercepts of Eq.(1), i.e. (c/a,0,0), (0,c/b,0) and (0,0,c/a), then we have at least one non-negative solution. But the in-circle radius has an inconvenient relationship with the original variables (a,b,c,d), and may not be a monotonic function of d.

Is there a smarter way to do this? and if such a bound exists, can it be extended to higher dimensions?

Thanks.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

The question of determining the lower bound on $d$ is called the Frobenius problem. For $2$ variables your bound can be improved: every integer starting from $(a-1)(b-1)$ is representable as a non-negative combination. Some general results on this problem are available in this paper, - even on the first page (which is open-access): it is stated that for $a>b>c$ the number $(c-1)(a-1)$ gives a bound. However, it is probably very far from optimal; there are various conjectures and partial results on the asymptotic behaviour of these numbers for big $a,b,c$ (and similarly for larger dimensions). In particular, some conjectures on Frobenius problem were formulated by late Vladimir Arnold in the past decade, see, e.g. this article and this article; some progress has been made in that direction, see e.g. like this paper.

share|improve this answer
    
@Vladimir In the answer by Pete on another question on MathOverflow mathoverflow.net/questions/19587/… , there seems to be a claim that Sylvester had shown that for the two variable case the Frobenius number is precisely $ab-a-b$ (in your notation) Doesn't that contradict what you saying in the two variable case? –  Anirbit Apr 12 '11 at 16:03
    
Huh? $ab-a-b=(a-1)(b-1)-1$, so these two statements match perfectly. –  Vladimir Dotsenko Apr 13 '11 at 22:13
    
@Vladimir Oh..sorry..I was not accounting for the "-1". The number you quote is the minimum number that is representable and hence the Frobenius number would be one less than that. Okay! –  Anirbit Apr 16 '11 at 8:34

There's a whole book on this problem; J L Ramirez Alfonsin, The Diophantine Frobenius Problem, Oxford University Press, 2005.

share|improve this answer

A bunch of various bound for Frobenius number is given in this paper.

Wikipedia article may be helpful as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.