NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/math/9585

Text File | 1992-07-27 | 1.8 KB | 44 lines

Newsgroups: sci.math
Path: sparky!uunet!elroy.jpl.nasa.gov!nntp-server.caltech.edu!heckle!allenk
From: [e-mail] (Allen Knutson)
Subject: Re: Square roots of polynomials
Message-ID: <allenk.712272394@heckle>
Sender: [e-mail]
Nntp-Posting-Host: heckle.ugcs.caltech.edu
Organization: California Institute of Technology, Pasadena
References: <[e-mail]>
Date: Mon, 27 Jul 1992 21:26:34 GMT
Lines: 31

[e-mail] (Danny Keren) writes:

>I am looking for

>1) An algorithm that can decide whether a polynomial in one variable
>   (over the integers or reals) has a square root.

>2) An algorithm to compute such roots.

It seems the best way is to start at the constant term and figure out
inductively what the coefficients of a supposed square root must be.
This essentially calculates the Taylor series at 0. (Unsurprisingly,
this method asks you to divide by the constant term, so you have to start
by dividing by x^2n to get that to be nonzero.) If your polynomial is
of degree 2N, stop at N, and square the attempted root to see if you get
the given (i.e. if the Taylor series of the square root terminates at
that point).

Here's a more fun method that calculates a little bit more than you want.
(I have only thought about it in the real case.)

Let p be our poly, p' be its derivative, (p,p') be their GCD. The roots
of (p,p') are all the same as those of p, just raised to 1 lower power.
So p/(p,p') has all the same roots as p, but to the first power.
So if p is a square, (p/(p,p')) ^2 divides p. Reduce now to p / (p/(p,p'))^2,
which is of lower degree, and a square iff p is. (In order to finish up
with the actual root, keep a running product of the p/(p,p')'s.)

In particular, this algorithm will compute the largest square dividing p.
                                Allen K.