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.

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

  • 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
    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