Counting and summing over solutions of a Diophantine equation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:13:28Z http://mathoverflow.net/feeds/question/61329 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61329/counting-and-summing-over-solutions-of-a-diophantine-equation Counting and summing over solutions of a Diophantine equation Anirbit 2011-04-11T19:39:06Z 2011-04-12T05:19:12Z <p>Say I have a Diophantine equation of the form $a_1 x_1 + a_2 x_2 + ... + a_m x_m = n$ such that the $a_is$ are all co-prime to each other. And I also have a function say $f$ which depends only on the $x_i's$ (and will be evaluated on solutions of the equations) </p> <ul> <li><p>Is there a general method or simple examples of summing over the values of $f$ evaluated on the non-negative integral solutions of the equation? </p></li> <li><p>Is there a way to count the number of non-negative integral solutions of such Diophantine equations? (...I am aware that it is trivially doable in some special cases like when all the $a_is$ are equal to $1$ or when $a_i = i$ and $m=n$...)</p></li> </ul> http://mathoverflow.net/questions/61329/counting-and-summing-over-solutions-of-a-diophantine-equation/61333#61333 Answer by quid for Counting and summing over solutions of a Diophantine equation quid 2011-04-11T20:21:11Z 2011-04-11T20:21:11Z <p>This is no way a complete answer, but it shows that one cannot ask for too much, or might have to impose some additional conditions, perhaps relative size assumptions. </p> <p>Let us just say we want to know if there is at least one or no solution. Given <code>$a_i$</code> it follows easily that for all sufficiently large $n$ there is at least some solution, and we can thus answer this question in case $n$ is 'large'. However, what does 'large' mean exactly? The problem of determining the precise threshold is known as the <a href="http://en.wikipedia.org/wiki/Coin_problem" rel="nofollow">Frobenius problem</a> (or also Coin problem).</p> <p>This is a well-investigated and difficult problem (except for only two <code>$a_i$</code>). In general, no 'formula' is known; yet good algorithms to compute the exact threshold are known if the number of <code>$a_i$</code> s is fixed; if not, this is not so.</p> <p>So, even to decide whether such an equation has a solution or not can be a very challenging question if $n$ is not 'large'.</p> http://mathoverflow.net/questions/61329/counting-and-summing-over-solutions-of-a-diophantine-equation/61364#61364 Answer by Gerry Myerson for Counting and summing over solutions of a Diophantine equation Gerry Myerson 2011-04-12T04:54:12Z 2011-04-12T04:54:12Z <p>The number of solutions of $a_1x_1+\dots+a_mx_m=n$ in non-negative integers $x_1,\dots,x_m$, call it $d(n;a_1,\dots,a_m)$, is called the $\it denumerant$. This goes back to Sylvester, On the partition of numbers, Quart J Pure Appl Math 1 (1857) 141-152. Much is known. For example, Schur proves that if $\gcd(a_1,\dots,a_m)=1$ and $P_m=\prod a_i$ then $d(n;a_1,\dots,a_m)$ is asymptotic to $P_m^{-1}n^{m-1}/(m-1)!$ as $n\to\infty$. (The reference is Zur additiven zahlentheorie, Sitzungsberichte Preussiche Akad Wiss Phys Math Kl (1926) 488-495.) </p> <p>This and more is in Chapter 4 of J L Ramirez Alfonsin, The Diophantine Frobenius Problem, published by Oxford. </p>