Understanding Sturm's theorem

Question

I am having trouble understanding why the Sturm theorem works. I understand how to calculate a Sturm sequence.

However, I haven't got a clue how the change of signs of the polynomials in the sturm sequence at the boundary of $[a,b]$ is related to the number of zeros of $f$ in this interval. How can this feel natural?

Addendum:

The Spanish Wikipedia article on the Sturm theorem features some images explaining the theorem. This helped me a little. Maybe someone can make more out if it than I can.

Answer 1

So the main idea behind Sturm's theorem is very simple. The idea is the recurrence (in the Spanish Wikipedia page here (note : translate to English, the translation is decent, or test your Spanish out!) given by : $$ f_{n+1}(x) = q_nf_{n}(x) - f_{n-1}(x) $$ where $f_{n+1},f_n,f_{n-1}$ are polynomials with $f_{n+1}$ being the remainder when $f_{n+1}$ is divided by $f_n$. This recurrence alone does all the "natural" lifting that the Sturm lemma requires. Why? Because in one shot, this recurrence establishes some properties between the roots of $f_{n+1},f_n, f_{n-1}$, and the behaviour of these functions in intervals around those roots. Let me quickly explain all the lifting this recurrence does.

• The root transfer property : Let $\alpha$ be a root that is common to both $f_{m}$ and $f_{m-1}$ for some $m$. Then, it will be a root of $f_{m-2}$ as well, because of the recurrence. Then it's a root of $f_{m-1}$ and $f_{m-2}$ as well, and therefore of $f_{m-3}$.

  • Like this, the root gets "carried" to become a root of all $f_k$ for $k \leq m$, IF it is a root of $f_{m}$ and $f_{m-1}$. In particular, every $\alpha$ that is a root of both $f_{m}$ and $f_{m-1}$ for some $m$, will also be a root of $f_0$. Thus, the nature of the final $f$ is important.

  • BUT : Because the degrees of $f$ are decreasing, the last $f$ will in fact be some polynomial of small degree, that will be easy to spot and factorize. This way, what happens is that multiple roots of the sequence are reflected in the final $f$. This is important.

  • The roots also get carried UP : because $f_{m+1} = q_mf_m - f_{m-1}$, the root $\alpha$ will also be a root of $f_{m+1}$, then similarly of $f_{m+2}$ and so on. So at the end of all this : a root common to consecutive functions is common to all the functions.

• The sign-reversal property : Let $\alpha$ be a root of $f_n$. Then, at $\alpha$, we have $f_n(\alpha) = 0$ so $f_{n+1}(\alpha) = -f_{n-1}(\alpha)$. This is sign-reversal : the sign at the root of $f_n$ being opposite for $f_{n+1}$ and $f_{n-1}$. (Or both are zero, in which case we come back to the zero carrying property).

These properties are the two KEY properties that come from the recurrence relation. The root transfer property, and the sign reversal property. Let us now see what happens.

---

Now, we go back to our choice of first functions for the Sturm theorem i.e. recall that $f_{n}(x) = p(x)$ and $f_{n-1}(x) = p'(x)$, the derivative of $x$. Furthermore, we assumed that $p(x)$ is a polynomial that has only simple roots i.e. roots with multiplicity $1$. That is, for no real $\alpha$ does $(x-\alpha)^2$ divide $p(x)$.

But, this property dovetails with the root transfer and the sign-reversal property beautifully :

• If $p$ is a polynomial with only simple roots, then one can see that (1) $p$ and $p'$ don't have common roots and (2) between any two roots of $p$ lies a root of $p'$ (this follows from Rolle's theorem). Now, by using the root transfer property, we can see that NO TWO $f_{m},f_{m-1}$ can share a common root! Because if they did, then lifting up the root will tell us that $p$ and $p'$ have that root common as well, a contradiction! Hence, we've managed to use just the recurrence and derivative properties to get a sequence of polynomials such that no two consecutive polynomials can share a root.

  • Note that the last polynomial $f_0$ in the sequence will be a constant polynomial, but it cannot be the zero polynomial(why? Because then $f_0,f_1$ will share a root obviously!). So this polynomial is either positive or negative.

