# Finding the new zeros of a “perturbed” polynomial

Given a univariate polynomial with real coefficients, p(x), with degree n, suppose we know all the zeros xj, and they are all real. Now suppose I perturb each of the coefficients pj (for j ≤ n) by a small real perturbation εj. What are the conditions on the perturbations (edit: for example, how large can they be, by some measure) so that the solutions remain real?

Some thoughts: surely people have thought of this problem in terms of a differential equation valid for small ε that lets you take the known solutions to the new solutions. Before I try to rederive that, does it have a name? This seems like a pretty general solution technique, but perhaps it is so general as to be intractable practically, which might explain why I don't know about it.

If you ignore the smallness of the perturbation, then there is a general question here which seems like it might be related to Horn's problem: given two real polynomials p(x) and q(x) of degree n and their strictly real roots, what can you infer about the roots of p(x)+q(x)? This question is very interesting and I would love to hear what people know about it. But I'm also happy with the perturbed subproblem above, assuming it is indeed simpler.

-
You might be interested in en.wikipedia.org/wiki/Wilkinson%27s_polynomial . –  Qiaochu Yuan Nov 23 '09 at 17:09
All real and distinct? If there are even multiplicities, then in general no perturbation is allowed, I think. –  Theo Johnson-Freyd Nov 23 '09 at 22:23
Well it depends on what "direction" the perturbation is in. p(x)=x^2 can be perturbed by adding any negative constant, but no positive constant. –  j.c. Nov 23 '09 at 23:51

Assume that the roots of $p(x)$ are real and distinct. Then we may let $\mu > 0$ denote the minimum distance between any two roots. Let $q(x)$ be any polynomial of degree $< n$ such that $|q(\alpha)| < (\mu/2)^n$ for any root $\alpha$ of $p(x)$. Then I claim that $g(x) = p(x) + q(x)$ has real roots.

Note that for a root $\alpha$ of $p(x)$, we have $|g(\alpha)| = |q(\alpha)| < (\mu/2)^n$. Yet

$$|g(\alpha)| = \prod |\alpha - \beta_i|$$

where the $\beta_i$ are the roots of $g$. It follows that $g(x)$ has a root $\beta$ such that $|\alpha - \beta| < \mu/2$. By the triangle inequality, $\alpha$ is uniquely determined by $\beta$ and this inequality. In particular, $g(x)$ has exactly one root within $\mu/2$ of each root of $p(x)$. Since $g(x)$ and $p(x)$ have the same degree, this exhausts all the roots of $g(x)$. Yet if $\beta$ was complex, then $|\alpha - \beta| = |\alpha - \overline{\beta}| < \mu/2$, a contradiction.

If the roots of $p(x)$ are not distinct, then one is in trouble, as the example $p(x) = x^2$ shows.

This can be thought of as an application of the $\mathbf{R}$-version of Krasner's Lemma, and is, in particular, an (exact) analog of the argument that the splitting field of a separable polynomial $f(x)$ over the $p$-adics is locally constant.

EDIT: I am confused about your second question. Let $f(x)$ be any polynomial of degree $n$ with real coefficients. Let $A$ and $B$ denote the maximum and minimum values of $f(x)$ on the interval $[0,n]$. Choose any $M > \max(|A|,|B|)$. A polynomial of degree $n$ may be defined by specifying $n+1$ of its values. Let $p(x)$ be the polynomial of degree $n$ such that the values $p(k)$ for $k = 0,\ldots,n$ are alternatively $-M$ and $+M$. By the intermediate value theorem, $p(x)$ has $n$ real roots.

Let $q(x) = f(x) - p(x)$. The signs of $q(k)$ also alternate for $k = 0, \ldots,n$ by construction. It follows that $q(x)$ also has $n$ real roots. Yet $p(x) + q(x) = f(x)$, and thus the sum of two polynomials with real roots does not satisfy any restrictions.

-
Those are both very nice answers. In the case of the sum of two arbitrary polynomials, is there an obvious way to make the question less trivial so that it has an interesting answer? (Just out of curiosity.) –  Steve Flammia Nov 24 '09 at 4:11

