30
$\begingroup$

One of the old classic MO questions is a of proofs of the fundamental theorem of algebra. Here is a second question about this big list:

Which of the FTA proofs can, even in principle, be mined to produce bounds on where the roots of a complex polynomial $f(z) = z^n + a_{n-1} z^{n-1} + \dots + a_0 = 0$ are, as a function of its coefficients? Which of them can further be mined to produce algorithms for locating roots?

Here my interest is not in actually having such bounds or algorithms, since clearly there are more direct ways to find them; it's in classifying the proofs based on how effective or explicit they are or can be made.

Example. The proof via Rouche's theorem proceeds as follows: we want to find $R$ such that Rouche's theorem guarantees that $z^n$ and $f(z)$ have the same number of roots in the disk of radius $R$. Rouche's theorem says that it suffices to find $R$ such that $|z^n| > |a_{n-1} z^{n-1} + \dots + a_0|$ for all $|z| = R$. This is guaranteed if we guarantee

$$R^n > |a_{n-1}| R^{n-1} + \dots + |a_0|$$

so we can pick, for example, $R > \text{max}(|a_{n-1}| + \dots + |a_0|, 1)$, and then Rouche's theorem guarantees that $f(z)$ has $n$ roots in the disk of radius $R$.

(Note that the assumption that $z$ is a root of $f(z)$ immediately gives $|z^n| = |a_{n-1} z^{n-1} + \dots + a_0| \ge |a_{n-1}| |z|^{n-1} + \dots + |a_0|$, so we already know that if any roots exist they must lie in this disk; again, my interest isn't in actually having bounds, it's in knowing what bounds can be mined from what proofs!)

This example is relatively straightforward; it's much less clear whether the proofs that proceed via e.g. Liouville's theorem, degree arguments, fundamental group computations, cohomology computations, the Lefschetz fixed point theorem, etc. can be mined to produce bounds, but I have hope that at least some of them can, possibly after substantial effort, and possibly with terrible bounds. For example one might hope to mine a bound from the Lefschetz fixed point argument by bounding how complicated the simplicial subdivision + homotopy to a simplicial map you need is, etc.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think the fundamental group argument also essentially produces roots in the same disk as the Rouche's theorem one - we want to find a circle in the complex plane that wraps $n$ times around $0$, for which it suffices to know the leading term dominates as then we can deform one to the other without touching zero. I guess this is more or less how Rouche's theorem is proved. $\endgroup$
    – Will Sawin
    Commented Sep 24, 2019 at 19:46
  • 2
    $\begingroup$ Similarly the proof via Liouville's theorem, e.g. the first paragraph at en.wikipedia.org/wiki/… and then the paragraph called "another analytic proof", shows that if $|p(z)|>|p(0)|$ whenever $|z|>r$, then there is a root $z_0$ with $|z_0|<r$. Wikipedia's proof has a gap in that it doesn't show you how to compute this $r$, but once again $\max(1,\sum|a_i|)$ is good enough. $\endgroup$
    – user44143
    Commented Oct 9, 2019 at 19:09

1 Answer 1

Reset to default
8
$\begingroup$

Here is an article with a proof where the abstract says "Moreover, the proof is constructive and immediately translates to an algebraic root-finding algorithm" : https://pnp.mathematik.uni-stuttgart.de/igt/eiserm/publications/roots.pdf . It also discusses your question with an historical last section.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The proof and the historical section are both fantastic, thank you! $\endgroup$
    – Qiaochu Yuan
    Commented Oct 15, 2019 at 20:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .