Algorithm for polynomial square roots?

[gmalivuk]

The long-hand method for square rooting real numbers has been mentioned here in a couple of threads.

Is there a way to adapt this method for taking the square roots of polynomials, like you can do with long division and polynomial division? (Basically, it would amount to getting a Laurent series for sqrt(p(x)) where p is a polynomial.)

[skeptical scientist]

Couldn't you just substitute it in to the series for sqrt(x)?

[gmalivuk]

for what x0 value?

Also, any reasonable polynomial square root algorithm would have to give x+1 for the square root of x^2+2x+1, for instance. An infinite series isn't going to do that.

[skeptical scientist]

Ok, what exactly is it that you want? A procedure that gives the Laurent series (about 0) for the square root of any even degree polynomial? Of course even degree polynomials have Laurent series for sufficiently large annuli, because the x^2n term dominates and has a single-valued square root (2, in fact). On the other hand, if your polynomial has odd degree you won't have a Laurent series for large annuli - your only hope is for small annuli if the other terms let you behave nicely enough somewhere that you have a single-valued square root, which isn't ensured in general.

Anyways, wouldn't any reasonable square root algorithm be analogous to the division algorithm, and therefore calculate higher order terms first and then calculate lower order terms, which would pretty much destroy all hope when you have infinitely many terms with positive degree?

Of course, if you just look in a neighborhood around some point z_0 your polynomial p is nonzero, you can get a perfectly nice Laurent expansion for sqrt(p(z)) - in fact a Taylor series expansion. And since Taylor series are unique, you should just get the Taylor series for sqrt (about p(z_0)) applied to p(z) (i.e. plug in p(z)^n for z^n, expand it out, and regroup terms so you again get a power series). Which means that if p(z) is already a square in C[z], you should get a lot of cancellations of terms in the Taylor series and be left with it's square root (since Taylor series are unique). That's what I meant by substituting it into the series for sqrt(x).

[bitwiseshiftleft]

The long-hand method for square rooting real numbers has been mentioned here in a couple of threads.

Is there a way to adapt this method for taking the square roots of polynomials, like you can do with long division and polynomial division? (Basically, it would amount to getting a Laurent series for sqrt(p(x)) where p is a polynomial.)

Sure. It's a Hensel's lemma type thing, and it's even easier than square-rooting real numbers. (It's the same as the long-hand algorithm, but with no carries.)

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.