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

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

If I'm reading your question right, mn is incorrect.

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

Re: polynomials with nonzero terms

Indeed, this one is a scratcher for sure--but assuredly it should be *mn*..

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

Re: polynomials with nonzero terms

The correct answer IS indeed mn. For example, we might have:

f(x) = x^{2}+x+1

g(x) = x^{6}+x^{3}+1, in which case:

f(x)g(x) = x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+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 x^{k}, 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.

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.

Re: polynomials with nonzero terms

Aha! I didn't see the inequality in the OP's statement. Sorry about that.

-Dan

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

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.

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

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.

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) = c_{1}x^{k1} + c_{2}x^{k2} +...+ c_{m}x^{km}, where k_{1} < k_{2} <...< k_{m}, c_{j} ≠ 0.

Let g(x) = 1 + x^{km+1} + x^{2km+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) + (x^{km+1})(f(x)) + (x^{2km+2})(f(x)) +....+ (x^{(n-1)km+n-1})(f(x)).

The highest term of x^{jkm+j}(f(x)) (for j = 0,1,...,n-2) is some (constant) multiple of x^{jkm+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)k_{m}+j < (j+1)k_{m}+(j+1) ≤ (j+1)k_{m}+(j+1)+k_{1}.

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

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

g(x) = 1 + x^{6} + x^{12} + x^{18}.

Then f(x)g(x) = (1 + 3x^{3} + 2x^{5}) + x^{6}(1 + 3x^{3} + 2x^{5}) + x^{12}(1 + 3x^{3} + 2x^{5}) + x^{18}(1 + 3x^{3} + 2x^{5})

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 = A_{1}+...+A_{m}, and ANY sum with n terms, say T = B_{1}+...+B_{n}

ST = A_{1}(B_{1}+...+B_{n}) + A_{2}(B_{1}+...+B_{n}) +...+ A_{m}(B_{1}+...+B_{n})

= A_{1}B_{1}+...+ A_{1}B_{n} +...+A_{m}B_{1}+...+A_{m}B_{n}, 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).