Return to Question

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)
• ${s-1 \choose r-1} + {s-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {s \choose r}$ (Applying the above multiple times)

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.

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.

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 {n-a_i \choose r-b_i}$$

For all integers $n, 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 {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {n-c_i \choose r-d_i}$$

For all integers $n, 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:

• ${n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}$ (Using Pascal's Triangle)
• ${n-1 \choose r-1} + {n-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {n \choose r}$ (Applying the above multiple times)

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 {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i\cdot n-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.

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)
• ${s-1 \choose r-1} + {s-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {s \choose r}$ (Applying the above multiple times)

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.

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 {n-a_i \choose r-b_i}$$

For all integers $n, r >= 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 {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {n-c_i \choose r-d_i}$$

For all integers $n, r >= 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:

• ${n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}$ (Using Pascal's Triangle)
• ${n-1 \choose r-1} + {n-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {n \choose r}$ (Applying the above multiple times)

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 >= 0$, and we're still interested in finding the smallest size $m$ such that

$$\sum\limits_{i=1}^n {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i*n-c_i \choose f_i*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.

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 {n-a_i \choose r-b_i}$$

For all integers $n, 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 {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {n-c_i \choose r-d_i}$$

For all integers $n, 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:

• ${n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}$ (Using Pascal's Triangle)
• ${n-1 \choose r-1} + {n-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {n \choose r}$ (Applying the above multiple times)

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 {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i\cdot n-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.