Newton Sums and Monic Polynomial Roots
Date: 11/06/2004 at 21:31:27 From: Matthew Subject: Calculating Roots through something called Newton Sums Hello Dr. Math, I have come across a rather difficult problem involving the roots of a polynomial and can't seem to find how to work it. The question is as follows. There are 311 distinct solutions to the equation x^311 = 311x + 311. These solutions are designated by the 311 variables a_1,a_2,....a_311. Find the sum (a_1)^311 + (a_2)^311 + (a_3)^311 + ... + (a_311)^311. Someone has told me about how Newton Sums are used here, and that is what I cannot find. Would you please tell me how to work problems of this nature so I can apply this knowledge to the future? (And please without a calculator, just variables.) Thanks, Matthew
Date: 11/09/2004 at 10:52:44 From: Doctor Vogler Subject: Re: Calculating Roots through something called Newton Sums Hi Matthew, Thanks for writing to Dr. Math. This comes from the book "Abstract Algebra," second edition, by Dummit and Foote, pages 599 to 600. It's a great book which I would recommend for anything to do with abstract algebra EXCEPT your first introduction to the subject. If f(x) is a monic polynomial of degree n whose roots are r_1, r_2, r_3, ... r_n, then that means f(x) = (x - r_1)(x - r_2)(x - r_3) ... (x - r_n). If you multiply this all out, then you get f(x) = x^n - s_1*x^(n-1) + s_2*x^(n-2) - s_3*x^(n-3) + ... + (-1)^n*s_n where s_1 through s_n are the "elementary symmetric functions" in the n roots. That is, s_i is the sum of all n-choose-i products of i of the n roots (r_1 through r_n). So s_1 = r_1 + r_2 + ... + r_n s_2 = r_1*r_2 + r_1*r_3 + ... + r_1*r_n + r_2*r_3 + r_2*r_4 + ... r_(n-1)*r_n etc. And then you generally consider s_i = 0 if i > n. (Because there are no products of i of the n roots if i is bigger than n.) The idea is generally to pull the s_i values out of the polynomial coefficients. Don't forget to alternate the signs. Then the Newton sums are denoted p_i (that's p-sub-i, not the constant pi=3.14159...), and p_i is the sum of the i'th powers of the n roots. So p_i = r_1^i + r_2^i + r_3^i + ... + r_n^i. For example, p_1 and s_1 are the same thing, and p_0 = n. Then you have the Newton's formulas: p_1 - s_1 = 0 p_2 - s_1*p_1 + 2*s_2 = 0 p_3 - s_1*p_2 + s_2*p_1 - 3*s_3 = 0 ... p_i - s_1*p_(i-1) + s_2*p_(i-2) - ... + (-1)^(i+1)*s_(i-1)*p_1 + (-1)^i*i*s_i = 0 ... You can use Newton's formulas to get the p_i values from the s_i values. In your case, most of the s_i values are zero, so you can look for a pattern and get a formula for the p_i values. That's what I'd recommend. If you want to know how to prove the above formulas, I think you'll want to use mathematical induction, though I haven't tried it myself. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.