# Does multiplying polynomials ever decrease the number of terms?

Let $p$ and $q$ be polynomials (maybe in several variables, over a field), and suppose they have $m$ and $n$ non-zero terms respectively. We can assume $m\leq n$. Can it ever happen that the product $p\cdot q$ has fewer than $m$ non-zero terms?

I ask this because I vaguely recall seeing a positive answer in book somewhere (probably about computation or algorithms since the polynomials were unwieldy). If anyone knows what book this is from it would be much appreciated.

-
If you meant by number of terms as degree, then no, multiplying polynomials would never decrease the degree of the resulting polynomial. If you meant by number of terms as in the number of non-zero coefficients, then others have given examples where it does happen. –  Lie Ryan Dec 12 '12 at 4:57
@LieRyan Well, not never. Consider multiplying $2x^2$ and $3x^3$ over $\mathbb Z/6\mathbb Z$... –  Potato Dec 12 '12 at 19:26

Yes, in the case of $p=q$ it can even happen. See here : http://mathworld.wolfram.com/SparsePolynomialSquare.html

-
Thanks; I'm pretty sure this is what I remember seeing, wherever it was. Sparse seems to be the key word, since anything else I typed in Google returned nothing but things like "How do you multiply polynomials?". –  Daenerys Naharis Dec 11 '12 at 5:04

$$(x^2-2x+2)(x^2+2x+2)=x^4+4.$$

-
Ah, how did I miss this one? This is exactly the example I keep in my mind to remember that having no roots does not imply irreducibility –  Daenerys Naharis Dec 11 '12 at 6:14
Generalizing; let a,b,c,d be non-zero. (x^2 + a x + b)(x^2 + c x + d) = x^4 + (a+c)x^3 + (ac+b+d )x^2 + (ad + bc) + b d. So if a+c = 0, ad + bc + 0, and ac + b+ d = 0 it works. The first eqn gives c = -a; which reduces the second equation to (a)(d-b) = 0, and since a is non-zero means b=d. Hence the last equation becomes 2b - a^2 = 0. So this works for any non-zero a of the form: (x^2 + a x + a^2/2)(x^2 - ax + a^2/2). –  dr jimbob Dec 11 '12 at 18:50

Here's an elementary example. Start with the well-known identity $x^n - 1 = (x-1) (x^{n-1} + x^{n-2} + \ldots + x + 1)$. If $n$ is odd, we can factor $x^n+1$ in a similar way by flipping the signs: $x^n + 1 = (x+1) (x^{n-1} - x^{n-2} + \ldots - x + 1)$. Now mix and match the two: \begin{align*} x^{2n} - 1 &= (x^n - 1) (x^n + 1) \\ &= (x-1) (x^{n-1} + x^{n-2} + \ldots + x + 1) (x+1) (x^{n-1} - x^{n-2} + \ldots - x + 1) \\ &= (x+1) (x^{n-1} + x^{n-2} + \ldots + x + 1) (x-1) (x^{n-1} - x^{n-2} + \ldots - x + 1) \\ &= (x^n + 2x^{n-1} + 2x^{n-2} + \ldots + 2x + 1) (x^n - 2x^{n-1} + 2x^{n-2} - \ldots + 2x - 1) \end{align*} I don't see an obvious generalization to even values of $n$.

-
Very nice example! –  André Nicolas Dec 11 '12 at 16:37