Saturday, October 03, 2009

A polynomial invariant on all but one variable

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Lemma:

Let g be a polynomial in n indeterminates x1, ..., xn over some field K.

Let g be invariant under every permutation of x2, ..., xn

Then:

g can be written as a polynomial in x1 and the elementary symmetric polynomials s1, ..., sn-1 in x1, ..., xn

Proof:

(1) We can view g as a polynomial in x2, ..., xn with coefficients in K[x1].

(2) Using Waring's Method [see Theorem 4, here], we know that g can be written as a polynomial in the elementary symmetric polynomials s'1, ..., s'n-1 in x2, ..., xn with coefficients in K[x1]

(3) Therefore, there exists a polynomial g' such that:

g(x1, ..., xn) = g'(x1, s'1, ..., s'n-1)

where:

s'1 = x2 + ... + xn

s'2 = x2x3 + ... + xn-1xn

...

s'n-1 = x2*...*xn

(4) To complete the proof, we need to show that s'1, s'2, ..., s'n-1 can be restated in terms of s1, s2, ..., sn where:

s1 = x1 + ... + xn

s2 = x1x2 + ... + xn-1xn

...

sn = x1*...*xn

(5) We know that for any given polynomial [see Theorem 1, here]:

(X - x1)*...*(X - xn) = Xn - s1Xn-1 + ... + (-1)nsn

(6) Now, we can use the same principle to get:

(X - x2)*...*(X - xn) = Xn-1 - s'1Xn-2 + ... + (-1)n-1s'n-1

(7) Multiplying the above equation by (X - x1) gives us:

(X - x1)*...*(X - xn) = (X - x1)Xn-1 - (X - x1)s'1Xn-2 + ... + (X - x1)(-1)n-1s'n-1 =

Xn - (x1+s'1)Xn-1 + (x1s'1 + s'2)Xn-2 - (x1s'2 + s'3)Xn-3 + ... + (-1)n(x1s'n-1)

(8) Combining step #5 and step #7 gives us:

s1 = x1 + s'1

so that:

s'1 = s1 - x1


s2 = x1s'1 + s'2

so that:

s'2 = s2 - x1s'1 = s2 - x1(s1 - x1) = s2 - x1s1 + x12

and so on...

(9) Since we can subtitute all values s'i in terms of x1 and s1, ..., sn, we can use the equation in step #3 to get:

g(x1, ..., xn) = g'(x1, s'1, ..., s'n-1) = g'(x1, s1 - x1, s2 - s1x1 + x12, ... )

QED

References

Thursday, October 01, 2009

Nonzero Polynomials with Distinct Parameters

The following is taken from Harold M. Edwards in his book Galois Theory.

Theorem:

Let K be a field.

Let x1, x2, x3, ... be an infinite sequence of distinct elements of K

Let f(A,B,C,...) be a nonzero polynomial in n variables A,B,C,... with coefficients in K

Then:

It is possible to select values A=xj, B = xk, C = xm for the variables A,B,C from the sequence x1, x2, x3, ... so that F( xj, xk, xm, ...) ≠ 0

Proof:

(1) Assume that f(x) is a nonzero polynomial of one variable with degree m.

(2) Using the Fundamental Theorem of Algebra (see Theorem, here), we know that f(x) has at most m distinct roots.

(3) If we list off m+1 distinct elements of K from the infinite sequence, it is clear that at least one (let us say xr) will not be a root.

(4) So that f(xr) ≠ 0

(5) Assume that this is true up to n-1 variables for F(A,B,C...,Y) so that we know that F(xi, xj, ..., xy) ≠ 0

(6) Let G be a function of n variables so that we have G(A,B,C,...Z)

(7) Let H be a function on the first n-1 variables so that we have H(A,B,C,...Y) = G(A,B,C,...,Y,1)

(8) By assumption, we can find xi, xj, ... xy such that:

H(xi, xj, ..., xy) ≠ 0

(9) But then G(xi, xj, ..., xy, 1) ≠ 0.

QED

References

Products of Nonzero Polynomials

The following is taken from Harold M. Edwards in his book Galois Theory.

