Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@LieRyan Well, not never. Consider multiplying $2x^2$ and $3x^3$ over $\mathbb Z/6\mathbb Z$... –  Potato Dec 12 '12 at 19:26
add comment

3 Answers

up vote 23 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
6  
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
2  
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
add comment

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

share|improve this answer
    
Very nice example! –  André Nicolas Dec 11 '12 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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