4
$\begingroup$

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

$\endgroup$
4
  • $\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, 2011 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, 2011 at 20:00
  • $\begingroup$ What kind of functions $f$ are you interested in? $\endgroup$ Apr 12, 2011 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, 2011 at 4:45

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
6
  • $\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, 2011 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$ Apr 12, 2011 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$ Apr 12, 2011 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, 2011 at 7:09
  • 1
    $\begingroup$ @Anirbit, any hope of you trying to read the book? $\endgroup$ Apr 12, 2011 at 13:03
0
$\begingroup$

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

$\endgroup$
3
  • $\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, 2011 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, 2011 at 22:34
  • $\begingroup$ Since meanwhile another answer appeared, I consider this as obsolete. $\endgroup$
    – user9072
    Apr 12, 2011 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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