Theorem: The product of nonzero polynomials is a nonzero polynomial

Proof:

(1) This theorem is clearly true in the case of one nonzero polynomial.

(2) Let's assume that it is true up to p-1.

(3) So that the product of p-1 nonzero polynomails is a nonzero polynomial g(x) of degree n so that we have:

g(x) = a0xn + a1xn-1 + ... + an-1x + an

where a0 is nonzero.

(4) Let us assume that f(x) is a nonzero polynomial of degree m so that:

f(x) = b0xm + b1xm-1 + ... + bm-1x + bm

where b0 is nonzero

(5) f(x)*g(x) is nonzero since:

the only term with degree m+n is a0*b0 which cannot be 0.

(6) So, by induction this proposition is true for all products.

QED

References

Tuesday, September 29, 2009

The Discriminant

The content in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

For a definition of symmetric polynomials, see Definition 1, here.

Lemma 1:

Let


Then:

Δ(x1, ..., xn)2 is a symmetric polynomial

Proof:

(1) Let P = ∏ (xi - xj)

(2) If any xi = xj, then P = 0. [that is, if there is a multiple root]

(3) Assume that there are no multiple roots.

(4) If we swap any two roots, then the result is either P or -P, then the result is to permute the ordering of each of the differences and to change the signs of some.

(5) Ordering doesn't change the product so the only the change that occurs is the sign of the product. That is, the result is P or -P depending upon which parameters get swapped.

(6) So it is clear that ∏ (xi - xj) is not symmetric.

(7) If we permutate the values of [∏ (xi - xj)]2, it is clear that the result is always P2 = P2 = (-P)2

QED


Using Waring's Method (see Theorem 4, here), we know that [∏ (xi - xj)]2 can be expressed as a function of the elementary symmetric polynomials (for review, see here) so that we have:

Definition 1: The Discriminant Δ

Let



Then the Discriminant D is:

D(s1, ..., sn) = Δ(x1, ..., xn)2

where s1, ..., sn are the elementary symmetric polynomials.


Example 1: Discriminant of a generic polynomial of degree 2

D(s1,s2) = s12 - 4s2

First, we carry out the multiplication:

Δ(x1,x2)2 = (x1 - x2)2 = x12 + x22 - 2x1x2

Then, we show it as a function of the elementary symmetric polynomials:

x12 + x22 - 2x1x2 = (x1 + x2)2 - 4x1x2=s12 - 4s2


Example 2: Discriminant of a generic polynomial of degree 3

D(s1,s2,s3) = s12s22 + 18s1s2s3 - 27s32 -4s13s3 - 4s23

We note that:

Δ(x1,x2,x3) = (x1 - x2)(x1 - x3)(x2 - x3)

We can simplify this by restating Δ(x1,x2,x3) as:

Δ(x1,x2,x3) = A - B

where:

A = x12x2 + x22x3 + x32x1

and

B = x1x22 + x2x32 + x3x12

So that:

Δ(x1,x2,x3)2 = (A - B)2 = A2 + B2 - 2AB = (A + B)2 - 4AB

Now, we note that A+B and AB are symmetric polynomials and using Waring's method (see Theorem 4, here), we have:

A + B = ∑ x12x2 = s1s2 - 3s3

AB = ∑ x14x2x3 + ∑ x13x23 + 3x12x22x32 = s13s3 + s23 - 6s1s2s3 + 9s32

Now, we can combine these results to get the discriminant:

(A + B)2 - 4AB = ( s1s2 - 3s3)2 - 4( s13s3 + s23 - 6s1s2s3 + 9s32) =

= s12s22 + 18s1s2s3 - 27s32 -4s13s3 - 4s23


Example 3: Discriminant of x3 + px + q

D(s1,s2,s3) = -27q2 - 4p3

First, we note that the values of the elementary symmetric polynomials can be derived from the coefficients of a polynomial (see Theorem 1, here) so that:

s1 = 0

s2 = p

s3 = -q

So that:

s12s22 + 18s1s2s3 - 27s32 -4s13s3 - 4s23= 0 + 0 - 27(-q)2 - 0 - 4p3 = -27q2 - 4p3


