46
$\begingroup$

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.

  • 1
    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.2012-12-12
  • 3
    @LieRyan Well, not never. Consider multiplying $2x^2$ and $3x^3$ over $\mathbb Z/6\mathbb Z$...2012-12-12

3 Answers 3

30

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

  • 0
    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?".2012-12-11
104

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

  • 9
    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 irreducibility2012-12-11
  • 6
    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)`.2012-12-11
45

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

  • 0
    Very nice example!2012-12-11
  • 0
    i like this example, two polynomials with $n+1$ terms multiplied together, the result coalesces into two terms! fantastic2014-10-21
  • 0
    I like it. For example taking $n=5$ gives: $$(x^5+2x^4+2x^3+2x^2+2x+1)(x^5-2x^4+2x^3-2x^2+2x-1) = x^{10}-1$$ Of 36 product terms, everything vanishes but 2 terms, the most significant and the least significant one. An example where _less_ than 2 terms survive is impossible.2017-04-15