Why is polynomial convolution equivalent to multiplication in $F[x]/(x^n-1)$?

Solution 1:

Note that the product of the polynomials is given by $$ \begin{align} fg&=\sum_{k=0}^{2n-2}\sum_{i+j=k}f_ig_jx^k\\ &=\sum_{k=0}^{n-1}\left(\sum_{i+j=k}f_ig_j+\sum_{i+j=k+n}f_ig_jx^n\right)x^k\\ &=f*g +(x^n-1)\sum_{k=0}^{n-1}\sum_{i+j=k+n}f_ig_jx^k \end{align} $$ So, $fg=f*g$ mod $x^n-1$ as claimed. In mod $x^n-1$ arithmetic the terms $x^k$ and $x^{k+n}$ become the same, which is why you have a sum over $i+j=k$ mod $n$ in the expression for $c_k$.

Solution 2:

This is a special case of the isomorphism between the group algebra $K[G]$ of a group $G$ under multiplication and the algebra of finitely supported functions $G \to K$ under convolution. The isomorphism sends an element $g \in K[G]$ to the indicator function $1_g$ of $g$ and is not hard to verify explicitly.

For polynomials, take $G = \mathbb{Z}$ (and ignore negative terms); for polynomials in the context of DFT, take $G = \mathbb{Z}/n\mathbb{Z}$.