Non-negative integer solutions of a single Linear Diophantine Equation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:22:01Z http://mathoverflow.net/feeds/question/27884 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation Non-negative integer solutions of a single Linear Diophantine Equation TGM 2010-06-11T23:12:12Z 2010-07-08T16:18:32Z <p>Consider the following linear Diophantine Equation::</p> <pre><code> ax + by + cz = d ------------ (1) </code></pre> <p>for all, a,b,c and d positive integers, and relatively prime, and assume a>b>c without loss of generality.</p> <p>Can we find a lower bound on d which ensures at least one non-negative solution to this equation?</p> <p>I know we can solve this problem easily for </p> <pre><code> ax+by = c. -------- (2) </code></pre> <p>The answer is </p> <p>c>=ab, ------------(3)</p> <p>which derives from the fact that the distance between two consecutive solutions of this equation is</p> <pre><code> $D = (\sqrt(a^2 + b^2))$ ----------(4) </code></pre> <p>and c>=ab ensures that the length of line in x-y plane is large enough to include at least one solution).</p> <p>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. </p> <p>Is there a smarter way to do this? and if such a bound exists, can it be extended to higher dimensions?</p> <p>Thanks.</p> http://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation/27886#27886 Answer by Vladimir Dotsenko for Non-negative integer solutions of a single Linear Diophantine Equation Vladimir Dotsenko 2010-06-11T23:36:06Z 2010-06-11T23:36:06Z <p>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 <a href="http://www.jstor.org/pss/2371684" rel="nofollow">this paper</a>, - 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. <a href="http://www.springerlink.com/content/b373168270250837/" rel="nofollow">this article</a> and <a href="http://www.springerlink.com/content/04tr526471584276/" rel="nofollow">this article</a>; some progress has been made in that direction, see e.g. like <a href="http://www.turpion.org/php/paper.phtml?journal_id=sm&amp;paper_id=4011" rel="nofollow">this paper</a>. </p> http://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation/29994#29994 Answer by Max Alekseyev for Non-negative integer solutions of a single Linear Diophantine Equation Max Alekseyev 2010-06-30T01:07:59Z 2010-06-30T01:07:59Z <p>A bunch of various bound for Frobenius number is given in <a href="http://arxiv.org/abs/math/0305420" rel="nofollow">this paper</a>. </p> <p><a href="http://en.wikipedia.org/wiki/Frobenius_number" rel="nofollow">Wikipedia article</a> may be helpful as well.</p> http://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation/29996#29996 Answer by Gerry Myerson for Non-negative integer solutions of a single Linear Diophantine Equation Gerry Myerson 2010-06-30T01:26:07Z 2010-06-30T01:26:07Z <p>There's a whole book on this problem; J L Ramirez Alfonsin, The Diophantine Frobenius Problem, Oxford University Press, 2005. </p> http://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation/31071#31071 Answer by TGM for Non-negative integer solutions of a single Linear Diophantine Equation TGM 2010-07-08T16:18:32Z 2010-07-08T16:18:32Z <p>Thanks everbody. </p>