Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
No, actually I don't know: what are "the sturm's axioms"? (I am vaguely aware of Sturm's Algorithm...) –  Pete L. Clark Feb 21 '11 at 13:55
    
To @Pete L. Clark,that is a set of four axioms such that we can calculate the number of roots of an arbitrary polynomial with a set satisfying these axioms which is rarely known now, while it is in practice important in doing so. –  awllower Feb 21 '11 at 14:04
    
Though it, as I know, leads to no generalizations and further theoretical developments. –  awllower Feb 21 '11 at 14:04
    
Sturm's algorithm is intended to count roots in an interval; why should it be good for anything else? Perhaps it can give more information, like the usual GCD algorithm leading to a bilinear expression, but other than that it will be very surprising if one and the same algorithm solves several different algorithmic problems. –  Yuval Filmus Feb 21 '11 at 15:39
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? –  Arturo Magidin Feb 21 '11 at 16:25

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  awllower Mar 8 '13 at 7:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.