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.
Best Answer
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.