Continuity of the roots of a polynomial in terms of its coefficients

Question

It's commonly stated that the roots of a polynomial are a continuous function of the coefficients. How is this statement formalized? I would assume it's by restricting to polynomials of a fixed degree n (maybe monic? seems like that shouldn't matter), and considering the collection of roots as a a point in $F^n/\sim$ where F is the field and $\sim$ is permutation of coordinates, but is there something I'm missing? More to the point, where would I find a proof?

At least, I've seen this stated for C (and hence R); is this even true in general -- say, for an algebraically closed valued field (and hence complete non-Archimedean field because those extend uniquely)? I've seen it implied that it's not always true in the non-Archimedean case; is this correct? What's a counterexample? (If this is wrong and it is true in this generality, is it true in any greater generality?)

Answer 1

Here is a version of continuity of the roots.
Consider the monic complex polynomial $f(z)=z^n+c_1z^{n-1}+...+c_n\in \mathbb C[z]$ and factor it as $$f(z)=(z-a_1)...(z-a_n) \quad (a_k\in \mathbb C)$$ where the roots $a_k$ are arranged in some order, and of course needn't be distinct.
Then for every $\epsilon \gt 0$, there exists $\delta \gt 0$ such that every polynomial $ g(z) =z^n+d_1z^{n-1}+...+d_n\in \mathbb C[z]$ satisfying $|d_k-c_k|\lt \delta \quad (k=1,...,n)$ can be written $$g(z)=(z-b_1)...(z-b_n) \quad (b_k\in \mathbb C)$$
with $|b_k-a_k|\lt \epsilon \quad (k=1,...,n)$.

A more geometric version is to consider the Viète map $v:\mathbb C^n \to \mathbb C^n $ sending, in the notation above, $(a_1,...,a_n)$ to $(c_1,...,c_n)$ (identified with $z^n+c_1z^{n-1}+...+c_n=(z-a_1)...(z-a_n)$ ).
It is a polynomial map (and so certainly continuous!) since $c_k=(-1)^{k} s_k( a_1,...,a_n)$, where $s_k$ is the $k$-th symmetric polynomial in $n$ variables.
There is an obvious action of the symmetric group $S_n$ on $\mathbb C^n$ and the theorem of continuity of the roots states that the Viète map descends to a homeomorphism $w: \mathbb C^n / S_n \to \mathbb C^n$. It is trivial (by the definition of quotient topology) that $w$ is a bijective continuous mapping, but continuity of the inverse is the difficult part.
The difficulty is concentrated at those points $(c_1,...,c_n)$ corresponding to polynomials $z^n+c_1z^{n-1}+...+c_n$ having multiple roots.

This, and much more, is proved in Whitney's Complex Analytic Varieties (see App. V.4, pp. 363 ff).

Algebraic geometry point of view Since you are interested in general algebraically closed fields $k$, here is an interpretation for that case.
The symmetric group $S_n$ acts on $\mathbb A_k^n$ and the problem is whether the quotient set $\mathbb A_k^n /S_n$ has a reasonable algebraic structure. The answer is yes and the Viète map again descends to an isomorphism of algebraic varieties $\mathbb A_k^n /S_n \stackrel {\sim }{\to} \mathbb A_k^n $.
This is the geometric interpretation of the fundamental theorem on symmetric polynomials.
The crucial point is that the symmetric polynomials are a finitely generated $k$-algebra.

Hilbert's 14th problem was whether more generally the invariants of a polynomial ring under the action of a linear group form a finitely generated algebra. Emmy Noether proved in 1926 that the answer is yes for a finite group (in any characteristic), as illustrated by $S_n$.
However Nagata anounced counterexamples (in all characteristics) to Hilbert's 14th problem at the International Congress of Mathematicians in 1958 and published them in 1959.

Answer 2

I think there might be a proof of your statement using the following complex analysis trick (I don't know if a similar idea could work in $\mathbb{C}_p)$: if $U$ is an open subset with smooth boundary $\partial U$ consider,

$$N_{U}(p) = \frac{1}{2i \pi} \oint_{\partial U} \frac{p'(z)}{p(z)}dz$$

When it's defined, $N_U(p)$ is the number of zeros of $p$ in $U$ counted with multiplicity. Then fix a polynomial $p_0$ of degree $n$, and pick $U$ a neighborhood of its zeros. Then the map $p \mapsto N_U(p)$ is well defined and continuous in a neighborhood of $p_0$, but since it can only take integer values, it's constant and equal to $n$. So if $p$ in that neighborhood has degree $n$, all its roots are in $U$.

Answer 3

I posed this as a problem in a course on local fields I taught a little while ago. One of my students, David Krumm, solved it and wrote it up here. The context of David's solution is that $K$ is an arbitrary normed field, with some chosen extension of the norm to the algebraic closure of $K$. (If $K$ is complete or even Henselian, the norm extends uniquely; in general it does not.) Then he shows that for every $\epsilon > 0$ there exists some $\delta > 0$ so that if you perturb each of the coefficients of your polynomial $f$ by at most $\delta$, every root of $f_{\delta}$ is wtihin $\epsilon$ of some root of $f$ and vice versa. (I didn't think of this until just now, but I guess this is equivalent to saying that the sets of roots are within $\epsilon$ of each other for the Hausdorff metric.) He also shows that if $f$ itself has distinct roots, then for sufficiently small $\delta$ so does $f_{\delta}$ and then you can match up the roots in a canonical way.

After he solved this problem I looked into the literature and found a dozen papers or more on various refinements of it, including some very recent ones. At the moment these papers seem to be hiding from me, but if/when I find them I'll give some references.

Answer 4

Here is my favorite proof. Let $f:\mathbb{C}^n\to\mathbb{C}^n$ be the map taking $(a_1,\dots,a_n)\in\mathbb{C}^n$ to the coefficients of the monic polynomial $\prod_{i=1}^n(x-a_i)$. This map is clearly continuous and, since it is invariant under permuting the $a_i$, it descends to a continuous map $g:\mathbb{C}^n/S_n\to\mathbb{C}^n$ where $S_n$ acts on $\mathbb{C}^n$ by permuting the coordinates. The claim is then that this map $g$ is a homeomorphism.

It is clear that $g$ is a bijection, since every monic polynomial of degree $n$ factors as a product $\prod_{i=1}^n(x-a_i)$, uniquely up to permuting the factors. So, the hard part is to prove $g^{-1}$ is continuous.

The trick for this is to homogenize the polynomials to extend the maps to projective space so that compactness gives you continuity of the inverse for free. Let us consider $\mathbb{C}$ as a subspace of $\mathbb{CP}^1$ and $\mathbb{C}^n$ as a subspace of $\mathbb{CP}^n$ in the usual way. Then $f$ extends to a map $F:(\mathbb{CP}^1)^n\to\mathbb{CP}^n$ as follows. Identify $\mathbb{CP}^1$ with the projectivization of the space of homogeneous linear polynomials in two variables, and identify $\mathbb{CP}^n$ with the projectivization of the space of homogeneous degree $n$ polynomials in two variables. Then $F$ is just the map which takes $n$ linear homogeneous polynomials and multiplies them together to get a degree $n$ homogeneous polynomial. (To see that this extends $f$, identify $a_i\in\mathbb{C}$ with the homogeneous polynomial $x-a_iy$, so then $F$ maps $(a_1,\dots,a_n)$ to $\prod_{i=1}^n(x-a_iy)$ whose coefficients are the same as those of $\prod_{i=1}^n(x-a_i)$.)

Just like $f$, this extension $F$ in invariant under permuting the inputs, so it descends to a continuous map $G:(\mathbb{CP}^1)^n/S_n\to\mathbb{CP}^n$ which extends $g$. Just like $g$, this map $G$ is easily seen to be a bijection. But now for the magic: since $(\mathbb{CP}^1)^n/S_n$ is compact and $\mathbb{CP}^n$ is Hausdorff, any continuous bijection between them is automatically a homeomorphism! Thus $G$ is a homeomorphism.

There's one detail left to check: we now know that $g$ is a homeomorphism when you consider its domain as a subspace of $(\mathbb{CP}^1)^n/S_n$, but is that subspace topology the same as the quotient topology on $\mathbb{C}^n/S_n$? The answer is yes, because $\mathbb{C}^n$ is open in $(\mathbb{CP}^1)^n$ and invariant under the action of $S_n$, so an $S_n$-invariant open subset of $\mathbb{C}^n$ is the same thing as an $S_n$-invariant open subset of $(\mathbb{CP}^1)^n$ that happens to be contained in $\mathbb{C}^n$.

Answer 5

Suppose $P_a(z)=\sum\limits_{k=0}^na_kz^k$. Taking the partial of $P_a(z)=0$ with respect to $a_k$, we get $$ 0=P_a^{\;\prime}(z)\frac{\partial z}{\partial a_k} + z^k $$ Thus, we get that $$ \frac{\partial z}{\partial a_k}=-\frac{z^k}{P_a^{\;\prime}(z)} $$ The existence of these partial derivatives are guaranteed by the Inverse Function Theorem.

Thus, as long as $P_a^{\;\prime}(z)\ne0$ when $P_a(z)=0$, $\frac{\partial z}{\partial a_k}$ will exist and be finite. Therefore, if $P_a$ has no repeated roots, $\frac{\partial z}{\partial a_k}$ is finite.

This shows that unless $P_a$ has repeated roots, each root is a smooth function of the coefficients.

Answer 6

I think this problem can be dealt with Rouche's theorem. Recall that Rouche's theorem in complex analysis says

(Rouche's theorem) If $f(z)$ and $g(z)$ are analytic interior to a simple closed Jordan curve $C$ and if they are continuous on $C$ and $$ |g(z)|\leq |f(z)|,\quad z\in C,$$ then the function $f(z)+g(z)$ has the same number of zeros (counted with multiplicity) interior to $C$ as does $f(z)$.

Consider the polynomial $$ f(z)=a_0+a_1z+\cdots+a_nz^n,\quad a_n\neq 0.$$ Let $\zeta$ be a root of $f(z)$ and $\varepsilon>0$. To prove the continuity, we need to show that there exists a $\delta$ such that the perturbed polynomial $$ g(z)=a_0+\delta_0+(a_1+\delta_1)z+\cdots+(a_n+\delta_n)z^n$$ where $|\delta_i|\leq \delta$, has the same number of zeros as $f(z)$ inside the circle $C(\zeta,\varepsilon)$ with center $\zeta$ and radius $\varepsilon$,

We may suppose that $\varepsilon$ is smaller than the distances from $\zeta$ other zeroes of $f(z)$, so that $f(z)$ is nonzero on $C(\zeta,\varepsilon)$. Since the circle is compact, $|f(z)|$ attains its minimum $m>0$ on it.

Let $h(z)=f(z)-g(z)$. Then on $C(\zeta,\varepsilon)$, we have $$|h(z)|=|\delta_0+\delta_1z+\cdots+\delta_n z^n|\leq \delta \sum_{j=0}^{n}(|\zeta|+\varepsilon)^j. $$ Thus if we choose $\delta< \frac{m}{\sum_{j=0}^n(|\zeta|+\varepsilon|)^j}$, then $|h(z)|<|f(z)|$ on $C(\zeta,r)$. Hence by Rouche's theorem, we can conlude that $f(z)$ and $g(z)$ has the same number of zeros inside $C(\zeta,r)$.

Answer 7

In the complex case, if we ignore or forbid multiple roots and fix the degree: We can assume without loss of generality that the leading coefficient is always 1 -- normalizing the coefficients is a continuous transformation of coefficient space.

Now, then, the coefficients are a continuous injective function of the roots -- we can find them by multiplying linear polynomials with the given roots together. On the other hand, with the leading coefficient fixed to 1, both the space of possible coefficients and $\mathbb C^n/\sim$ minus multiple-root points are locally just copies of $\mathbb C^n$, so the inverse mapping from coefficients back to roots also has to be continuous.

This argument ought to work in any algebraically closed topological field (or would it? I'm not actually sure how wild a topological field is allowed to be). I'm not quite sure about how well it generalizes to situations involving multiple roots, though. The best arguments for that I can imagine right away are somewhat specific to $\mathbb C$.

Answer 8

Here is a link to a short note establishing that the roots of a polynomial are $C^\infty$ functions of the coefficients using the implicit function theorem.

Answer 9

Here's a proof without using complex analysis, differential geometry or the projective plane, and only using results from general topology.

Consider the equivalence relation on $\mathbb{C}^n$ given by $x\sim y$ iff $y = sx := (x_{s(1)}, ..., x_{s(n)})$ for some $s\in S_n$. Give $\mathbb{C}^n/\sim$ the quotient topology and let $q:\mathbb{C}^n\to\mathbb{C}^n/\sim$ be the quotient map. Note that $q^{-1}q[x+B_r] = \bigcup_{s\in S_n} (sx+B_r)$ is open, where $B_r = \{y : |y| < r\}$, so that $q[x+B_r]$ is open. If $U\subseteq \mathbb{C}^n/\sim$ is open and $q(x)\in U$ then by taking $r > 0$ such that $x+B_r\subseteq q^{-1}[U]$, it follows that $\{q(x+B_r) : x\in \mathbb{C}^n, r > 0\}$ forms a basis for $\mathbb{C}^n/\sim$. Let $$d(q(x), q(y)) = \min\{|x'-y'| : x'\sim x, y'\sim y\}.$$ Clearly $d(q(x), q(y)) = 0$ iff $q(x) = q(y)$ and $d(q(x), q(y)) = d(q(y), q(x))$. Given $x, y, z\in\mathbb{C}^n$, let $x'\sim x$ be such that $d(q(x), q(y)) = |x'-y|$. Then $$d(q(x), q(z))\leq |x'-z'| \leq |x'-y|+|y-z'| = d(q(x), q(y))+|y-z'|$$ for $z'\sim z$. Taking minimum over all $z'\sim z$, we obtain triangle inequality for $d$. So $d$ is a metric. Notice that $q[x+B_r] = \{q(y) : d(q(x), q(y)) < r\}$ so that $\mathbb{C}^n/\sim$ is metrizable with metric $d$.

Let $\sigma:\mathbb{C}^n\to\mathbb{C}^n$ map $(\lambda_1, ..., \lambda_n)$ to coefficients of $(x-\lambda_1)...(x-\lambda_n) = x^n+a_1x^{n-1}+...+a_n$. From Viete's formulas, $\sigma$ is continuous. Note the following theorem:

Theorem 1. Let $f:X\to Y$ be a continuous map between metrizable spaces. Then $f$ is perfect iff for all $x_n\in X$ such that $f(x_n)$ is convergent, it follows that $x_n$ has a convergent subsequence.

For reference of this see chapter 2 of Geometric Aspects of General Topology by K. Sakai.

Suppose that $\lambda^{(m)} = (\lambda_1^{(m)}, ..., \lambda_n^{(m)})$ is such that $\sigma(\lambda^{(m)}) = (a_1^{(m)}, ..., a_n^{(m)})$ is convergent. Note that $$|\lambda_i^{(m)}|^n = \left|\sum_{j=1}^n a_j^{(m)}(\lambda_i^{(m)})^{n-j}\right|\leq \sum_{j=1}^n |a_j^{(m)}||\lambda_i^{(m)}|^{n-j}.$$ If $|\lambda_i^{(m)}|\geq 1$ then by dividing above inequality by $|\lambda_i^{(m)}|^{n-1}$, it follows that $|\lambda_i^{(m)}|\leq \sum_{j=1}^n |a_j^{(m)}|$, thus for arbitrary $\lambda_i^{(m)}$ we have $|\lambda_i^{(m)}|\leq \max(1, \sum_{j=1}^n |a_j^{(m)}|)$ so that $\lambda_i^{(m)}$ are bounded. Thus we can take convergent subsequence $\lambda^{(m_k)}$ of $\lambda^{(m)}$. It follows that $\sigma$ is a perfect map.

Theorem 2. Let $f:X\to Y$, $q:X\to Z$ a quotient map and $g = f\circ q^{-1}:Z\to Y$ be well-defined. If $f$ is continuous/open/closed, then so is $g$.

See e.g. chapter 6 of Dugundji's Topology.

Thus since $\sigma$ is a perfect map, it follows that $\sigma\circ q^{-1}:\mathbb{C}^n/\sim\to \mathbb{C}^n$ is a closed continuous bijection, thus a homeomorphism. As a corollary we can state:

Corollary 1. Let $a_1, ..., a_n\in\mathbb{C}$ and $\lambda_1, ..., \lambda_n$ be roots of $x^n+a_1x^{n-1}+...+a_n$, $\varepsilon > 0$, then there exists $\delta > 0$ such that if $|a_i-b_i| < \delta$ then there exists an arrangement $\mu_1, ..., \mu_n$ of roots of $x^n+b_1x^{n-1}+...+b_n$ such that $|\lambda_i-\mu_i| < \varepsilon$ for $i = 1, ..., n$.

Corollary 2. If $a_1, ..., a_n\in\mathbb{R}$, let $\lambda_1, ..., \lambda_n$ be roots of $x^n+a_1x^{n-1}+...+a_n$ ordered so that $\text{Re}(\lambda_1) \leq ... \leq \text{Re}(\lambda_n)$. Define $f:\mathbb{R}^n\to\mathbb{R}^n$ as $f(a_1, ..., a_n) = (\text{Re}(\lambda_1), ..., \text{Re}(\lambda_n))$. Then $f$ is continuous.

Proof: The map $g:\mathbb{R}^n\to\mathbb{R}^n$ ordering elements of $\mathbb{R}^n$ increasingly is continuous, since if $a\in \mathbb{R}^n$ and $r_1 < ... < r_m$ are distinct among elements in $g(a)$, then for any $\varepsilon > 0$, if $0 < \delta < \min(\varepsilon, \frac{r_2-r_1}{2}, ..., \frac{r_m-r_{m-1}}{2})$ and $|a-b| < \delta$, then $|g(a)-g(b)| = |a-b| < \varepsilon$. The map $f$ is then composition of $(\sigma\circ q^{-1})^{-1}\restriction_{\mathbb{R}^n}$, the map $\mathbb{C}^n/\sim\to \mathbb{R}^n/\sim$ induced by the map $(z_1, ..., z_n)\to (\text{Re}(z_1), ..., \text{Re}(z_n))$, and the map $\mathbb{R}^n/\sim\to\mathbb{R}^n$ induced by $g$, and as such is continuous. $\square$