Convolution of polynomials

Let $n$ be a positive integer and ${\omega} \in R$ be a primitive $n$ -th root of unity.

Definition 3   The convolution w.r.t. $n$ of the polynomials $f = {\Sigma}_{0 \, \leq \, i \, < \, n} \ f_i \, x^i$ and $g = {\Sigma}_{0 \, \leq \, i \, < \, n} \ g_i \, x^i$ in $R[x]$ is the polynomial

$$h \ = \ {\Sigma}_{0 \, \leq \, k \, < \, n} \ h_k \, x^k$$ (17)

such that for every $k = 0 \cdots n-1$ the coefficient $h_k$ is given by

$$h_k \ = \ {\Sigma}_{i+j \equiv k \mod{\, n}} \ \ f_i \, g_j$$ (18)

The polynomial $h$ is also denoted by $f \, *_n \, g$ or simply by $f \, * \, g$ if not ambiguous.

Remark 2   Observe that the product of $f$ by $g$ is

$$p \ = \ {\Sigma}_{0 \, \leq \, k \, < \, 2n-1} \ \ p_k \, x^k$$ (19)

where for every $k = 0 \cdots 2n-2$ the coefficient $p_k$ is given by

$$p_k \ = \ {\Sigma}_{i+j = k} \ \ f_i \, g_j$$ (20)

We can rearrange the polynomial $p$ as follows.

$$\begin{array}{rcl} p & = & {\Sigma}_{0 \, \leq \, k \, < \, n... ...\, k \, < \, n} \ (p_k \ + \ p_{k+n} \, x^n) \, x^k \end{array}$$ (21)

Therefore we have

$$f \, * \, g \ \equiv \ fg \mod{\, x^n - 1}$$ (22)

Example 5   Let $R = {\mbox{${\mathbb{Z}}$}}/5{\mbox{${\mathbb{Z}}$}}$ , $n = 4$ , $u \in R$ and consider the polynomials

$$f \ = \ x^3 + 1 \ \ {\rm and} \ \ g \ = \ 2x^3 + 3x^2 + x + 1.$$ (23)

Assume that we want to multiply $f$ and $g$ modulo $x^4 = u$ . Then we have to arrange the product $fg$ in a form $q (x^4 -u) + r$ where $r$ has degree less than $4$ . We obtain

$$\begin{array}{rcl} f \, g & = & {2 \ {x^6}}+{3 \ {x^5}}+{x^4}... ...x^4 -u) + 3x^3 + (3 + 2u) x^2 + (1 + 3u)x + (1 + u) \end{array}$$ (24)

For $u = 1$ we obtain

$$f \, * \, g \ = \ 3x^3 + 4x + 2$$ (25)

Lemma 2   For $f,g \in R[x]$ univariate polynomials of degree less than $n$ we have

$$DFT_{\omega}(f * g) \ = \ DFT_{\omega}(f) DFT_{\omega}(g)$$ (26)

where the product of the vectors $DFT_{\omega}(f)$ and $DFT_{\omega}(g)$ is computed componentwise.

Proof. Since $f \, * \, g$ and $f \, g$ are equivalent modulo $x^n - 1$ , there exists a polynomial $q \in R[x]$ such that

$$f \, * \, g \ = \ f \, g + q \, (x^n - 1)$$ (27)

Hence for $i = 0 \cdots n-1$ we have

$$\begin{array}{rcl} (f \, * \, g)({\omega}^i) & = & f({\omega}... ... \, n} - 1) \\ & = & f({\omega}^i) \, g({\omega}^i) \end{array}$$ (28)

since ${\omega}^{n} = 1$ . $\qedsymbol$

Remark 3   Consider the multi-point evaluation map

$$E_{\omega} \, : \ \left\{ \begin{array}{rcl} R[x] & \longmapsto &... ...(1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array} \right.$$ (29)

Its kernel is generated by $x^n - 1$ . Since $E_{\omega}$ is surjective, it follows that

$$R[x] / \langle x^n - 1 \rangle \ \simeq \ R^n$$ (30)

(which is not a surprise!) and $DFT_{\omega}$ realizes this isomorphism.

If $R$ is a field, then this a special case of the Chinese Remaindering Theorem where $m_i = x - {\omega}^i$ for $i = 0 \cdots n-1$ .