• Suppose that $\alpha$ is a root of $p$. Then, because $p'$ can't have a root there, this means that $p'$ is either greater than, or less than zero. But more importantly, it means that $p$ changes sign at $\alpha$, because the derivative's non-negativity will tell you that $p$ is either strictly increasing or decreasing in a neighbourhood of $\alpha$ and therefore must change sign at $\alpha$.

  • Furthermore, note that if $p'>0$ then $p$ is increasing so there's a $-$ to $+$ sign change, and if $p'<0$ then $p$ is decreasing so there's a $+$ to $-$ sign change any root. This means : roots of $p$ link to sign changes of $p$ by virtue of $p$ being simple, and the changes in sign are provided by the sign of the derivative at these points.

So what's happened, is that the fact that we started out with $p$ and $p'$ , and the fact that our recurrence is of a certain kind, give us very natural relations between the roots of various $f_i$ and the sign changes of these $f_i$ at roots of nearby $f_i$. All this will move very smoothly into gear when we see what happens when we look at the sign-sequence.

The reason why we are looking at the change-in-sign sequence , is because let's say I take a sequence of signs like $+,-,+,+,-$ etc. Now, if I change one sign, then the number of changes of sign will depend ONLY UPON the signs which are NEXT to it. That's exactly why we have the two-term recurrence : to see how much one sign changing affects the change-in-sign count , you only need to observe it's neighbours. See how natural this feels now.

---

Let $\alpha$ be some real number. Now, what we are going to do is look at the sequence given by $p(\alpha),p'(\alpha), f_{n-2}(\alpha), f_{n-3}(\alpha),...,f_{0}(\alpha)$, and we are going to be looking for the number of sign-changes in this sequence, leaving zeros out. So for example, $1,0,-4,10$ has two sign changes. We call the number of changes as $\sigma(\alpha)$.

What we do, is move from left-to-right and then see what happens to $\sigma$.

• Suppose that $\alpha$ is NOT a root of any of the $f_i$. Then, by continuity, none of the $f_i$ have a root in a neighbourhood of $\alpha$ so $\sigma(\alpha)$ is constant in a neighbourhood of $\alpha$.

• Suppose that $\alpha$ is a root of , say $f_m$ for $n>m>0$. Then, we know that $\alpha$ is not a root of either $f_{m-1}$ OR $f_{m+1}$, and therefore in a neighbourhood of $\alpha$, the signs of these quantities remain constant and opposite to each other. Thus, in a neighbourhood of $\alpha$, the sign sequence at $m+1,m,m-1$ either reads like $+,-,-$ or $+,+,-$ or $-,-,+$ or $-,+,+$. So the sign change across this part is the same for all these combinations i.e. one sign change, in a neighbourhood of $\alpha$. Furthermore, even if $\alpha$ is a root of two common $f_i,f_j$ then they will have separate $+,-,-$-type blocks on which the sign change remains $1$ throughout a neighbourhood of $\alpha$.

  • The upshot of all this, is that $\sigma$ doesn't change at a root of $f_m$!

• Suppose $\alpha$ is a root of $p$. Then, obviously $\alpha$ is not a root of $p'$ so the sign for $p$ flips but that for $p'$ stays constant, so the number of sign-changes increases by $1$!

If you notice the above, we have shown that:

$\sigma(x)$ increases by $1$ at every root $x$ of $p$, and is constant elsewhere.

Therefore, the number of roots of $p$ in $[a,b]$ is obviously given by $\sigma(b) - \sigma(a)$.

Now, you may hopefully understand the Sturm algorithm better. I will edit this question to present a generalization, but this I will keep for later.

---

Key points :

• The recurrence giving root-transfer and sign-reversal properties.

• The derivative properties and simplicity linking sign-changes to roots further.

• The idea that sign-changes and the two-term recurrence go together very well (see the highlighted box).

• The final proof where everything comes together splendidly.

I used this as a reference as well, but I'll hopefully have time to put in the generalization as well.