Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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 \mod 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$?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Or, what Qiaochu said... –  George Lowther Feb 20 '11 at 0:11
    
I guess that's what I was missing: $x^{k+n}$ rem $(x^n-1)$ = $x^k$. I will study what @Qiaochu said though. –  user2468 Feb 20 '11 at 0:38

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.