There is a famous example of this in numerical analysis called Winkinson's polynomial. A tiny change to one coefficient causes the location of some roots to change dramatically. Also, the polynomial goes from all real roots to having large imaginary components. The example shows that finding roots can be an ill-conditioned problem.

-

I don't know exactly what sort of answer you are expecting. An obvious observation (which you have presumably made yourself) are that if all the roots are simple then a sufficiently small perturbation will do. Conversely, if there is a repeated root then I'm pretty sure there are arbitrarily small perturbations that have imaginary root. This is obvious for roots with even multiplicity. Actually, it's also obvious for roots with odd multiplicity because one can perturb them to have multiplicity 1 (by adding a very small multiple of (x-c), where c is the root) and thereby not having a full set of real roots.

But you seem to be asking for a more detailed answer, such as how to tell from the polynomial how small the perturbation needs to be. One thing that seems worth doing is working out the highest common factor of the polynomial and its derivative. If there are no repeated roots, then this will be 1, and if there aren't then it won't. But probably if the polynomial comes very close to having a repeated root (it might, say, be the polynomial x^2-0.0000000001) then something will show up in the calculation of the hcf. If I do Euclid's algorithm on x^2-t and 2x, then I get x^2-t=(x/2)2x-t and then 2x=(-2x/t)(-t). The very large coefficient (-2x/t) seems to be telling me that I only just managed to get a constant. Or perhaps it's easier just to say that x^2-t is almost a multiple of 2x.

Anyhow, it seems likely that if Euclid's algorithm works robustly, then you can afford bigger perturbations.

-

The following criterion might help (see for example these lecture notes):

all roots of a polynomial are real if and only if the $n \times n$ Hankel matrix defined by $H_{ij}=s_k$ for all $i+j=k-2$ is positive definite,

where $s_k$ is the sum of the $k$-th powers of the $n$ roots, i.e. $s_k = \sum_{i=1}^n x_i^k$ with your notation. These sums can be computed directly from the polynomial coefficients using Newton's identities.

-
Nice, I think the inequalities derived in those notes are the ones I was grasping for in my answer. –  j.c. Nov 23 '09 at 20:26
That's a pretty neat result! Before I wade through the lecture notes, is there a simple intuition (perhaps having to do with moments?) as to why this might be true? –  Steve Flammia Nov 23 '09 at 20:28
Well, one direction is easy. Suppose the roots are real. Let M be the Vandermonde matrix M_{ij} = (x_i)^j. Then the Hankel matrix in question is M^T M, so it is positive definite. –  David Speyer Nov 24 '09 at 0:18

One way to go about this kind of question is to realize that the set of all real polynomials of degree n, interpreted as the space R^{n+1} of its coefficients is partitioned into sets in which the "behavior of the roots" is the same. E.g. for real quadratics $a_2 x^2 + a_1 x + a_0$, one has either two real roots or two complex roots depending on whether the discriminant $a_1^2-4a_0 a_2>0$ or <0 (when it's equal to zero one has a double root).

The idea is that the behavior of the roots is the same in each chamber, where the chambers are separated by the set of polynomials that have multiple roots, i.e. where the discriminant of the polynomial is zero. This set is called the discriminant variety. (After taking logarithms, one can see the amoeba. In pictures like those, one should view the different components of the complement of the amoeba as the sets in the partition I'm talking about.)

Hence one imagines your starting polynomial p(x) as a point in the space of polynomials which is in the chamber of polynomials where all roots are real and one can figure out which perturbations keep it in this chamber by calculating the shape of the discriminant variety.

This is where my knowledge gets shaky. I believe it is known how to calculate the shape of the discriminant variety and the chambers, in terms of inequalities on the coefficients (see e.g. the answer to this question) but I was never able to figure out all the details myself. See e.g. Passare and Tsikh's article "Algebraic equations and hypergeometric series" which unfortunately is not online anywhere. Does anybody know how to do these calculations?

(See the notes in F G's answer, I think they provide a way of making what I've said more explicit. In particular, Lemma 9)

I might ask this second part as a question myself if nobody steps up to fill the rest of this answer in.

-