Sums of Powers in Terms of Symmetric Functions
Given a set of N values x1,x2,..,xN it is often useful to express
the sum of the n powers
n n n
s_n = x1 + x2 + ... + xN
in terms of the elementary symmetric functions of the x values. In
general the jth symmetric function is the sum of all products of j
distinct x values.
To illustrate, suppose we have three values x1,x2,x3, and we wish to
express the sum of the nth powers of these values in terms of the
elementary symmetric functions
U = x1 + x2 + x3
V = x1 x2 + x1 x3 + x2 x3
W = x1 x2 x3
We know that the symmetric functions are just the coefficients (up
to sign) of the polynomial with the roots x1,x2,x3. In other words,
the values of x1,x2,x3 each satisfy the polynomial
3 2
x - U x + V x - W = 0
Obviously we can multiply through by any power of x to give the
relation
n n-1 n-2 n-3
x - U x + V x - W x = 0
for any n, and since this applies to each of the roots x1,x2,x3,
we immediately have
s[n] - U s[n-1] + V s[n-2] - W s[n-3] = 0
From this it's easy to recursively generate expressions for s[n] as
a function of the symmetric functions U,V,W as follows:
n s[n]
----- --------------------------------------------------------
0 3
1 U
2 U^2 - 2V
3 U^3 - 3UV + 3W
4 U^4 - 4U^2 V + 2V^2 + 4UW
5 U^5 - 5U^3 V + 5U^2 W + 5UV^2 - 5VW
6 U^6 - 6U^4 V + 6U^3 W + 9U^2 V^2 - 12UVW - 2V^3 + 3W^2
and so on. Since U is of degree 1, V is of degree 2, and W is of
degree 3, each of these expressions is homogeneous. Also, the
expression for s[n] contains a term for each partition of n into
components of size 1, 2, or 3. For example, the partitions of
n=5 are
5 = 5
= 4+1
= 3+2 VW
= 3+1+1 U^2 W
= 2+2+1 U V^2
= 2+1+1+1 U^3 V
= 1+1+1+1+1 U^5
but the first two don't apply, because they involves components
greater than 3. Thus the expression for s[5] consists of five terms
as indicated above. Also, we can easily infer the sign of each
term based on the parity of the sum of exponents on the symmetric
functions. If the parity is the same as the parity of the leading
(monic) term, then the term is positive. Otherwise it is negative.
This leaves the question of how to determine the magnitude of the
coefficient of each term. For a function of three variables (as
in this example) we need only produce a 3-dimensional array A(i,j,k)
with the boundary values
A(i,0,0) = 1 A(0,i,0) = 2 A(0,0,i) = 3
for all positive integers i, with the understanding that A is zero
if any of it's indices is negative. Then the remaining values of
this array are filled in using the recurrence
A(i,j,k) = A(i-1,j,k) + A(i,j-1,k) + A(i,j,k-1)
Then A(i,j,k) is the magnitude of the coefficient of U^i V^j W^k.
The first several values in this array are shown below.
k=0
j
i 0 1 2 3 4 5
--- --- --- --- --- --- ---
0 0 2 2 2 2 2
1 1 3 5 7 9 11
2 1 4 9 16 25 36
3 1 5 14 30 55 91
4 1 6 20 50 105 196
5 1 7 27 77 182 378
k=1
j
i 0 1 2 3 4 5
--- --- --- --- --- --- ---
0 3 5 7 9 11 13
1 4 12 24 40 60 84
2 5 21 54 110 195 315
3 6 32 100 240 490 896
4 7 45 165 455 1050 2142
5 8 60 252 784 2016 4536
k=2
j
i 0 1 2 3 4 5
--- --- --- --- --- --- ---
0 3 8 15 24 35 48
1 7 27 66 130 225 357
2 12 60 180 420 840 1512
3 18 110 390 1050 2380 4788
4 25 180 735 2240 5670 12600
5 33 273 1260 4284 11970 29106
To illustrate how this array allow us to determine the expression
for s[n] in terms of the elementary symmetric functions, let's take
the example n=7. The partitions of 7 into parts no greater than 3
are
sum of
exponents
---------
7 = 3+3+1 + U W^2 3
= 3+2+2 + V^2 W 3
= 3+2+1+1 - U^2 V W 4
= 3+1+1+1+1 + U^4 W 5
= 2+2+2+1 - U V^3 4
= 2+2+1+1+1 + U^3 V^2 5
= 2+1+1+1+1+1 - U^5 V 6
= 1+1+1+1+1+1+1 + U^7 7
To find the magnitude of the coefficient of any one of these terms,
recall that A(i,j,k) is the size of the coefficient of U^i V^j W^k.
So, for example, the coefficient of U^2 V W is (the negative of)
A(2,1,1) = 21. In this way we can easily determine that the entire
expression for s[7] is
s[7] = U^7 - 7 U^5 V + 7 U^4 W + 14 U^3 V^2
- 21 U^2 V W - 7 U V^2 + 7 U W^2 + 7 V^2 W
Notice that if i+2j+3k = p for the prime p, then A(i,j,k) is a
multiple of p.
The above approach immediately generalizes to any number of basic
variables x1,x2,...xN. In the general case, the expression for s[n]
contains one term for each partition of n into parts no greater than
N. The coefficient of each term is given by an N-dimensional array,
defined with the boundary values
A(i,0,0,...) = 1
A(0,i,0,...) = 2
A(0,0,i,...) = 3
...
A(0,0,0,..i) = N
and the recurrence relation
A(i,j,k,...) = A(i-1,j,k,...) + A(i,j-1,k,...) + A(i,j,k-1,...)
+ ... + A(i,j,k,...,l-1)
We can also specialize these results, and apply them to some simple
algebraic problems. For example, in another article we consider
the fact that Case 1 of Fermat's Last Theorem follows if the
congruence
p p p
(x+y) - x - y = 0 (mod p^2)
has no non-zero solutions. To evaluate this for various odd exponents
n, we can consider this expression as the Newton's sum
n n n
s[n] = (x+y) + (-x) + (-y)
so the three quantities are x+y, x, and y, which have the elementary
symmetric functions
U = 0 V = -(x^2 + xy + y^2) W = xy(x+y)
Consequently, the expressions for s[n] satisfy the recurrence
s[n] = -V s[n-2] + W s[n-3]
Of course, this will give the same results as deriving the general
3-variable expression (as tabulated above) and then setting the first
symmetric function U equal to zero. Writing these in terms of v=-V
and w=W, so that we have the positively signed quantities
v = x^2 + xy + y^2 w = xy(x+y)
the results are tabulated below.
n s[n]
--- ------------------------------------
0 3
1 0
2 2 v
3 3 w
4 2 v^2
5 5 v w
6 2 v^3 + 3 w^2
7 7 v^2 w
8 2 v^4 + 8 v w^2
9 9 v^3 w + 3 w^3
10 2 v^5 + 15 v^2 w^2
11 11 v^4 w + 11 v w^3
12 2 v^6 + 24v^3 w^2 + 3 w^4
13 13 v^5 w + 26 v^2 w^3
14 2 v^7 + 35 v^4 w^2 + 14 v w^4
15 15 v^6 w + 50 v^3 w^3 + 3 w^5
16 2 v^8 + 48 v^5 w^2 + 40 v^2 w^4
17 17 v^7 w + 85 v^4 w^3 + 17 v w^5
and so on. Clearly the powers of v which algebraically divide s[n]
follow the pattern 0,2,1,0,2,1,0,2,1,... and the powers of w that
divide s[n] follow the pattern 0,1,0,1,0,1,0,1,... Thus w divides
s[n] for every odd n, and the power of v dividing s[n] is 0, 1, or
2, accordingly as n is congruent to 0, 2, or 1 modulo 3. With
this information, together with the fact that the coefficients of
s[n] are all divisible by n if n is a prime, we can algebraically
factor s[p] for any odd prime p as indicated below
p (x+y)^p - x^p - y^p
--- -----------------------------------------
3 3w
5 5vw
7 7v^2 w
11 11vw (v^3 + w^2)
13 13v^2 w (v^3 + 2w^2)
17 17vw (v^6 + 5v^3 w^2 + w^4)
19 19v^2 w (v^6 + 7v^3 w^2 + 3w^4)
23 23vw (v^9 + 12v^6 w^2 + 14v^3 w^4 + w^6)
Dividing each of these expressions by p, we can see that Case 1 of
Fermat's Last Theorem follows if the remaining expression cannot
vanish modulo p given that w=xy(x+y) is non-zero modulo p. This
is obviously true with p=3. Also, for p=5 we see that Case 1 of
FLT could fail only if v=0 (mod 5), which implies
x^2 + xy + y^2 = 0 (mod 5)
If we make the substitution x=r+s and y=r-s this becomes
s^2 + 3r^2 = 0 (mod 5)
which requires s^2 = -3r^2 (mod 5). But this is impossible because
-3=2 is not a square modulo 5. However, this argument fails for p=7,
and for every other prime congruent to +1 mod 3, because -3 IS a
square modulo each of those primes.
It's also worth noting that the general Newton sum s[p] for 3
arbitrary integers x,y,z constitutes a monic polynomial in the
first symmetric function U=x+y+z, and each of the other coefficients
are divisible by p. Hence, Eisenstein's irreducibility tells us
that, in order to have integer solutions, the sum of the terms of
this expression that do not involve U must be divisible by p^2,
because otherwise the polynomial has no rational roots. Thus, we
are again led to consider the expressions with U=0 for primes p,
as summarized in the preceding table. In general, an integer solution
of the Fermat equation (under Case 1 or Case 2) would require that
the above expression vanish modulo p^2. The added simplicity of Case
1 is that we can assume w doesn't vanish.
Return to MathPages Main Menu