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.

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

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

$\endgroup$
  • $\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$ – Chris Brooks Dec 11 '12 at 5:04
104
$\begingroup$

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

$\endgroup$
  • 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$ – Chris Brooks Dec 11 '12 at 6:14
  • 6
    $\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 '12 at 18:50
45
$\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$
  • $\begingroup$ Very nice example! $\endgroup$ – André Nicolas Dec 11 '12 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 '14 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$ – Jeppe Stig Nielsen Apr 15 '17 at 0:11

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.