Simple (?) Polynomial Result

Discussion in 'Undergraduate Math' started by Anna R., Sep 1, 2010.

  1. Anna R.

    Anna R. Guest

    I'm working through a book and reached the result below. Verying the truth
    of the statement is claimed to be easy but I've had little luck. Any ideas
    how to proceed?

    Let f(x) be a monic polynomial in Q[x] of degree n where n happens to be
    even. Then there exist polynomials g(x) and h(x) such that f(x)=g(x)^2-h(x)
    and g(x) has degree 1/2*n and h(x) has degree at most 1/2*n-1.

    Thank you for any comments.
     
    Anna R., Sep 1, 2010
    #1
    1. Advertisements

  2. Anna R.

    Chip Eastham Guest

    I think this is analogous to the long-hand algorithm for taking a
    square
    root.

    I took a quick stab at illustrating the idea with a sixth degree
    polynomial
    but my brain seems to want sleep for some reason...

    Maybe someone else can explain the idea more clearly:

    [Methods of computing square roots (digit-by-digit) -- Wikipedia]
    http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation

    regards, chip
     
    Chip Eastham, Sep 1, 2010
    #2
    1. Advertisements

  3. let f(x) = f_0 + f_1 x + f_2 x^2 + . . . + f_(n-1) x^(n-1) + x^n
    g(x) = g_0 + g_1 x + g_2 x^2 + . . . + g_(n/2) x^(n/2);
    h(x) = h_0 + h_1 x + h_2 x^2 + . . . + h_(n/2-1) x^(n/2-1)

    (note that g_n/2 = 1 is forced)
    Then, matching g^2 coefficients (for terms x^(n/2) and higher order)
    to f wields a system of n/2 equations and unknowns (since the f_i are
    known). Working from the highest order term downward (and substituting
    solved coefficients as you go) gives you n/2 linear equations in the
    g_i, all easily solved. Now take f - g^2. Since they agree on the
    coefficients for x^n/2 and highers, the difference is a polynomial of
    degree at most n/2 - 1. That is -h.
     
    The Qurqirish Dragon, Sep 1, 2010
    #3
  4. After three tries, I'll give Google a chance.

    Write n = 2k and induct on k.

    The k = 1 case is the familiar "complete the square" from Calculus.

    Suppose f is monic with degree 2k + 2. Subtract from f the x-term and
    the constant term. Factor x^2 out of what is left. The result will be
    monic of degree 2k so the induction hypothesis applies. Apply it,
    rebuild f and check degrees.

    A word of caution: I haven't done thiis carefully and in
    detail.enhochi
     
    Paul Sperry2/13/39, Sep 2, 2010
    #4
  5. Anna R.

    Paul Sperry Guest

    This will be my fourth try through my usual server it duplicates my
    screwed up post through Google. The group alt.sci.math to which the
    original post was cross posted does not seem to exist which was causing
    my problems. Excuse the duplicate post.

    Write n = 2k and induct on k.

    The k = 1 case is the familiar "complete the square" from Calculus.

    Suppose f is monic with degree 2k + 2. Subtract from f the x-term and
    the constant term. Factor x^2 out of what is left. The result will be
    monic of degree 2k so the induction hypothesis applies. Apply it,
    rebuild f and check degrees.

    A word of caution: I haven't done thiis carefully and in detail.
     
    Paul Sperry, Sep 2, 2010
    #5
  6. Anna R.

    Anna R. Guest

    Thanks Paul! However, the degree of h(x) in the inductive step could be as
    high as k+1 when it must be at most 1/2(2*(k+1))-1=k. I would have loved a
    simple induction argument such as this.
     
    Anna R., Sep 2, 2010
    #6
  7. Anna R.

    Anna R. Guest

    Great, thanks very much indeed! I agree that this works well (except,
    trivially, that g_n/2 can also equal -1)

    let f(x) = f_0 + f_1 x + f_2 x^2 + . . . + f_(n-1) x^(n-1) + x^n
    g(x) = g_0 + g_1 x + g_2 x^2 + . . . + g_(n/2) x^(n/2);
    h(x) = h_0 + h_1 x + h_2 x^2 + . . . + h_(n/2-1) x^(n/2-1)

    (note that g_n/2 = 1 is forced)
    Then, matching g^2 coefficients (for terms x^(n/2) and higher order)
    to f wields a system of n/2 equations and unknowns (since the f_i are
    known). Working from the highest order term downward (and substituting
    solved coefficients as you go) gives you n/2 linear equations in the
    g_i, all easily solved. Now take f - g^2. Since they agree on the
    coefficients for x^n/2 and highers, the difference is a polynomial of
    degree at most n/2 - 1. That is -h.
     
    Anna R., Sep 2, 2010
    #7
  8. Here: http://forums.xkcd.com/viewtopic.php?f=17&t=5711 I found:

    "For a polynomial P, define P_j to be the j-th coefficient and higher.

    Assume that the polynomial P(x) is monic and of even degree 2i, over a
    field of characteristic other than 2. Now start the square root
    polynomial Q_i(x) at x^i. Then Q_j = Q_j+1 + (P - ((Q_j+1)^2)_{i+j} / 2
    x^i}.

    For instance, to compute the square root of P := x^4 + 4x^3 + 6x^2 + 4x
    + 1, set Q_2 = x^2. Then Q_1 = Q_2 + ((P - x^4) / 2)_3 / 2x^2 = Q_2 + 2x
    = x^2 + 2x. Q_0 = Q_2 + ((P- (x^4 + 4 x^3 + 4x^2))_2) / 2x = Q_1 + 1 =
    x^2 + 2x + 1.

    In this case, the polynomial is square, so you're done, but if it's not
    square you can make a Laurent series."

    That's quoted literally and it seems to have typos in it. I think
    what's meant is:

    For a polynomial P, define P_j to be the degree j and higher terms.

    Assume that the polynomial P(x) is monic and of even degree 2i, over
    a field of characteristic other than 2. Now start the square root
    polynomial Q_i(x) at x^i. Then

    Q_j = Q_{j+1} + ((P - (Q_{j+1})^2)/2)_{i+j} / 2 x^i}.

    For instance, to compute the square root of

    P = x^4 + 4x^3 + 6x^2 + 4x + 1,

    set Q_2 = x^2. Then

    Q_1 = Q_2 + ((P - x^4)/ 2)_3 / 2x^2
    = Q_2 + 2x
    = x^2 + 2x.

    Q_0 = Q_1 + (((P - (x^4 + 4x^3 + 4x^2))/2)_2 / 2x
    = Q_1 + 1
    = x^2 + 2x + 1.

    In this case, the polynomial is square, so you're done, but if it's
    not square you can make a Laurent series.

    I assume that, instead of continuing with negative exponents one can
    stop with a remainder, Anna's h(x).
    I tried with degree 4 and got in a muddle. So maybe my "corrections"
    were no such thing.
     
    Frederick Williams, Sep 2, 2010
    #8
  9. Anna R.

    hagman Guest

    Among all monic g of degree n/2 select one that minimizes deg(g^2 -
    f).
    Let h = g^2 - f.
    Clearly, deg h < n.
    Consider the expansion
    (g+k)^2 -f = g^2 -f + 2 g k + k^2 = h + 2 g k + k^2
    We may try k(x) = -a/2 * x^(deg(h) - deg(g)) where a is the leading
    coefficient of h.
    Then the right hand side is of degree < deg(h) (note that deg(k^2) = 2
    deg(h) - n < deg(h) ).
    This leads to a contradiction to the minimality achieved by g (as
    clearly deg(k)<n, so
    g+k is also monic of degree n/2).
    Doing so ist possible if deg(h) >= deg(g), hence we must have deg(h) <
    deg(g) = n/2

    hagman
     
    hagman, Sep 7, 2010
    #9
  10. I'm working through a book and reached the result
    f is monic with degree 2m
    As mentioned in a previous post,
    consider the quotient g when f is divided by x^2
    f(x) = x^2 g(x) + L(x) where
    g is monic with degree 2m-2 and
    L is linear.
    By the induction hypothesis,
    g(x) = h(x)^2 + a x^(m-2) + k(x) where
    h is monic of degree m-1,
    a is constant and
    degree k is < m-2
    It is then easy to check that
    x h(x) + a/2 is the square root of f

    We need a recursive algorithm / program to implement this.
     
    Ara M Jamboulian, Sep 14, 2010
    #10
  11. This is essentially an existence theorem for a square root, with remainder,
    of monic polynomials of even degree.

    It should be possible to prove it by mathematical induction.

    It's obviously true for n=2 by the usual method of completing the square.

    Suppose we have a monic polynomial f of even degree n greater than 2. Let
    f_1 be the result of dropping the two lowest degree terms and dividing by
    x^2 - i.e., the result of dividing x^2 into f and discarding the remainder.

    Then, by inductive hypothesis, there exists g_1(x) and h_1(x) satisfying

    (I) f_1 = g_1 * g_1 + h_1 .

    Multiplying by x^2, get

    (II) x^2 * f_1 = (x * g_1) ^ 2 + x^2 * h_1 .

    If we had been lucky this would have led immediately to the desired form,
    but the final term can have a degree one higher than desired. I leave it as
    an exercise to the reader to come up with a constant c to add to x * g_1,

    (III) g = x * g_1 + c,

    such that expanding (II) after substituting g - c for x * g_1 results in the
    high order term of x^2 * h_1 being eliminated.

    Note that we have ignored the two low order terms that were dropped from f
    to begin with, but it is clear that those terms have no effect on the degree
    of the result as long as n > 2, and hence can be added back in to both sides
    afterwards.

    G.Cornelius
     
    George Cornelius, Jan 16, 2011
    #11
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.