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

  • $\begingroup$ Do you want all the a_i positive? Also the f, I assume it is a function of the 'solutions' so x_i not a_i, or am I confusing something. $\endgroup$ – user9072 Apr 11 '11 at 19:47
  • $\begingroup$ Yes. I want all the a_i's to be positive. The typos with f has been corrected. It depends on the solutions and not $a_i$s. Thanks for pointing out! $\endgroup$ – Anirbit Apr 11 '11 at 20:00
  • $\begingroup$ What kind of functions $f$ are you interested in? $\endgroup$ – Gjergji Zaimi Apr 12 '11 at 3:09
  • $\begingroup$ In the specific case I am concerned with $f$ will be the number of solution of the Polya problem for the cyclic group and with $m$ colours, $x_1$ balls of the first colour, $x_2$ balls of the second colour etc. $\endgroup$ – Anirbit Apr 12 '11 at 4:45

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.

| cite | improve this answer | |
  • $\begingroup$ @Gerry! By tinkering around I had guessed this result you say is by Schur! But haven't been able to give a precise proof. Does Ramirez's book explain this? $\endgroup$ – Anirbit Apr 12 '11 at 6:31
  • $\begingroup$ @Anirbit : Schur's theorem is also proved in the book Generatingfunctionology by H.S. Wilf (section 3.15) math.upenn.edu/~wilf/DownldGF.html $\endgroup$ – François Brunault Apr 12 '11 at 6:53
  • $\begingroup$ @Anirbit, yes, Ramirez Alfonsin gives a proof - and many more results, besides. If you're interested in this problem I strongly suggest you track down a copy of the book. $\endgroup$ – Gerry Myerson Apr 12 '11 at 7:02
  • $\begingroup$ @Gerry Thanks for the references. And any hope of an exact solution? And any ideas about doing the sum over solutions part of the question? $\endgroup$ – Anirbit Apr 12 '11 at 7:09
  • 1
    $\begingroup$ @Anirbit, any hope of you trying to read the book? $\endgroup$ – Gerry Myerson Apr 12 '11 at 13:03

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

| cite | improve this answer | |
  • $\begingroup$ Even if I assume that my $n$ is large enough for solutions to exist then is there a way to count the number of non-negative integral solutions? Asymptotically? $\endgroup$ – Anirbit Apr 11 '11 at 20:26
  • $\begingroup$ @Anirbit, perhaps yes, as one can count the number of suitable related congruences, but I am not sure this helps. I will think a bit about it and report if I find something. (But I cannot do so within the next ca 16 hours.) $\endgroup$ – user9072 Apr 11 '11 at 22:34
  • $\begingroup$ Since meanwhile another answer appeared, I consider this as obsolete. $\endgroup$ – user9072 Apr 12 '11 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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