Saturday, January 17, 2009

Sturm's Theorem: Sturm Chains

Before proceeding to Sturm's Theorem, let's talk about Sturm Chains.

Definition 1: Sturm Chain

A Sturm Chain is a series of polynomials P0, ...., Pm

such that:

(1) For any value of i where i ≥ 1, if Pi(x)=0, then Pi-1(x) = -Pi+1(x)

(2) If Pi(x) = 0 then Pi+1(x) ≠ 0 and if i ≥ 1, then Pi-1(x) ≠ 0.

(3) For a sufficiently small area surrounding a zero point of P0(x), P1(x) is everywhere greater than 0 or everywhere smaller than 0.

Lemma 1: Constructibility of a Sturm Chain from a Polynomial

If a polynomial P is differentiable and has only simple roots, then it is possible to construct a Sturm Chain based on it.

Proof:

(1) Let P0 be the polynomial and P1 be the first derivative of P0.

(2) We can now use an alternate form of Euclid's Algorithm for Greatest Common Divisor of Polynomials (see Theorem 1, here) to get the following:

P0 = Q1P1 - P2
...

Pm-2 = Qm-1Pm-1 - Pm

where all deg Pi is less than deg Pi-1 and deg Pm = 0.

(3) Since P0 is simple, we know that P0 and P1 are relatively prime [See Lemma 2, here].

(4) Therefore, Pm is degree 0. [See definition 3, here for the definition of relatively prime polynomials]

(5) Now, we can show that P0, P1, ..., Pm form a Sturm Chain. Here's the reasoning.

(6) Using step #2 above, we know for i, we have the following equation:

Pi-1 = QiPi - Pi+1

(7) Assume that Pi(x) = 0.

(8) Then it follows that:

Pi-1 = -Pi+1

(9) Assume that Pi(x) = 0 and Pi+1(x) = 0

(10) Then it follows that Pi+2(x) = 0 and so on.

(12) So that Pm(x) = 0. But this is impossible since Pm is a constant (a polynomial of degree 0)

(13) Therefore, we reject our assumption in step #7 and conclude that Pi+1(x) ≠ 0.

(14) In the same way, we can show that if Pi(x) = 0, then it follows that Pi-1 ≠ 0.

(15) Finally, since P0=P is a polynomial with only simple roots and P1 = P' is its derivative, we know that (see Lemma, here), for a sufficiently small area surrounding a zero point of P0(x), P1(x) is everywhere negative or everywhere positive.

QED

References

8 comments:

Ross_Cagan@me.com said...

Hi Larry,

I stumbled on your blog and have a question. I was noting to my daughter my magic equation for calculating Pythagorean Triplets:

y = (Ax)+A
z = y+1
where...
A= (0.5x-0.5)

It works with any real number I've tried (e.g., 8, 31.5, 32.5) including fractions, negative numbers, etc, though I haven't tried many. True? I was relating the story of how describing it to my 6th grade teacher eventually got me kicked out of class (long story).

Your input would be appreciated.

Thanks...Ross
ross.cagan@mssm.edu

Larry Freeman said...

Hi Ross,

I checked your formulas and they work.

Here are my notes:

Z^2 = (y+1)^2 = y^2+2y+1 = [Ax+A]^2 + 2[Ax+A] + 1

X^2+Y^2 = X^2 + [Ax+A]^2

2A = x - 1

2[Ax+A]+1 = 2Ax + 2A + 1 = x[x-1] + [x-1] + 1 = x^2-x + x - 1 +1 = x^2

-Larry

Ross_Cagan@me.com said...

Thanks, Larry. An elegant proof.

Ross_Cagan@me.com said...

We (my daughter and I) were wondering: what other equations are used to calculate P triplets?

Larry Freeman said...

Hi Ross,

Here's a solution that I blogged about in an earlier blog entry.

Let d,p,q be any integers that you want.

z = d[p^2 + q^2]
y = d[p^2 - q^2]
x = d[2pq]

For example, if p = 2 and q = 1 and d = 2, we get:
z = (2)(5) = 10
y = (2)(3) = 6
x = (2)(4) = 8

36 + 64 = 100.

The proof can be found here.

-Larry

Ross_Cagan@me.com said...

Got it. I'm a bit confused (and looking for reasons to not work on a grant): isn't this proof for something that is different (or at least just a subset) of 'my' equation? A rule you postulate is that Z must be odd, but I don't see why that is fundamental unless you limit the set to whole numbers.

Larry Freeman said...

Hi Ross,

Actually z doesn't have to be odd. See my example where z=10.

You are right. My proof only relates to integers.

The Pythagorean Triples are usually limited to integers because it is harder to come up with integers than real numbers that satisfy x^2 + y^2 = z^2.

For example, regardless of the value of x or y, I could set z = sqrt(x^2 + y^2) to get the third triple.

I think that your method is interesting because it is not obvious that it works.

-Larry

Reliable Home Inspection said...

Hi Larry
I have a 1 page proof of Fermat's Last Theorem which I believe is the original proof that Fermat made.Check it out. Here is the link

http://www.youtube.com/watch?v=gwbHORdjcbQ

Michael