Talk:Sturm's theorem

Open interval, instead of Half-Open?

According to Basu, Pollack, Roy (2006, p. 52), Sturm's theorem yields the number of real roots in the open interval (a,b), not the half-open (a,b], or am I getting something wrong? — Preceding unsigned comment added by 141.3.74.113 (talk) 12:10, 2 January 2012 (UTC)

See the statements of Budan's theorem and Fourier's theorem and look for the "provided $p(r)\neq 0$" part. That makes the theorem work for open intervals. Without it the theorem works for half-open inrevals.Akritas2 (talk) 05:13, 26 April 2012 (UTC)

Sturm, not Fourier

Charles Sturm wrote that he had indeed been reading some of Fourier's papers when he found the ideas leading to Sturm's theorem in 1829. However, he makes it clear that his theorem was new. These papers of Fourier were published later by Navier (Analyse des équations déterminées, Paris, F. Didot, 1831). A very complete article about this history, with ALL references, was published in 1988 in Revue d'histoire des Sciences, "Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm" by Hourya Benis-Sinaceur. I render unto Sturm what belongs to Sturm. It is important to differentiate between Sturm's theorem and the Budan-Fourier theorem.

Forget Zero Values

If in a Sturm chain, a term after the first evaluates to zero, then this term can be considered +0 or -0 at will. Since that zero term will be bracketed by terms of opposite signs, the total count of sign changes will always be one as in ( +, +0, -) or (+, -0, -) etc. The sign variation may occur at either side of the zero term, but the number of variations is still one. —Preceding unsigned comment added by 70.24.61.22 (talk) 06:30, 19 February 2010 (UTC)

Error in def of Sturm chain?

The definition here is inconsistent with the Sturm chain (Sturm's one) given later in the article: Second point in the definition says:

• if $p(\xi )=0$, then $\operatorname {sign} (p_{1}(\xi ))=-\operatorname {sign} (p'(\xi ));$

However, $p_{1}(x)=p'(x)$ as defined several lines after that, so $\operatorname {sign} (p_{1}(\xi ))=+\operatorname {sign} (p'(\xi ))$ (this combined with the point above would imply that $\xi$ is a double root, which we assumed to not exist).

I just fixed this. Baccala@freesoft.org (talk) 20:06, 15 May 2009 (UTC)

Question by Krishnavedala

What if the sequence evaluates to '0' (zero)? Zero is neither negative nor positive. So, What will it be considered as and why? I have seen it being considered as positive value .. but, did not find any reason. --Electron Kid (talk) 21:43, 12 March 2008 (UTC)

For counting sign changes, treat the zero as not there. I.e. +1, 0, +1 has 0 sign changes. -1, 0, -1 has 0 sign changes. +1, 0, -1 has one sign change. 81.32.98.44 (talk) 19:13, 5 October 2008 (UTC)

Square-free stronger than needed?

As far as I can tell, the requirement that $p$ be square-free is stronger than needed for the proof. The proof only uses the square-free property to show that $p_{m}(\xi )\neq 0$; non-constant $p_{m}$ sampled at a $\xi$ that is not one of its roots should still allow the same proof to work. Put another way, if $p_{m}(\xi )\neq 0$ then $\sigma (\xi )$ is the same for $p$ and $p/p_{m}$.

Luther 14:02, 7 October 2009 (UTC) —Preceding unsigned comment added by Luther Tychonievich (talk • contribs)

The requirement that p be square-free is completely redundant. Sturm's theorem holds for all polynomials, provided the numbers a, b mentioned in the statement are not multiple roots of p.—Emil J. 18:25, 3 December 2010 (UTC)

Example

This article needs an example or two. --Asmeurer (talk ♬ contribs) 04:11, 21 May 2010 (UTC)

"p_m doesn't change sign"

This needs elaboration. I'm guessing it means that $sign(p_{m}(x))$ is constant on the interval $(a,b]$, and not some other interval, or even something else entirely like that the coefficients all have the same sign. (a particularly relevant concern, given the relation to Descartes' rule of signs....) A (very) brief google search doesn't immediately turn up an answer, so I'll leave fixing it to someone who actually has a reference handy. Hurkyl (talk) 00:07, 14 February 2012 (UTC)

Generalized Sturm Chains?

