2
$\begingroup$

As we all know, Sturm's axioms have completely solved the problem for finding the number of roots in an arbitrary interval $[a,b]$, using the derivative and forms a Sturm set.

Now my question follows naturally that is there any other use of this axiom.
When I learned the Sturm set, I thought it will be difficult to find any such set for an arbitrary polynomial, nonetheless, the use of derivatives is really marvelous, and from then on, this question has occupied a part of my mind, shouting at me, asking me to treat it seriously.

Any response is well appreciated, thanks.

Edit: The four axioms are as follows as far as I am concerned:
Given a set of polynomials ordered by natural numbers and the 0-th is the desired polynomial.
(1): $\forall i \in \{1, \ldots, n\}$, $f_{i}$ and $f_{i+1}$ do not share the same root.
(2):$f_n(x)$ does not have one root.
(3):If $\mathfrak{a}$ is a root of $f_k$, then $f_{k-1}(\mathfrak{a})$ and $f_{k+1}(\mathfrak{a})$ do not have the same sign.
(4):If $\mathfrak{b}$ is a root of f(x), then in the interval $(-\infty, \mathfrak{b})$, $f_0(\mathfrak{b})$ and $f_1(\mathfrak{b})$ do not have the same sign; and in the interval $(\mathfrak{b},\infty)$, they share the same sign.

After reading the answer by @Bill Dubuque, since I am not familiar with the theory of algorithms, I found the Sturm's set to be full of unfamiliar things. In any case, thanks very much.

  • 4
    Since, as you say, it "is rarely known now", and Pete (and I, for that matter) has come forward as one of those who don't know them, perhaps you can edit your question and state these four axioms explicitly?2011-02-21

1 Answers 1

6

Presumably by "four axioms" you refer to the properties that define a polynomial Sturm sequence. Sturm's polynomial root-counting algorithm algorithm works in any real-closed-field. Recall that a field is real if $-1$ is not a sum of squares, and a real-closed field is a real field with no proper real algebraic extension. There are many equivalent ways to characterize real-closed fields $\rm\:R\:,\:$ e.g. either $\rm\:r\:$ or $\rm\:-r\:$ has a square-root $\rm\in R$ and every odd-degree polynomial $\rm\ f(x)\in R[x]$ has root $\rm\in R\:.\:$ Alternatively: $\rm\ R\ $ is an ordered field wrt the order $\rm\ r\ge 0\iff r\ $ is a square, and $\rm\ R\ $ has the intermediate value property wrt this order.

Sturm's algorithm plays a fundamental role in the theory of real-closed fields. For example, it easily yields the uniqueness of a real-closure fixing a given order. Further it can be generalized to prove that the projection of a semi-algebraic set is semi-algebraic - a geometric form of Tarski's celebrated quantifier elimination for real-closed fields. This leads to an effective algorithm for deciding the truth of first order statements in real-closed fields - by cylindric algebraic decomposition (CAD). The algorithm simply decomposes $\rm\ R^n\ $ into a finite number of constant-sign "cylinders" and then simply inspects the sign on each component (this is completely obvious in the one-dimensional case, e.g. see here). You can read about this in any textbook on real algebraic geometry.

  • 0
    Thanks for this wonderful answer; in particular, it says that the result is not "rarely known" now, as I used to suppose. Though it is one year earlier, I still find it of gigantic interest now.Indeed this notion of real-closed fields is rather intriguing.2013-03-08