# polynomials with nonzero terms

• Sep 11th 2013, 08:57 AM
dannyc
polynomials with nonzero terms
A polynomial in x has m nonzero terms. Another polynomial in x has n nonzero terms where m < n. These polynomials are multiplied and all like terms are combined. The resulting polynomial in x has a maximum of how many nonzero terms?

The answer shows mn but why??
• Sep 11th 2013, 09:22 AM
topsquark
Re: polynomials with nonzero terms
Quote:

Originally Posted by dannyc
A polynomial in x has m nonzero terms. Another polynomial in x has n nonzero terms where m < n. These polynomials are multiplied and all like terms are combined. The resulting polynomial in x has a maximum of how many nonzero terms?

The answer shows mn but why??

An example of this:
$\displaystyle (ax + b)(cx^2 + dx + e) = ax(cx^2 + dx + e) + b(cx^2 + dx + e)$

$\displaystyle = ~ acx^3 + adx^2 + aex + bcx^2 + bdx + be$ ===> 6 terms

$\displaystyle = ~ acx^3 + (ad + bc)x^2 + (ae + bd)x + be$ ===> 4 terms

-Dan
• Sep 11th 2013, 09:25 AM
dannyc
Re: polynomials with nonzero terms
Indeed, this one is a scratcher for sure--but assuredly it should be mn..
• Sep 11th 2013, 09:27 AM
topsquark
Re: polynomials with nonzero terms
Quote:

Originally Posted by dannyc
Indeed, this one is a scratcher for sure--but assuredly it should be mn..

Are you certain that the question is asking for the number of terms after simplifying and not before?

-Dan
• Sep 11th 2013, 10:24 AM
Deveno
Re: polynomials with nonzero terms
The correct answer IS indeed mn. For example, we might have:

f(x) = x2+x+1
g(x) = x6+x3+1, in which case:

f(x)g(x) = x8+x7+x6+x5+x4+x3+x2+x+1, which has 9 = 3*3 terms

(it might not be possible to "combine and simplify", because there may be NO "overlap" of equal terms of xk, for any given k).

The general formula for polynomial multiplication is:

$\displaystyle \left(\sum_{i=0}^m a_ix^i \right)\left(\sum_{j=0}^nb_jx^j \right) = \sum_{k = 0}^{m+n}\left(\sum_{i+j = k} a_ib_j \right)x^k$

So it is tempting to think that the number of terms will not exceed m+n, but in the formula above, the number of 0 terms in the first polynomial could be fairly large, with just enough "gaps" in the non-zero terms to completely put a polynomial with the number of terms in the second polynomial "in the gaps".

As is easily verifed (you can use induction), the number of possible terms (with NO combining of "like terms", which may not exist) of a product of a sum with m summands, and a sum with n summands, is a sum with mn summnads.
• Sep 11th 2013, 10:36 AM
emakarov
Re: polynomials with nonzero terms
Yes, I was thinking the same thing. If f(x) is a polynomial, let terms(f) denote the number of nonzero terms in f(x). I believe the statement says: For all polynomials f and g, if terms(f) < terms(g), then terms(fg) <= terms(f)terms(g), and this upper bound is sharp, i.e., the inequality turns into an equality (only) for some f, g. The fact that the inequality is strict for some f and g or even for some classes of polynomials does not refute this statement.
• Sep 11th 2013, 10:48 AM
topsquark
Re: polynomials with nonzero terms
Aha! I didn't see the inequality in the OP's statement. Sorry about that.

-Dan
• Sep 11th 2013, 02:20 PM
dannyc
Re: polynomials with nonzero terms
I'm sorry but the conversations above are just too over my head.. (Speechless)
Is there a simpler way to break this down for a student who hasn't really worked with summations..?
• Sep 11th 2013, 02:39 PM
emakarov
Re: polynomials with nonzero terms
Show that the product of two polynomials with m and n terms, respectively, has <= mn terms. This is easy if you know how polynomials are multiplied. Then note Deveno's example where the product, after adding like terms, has exactly mn terms. Thus, saying that the product has < mn terms (instead of <= mn terms) is incorrect. So, the maximum number of terms in a product is mn. This maximum is achieved for some pairs of polynomials, and for other pairs (as in topsquark's example) it is not.
• Sep 11th 2013, 02:49 PM
topsquark
Re: polynomials with nonzero terms
Quote:

Originally Posted by dannyc
I'm sorry but the conversations above are just too over my head.. (Speechless)
Is there a simpler way to break this down for a student who hasn't really worked with summations..?

Now that I have read the whole problem...

Think of the distributive law: a(b + c) = ab + ac.

Now for an example: Say your first polynomial has two terms (m = 2), ax^p + bx^q, and your second polynomial has three terms (n = 3), cx^r + dx^s + ex^t. Then
$\displaystyle (ax^p + bx^q)(cx^r + dx^s + ex^t) = ax^p(cx^r + dx^s + ex^t) + bx^q(cx^r + dx^s + ex^t)$

So there will be m terms that distribute and, one at a time, multiplies the n terms. So before simplification we have mn terms. (Simplifying will merely reduce the number of terms to less than mn.)

Can you work this into a proof?

-Dan
• Sep 11th 2013, 02:53 PM
SworD
Re: polynomials with nonzero terms
Simply, in the most general case, in the most suitable conditions, each term in one of the polynomials can generate a term for each term in the other polynomial, as though you were talking about ordered pairs. So you just multiply the two.
• Sep 12th 2013, 05:16 AM
Deveno
Re: polynomials with nonzero terms
It is easy to show that one can always pick a polynomial g(x) with n non-zero terms given a polynomial f(x) with m non-zero terms such f(x)g(x) has mn non-zero terms.

Suppose f(x) = c1xk1 + c2xk2 +...+ cmxkm, where k1 < k2 <...< km, cj ≠ 0.

Let g(x) = 1 + xkm+1 + x2km+2 +...+ x(n-1)km+n-1, for any n > m, which clearly has n non-zero terms.

then f(x)g(x) = f(x) + (xkm+1)(f(x)) + (x2km+2)(f(x)) +....+ (x(n-1)km+n-1)(f(x)).

The highest term of xjkm+j(f(x)) (for j = 0,1,...,n-2) is some (constant) multiple of xjkm+j+km = x(j+1)km+j, whereas the lowest term of

x(j+1)km+(j+1)(f(x)) is some (constant) multiple of x(j+1)km+(j+1)+k1, and:

(j+1)km+j < (j+1)km+(j+1) ≤ (j+1)km+(j+1)+k1.

Now all theses j's and k's might be confusing. Here is a concrete example:

Suppose f(x) = 1 + 3x3 + 2x5 (3 non-zero terms). To find a polynomial g(x) with 4 non-zero terms we pick:

g(x) = 1 + x6 + x12 + x18.

Then f(x)g(x) = (1 + 3x3 + 2x5) + x6(1 + 3x3 + 2x5) + x12(1 + 3x3 + 2x5) + x18(1 + 3x3 + 2x5)

As you can see the highest power of x in each grouping is less than the lowest power of x in the next grouping, so we will have 12 non-zero terms.

On the other hand, for ANY sum (polynomial or not) with m terms, say:

S = A1+...+Am, and ANY sum with n terms, say T = B1+...+Bn

ST = A1(B1+...+Bn) + A2(B1+...+Bn) +...+ Am(B1+...+Bn)

= A1B1+...+ A1Bn +...+AmB1+...+AmBn, which has mn terms (before simplification).

So the largest possible number of terms is mn, and this bound is indeed reached (for some polynomial products).