Erm... so what? I can understand the need for having a reference, but it really needs some more comment -- most importantly, a statement of whether or not there's a variation of Sturm's theorem that involves them. (or if there isn't one, an explicit comment to that effect) Hurkyl (talk) 00:11, 14 February 2012 (UTC)

The introductory paragraph

I propose the following text for the introductory paragraph.

In mathematics, Sturm's theorem yields a symbolic procedure to count the number of distinct real roots of a polynomial located in an interval. It was named for Jacques Charles François Sturm. Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, Sturm's theorem gives information about their location, albeit limited only to the real roots and without counting multiplicity.

The older versions of this paragraph omitted the key aspect of Sturm's theorem: that it gives location information. In regards to the most recent revision, Sturm's theorem does not enumerate and isolate the roots of a polynomial, although it could be used as a key component of such an algorithm. This fact is probably worth mentioning, but as an additional paragraph -- assuming it belongs in the introduction rather than its own section of the article. Hurkyl (talk) 02:46, 19 February 2012 (UTC)

No objection, except that "enumerate" == "count the number of". So Sturm's theorem does enumerate distinct real roots of a polynomial. Maxal (talk) 15:17, 19 February 2012 (UTC)

Interesting; I've always seen the term "enumerate" used for actually listing them out, as in enumeration. I didn't know it was used in other ways. Hurkyl (talk) 23:40, 19 February 2012 (UTC)

Reference to Fourier sequence

The assertion on Fourier sequence has a number of issues:

• It is wp:original research, as it is not sourced.
• If it were correct, its place would not be in the lead but in a history section or in a section about other similar sequences.
• "please note" and "ingenious" are not a correct style for an encyclopedia (see WP:Manual of style)
• The assertion is wrong: Fourier's sequence is an "ingenious modification" of Descartes rule of signs, which involves the successive derivatives, while Sturm's sequence involves only the first derivative, but involves also a remainder sequence, which does not appears at all in Fourier's sequence.

For all these reasons, I'll revert the edit introducing this assertion.

To Akritas: Reverting again my edits, without giving any reason, will be considered as disruptive edits and you could be blocked to edit for that.

D.Lazard (talk) 11:36, 19 April 2012 (UTC)

After removing the two flowery words, and moving the inappropriate lead material to a section of its own, my change was reverted with the edit summary "restored version erased by Rschwieb". Another edit to make the article comply with the MOS on casual "we" was reverted in 60 seconds as "vandalism". Akritas, such edits are considered disruptive behavior. It appears as if you are unwilling to accept any edit to your version. Please see WP:OWN before engaging in any more reverts in this manner. Rschwieb (talk) 13:45, 19 April 2012 (UTC)

Sorry Rscwieb. I thanked you in the comments.Akritas2 (talk) 07:58, 21 April 2012 (UTC)

To Lazard: STOP DISTORTING assertions I made in my papers and in the Wikipedia!! To wit,

• we never called the Vincent-Collins-Akritas method "Uspensky's method" as you repeatedly claimed.
• your assertion above that " Fourier's sequence is an "ingenious modification" of Descartes rule of signs, which involves the successive derivatives, while Sturm's sequence involves only the first derivative, but involves also a remainder sequence, which does not appears at all in Fourier's sequence."

IS INDEED WRONG -- AND IT IS YOUR ASSERTION.

For the record, my assertion was" Sturm's sequence is an "ingenious modification" of Fourier's sequence" AND THIS IS IN AGREEMENT with the statement (from the topic "Sturm, not Fourier", in the beginning of this page) "Charles Sturm wrote that he had indeed been reading some of Fourier's papers when he found the ideas leading to Sturm's theorem in 1829. However, he makes it clear that his theorem was new." No one denies that Sturm's theorem is new, but (at least I personally) one cannot help but see the influence Fourier's theorem had on him.

AND, my point of view agrees BOTH (A) with that of Benis-Sinaceur Hourya. Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm. In: Revue d'histoire des sciences. 1988, Tome 41 n°2. pp. 99-132, when he states in the abstract that "... the origins of Sturm's theorem, which lay in J. Fourier's similar theorem", and (B) most importantly with that of Sturm himself. To use Sturm's own words

« Je déclare, écrit-il, que j'ai eu pleine connaissance de ceux des travaux inédits (18) de M. Fourier qui se rapportent à la résolution des équations, et je saisis cette occasion de lui témoigner la reconnaissance dont ses bontés m'ont pénétré. » (19) Puis il ajoute : « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nou veaux théorèmes que je vais énoncer. »

Akritas2 (talk) 08:12, 21 April 2012 (UTC)

Sturm's statement on the influence by Fourier's theorem

I have included a statement by Sturm showing how he was influenced by Fourier's theorem. Should this statement be translated into English??Akritas2 (talk) 09:08, 21 April 2012 (UTC)

It should be, but I will not do it myself, because the style is too elaborate for my knowledge of English. D.Lazard (talk) 09:52, 21 April 2012 (UTC)

I believe you know English very well:-))Akritas2 (talk) 11:03, 21 April 2012 (UTC)

I came up with the following translation

"It is by relying upon the principles he laid out and by imitating his proofs that I have found the new theorems which I will announce"

