20
$\begingroup$

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:

Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, $a_i, b_i \geq 0$, consider

$$\sum\limits_{i=1}^n {s-a_i \choose r-b_i}$$

For all integers $s, r \geq max(a_1, a_2, a_3, … a_n, b_1, b_2, b_3, ... , b_n)$, where ${x \choose y}=0$ for all $y>x$, and ${x \choose 0}=1$ for all $x \geq 0$.

Goal: Find the smallest size $m$ such that, for $c_1, c_2, c_3, … c_m, d_1, d_2, d_3, ... , d_m$, where $c_i, d_i \in \mathbb{Z}$, $c_i, d_i \geq 0$

$$\sum\limits_{i=1}^n {s-a_i \choose r-b_i} = \sum\limits_{i=1}^m {s-c_i \choose r-d_i}$$

For all integers $s, r \geq max(a_1, a_2, … a_n, b_1, b_2, ... , b_n, c_1, c_2, ..., c_m, d_1, d_2, ... d_m)$.

Alternatively, find $c_i$ and $d_i$ such that $m$ is as small as possible.

For example:

  • ${s-1 \choose r-1} + {s-1 \choose r} = {s \choose r}$ (Using Pascal's Triangle)
  • Any linear dependence $\sum\limits_{i=1}^n α_i {r−a_i \choose s−b_i}=0$ valid for all sufficiently large $r$,$s$ is a linear combination of the Pascal triangle identities ${r−a+1 \choose s−b+1} − {r−a \choose s−b+1} − {r−a \choose s−b}=0$

Do we know if any complexity bounds/computability bounds are known for this problem in general?

I'm also interested in the alternate problem where we're allowed integer constants $e_i, f_i \geq 0$, and we're still interested in finding the smallest size $m$ such that

$$\sum\limits_{i=1}^n {s-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i\cdot s-c_i \choose f_i\cdot r-d_i}$$

However I'm primarily interested in the first problem - I just mention this second problem partially in case there is a trivial solution to the first that I'm not aware of.

$\endgroup$
  • $\begingroup$ In your original sum, `$n$' occurs both as the upper summation limit and in the binomial coefficient. Is this intentional? $\endgroup$ – Michael Stoll Nov 23 '14 at 11:23
  • $\begingroup$ Sorry! No it was not. I edited the question now. $\endgroup$ – Phylliida Nov 23 '14 at 19:24
  • $\begingroup$ For the second more general problem, you can insure m=1 by picking d = fr-1. The first problem looks less trivial to me. $\endgroup$ – The Masked Avenger Nov 23 '14 at 20:17
  • 5
    $\begingroup$ This doesn’t answer the question, but it is not hard to prove that any linear dependence $\sum_{i=1}^n\alpha_i\binom{r-a_i}{s-b_i}=0$ valid for all sufficiently large $r,s$ is a linear combination of the Pascal triangle identities $\binom{r-a+1}{s-b+1}-\binom{r-a}{s-b+1}-\binom{r-a}{s-b}=0$. $\endgroup$ – Emil Jeřábek Nov 23 '14 at 20:54
  • 2
    $\begingroup$ Now that I have read your comments, can you explain to me how your second bulleted example is an example of the problem? It seems the dependence on r makes it not an example. $\endgroup$ – The Masked Avenger Nov 24 '14 at 3:52
1
$\begingroup$

Addendum: I misread the problem, not paying attention to the for all s and r. Thus the trivial answer to the second more general question trivially misses the intent. However, one can change the problem representation by picking A large enough, encoding each of the n summands as a vector which, dotted with the vector whose ith component is (s-A) choose i, sums to that summand, and then add all the vectors together and try the greedy algorithm below on the summed vector. Another approach is to try the algorithm with several specific choices for r and s, and try to deduce a new sum based on the results. This approach I see as akin to checking for a symbolic determinant being identically 0 or not by plugging in numerical values and evaluating the determinant numerically. So I say without proof but with evidence that the below algorithm respects the intent of the question. End of Addendum.

Here is a half baked approach. Compute the total T of the n terms, and subtract multiples of s choose r until the result S is less than s choose r. As the central binomial coefficients grow like powers of 2, a greedy approach should get you an m of the order r log s. Now if needed, try minimizing the greedy sum S of m terms by choosing slightly less greedy choices smaller than s choose r.

As observed in a comment, the more general problem has enough freedom to admit a trivial or nearly trivial solution, with bottom coefficient equal to m which is equal to 1.

$\endgroup$
  • $\begingroup$ I assume 2r is less than s in the above. If this is not the case, tweak the algorithm more greedily. $\endgroup$ – The Masked Avenger Nov 23 '14 at 20:36
  • $\begingroup$ Unless I am misunderstanding what this algorithm does, I believe it has the same problem as your comment earlier: the relation must hold for all s and r > all the constants, not just for fixed values of s and r. If this wasn't the case, the problem would be trivial - simply compute the total T of the n terms, call this w, and return w choose 1, aka m=1. I assume this is what you meant in your comment (since you can't do _ choose 1 in the first problem but you can in the second), however this method isn't valid for either because s and r aren't constants. $\endgroup$ – Phylliida Nov 23 '14 at 22:28
  • $\begingroup$ Though this answer would be a good algorithm for solving the first problem as well in a similar fashion, if s and r were constants, you're right. $\endgroup$ – Phylliida Nov 23 '14 at 22:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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