Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search