# Simple (?) Polynomial Result

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

1. ### 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.

Anna R., Sep 1, 2010

2. ### Chip EasthamGuest

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

3. ### The Qurqirish DragonGuest

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
4. ### Paul Sperry2/13/39Guest

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
5. ### Paul SperryGuest

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
6. ### 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
7. ### 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
8. ### Frederick WilliamsGuest

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
9. ### hagmanGuest

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
10. ### Ara M JamboulianGuest

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
11. ### George CorneliusGuest

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