Results 1 to 12 of 12
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By emakarov

Math Help - polynomials with nonzero terms

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    64

    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??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1

    Re: polynomials with nonzero terms

    Quote Originally Posted by dannyc View Post
    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:
    (ax + b)(cx^2 + dx + e) = ax(cx^2 + dx + e) + b(cx^2 + dx + e)

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

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

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    64

    Re: polynomials with nonzero terms

    Indeed, this one is a scratcher for sure--but assuredly it should be mn..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1

    Re: polynomials with nonzero terms

    Quote Originally Posted by dannyc View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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:

    \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.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    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.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1

    Re: polynomials with nonzero terms

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

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Mar 2010
    Posts
    64

    Re: polynomials with nonzero terms

    I'm sorry but the conversations above are just too over my head..
    Is there a simpler way to break this down for a student who hasn't really worked with summations..?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1

    Re: polynomials with nonzero terms

    Quote Originally Posted by dannyc View Post
    I'm sorry but the conversations above are just too over my head..
    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
    (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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Sep 2012
    From
    Planet Earth
    Posts
    215
    Thanks
    55

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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).
    Last edited by Deveno; September 12th 2013 at 06:20 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: December 4th 2011, 03:34 AM
  2. IBVP with a nonzero BCs
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: September 26th 2010, 06:23 AM
  3. Replies: 3
    Last Post: June 6th 2010, 05:42 PM
  4. First Four nonzero terms in power series expansion
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: July 29th 2009, 12:44 PM
  5. Nonzero numbers? (587)
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 22nd 2008, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum