Monday, July 16, 2007

Newton's Identities: Newton's Formula

Newton's identities (see here for an introduction to Newton's identities) are relationships between the roots of a cubic polynomial and its coefficients. They were first presented by Albert Girard but were presented in even greater detail independently by Sir Isaac Newton.

In today's blog, I will present Newton's formula and show how it leads to Newton's identities. In a future blog, I will provide the proof for the formula.

Definition 1: Newton's Formula for Newton's Identities

For a polynomial of degree n, with roots { r1, ..., rn }:

For any integer i, let si be the sum based on the roots:

si = r1i + r2i + ... + rni.

For any integer j, Let σj be the elementary symmetric polynomial for j in n [see here for details if needed on elementary symmetric polynomials]

Then, Newton's formula is:



where σ0 = 1 and if k is greater than n, σk=0.

We can now use it to build some equations for si and σj.

If k=1, then we have:

s1 = σ1

If k ≥ 2, then we have:

sk = ∑ (i=1, k-1) (-1)i+1sk-iσi + (-1)k+1k

Using the above formula gives us:

s1 = σ1

s2 = s1σ1 - 2σ2

s3 = s2σ1 - s1σ2 + 3σ3

s4 = s3σ1 - s2σ2 + s1σ3 - 4σ4

s5 = s4σ1 - s3σ2 + s2σ3 - s1σ4 + 5σ5

...

Now, building each formula based on the previous formula gives us the following formulas for sk in term so of σi:

s1 = σ1

s2 = s1σ1 - 2σ2 = (σ11 - 2σ2 = σ12 - 2σ2

s3 = s2σ1 - s1σ2 + 3σ3 = (σ12 - 2σ21 - (σ12 + 3σ3 = σ13 -3σ1σ2 + 3σ3

s4 = s3σ1 - s2σ2 + s1σ3 - 4σ4 = σ1( σ13 -3σ1σ2 + 3σ3) - σ212 - 2σ2) + σ31) - 4σ4 =

= σ14 - 3σ12σ2 + 3σ1σ3 - σ12σ2 + 2σ22 + σ1σ3 - 4σ4 =

= σ14 -4σ12σ2 + 4σ1σ3 + 2σ22 - 4σ4


...

Further, we can use these same formulas for each σi so that:

σ1 = s1

σ2 = (1/2)[s1σ1 - s2]

σ3 = (1/3)[s3 - s2σ1 + s1σ2]

σ4 = (1/4)[-s4 + s3σ1 - s2σ2 + s1σ1

σ5 = (1/5)[s5 - s4σ1 + s3σ2 - s2σ3 + s1σ4]


Now, I will show these equations can be used to derive Newton's identities for cubic polynomials (that is, where n = 3). [See here for review of Newton's identities] where I am assuming an equation of the following form:

x3 + bx2 + cx + d = 0

Here are the justifications for each formula presented previously.

Identity 1:
r + s + t = -b

Proof:

σ1 = r + s + t
[See Definition 1, here]

σ1 = (-1)1(b) = -b
[See Lemma 1, here]

QED

Identity 2: r2 + s2 + t2 = b2 - 2c

Proof:

s2 = r2 + s2 + t2 [See Definition 1 above]

s2 = σ12 - 2σ2 [See formula above]

σ12 - 2σ2 = ((-1)1b)2 - 2(-1)2(c) = b2 - 2c.

QED

Identity 3: r3 + s3 + t3 = -b3 + 3bc - 3d

Proof:

s3 = r3 + s3 + t3 [See Definition 1 above]

s3 = σ13 -3σ1σ2 + 3σ3 [See formula above]

σ13 -3σ1σ2 + 3σ3 = [(-1)1b]3 - 3(-1)1b(-1)2c + 3(-1)3d =

= -b3 +3bc -3d.

QED

Identity 4: rs + rt + st = c

Proof:

σ2 = rs + rt + sr + st +tr + ts [See Definition 1, here]

σ2 = (-1)2c = c

QED

Identity 5: r2s + r2t + s2r + s2t + t2r + t2s = -bc + 3d

Proof:

(rs + rt + sr + st +tr + ts)(r + s + t) - 3rst = r2s + r2t + s2r + s2t + t2r + t2s

(rs + rt + sr + st +tr + ts)(r + s + t) - 3rst = σ2σ1 - 3σ3 = (-1)1b(-1)2c - 3*(-1)3d = -bc + 3d.

QED

Identity 6: r3s + r3t + s3r + s3t + t3r + t3s = b2c - 2c2 - bd

Proof:

(r3 + s3 + t3)(r + s + t) - (r4 + s4 + t4) = r3s + r3t + s3r + s3t + t3r + t3s

(r3 + s3 + t3)(r + s + t) - (r4 + s4 + t4) =( s3)(σ1) - s4

( s3)(σ1) - s4 = (σ13 -3σ1σ2 + 3σ3)(σ1) - (σ14 - 4σ12σ2 + 4σ1σ3 + 2σ22 - 4σ4) =

= σ12σ2 - σ1σ3 - 2σ22 + 4σ4 = [(-1)b]2(-1)2c - 2[(-1)2c]2 - [(-1)b(-1)3d] =

= b2c - 2c2 - bd + 0 = b2c - 2c2 - bd

QED

Identity 7: r2s2 + r2t2 + s2t2 = c2 - 2bd

Proof:

r2s2 + r2t2 + s2t2 = (1/2)(r2 + s2 + t2)(r2 + s2 + t2) - (1/2)(r4 + s4 + t4) - =

= (1/2)s2*s2 - (1/2)s4 =

= (1/2)(σ12 - 2σ2)(σ12 - 2σ2) - (1/2)( σ14 - 4σ12σ2 + 4σ1σ3 + 2σ22 - 4σ4) =

= (1/2)σ14 - 2σ12σ2 + 2σ22 - (1/2)σ14 + 2σ12σ2 - 2σ1σ3 - σ22 + 2σ4 =

= σ22 - 2σ1σ3 + 2σ4 =

= (c)2 - 2*(-1)(b)(-1)(d) + 2*(0) = c2 -2bd.

QED

Identity 8: r3s2 + r3t2 + s3r2 + s3t2 + t3r2 + t3s2 = -bc2 + 2b2d + cd

Proof:

(1) (r2s2 + r2t2 + s2t2)(r + s + t) - (rst)(rs + rt + st) =
r3s2 + r3t2 + s3r2 + s3t2 + t3r2 + t3s2

(2) (r2s2 + r2t2 + s2t2)(r + s + t) - (rst)(rs + rt + st) =

=(σ22 - 2σ1σ3 + 2σ4 )1) - (σ3)(σ2) =

= σ1σ22 - 2σ12σ3 + 2σ1σ4 - σ2σ3 =

= (-1)b(c)2 - 2(b)2(-d) + 2(-b)(0) - (c)(-d) =

= -bc2 + 2b2d + cd

QED


Identity 9: r3s3 + r3t3 + s3t3 = c3 - 3bcd + 3d2

Proof:

(1) r3s3 + r3t3 + s3t3 = (r2s2 + r2t2 + s2t2)(rs + rt + st) - (r3s2t + r3st2 + s3r2t + s3t2r + t3r2s + t3s2r )

(2) (r2s2 + r2t2 + s2t2)(rs + rt + st) - (r3s2t + r3st2 + s3r2t + s3t2r + t3r2s + t3s2r ) = (c2 - 2bd)(σ2) - (bcd - 3d2) =

=
(c2 - 2bd)(c) - (bcd - 3d2) = c3 - 2bcd -bcd + 3d2 =

= c3 - 3bcd +3d2

QED

Identity 10: rst = -d

Proof:

σ3 = rst

σ3 = (-1)3d = -d

QED

Identity 11: r2st + s2rt + t2rs = bd

Proof:

r2st + s2rt + t2rs = rst(r + s + t) = σ31 = (-1)(d)(-1)(b) = bd

QED


Identity 12: r3st + s3rt + t3rs = -b2d + 2cd

Proof:

(rst)(r2 + s2 + t2) = r3st + s3rt + t3rs

(rst)(r2 + s2 + t2) = σ3s2 =

= σ3(
σ12 - 2σ2) = (-d)(b2 -2c) = -b2d + 2cd.

QED

Identity 13: r2s2t + r2st2 + rs2t2 = -cd

Proof:

(rst)(rt + rs + st) = r2s2t + r2st2 + rs2t2

(rst)(rt + rs + st) = σ3σ2 = (-d)(c) = -cd.

QED
Identity 14: r3s2t + r3st2 + s3r2t + s3t2r + t3r2s + t3s2r = bcd - 3d2

Proof:

(rst)[(rs + rt + st)(r + s + t) - 3rst] = r3s2t + r3st2 + s3r2t + s3t2r + t3r2s + t3s2r
(rst)[(rs + rt + st)(r + s + t) - 3rst] = σ3[(σ2)(σ1) - 3σ3] =
σ3[(σ2)(σ1) - 3σ3] = (-1)d[c(-b) - 3(-1)d] = (-d)[-bc + 3d] = bcd - 3d2

QED

Identity 15: r3s3t + r3t3s + s3t3r = -c2d + 2bd2

Proof:

(rst)[(1/2)(r2 + s2 + t2)(r2 + s2 + t2) - (1/2)(r4 + s4 + t4) ] = r3s3t + r3t3s + s3t3r

(rst)[(1/2)(r2 + s2 + t2)(r2 + s2 + t2) - (1/2)(r4 + s4 + t4) ] =

= σ3[(1/2)(s2)(s2) - (1/2)s4 ] =

= σ3[(1/2)(σ12 - 2σ2)(σ12 - 2σ2) - (1/2)( σ14 - 4σ12σ2 + 4σ1σ3 + 2σ22 - 4σ4)] =

= σ3[(1/2)σ14 - 2σ12σ2 + 2σ22 - (1/2)σ14 + 2σ12σ2 - 2σ1σ3 - 2σ22 + 2*0)] =

= σ322 -2σ1σ3] = (-1)d[(c)2 - 2*(-1)b(-1)d] =

= (-d)[c2 - 2bd] = -c2d + bd2.

QED

Identity 16: r2s2t2 = d2

Proof:

r2s2t2 = (rst)2 = (σ3)2 = [(-1)3d]2 = d2

QED

Identity 17: r3s2t2 + s3r2t2 + t3r2s2 = -bd2

Proof:

(rst)(rst)(r + s + t) = r3s2t2 + s3r2t2 + t3r2s2

(rst)(rst)(r + s + t) = σ321 = (-b)d2= -bd2

QED

Identity 18: r3s3t2 + r3t3s2 + s3t3r2 = cd2

Proof:

(rs + rt + st)(rst)(rst) =
r3s3t2 + r3t3s2 + s3t3r2

(rs + rt + st)(rst)(rst) = σ232 = (c)(d)2 = cd2

QED

Identity 19: r3s3t3 = -d3

Proof:

r3s3t3 = (rst)3 = (σ3)3 = (-d)3 = -d3

QED

References