If someone else gets it better please let us know.Akritas2 (talk) 11:30, 21 April 2012 (UTC)

To Lazard: (Answer to the first post in #Reference to Fourier sequence. Comment added by D.Lazard (talk) 16:59, 21 April 2012 (UTC))

For the record, my assertion was : "Sturm's sequence is an "ingenious modification" of Fourier's sequence", and this is in agreement with historical facts. I have reinstated a variant of that statement with ample documentation in the lead. (You can put it in the comments/history part if you like, but I believe it is of great importance for some people to read this fact right away, because they might never get to the comments/history part). The question is :: Do we translate the french statement into english or leave it as is??

In the meantime I saw that you agree with the translation and I inserted it as well. Akritas2 (talk) 11:47, 21 April 2012 (UTC)

I agree that Sturm was inspired by Fourier, but this does not mean that Sturm's sequence is a "modification" of Fourier sequence, nor that it is "based on" Fourier's sequence. These wordings would be correct only if Sturm's theorem did not contain a completely new idea, namely the use of remainder sequences. This for this reason that I have replaced "based on" by "inspired by". D.Lazard (talk) 13:22, 21 April 2012 (UTC)

I let it stand as you put it even though I do not agree with you. As Sturm himself said, "he relied .." on Fourier's theorem, which, to me, means he used it as a basis. As it is "your page" I even changed the Budan-VAS relation to your wording. HOWEVER, I would like a THIRD opinion on this topic !! (BTW, your english becomes astonishingly perfect at times ...)Akritas2 (talk) 14:49, 21 April 2012 (UTC)

It is not "my" page. Articles are not owned by anybody (see WP:OWN). I am not even the main author of this page that I find poorly written. In particular the definition of abstract Sturm's sequences which is given is probably WP:original research. Even if it is not, for being understandable to the non specialist, such a definition should appear at the end (in the section "Generalizations") and in any case after the definition of the original Sturm's sequence. Lacking of time, I have only rewritten (before your edits) the lead to follows MOS:LEAD

About Sturm's citation: He does not claim to use any Fourier's theorem. Only to follow the principles guiding Fourier and trying to imitate his style of proofs. This enforces my opinion that there is not mathematical dependence between these results. On the other hand, VAS method uses Budan's theorem and "based on" is perfectly correct and I would prefer it in this case. I leave to you the choice of restoring or not this wording here.

D.Lazard (talk) 17:28, 21 April 2012 (UTC)

First of all thank you for cleaning up my messages. I am new to this and have already learnt a lot from you (and about you:-)). Second, I reverted to "VAS is based on Budan's theorem", but I still disagree with you. Here are the reasons why: A. Sturm himself said "m'appuyant sur" = "by relying upon" and not "having been inspired by". B. In Greek, "to rely upon" is βασίζομαι, and there you can see the word βάση which means base. I also leave it up to you to decide the wording for Sturm's method and Fourier's theorem. I simply cannot accept the word inspiration.

Akritas2 (talk) 18:27, 21 April 2012 (UTC)

Question to Lazard: Do you feel comfortable with the following statement: "VAS is based (directly) on Budan's theorem whereas Sturm's method is (indirectly) based on Fourier's theorem". I believe this has the advantage of (strictly) using Sturm's own words and avoiding the subjective word inspired. Akritas2 (talk) 05:36, 22 April 2012 (UTC)

No: Sturm was relying upon Fourier's work to find his method. But Sturm's theorem does not relies in any way to Fourier's theorem. A formulation has to be found to make this distinction clear (the "life" of a mathematical result is independent of the way it has been found). On the other hand, I do not think that "inspired" has a religious connotation: see for example the article Muse where "inspire" and its derivatives appear several times, exactly with the meaning we need here. D.Lazard (talk) 12:56, 22 April 2012 (UTC)

I agree with what you say, but the formulation does not make me happy; I have the feeling we are putting words into Sturm's mouth. Finally, how do you feel about "VAS is based on Budan's theorem, but it was Fourier's theorem that led Sturm to his own method"? Also, Lazard, I would like to kindly ask you to take a look at Budan's theorem and tell us your comments. My students and I would be very grateful.Akritas2 (talk) 17:16, 22 April 2012 (UTC)

Confusion regarding m=m′ in 5th paragraph of proof

