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