Non-linear convolution and power series

[burritoloco]

Homework Statement

Hi, suppose we have the summation
$$\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} a_j b_{i-j}^{j} x^i,$$

where the subscripts are taken modulo $n$, and $a_i^n = a_i, b_i^n = b_i$ for each $i$.

Write the above power series as a product of two power series modulo $x^n - x$.

Homework Equations

I'm only aware of the regular Cauchy (linear) convolution. That is,
$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j b_{i-j}x^i = \left( \sum_{i=0}^{n-1}a_i x^i \right) \left( \sum_{j=0}^{n-1}b_j x^j \right).$$

The Attempt at a Solution

I'm frankly not sure...

Thanks!

 

[mighty2000]

Hello, thank you for your question. I can suggest the following solution to write the given power series as a product of two power series modulo x^n - x:

1. Rewrite the given power series in terms of the linear convolution formula, as you have mentioned in the Homework Equations section. This will give you the following expression:

\left( \sum_{i=0}^{n-1}a_i x^i \right) \left( \sum_{j=0}^{n-1}b_j x^j \right) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j b_{i-j}x^i

2. Now, we can see that the given power series is a linear convolution of two power series, with the second power series being a shifted version of the first one. This means that we can write the second power series as a shifted version of the first one, i.e. b_{i-j} = a_{i-j+k}, where k is some constant.

3. Substituting this in the above expression, we get:

\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j a_{i-j+k}x^i = \left( \sum_{i=0}^{n-1}a_i x^i \right) \left( \sum_{j=0}^{n-1}a_{i-j+k} x^j \right)

4. Now, we can see that the second power series is a shifted version of the first one by k terms. This means that we can write the second power series as a power series in terms of x^k, i.e. a_{i-j+k} = c_{i-j}x^k, where c_{i-j} is some constant.

5. Substituting this in the above expression, we get:

\left( \sum_{i=0}^{n-1}a_i x^i \right) \left( \sum_{j=0}^{n-1}c_{i-j}x^{k+j} \right)

6. Now, we can see that this expression can be written as a product of two power series modulo x^n - x