9.7. THE GENERAL EQUATION OF DEGREE N
i
“bookmt” — 2006/8/8 — 12:58 — page 447 — #459
i
i
9.7. THE GENERAL EQUATION OF DEGREE N
447
9.6.8. Show that the monomial symmetric functions m with D .1; : : : ; n/ and jj D d form a linear basis of KS Œx
d 1; : : : ; xn.
9.6.9. Show that a symmetric function of degree d is an integer linear combination of monomials x˛ of degree d and, therefore, an integer linear combination of monomial symmetric functions m with jj D d .
(Substitute Zq-linear combinations in case the characteristic is q.)
9.6.10. Show that an upper triangular matrix T with 1’s on the diagonal and integer entries has an inverse of the same type.
9.6.11. Write out the monomial symmetric functions m3;3;1.x1; x2; x3/ and m3;2;1.x1; x2; x3/, and note that they have different numbers of summands.
9.6.12. Consult the Mathematica notebook Symmetric- Functions.nb, which is available on my World Wide Web site. Use the Mathematica function monomialSymmetric[ ] to compute the monomial symmetric functions m in n variables for (a) D Œ2; 2; 1; 1, n D 5 (b) D Œ3; 3; 2, n D 5 (c) D Œ3; 1, n D 5 9.6.13. Use the algorithm described in this section to expand the following symmetric polynomials as polynomials in the elementary symmetric functions.
(a) x 2
2
2
2
2
2
1 x2 x3 C x1 x2 x3 C x1 x2 x3 (b)
x3
1 C x3
2 C x3
3
9.6.14. Consult the Mathematica notebook Symmetric- Functions.nb, which is available on my World Wide Web site. Use the Mathematica function elementaryExpand[ ] to compute the expansion of the following symmetric functions as polynomials in the elementary symmetric functions.
(a)
Œ.x1
x2/.x1
x3/.x1
x4/.x2
x3/.x2
x4/.x3
x4/2
(b) m, for D Œ4; 3; 3; 1, in four variables 9.6.15. Suppose that f is an antisymmetric polynomial in n variables; that is, for each 2 Sn, .f / D ./f , where denotes the parity homomorphism. Show that f has a factorization f D ı.x1; : : : ; xn/g, where ı.x1; : : : ; xn/ D Qi
9.7. The General Equation of Degree n Consider the quadratic formula or Cardano’s formulas for solutions of a cubic equation, which calculate the roots of a polynomials in terms of the
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 448 — #460
i
i
448
9. FIELD EXTENSIONS – SECOND LOOK coefficients; in these formulas, the coefficients may be regarded as variables and the roots as functions of these variables. This observation suggests the notion of the general polynomial of degree n, which is defined as follows:
Let t1; : : : ; tn be variables. The general (monic) polynomial of degree n over K is Pn.x/ D xn t1xn 1 C C . 1/n 1tn 2 K.t1; : : : ; tn/.x/: Let u1; : : : ; un denote the roots of this polynomial in a splitting field E.
Then .x u1/ .x
un/ D Pn.x/; and tj D j .u1; : : : ; un/ for 1 j n, by Corollary 9.6.4. We shall now show that the Galois group of the general polynomial of degree n is the symmetric group Sn.
Theorem 9.7.1. Let E be a splitting field of the general polynomial Pn.x/ 2 K.t1; : : : ; tn/Œx. The Galois group AutK.t1;:::;tn/.E/ is the symmetric group Sn.
Proof. Introduce a new set of variables v1; : : : ; vn and let fj D j .v1; : : : ; vn/ for 1 j n; where the j are the elementary symmetric functions. Consider the polynomial
Q
X
Pn.x/ D .x v1/ .x
vn/ D xn C . 1/j fj xn j :
j
The coefficients lie in K.f1; : : : ; fn/, which is equal to KS .v1; : : : ; vn/ by Theorem 9.6.6. According to Proposition 9.6.2, K.v1; : : : ; vn/ is Galois over K.f1; : : : ; fn/ with Galois group Sn.
Furthermore, K.v1; : : : ; vn/ is the splitting field over K.f1; : : : ; fn/ of Q Pn.x/.
Let u1; : : : ; un be the roots of Pn.x/ in E. Then tj D j .u1; : : : ; un/ for 1 j n, so E D K.t1; : : : ; tn/.u1; : : : ; un/ D K.u1; : : : ; un/.
Since fti g are variables, and the ffi g are algebraically independent over K, according to Theorem 9.6.6, there is a ring isomorphism KŒt1; : : : ; tn !
KŒf1; : : : ; fn fixing K and taking ti to fi . This ring isomorphism extends to an isomorphism of fields of fractions K.t1; : : : ; tn/ Š K.f1; : : : ; fn/; and to the polynomial rings K.t1; : : : ; tn/Œx Š K.f1; : : : ; fn/ŒxI the isomorphism of polynomial rings carries Pn.x/ to Q Pn.x/. Therefore, by Proposition 9.2.4, there is an isomorphism of splitting fields E Š
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 449 — #461
i
i
9.7. THE GENERAL EQUATION OF DEGREE N
449
K.v1; : : : ; vn/ extending the isomorphism K.t1; : : : ; tn/ Š K.f1; : : : ; fn/:
It follows that the Galois groups are isomorphic:
AutK.t1;:::;tn/.E/ Š AutK.f1;:::;fn/.K.v1; : : : ; vn// Š Sn:
n
We shall see in Section 10.6 that this result implies that there can be no analogue of the quadratic and cubic formulas for equations of degree 5 or more. (We shall work out formulas for quartic equations in Section 9.8.)
The discriminant. We now consider some symmetric polynomials that arise in the study of polynomials and Galois groups.
Write
Y ı D ı.x1; : : : ; xn/ D
.xi
xj /: 1i
We know that ı distinguishes even and odd permutations. Every permutation satisfies .ı/ D ˙ı and is even if, and only if, .ı/ D ı. The symmetric polynomial ı2 is called the discriminant polynomial.
Now let f D Pi ai xi 2 KŒx be polynomial of degree n. Let ˛1; : : : ; ˛n be the roots of f .x/ in a splitting field E. The element ı2.f / D a2n 2
n
ı2.˛1; : : : ; ˛n/ is called the discriminant of f .
Now suppose in addition that f is irreducible and separable. Since ı2.f / is invariant under the Galois group of f , it follows that ı2.f / is an element of the ground field K. Since the roots of f are distinct, the element ı.f / D an 1 n
ı.˛1; : : : ; ˛n/ is nonzero, and an element 2 AutK.E/ induces an even permutation of the roots of f if, and only if, .ı.f // D ı.f /. Thus we have the following result:
Proposition 9.7.2. Let f 2 KŒx be an irreducible separable polynomial.
Let E be a splitting field for f , and let ˛1; : : : ; ˛n be the roots of f .x/ in E. The Galois group AutK.E/, regarded as a group of permutations of the set of roots, is contained in the alternating group An if, and only if, the discriminant ı2.f / of f has a square root in K.
Proof. The discriminant has a square root in K if, and only if, ı.f / 2 K.
But ı.f / 2 K if, and only if, it is fixed by the Galois group, if, and only if, the Galois group consists of even permutations.
n
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 450 — #462
i
i
450
9. FIELD EXTENSIONS – SECOND LOOK
We do not need to know the roots of f in order to compute the dis criminant. Because the discriminant of f D Pi ai xi is the discriminant of the monic polynomial .1=an/f multiplied by a2n 1
n , it suffices to give a method for computing the discriminant of a monic polynomial. Suppose, then, that f is monic.
The discriminant is a symmetric polynomial in the roots and, there fore, a polynomial in the coefficients of f , by Theorem 9.6.6 and Corollary 9.6.4. For fixed n, we can expand the discriminant polynomial ı2.x1; : : : ; xn/ as a polynomial in the elementary symmetric functions, say ı2.x1; : : : ; xn/ D dn.1; : : : ; n/. Then ı2.f / D dn. an 1; an 2; : : : ; . 1/na0/:
This is not the most efficient method of calculating the discriminant of a polynomial, but it works well for polynomials of low degree. (A program for computing the discriminant by this method is available on my Web site.)
Example 9.7.3. (Galois group of a cubic.) The Galois group of a monic cubic irreducible polynomial f is either A3 D Z3 or S3, according to whether ı2.f / 2 K. (These are the only transitive subgroups of S3.) We can compute that
ı2.x
2
2
3
3
2
1; x2; x3/ D 1 2 4 2 4 1 3 C 18 1 2 3 27 3 :
Therefore, a cubic polynomial f .x/ D x3 C ax2 C bx C c has ı2.f / D a2 b2 4 b3 4 a3 c C 18 a b c 27 c2:
In particular, a polynomial of the special form f .x/ D x3 C px C q has ı2.f / D 4 p3 27 q2; as computed in Chapter 8.
Consider, for example, f .x/ D x3 4x2 C 2x C 13 2 ZŒx. To test a cubic for irreducibility, it suffices to show it has no root in Q, which follows from the rational root test. The discriminant of f is ı2.f / D 3075. Since this is not a square in Q, it follows that the Galois group of f is S3.
Example 9.7.4. The Galois group of an irreducible quartic polynomial f must be one of the following, as these are the only transitive subgroups of S4, according to Exercise 5.1.20: A4; V A4, or S4; D4; Z4 6 A4.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 451 — #463
i
i
9.7. THE GENERAL EQUATION OF DEGREE N
451
We can compute that the discriminant polynomial has the expansion
ı2.x
2
2
2
3
2
3
3
3
1; : : : ; x4/ D1 2 3 4 2 3 4 1 3 C 18 1 2 3 27 4
2
3
4
3
3
4 1 2 4 C 16 2 4 C 18 1 2 3 4
80
2
2
2
2
4
2
1 2
3 4 6 1 3 4 C 144 2 3 4 27 1 4 C 144 2
2
2
2
2
3
1
2 4 128 2 4 192 1 3 4 C 256 4 : Therefore, for f .x/ D x4 C ax3 C bx2 C cx C d , ı2.f / Da2 b2 c2 4 b3 c2 4 a3 c3 C 18 a b c3 27 c4 4 a2 b3 d C 16 b4 d C 18 a3 b c d 80 a b2 c d 6 a2 c2 d C 144 b c2 d 27 a4 d 2 C 144 a2 b d 2 128 b2 d 2 192 a c d 2 C 256 d 3:
For example, take f .x/ D x4 C 3x3 C 4x2 C 7x 5. The reduction of f mod 3 is x4 C x2 C x C 1, which can be shown to be irreducible over Z3 by an ad hoc argument. Therefore, f .x/ is also irreducible over Q. We compute that ı2.f / D 212836, which is not a square in Q, so the Galois group must be S4, D4, or Z4.
Resultants. In the remainder of this section, we will discuss the notion of the resultant of two polynomials. This material can be omitted without loss of continuity.
The resultant of polynomials f D PniD0 aixi; g D Pm i D0 bi xi 2
KŒx, of degrees n and m, is defined to be the product
Y Y R.f; g/ D am n bn
m
.i
j /;
(9.7.1)
i
j
where the i and j are the roots of f and g, respectively, in a common splitting field.
The product Y Y R0.f; g/ D .i
j /;
(9.7.2)
i
j
is evidently symmetric in the roots of f and in the roots of g and, therefore, is a polynomial in the quantities .ai =an/ and .bj =bn/. We can show that the total degree as a polynomial in the .ai =an/ is m and the total degree as a polynomial in the .bj =bm/ is m. Therefore, the resultant (9.7.1) is a polynomial in the ai and bj , homogeneous of degree m in the ai and of degree n in the bj .
Furthermore, R.f; g/ D 0 precisely when f and g have a common root, that is, if, and only if, f and g have a a nonconstant common factor in KŒx. We shall find an expression for R.f; g/ by exploiting this observation.
If the polynomials f and g have a common divisor q.x/ in KŒx, then there exist polynomials '.x/ and .x/ of degrees no more than n 1 and
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 452 — #464
i
i
452
9. FIELD EXTENSIONS – SECOND LOOK
m
1, respectively, such that f .x/ D q.x/'.x/; and g.x/ D q.x/ .x/; so f .x/ .x/ D g.x/'.x/ D q.x/'.x/ .x/: Conversely, the existence of polynomials '.x/ of degree no more than n 1 and .x/ of degree no more than m 1 such that f .x/ .x/ D g.x/'.x/ implies that f and g have a nonconstant common divisor (Exercise 9.7.9).
Now, write .x/ D Pm 1 i D0 ˛i xi and '.x/ D Pn 1 i D0 ˇi xi , and match coefficients in the equation f .x/ .x/ D g.x/'.x/ to get a system of linear equations in the variables .˛0; : : : ; ˛m 1; ˇ0; : : : ; ˇn 1/:
Assuming without loss of generality that n m, the matrix R.f; g/ of the system of linear equations has the form displayed in Figure 9.7.1.
2a
3
0
b0
6a1
a0
b1
b0
7
6
7
6a2
a1
a0
b2
b1
b0
7
6 :
:
:
:
:
:
:
:
7
6 :: :: :: : : :: :: :: : :
7
6
7
6 :
:
:
:
:
:
7
6 :: :: :: : : :
a
:: :: :: : : :
7
6
0
7
6 :
:
:
7
6 :
: :: :: : : :
a
7
6
1
bm bm 1 bm 2 : : :
7
6 :: :: :: : :
7
6 :
:
: : : :
a2
bm
bm 1 : : : : : : :
7
6
7
6 :: :: :: ::
7
6 :
:
: : : : :
bm
: : : : : : : : : b0 7
6
7
6
: :
7
6an
an 1 : : : an mC1 : : : : : : : b1 7
6
7
6
:: :: :: 7
6
an : : : : : : : : : 7
6
: : 7
6
: : 7
6
an : : : : : : : : 7
6
:
:
: : 7
6
: : :: : : :: 7
4
5
an
bm
Figure 9.7.1. The matrix R.f; g/.
The matrix has m columns with ai ’s and n columns with bi ’s. It fol lows from the preceding discussion that f and g have a nonconstant common divisor if, and only if, the matrix R.f; g/ has determinant zero.
We want to show that det.R.f; g// D . 1/nCmR.f; g/. Since det.R.f; g// D am n bn m det.R.a 1 n f; b 1 m g//, and similarly, R.f; g/ D
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 453 — #465
i
i
9.7. THE GENERAL EQUATION OF DEGREE N
453
am n bn mR.a 1 n f; b 1 m g/, it suffices to consider the case where both f and g are monic.
At this point we need to shift our point of view slightly. Regard the roots i and j as variables, the coefficients ai as symmetric polynomials in the i , and the coefficients and bj as symmetric polynomials in the j .
Then det.R.f; g// is a polynomial in the i and j , symmetric with respect to each set of variables, which is zero when any i and j agree. It follows that det.R.f; g// is divisible by Q Q
i
j .i j / D R.f; g/ (Exercise 9.7.12). But as both det.R/ and R.f; g/ are polynomials in the ai and bj of total degree n C m, they are equal up to a scalar factor, and it remains to show that the scalar factor is . 1/nCm. In fact, det.R/ has a summand am 0 .
On the other hand R.f; g/ D . 1/nCm Qj f .ˇj /, according to Exercise 9.7.10, and so has a summand . 1/nCmam
0 .
Proposition 9.7.5. R.f; g/ D . 1/nCm det.R.f; g//.
We now observe that the discriminant of f can be computed using the resultant of f and its formal derivative f 0. In fact, from Exercise 9.7.10,
Y R.f; f 0/ D an 1 n
f 0.i /:
i
Using Y f .x/ D an
.x
i /;
i
we can verify that
Y f 0.i / D an
.i
j /: j ¤i
Therefore,
Y Y Y R.f; f 0/ D an 1 n
f 0.i / D a2n 1
n
.i
j / i
i j ¤i
D a2n 1 n
. 1/n.n 1/=2 Y.i j /2 i
Proposition 9.7.6. ı2.f / D a 1
n
. 1/n.n 1/=2 R.f; f 0/.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 454 — #466
i
i
454
9. FIELD EXTENSIONS – SECOND LOOK
Although determinants tend to be inefficient for computations, the ma trix R is sparse, and it appears to be more efficient to calculate the discriminant using the determinant of R.f; f 0/ than to use the method described earlier in this section.
Exercises 9.7 9.7.1. Determine the Galois groups of the following cubic polynomials: (a) x3 C 2x C 1, over Q (b) x3 C 2x C 1, over Z3 (c)
x3
7x2
7, over Q 9.7.2. Verify that the Galois group of f .x/ D x3 C 7x C 7 over Q is S3. Determine, as explicitly as possible, all intermediate fields between the rationals and the splitting field of f .x/.
9.7.3. Show that the discriminant polynomial ı2.x1; : : : ; xn/ is a polynomial of degree 2n 2 in the elementary symmetric polynomials. Hint: Show that when ı2.x1; : : : ; xn/ is expanded as a polynomial in the elementary symmetric functions, ı2.x1; : : : ; xn/ D dn.1; : : : ; n/; the monomial of highest total degree in dn comes from the lexicographically highest monomial in ı2.x1; : : : ; xn/. Identify the lexicographically highest monomial in ı2.x1; : : : ; xn/, say x˛, and find the degree of the corresponding monomial ˛.
9.7.4. Let f .x/ D Pi ai xi have degree n and roots ˛1; : : : ; ˛n. Using the previous exercise, show that ı2.f / D a2n 2
n
ı2.˛1; : : : ; ˛n/ is a homoge neous polynomial of degree 2n 2 in the coefficients of f .
9.7.5. Determine ı2.f / as a polynomial in the coefficients of f when the degree of f is n D 2 or n D 3.
9.7.6. Check that x4 C x2 C x C 1 is irreducible over Z3.
9.7.7. Use a computer algebra package (e.g., Maple or Mathematica) to find the discriminants of the following polynomials. You may refer to the Mathematica notebook Discriminants-and-Resultants.nb, available on my World Wide Web site. The Mathematica function Discriminant[ ], available in that notebook, computes the discriminant.
(a)
x4
3x2 C 2x C 5 (b) x4 C 10x3
3x C 4 (c)
x3
14x C 10 (d)
x3
12
i
i
i
i