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/