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

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

Marc Moreno Maza
2008-03-18