Statement

Let ${\mathbb{R}}$ be a commutative ring and let $n > 0$ be a power of $2$ . Let $f = {\Sigma}_{k=0}^{k=n-1} f_k x^k$ and $g = {\Sigma}_{k=0}^{k=2n-1} g_k x^k$ be two polynomials in ${\mbox{${\mathbb{R}}$}}[x]$ with degrees less than $n$ and $2n$ respectively. The product $h = fg$ has degree less than $3n$ and we can write

$$h = a_0 + \cdots + a_{n-1} x^{n-1} + b_n x^n + \cdots + b_{2n-1} x^{2n -1} + c_{2n} x^{2n} + \cdots c_{3n-1} x^{3n-1},$$

where $a_0, \ldots, a_{n-1}, b_n, \ldots, b_{2n-1}, c_{2n}, \ldots, c_{3n-1}$ belong to ${\mathbb{R}}$ . The goal of this exercise is to show that one can compute the coefficients $b_n, \ldots, b_{2n-1}$ at the cost of multiplying two polynomials in ${\mbox{${\mathbb{R}}$}}[x]$ with degree $2n-1$ . The polynomial $b_n x^n + \cdots + b_{2n-1} x^{2n -1}$ is called the middle product of $f$ and $g$ and plays an important role as we shall see in class.