Convolution of polynomials

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

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

h = $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ h_k x^k

(17)

such that for every k = 0^...n - 1 mathend000# the coefficient h_k mathend000# is given by

h_k = $\displaystyle \Sigma_{{{i+j \equiv k \mod{\, n}}}}^{{}}$ f_i g_j

(18)

The polynomial h mathend000# is also denoted by f *_n g mathend000# or simply by f * g mathend000# if not ambiguous.

Remark 2 Observe that the product of f mathend000# by g mathend000# is

p = $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, 2n-1}}}^{{}}$ p_k x^k

(19)

where for every k = 0^...2n - 2 mathend000# the coefficient p_k mathend000# is given by

p_k = $\displaystyle \Sigma_{{{i+j = k}}}^{{}}$ f_i g_j

(20)

We can rearrange the polynomial p mathend000# as follows.

p	=	$\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ (p_k x^k) + xⁿ $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n-1}}}^{{}}$ (p_k+n x^k)
	=	$\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ (p_k + p_k+n xⁿ) x^k

(21)

Therefore we have

f * g $\displaystyle \equiv$ fg mod xⁿ-1

(22)

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

f = x³ +1 and g = 2x³ +3x² + x + 1.

(23)

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

f g	=	2 x⁶ + 3 x⁵ + x⁴ + 3 x³ + 3 x² + x + 1
	=	(2x² +3x + 1)(x⁴ - u) + 3x³ +3x² + x + 1 + (2x² + 3x + 1)u
	=	(2x² +3x + 1)(x⁴ - u) + 3x³ + (3 + 2u)x² + (1 + 3u)x + (1 + u)

(24)

For u = 1 mathend000# we obtain

f * g = 3x³ + 4x + 2

(25)

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

DFT(f*g) = DFT(f )DFT(g)

(26)

where the product of the vectors DFT(f ) mathend000# and DFT(g) mathend000# is computed componentwise.

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

f * g = f g + q (xⁿ - 1)

(27)

Hence for i = 0^...n - 1 mathend000# we have

(f * g)( $\displaystyle \omega^{{i}}_{{}}$ )	=	f ( $\displaystyle \omega^{{i}}_{{}}$ ) g( $\displaystyle \omega^{{i}}_{{}}$ ) + q( $\displaystyle \omega^{{i}}_{{}}$ )( $\displaystyle \omega^{{{i \, n}}}_{{}}$ - 1)
	=	f ( $\displaystyle \omega^{{i}}_{{}}$ ) g( $\displaystyle \omega^{{i}}_{{}}$ )

(28)

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

Remark 3 Consider the multi-point evaluation map

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

(29)

Its kernel is generated by xⁿ - 1 mathend000#. Since E mathend000# is surjective, it follows that

R[x]/ $\displaystyle \langle$ xⁿ -1 $\displaystyle \rangle$ $\displaystyle \simeq$ Rⁿ

(30)

(which is not a surprise!) and DFT mathend000# realizes this isomorphism.

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