20 February 2009

Motion of zeroes of complex polynomials

Consider the polynomial f(z) = (z-1)(z-2)...(z-20). Clearly it has 20 roots; these are 1, 2, ..., 20.

Now consider the polynomial g(z) = -z20. It also has 20 roots, namely the origin with multiplicity 20.

And consider h(z) = t f(z) + (1-t) g(z), as t varies from 0 to 1. (Most of the "action" happens when t is very near 0 or 1, so this probably isn't the best parametrization.) Now, as t varies, you can find the roots numerically. Imagine the roots as twenty particles moving around in the plane. What happens, basically, is that as t increases roots start by sliding along the real axis, towards each other in pairs -- this is what you expect if you just plot f(z) as a real polynomial. (Interestingly, the collision appears to be perfectly elastic.) They then bang into each other and head off in the positive and negative imaginary directions. And eventually they curve around and approach the origin, on paths spaced 18 degrees apart. (I can try to produce graphics.)

There's nothing special about these polynomials -- that is, I suspect that something like this happens more generally. This is actually just an extension of an example in Peter Henrici's Applied and computational complex analysis (volume 1, p. 282) -- Henrici says that J. H. Wilkinson looked at the polynomial f(z) - 2-23z19 and saw that it had five pairs of complex conjugate zeroes.

But it seems like there should be some sort of general theory of the way that roots of families of polynomials "move around" in the plane. (And if there isn't, why not?) Does the situation I've described ring a bell for anybody?


Anonymous said...

The situation reminds me of the idea of a family of schemes. The roots of tg(X) + (1-t)f(X) form the closed points of Spec C[X]/(tg(X) + (1-t)f(X)), which is a family of schemes, as the fibers over t of Spec C[X,T]/(Tg(X) + (1-T)f(X)). There are also general results on the roots of polynomials in fields complete with respect to an absolute value, which are especially useful in algebraic number theory (e.g. to prove that the set of extensions of a complete field of a given degree is finite, together with Krasner's lemma). These results say that two monic polynomials very close to each other have very close roots. Though that, of course, doesn't answer your general question on the behavior of the roots, but it seemed relevant.

Anonymous said...

This is a common example in numerical analysis classes. Finding roots of a polynomial is an ill-conditioned problem: tiny changes in the problem can lead to enormous changes in the solution. Something about evenly spaced roots makes the problem ill-conditioned.

Unknown said...

A very similar setup is used to solve systems of multivariate polynomial equations. Start with a system you know the solutions to, use a parameter t (exactly like in your post) to move it to a system you want to know the solutions to, and trace the paths of the roots numerically as t goes to 1. This is called homotopy continuation; one of the more famous implementations is PHCpack. So there are people (not me) who know a lot about what happens to the roots in the multivariate case; presumably the univariate case is a simpler special case that's particularly well-understood (but I'm just guessing about that).

Unknown said...

I think this is very similar to root locus analysis, which is a major element of control theory.

Anonymous said...

"eventually they curve around and approach the origin, on paths spaced 18 degrees apart."

I'd like to explain why this part of your description is right. Let f(z) be any polynomial of degree <= 20, with nonzero constant term and set g_t(z) = z^{20} + t f(z). I claim that, as t goes to zero, the roots of g_t will approach zero on twenty paths spaced at equal angles. Proof sketch: the field \bigcup_{n=1}^{\infty} C((t^{1/n})) is algebraically closed, so g_t has twenty roots in this field. Each such root looks like

a t^e+ higher order terms

for some complex number a and some rational exponent e.

Comparing lowest order terms in the equation
(a t^e + ...)^{20}=t f(a t^e+..), we deduce that e is 1/20 and a is one of the twentieth roots of f(0). More specifically, there is one root for each twentieth root of f(0). For t small, these power series are convergent, so you can see the actual movements of the root by plugging in t. You will then see the roots move in toward zero at equally spaced angles.

More generally, if g_t(z) is any polynomial whose coefficients depend on t, the behavior of the roots of g_t near the origin can be described in terms of the Newton polygon of g_t.

Anonymous said...

I heard a talk today on W-spin structures. Part of the data of a W-spin structure is a polynomial with a high-order isolated zero at the origin; as part of the theory this polynomial is perturbed to get zeros of order 1.

The really intriguing part (to me) is that you can associate these polynomials to dynkin diagrams.

Daniel Doro Ferrante said...

Given that JG made a comment about "root locus"… i think i can say the following: this scenario reminds me very much of "Lee-Yang Zeros" in Physics… a "phase transition phenomena", where the zeros of a Partition Function (which is the analogue of the "Transfer Function" in the "root locus" business, i.e., control theory ;-) coalesce, pinching an axis.

This has an intimate relation with Stokes Phenomena and Catastrophe Theory.

Just my 2¢…