## Algorithm for polynomial square roots?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Algorithm for polynomial square roots?

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.)
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20301
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Couldn't you just substitute it in to the series for sqrt(x)?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6136
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20301
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

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).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6136
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Algorithm for polynomial square roots?

gmalivuk wrote: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.

bitwiseshiftleft

Posts: 291
Joined: Tue Jan 09, 2007 9:07 am UTC
Location: Stanford