4
$\begingroup$

(Context: polynomial multiplication using DFT/FFT)

Let $f = \sum\limits_{i=0}^{n-1} f_i x^i$ and $g = \sum\limits_{j=0}^{n-1} g_j x^j$ be polynomials in $F[x]$ for some field $F.$ The convolution of $f$ and $g$ is given by $f \ast g = \sum\limits_{k=0}^{n-1} c_k x^k$ where $c_k = \sum\limits_{i+j \equiv k \bmod n} f_i g_j.$ The $k$th coefficient in the product $fg$ is given by $\sum\limits_{i+j = k} f_i g_j.$ Why is convolution equivalent to multiplication in $F[x]/(x^n-1)?$ Shouldn't that be mod $x^n$?

2 Answers 2

5

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$.

  • 0
    I guess that's what I was missing: $x^{k+n}$ rem $(x^n-1)$ = $x^k$. I will study what @Qiaochu said though.2011-02-20
3

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}$.