In the fifth paragraph of the proof, there is confusion when involving the issue of multiple roots. A literal application of the definition of the canonical sequence gives me the relationship m=m′+1 rather than the m=m′ as stated, e.g. p(x)=(x-1)^2 gives p′=2(x-1), d=x-1, q=x-1, q′=1, and therefore m=m′+1. So I suspect there is a wording problem somewhere, either in the definition of canonical sequence or in the proof. 65.183.146.66 (talk) 16:40, 4 June 2015 (UTC) Just saw the confusion, rem=0 for the last item in the sequence. 65.183.146.66 (talk) 16:46, 4 June 2015 (UTC) Darn, it's back since the -rem=0 item is the m+1th one. 65.183.146.66 (talk) 16:50, 4 June 2015 (UTC) Which obviously applies to both sequences making the mth item in the first sequence non-constant. It may be correct but as before confusing. 65.183.146.66 (talk) 16:56, 4 June 2015 (UTC)

"therefore m=m′+1" is wrong: as p' divides p we have m = m' = 1. In fact, m and m' are not the degrees, but the number of divisions before getting a zero remainder. D.Lazard (talk) 17:51, 4 June 2015 (UTC)

For me, the confusion arose at the mth term in the first sequence for the polynomial with multiple roots, where the canonical sequence now fails to be a Sturm's sequence. I do realize that possibility was mentioned; I just didn't know when it would occur, and I suppose it caught me by surprise. 65.183.146.66 (talk) 10:39, 5 June 2015 (UTC)

Definition and uniqueness

The definition of a Sturm chain starts by requiring the polynomial p to be square-free. Later, we have the canonical Sturm chain — presumably, that used by Sturm — and the information that it may not be square-free. Yet, even then, "it still satisfies the conclusion of Sturm's theorem".

So, some questions:

1. If being square-free is unnecessary to the theorem, why is it needed at all in the definition?
2. Whose definition is this, anyway? (As with most of the article, we have no sources!)
3. Why are we playing fast and loose with the articles "a" and "the"? (Either the chain is unique or it isn't. If its uniqueness follows from the definition, let's state that, before using "the".)
4. (Much less important, but maybe helpful:) To give Sturm his due and give readers some historical context, why not include the date of his publication in the lead para? (There's just one date in the § History section; including more dates would help the interested reader follow the development of the art.)

yoyo (talk) 04:38, 5 November 2018 (UTC)

One must remark that the first definition of a Sturm sequence is not sourced. This is a generalization of the original Sturm sequence that seems WP:OR. It seems to have been introduced for applying Sturm's theorem with Pseudo-remainder sequences (see Polynomial greatest common divisor#Sturm sequence with pseudo-remainders).

IMO, this article deserves to be restructured by starting with original Sturm's sequence, and Sturm's theorem for square-free polynomials. Then the generalization to the non-square-free case; then the definition of the generalized Sturm sequences (given at the end of the article), and its two main applications, that of Polynomial greatest common divisor#Sturm sequence with pseudo-remainders, and that where $p_{1}(x)=p_{0}(x)q(x),$ which gives the the difference between the number of roots of p where q is positive and the number of roots of p where q is negative (together with Sturm sequence, this gives the number of roots of p where q > 0).

Are you willing to rewrite this article in this way? D.Lazard (talk) 10:33, 5 November 2018 (UTC)

I defer to your greater knowledge of the historical development, and suggest you'd be better placed to do such a rewrite, which would address most of the issues I see with the present article. However, I'm happy to help as and when I can. yoyo (talk) 13:04, 6 November 2018 (UTC)

Usage of pseudo-remainder sequences

In the paragraph "Use of pseudo-remainder sequences" there it says "...such that there are constants a_i and b_i" but "a_i" is never used again. — Preceding unsigned comment added by 62.197.243.82 (talk) 08:24, 5 February 2019 (UTC)

Nor $a_{i},$ nor $b_{i}$ are used again. They are here only for modifying Euclidean Algorithm. Typically, $a_{i}$ is a sufficiently high power of the leading coefficient of the divisor for not introducing denominators during Euclidean division, and $b_{i}$ is a common divisor of the coefficients of the remainder. For having a generalized Sturm sequence without having to test signs, one may take an even power and a negative common divisor. D.Lazard (talk) 10:09, 5 February 2019 (UTC)

Sorry for not being clear. What I meant was that the text says "...such that there are constants a_i and b_i such that b_i*p_{i+1} is the remainder of the Euclidean division of p_{i-1} by p_i". It shows how to use "b_i" (namely "b_i*p_{i+1}") but it does not explain how to use or what is a_i. Perhaps it would be more clear if it was compared to the Polynomial_greatest_common_divisor#Pseudo-remainder_sequences (that prem/alpha).

 Fixed. Typos are sometimes difficult to see when one knows the subject! Before seeing the typo, I have added some explanation between parentheses, which could be useful for some readers. D.Lazard (talk) 11:53, 5 February 2019 (UTC)

Thanks! — Preceding unsigned comment added by 62.197.243.82 (talk) 14:22, 5 February 2019 (UTC)