Counting and summing over solutions of a Diophantine equation - MathOverflow

Counting and summing over solutions of a Diophantine equation

2011-04-11T19:39:06Z

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)

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?
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$...)

Answer by quid for Counting and summing over solutions of a Diophantine equation

2011-04-11T20:21:11Z

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.

Let us just say we want to know if there is at least one or no solution. Given $a_i$ 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 Frobenius problem (or also Coin problem).

This is a well-investigated and difficult problem (except for only two $a_i$ ). In general, no 'formula' is known; yet good algorithms to compute the exact threshold are known if the number of $a_i$ s is fixed; if not, this is not so.

So, even to decide whether such an equation has a solution or not can be a very challenging question if $n$ is not 'large'.

Answer by Gerry Myerson for Counting and summing over solutions of a Diophantine equation

2011-04-12T04:54:12Z

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.)

This and more is in Chapter 4 of J L Ramirez Alfonsin, The Diophantine Frobenius Problem, published by Oxford.