Theorem 2:

Let P ∈ R[X] be a monic polynomial with real coefficients, which splits into a product of linear factors over C such that:

P = (x - u1)*...*(x - un)

for some u1, ..., un ∈ C.

Let d ∈ R be the discriminant of P

The equality d=0 holds if and only if P has a root of multiplicity at least 2 in C

If all the roots of P are real, then d ≥ 0. If n=2 or n=3 and not all the roots are real, then d ≤ 0.

Proof:

(1) d = ∏ (ui - uj)2 where 1 ≤ i is less than j ≤ n

(2) If P has a root of multiplicity at least 2, then d = 0 since we have a case where ui = uj

(3) If all the roots are real, then d ≥ 0 since any real number squared is greater or equal to 0 and product of nonnegative numbers is greater or equal to 0.

(4) Assume n =2

(5) d = (u1 - u2)2 [see Definition 1 above]

(6) If u1 is not real, then u2 = u1 [see Theorem 5, here]

(7) Let u1 = a + bi

(8) Let u2 = a - bi

(9) (u1 - u2)2 = (a + bi - [a - bi])2 = (2bi)2 = -4b2 = -abs(4*b2)

(10) So that d ≤ 0.

(11) Assume that n = 3

(12) Then, d = (u1 - u2)2(u1 - u3)2(u2 - u3)2

(13) Assume that not all three roots are real. So, we can assume that u1 is not real.

(14) Then, it follows that its conjugate is also a root. So we can assume that u2 is not real and u1 = u2

(15) We know that u3 is then real. [see Theorem 3, here]

(16) So there exists real numbers a,b,c such that:

u1 = a + bi

u2 = a - bi

u3 = c

And we have:

(u1 - u2)(u1-u3)(u2 - u3) = [a+bi - (a - bi)][a+bi - c][a-bi - c] = (2bi)([a-c]+bi)([a-c]-bi)

Now, we know that:

([a - c] + bi)([a - c] - bi) = [a - c][a - c] - bi[a - c] + bi[a - c] - [bi][bi] =[a - c]2 + b2

Combining this with the above we get:

(2bi)[(a - c)2 + b2] = i[(2b)(a - c)2 + 2b2]

Now, it is clear that (2b)(a - c)2 + 2b2 is a real number since a,b,c are real and we can set s = (2b)(a - c)2 + 2b2 where s is a real number.

So d = (is)2 = -(s2) = -abs(s2)

(17) So, d ≤ 0.

QED

Corollary 2.1:

x3 + px +q = 0

has three distinct real solutions if and only if (p/3)3 + (q/2)2 is less than 0.

Proof:

(1) By Exercise 3 above, the discriminant of x3 + px +q is d = -27q2 - 4p3

We further note that:

d = -27q2 - 4p3 = -2233[(p/3)3 + (q/2)2]

(2) Now if (p/3)3 + (q/2)2 is less than 0, it follows that d ≥ 0.

(3) So, using Theorem 2 above, we are done.

QED

References

Monday, September 28, 2009

Irreducible Polynomials and Relatively Prime Polynomials

Lemma 1:

Let g(x) be an irreducible polynomial with coefficients in a field K

Let h(x) be a polynomial with coefficients in a field K.

If g(x) does not divide h(x), then g(x) and h(x) are relatively prime

Proof:

(1) Let d(x) be the greatest common denominator for g(x) and h(x). [see Theorem 1, here for proof of the existence of d(x)]

(2) Since g(x) is irreducible, this means that d(x) must be of degree 0 or of the same degree as g(x). [see Definition 1, here]

(3) Assume that degree d(x) is nonzero.

(4) Then it follows that g(x)=C*d(x) where C is a constant. [since d(x) is a divisor of g(x) and since deg d(x) = deg g(x).]

(5) But then [1/C]*g(x) is a divisor of h(x) since d(x) is a divisor of h(x).

(6) But this is impossible since g(x) does not divide h(x).

(7) So we have a contradiction and we reject our assumption in step #3 and conclude that deg d(x) is 0.

(8) But then this means that g(x) and h(x) are relatively prime. [see Definition 3, here]

QED