> 
> There are $K$ vectors and all possible $K-1$-fold convolutions are needed to be determined. How many minimum number of convolutions are necessary?
> 
> 
> 

**Here is an example:**

Lets assume we have $K=4$. Then we have four vectors $v\_1$, $v\_2$, $v\_3$, $v\_4$ and the followings are to be computed:

$1.$ $v\_1\star v\_2\star v\_3$ here we need $2$ convolutions

$2.$ $v\_1\star v\_2\star v\_4$ here we need $1$ convolution because we already have $v\_1\star v\_2$ from the previous step

$3.$ $v\_3\star v\_4\star v\_1$ here we need $2$ convolutions

$4.$ $v\_3\star v\_4\star v\_2$ here we need $1$ convolution because we already have $v\_3\star v\_4$ from the previous step.

> 
> Altogether one needs $6$ convolutions which is normally $8$, if we do not use the convolutions already done in the previous steps. 
> 
> 
> 

If we use the same idea for $K=5$ 

$1.$ $v\_1\star v\_2\star v\_3\star v\_4$ here we need $3$ convolutions

$2.$ $v\_1\star v\_2\star v\_3\star v\_5$ here we need $1$ convolution

$3.$ $v\_1\star v\_2\star v\_4\star v\_5$ here we need $2$ convolutions

$4.$ $v\_5\star v\_4\star v\_3\star v\_1$ here we need $3$ convolutions

$5.$ $v\_5\star v\_4\star v\_3\star v\_2$ here we need $1$ convolutions

> 
> Altogether one needs $10$ convolutions which is normally $15$, if we do not use the convolutions already done in the previous steps.
> 
> 
> 

For $K=6$ one can reduce $24$ convolutions to $14$ and for $K=7$ instead of $35$ convolutions one only needs to calcule $19$ (added: it is actually $18$ according to my new calculation) convolutions if I am not mistaken.

**Here are the questions:**

> 
> **Question** $1$**:** I am wondering for a possible generalization to this. For example if we have $K=1000$ or $K=1000000$? How many minimum number of convolutions are necessary? 
> 
> 
> 

I can also find all $K-1$ convolutions by first convolving all $K$ vectors with each other resulting in say vector $v$. Then I go ahead with deconvolving $v$ with $v\_1$, then deconvolving $v$ with $v\_2$, etc.

In this way, I need to make only $999$ convolutions and $1000$ deconvolutions. 
However the size of devonvolutions is much bigger than the size of convolutions. For example if the length of $v\_1$ is $10$, then all convolutions are between vectors of size $1\times 10$. However, if we use the deconvolution idea, the deconvoltion will be beween a vector of size $10$ and size $9001$ for $K=1000$. Moreover, deconvolution is not always reliable.

> 
> **Question** $2$**:** which idea is the best to obtain $K-1$-fold convoltions with less number of computations for example if one wants to implement using a computer program?
> 
> 
> 

Here is the figure that I got from my examples above. The y axis is the ratio of the minimum that I found by my hands to the clairvoyent so $K(K-2)$. It is almost linear but it wont be like that forever..

[![enter image description here](https://i.stack.imgur.com/q7k48.png)](https://i.stack.imgur.com/q7k48.png)

Here is my handwork for $K=8$:[![enter image description here](https://i.stack.imgur.com/d9GUW.jpg)](https://i.stack.imgur.com/d9GUW.jpg)

> 
> So accroding to my examples, the answer should be $4K-10$, which is surprisingly linear. If true, it is also very interesting because for large $K$, one needs to have a very good strategy to achieve the minimum number of convolutions.. what should be the strategy? how can one prove it, if correct?
> 
> 
>