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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lie Ryan
    Dec 12, 2012 at 4:57
  • 4
    $\begingroup$ @LieRyan Well, not never. Consider multiplying $2x^2$ and $3x^3$ over $\mathbb Z/6\mathbb Z$... $\endgroup$
    – Potato
    Dec 12, 2012 at 19:26

3 Answers 3

109
$\begingroup$

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

$\endgroup$
2
  • 9
    $\begingroup$ 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 $\endgroup$ Dec 11, 2012 at 6:14
  • 7
    $\begingroup$ 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). $\endgroup$
    – dr jimbob
    Dec 11, 2012 at 18:50
46
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Very nice example! $\endgroup$ Dec 11, 2012 at 16:37
  • $\begingroup$ i like this example, two polynomials with $n+1$ terms multiplied together, the result coalesces into two terms! fantastic $\endgroup$
    – Rustyn
    Oct 21, 2014 at 17:06
  • $\begingroup$ 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. $\endgroup$ Apr 15, 2017 at 0:11
30
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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?". $\endgroup$ Dec 11, 2012 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.