_{1}, ..., s

_{n}). For review of the elementary symmetric polynomials, see here. For review of polynomials, see here. For review of a field, see here.

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

Definition 1: Symmetric Polynomial

A polynomial P(x

_{1}, ..., x

_{n}) in n indeterminates is symmetric if and only if it is not altered when the indeterminates are arbitarily permuted among themselves.

That is, for every permutation σ of 1, ..., n, we have:

P(x

_{σ(1)}, ..., x

_{σ(n)}) = P(x

_{1}, ..., x

_{n})

Definition 2: Symmetric Rational Fraction

A rational fraction P/Q in n indeterminates is symmetric if it is not altered when the indeterminates are permuted; i.e. for every permutation σ of 1,..., n:

P(x

_{σ(1)}, ..., x

_{σ(n)}) /Q(x

_{σ(1)}, ..., x

_{σ(n)}) = P(x

_{1}, ..., x

_{n})/Q(x

_{1}, ..., x

_{n})

Note: This is not mean that P,Q are necessarily symmetric. Still, it will be seen later that every symmetric rational fraction can be represented as the quotient of symmetric polynomials.

Definition 3: ∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in}

We can use this notation to characterize a symmetric polynomial. In this case, each monomial has the form expressed in the sum.

In using this notation, it is important to specify the value of n and the number of indeterminates. Otherwise, it is not clear how it is expressed.

For example for a symmetric polynomial in two variables:

∑ x

_{1}

^{2}x

_{2}= x

_{1}

^{2}x

_{2}+ x

_{1}x

_{2}

^{2}

For a symmetric polynomial in three variables, we have:

∑ x

_{1}

^{2}x

_{2}= x

_{1}

^{2}x

_{2}+ x

_{1}x

_{2}

^{2}+ x

_{1}

^{2}x

_{3}+ x

_{1}x

_{3}

^{2 }+ x

_{2}

^{2}x

_{3}+ x

_{2}x

_{3}2

We can also use this notation to represent the elementary symmetric polynomials:

s

_{1}= ∑ x

_{1}

s

_{2}= ∑ x

_{1}x

_{2}

...

s

_{n-1}= ∑ x

_{1}*...*x

_{n-1}

s

_{n}= ∑ x

_{1}*...*x

_{n}

Definition 4: deg (∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in})= (i

_{1}, ..., i

_{n})

Using the notation ∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in}, by degree, I mean the set of i

_{1}, ..., i

_{n}that make up the symmetric polynomial.

For any non-zero polynomial P = P(x

_{1}, ..., x

_{n}) in n indeterminates x

_{1}, ..., x

_{n}over a field, the degree of P is defined as the largest n-tuple (i

_{1}, ..., i

_{n}) for which the coefficient x

_{1}

^{i1}*...*x

_{n}

^{in}in P is nonzero.

For purposes of comparison, we assume that i

_{1}, ..., i

_{n}are ordered such that i

_{1}≥ i

_{2}≥ ... ≥ ... i

_{n}

Here are some examples:

deg s

_{1}= (1, 0, 0, ..., 0)

deg s

_{2}= (1,1,0,....,0)

...

deg s

_{n-1}= (1,1,...1,0)

deg ∑ x

_{1}

^{2}x

_{2}= (2,1,0, ..., 0)

Definition 5: N

^{n}

Let N

^{n}be the set of n-tuples of integers of the form of Definition 4.

So that:

N

^{n}= { (i

_{1}, ..., i

_{n}), (j

_{1}, ..., j

_{n}), (k

_{1}, ..., k

_{n}), ... }

Definition 6: Ordering of N

^{n}: (i

_{1}, ..., i

_{n}) ≥ (j

_{1}, ..., j

_{n})

(i

_{1}, ..., i

_{n}) ≥ (j

_{1}, ..., j

_{n}) if and only if for all values:

i

_{1}is greater than j

_{1}or

i

_{1}= j

_{1}and i

_{2}is greater than j

_{2}or

for all u, i

_{u}= j

_{u}or

there exists v, such that i

_{v}is greater than j

_{v}and for all u less than v, i

_{u}= j

_{u}

Lemma 1: deg(P+Q) ≤ max(deg P, deg Q)

Proof:

(1) Let P = ∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in}

(2) Let Q = ∑ x

_{1}

^{j1}x

_{2}

^{j2}*...*x

_{n}

^{jn}

(3) deg P = (i

_{1}, ..., i

_{n})

(4) deg Q = (j

_{1}, ..., j

_{n})

(5) Assume that (i

_{1}, ..., i

_{n}) is greater than (j

_{1}, ..., j

_{n})

(6) So, max(deg P,deg Q) = (i

_{1}, ..., i

_{n})

(7) If none of the resulting coefficients changes to zero, then:

deg(P+Q) = (i

_{1}, ..., i

_{n}) [This follows from definition 4 above]

(8) If at least one of the resulting coefficients changes to zero, then:

deg(P+Q) is less than (i

_{1}, ..., i

_{n})

(9) We know that deg(P+Q) cannot be higher because addition may change the coefficient but it cannot change the power of any of the terms.

QED

Lemma 2: deg(PQ) = deg P + deg Q

Proof:

(1) Let P = ∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in}

(2) Let Q = ∑ x

_{1}

^{j1}x

_{2}

^{j2}*...*x

_{n}

^{jn}

(3) deg P = (i

_{1}, ..., i

_{n})

(4) deg Q = (j

_{1}, ..., j

_{n})

(5) deg P + deg Q = (i

_{1}+ j

_{1}, ..., i

_{n}+j

_{n})

(6) P*Q = (∑ x

_{1}

^{i1}x

_{2}

^{i2}*...*x

_{n}

^{in})*(∑ x

_{1}

^{j1}x

_{2}

^{j2}*...*x

_{n}

^{jn}) = ∑ (x

_{1}

^{i1+j1}x

_{2}

^{i2+j2}*...*x

_{n}

^{in+jn})

(7) deg(P*Q) = (i

_{1}+ j

_{1}, ..., i

_{n}+j

_{n})

QED

Corollary 2.1: deg a

^{x}= x*deg(a)

Proof:

deg a

^{x}= deg (a*a*...*a) = deg(a) + deg(a) + ... + deg(a) = x*deg(a)

QED

Lemma 3: N

^{n}does not contain any infinite strictly decreasing sequence of elements.

That is if we take any x ∈ N

^{n}, we can only decrease it a finite amount of times.

Proof:

(1) This is clearly true for n=1.

(2) So, we can assume that this is true up to n-1.

(3) Assume that we have an infinite strictly decreasing sequence in N

^{n}such that:

(i

_{11}, i

_{12}, ..., i

_{1n}) is greater than (i

_{21}, i

_{22}, ..., i

_{2n}) which is greater than ... which is greater than (i

_{m1}, i

_{m2}, ..., i

_{mn}) is greater than ....

(4) Using Definition 6 above, we know that:

i

_{11}≥ i

_{21}≥ ... ≥ i

_{m1}≥ ....

(5) Since i

_{11}is finite, it follows that the only way that this can be infinite is if this sequence is eventually constant.

(6) Let us assume that it becomes constant starting with i

_{M1}so that for all m ≥ M, i

_{m1}= i

_{M1}

(7) By our assumption in step #3, it follows that the following sequence must also be infinite:

(i

_{M1}, i

_{M2}, ..., i

_{Mn}) is greater than (i

_{(M+1)1}, i

_{(M+1)2}, ...., i

_{(M+1)n}) is greater than ... and so on.

(8) Since all of the first elements are equal and from definition 6 above, we can remove the first element in all cases to get the following infinite sequence:

(i

_{M2}, ..., i

_{Mn}) is greater than (i

_{(M+1)2}, ...., i

_{(M+1)n}) is greater than ... and so on.

(9) But now we have a contradiction. Since we assumed in step #2 that there are no infinite strictly decreasing sequence of elements in N

^{n-1}

(10) So, we reject our assumption in step #3.

QED

Theorem 4: Waring's Method (Fundamental Theorem of Symmetric Polynomials)

A polynomial in n indeterminates x

_{1}, ..., x

_{n}over a field F can be expressed as a polynomial in s

_{1}, ..., s

_{n}if and only if it is symmetric.

In other words, for any symmetric polynomial, there exists a function g such that:

P(x

_{1}, ..., x

_{n}) = g(s

_{1}, ..., s

_{n})

where s

_{1}, s

_{2}, ..., s

_{n}are the elementary symmetric polynomials.

Proof:

(1) Let P ∈ F[x

_{1}, ..., x

_{n}] be a non-zero symmetric polynomial.

(2) Let deg P = (i

_{1}, ..., i

_{n}) ∈ N

^{n}where i

_{1}≥ i

_{2}≥ ... ≥ i

_{n}

(3) I will now show that P can be expressed as a function of the elementary symmetric polynomials.

(4) Let us define the following polynomial:

f = s

_{1}

^{i1 - i2}s

_{2}

^{i2-i3}*...*s

_{n-1}

^{in-1-in}s

_{n}

^{in}

(5) Using Lemma 2 above, we have:

deg f = deg(s

_{1}

^{i1 - i2}) + deg(s

_{2}

^{i2 - i3}) + ... + deg(s

_{n}

^{in})

(6) Using Corollary 2.1 above, we have:

deg f = (i

_{1}- i

_{2})deg(s

_{1}) + (i

_{2}- i

_{3})deg(s

_{2}) + ... + i

_{n}deg(s

_{n})

(7) Based on the definition of the elementary symmetric polynomials (see here), we have:

deg f = (i

_{1}- i

_{2},0,...,0) + (i

_{2}- i

_{3}, i

_{2}- i

_{3},0,...,0) + ... + (i

_{n}, ..., i

_{n}) = (i

_{1}, i

_{2}, ..., i

_{n})

(8) Also from the definition of the elementary symmetric polynomials, we know that the leading coefficient of f is 1.

(9) So, we can restate f as:

f = x

_{1}

^{i1}*...*x

_{n}

^{in}+ (terms of lower degree)

(10) Let a ∈ F

^{x}be the leading coefficient of P such that:

P = ax

_{1}

^{i1}*...*x

_{n}

^{in}+ (terms of lower degree)

(11) Let:

P

_{1}= P - af

(12) We can see that P

_{1}has the following properties:

(a) deg P

_{1}is less than deg P [See definition 4 above]

(b) P

_{1}is symmetric since P and f are symmetric

(c) We can assume that P

_{1}is nonzero. [If it were 0, we would be done with the proof. We only need to handle the case when P

_{1}is nonzero to finish the proof]

(13) Now since P

_{1}is a symmetric polynomial, we can repeat step #12 such that we define a polynomial P

_{2}

(14) In this way, we can continue to reduce P

_{i}until we P

_{i}- af = 0.

(15) We know that this process will eventually complete from Lemma 3 above.

QED

Example 4.1: S = ∑ x

_{1}

^{4}x

_{2}x

_{3}+ ∑ x

_{1}

^{3}x

_{2}

^{3}

(1) Let:

S = ∑ x

_{1}

^{4}x

_{2}x

_{3}+ ∑ x

_{1}

^{3}x

_{2}

^{3}

(so that: S = x

_{1}

^{4}x

_{2}x

_{3}+ x

_{1}x

_{2}

^{4}x

_{3}+ x

_{1}x

_{2}x

_{3}

^{4}+ x

_{1}

^{3}x

_{2}

^{3}+ x

_{1}

^{3}x

_{3}

^{3}+ x

_{2}

^{3}x

_{3}

^{3})

[See Definition 3 above for details if needed]

(2) Since (4,1,1) is greater than (3,3,0) [see Definition 6 above], it follows that [see Definition 4 above]:

deg(S) = (4,1,1)

(3) Let f = s

_{1}

^{4-1}s

_{2}

^{1-1}s

_{3}

^{1}= s

_{1}

^{3}s

_{3}

(4) Using the definitions for s

_{1}, ..., s

_{3}, we have:

s

_{1}

^{3}s

_{3}= (∑ x

_{1})

^{3}(x

_{1}x

_{2}x

_{3}) = ∑ x

_{1}

^{4}x

_{2}x

_{3}+ 3∑ x

_{1}

^{3}x

_{2}

^{2}x

_{3}+ 6x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(5) If we let S

_{1}= S - f, then we get:

S

_{1}= ∑ x

_{1}

^{3}x

_{2}

^{3}- 3∑ x

_{1}

^{3}x

_{2}

^{2}x

_{3}- 6x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(6) deg S

_{1}= (3,3,0)

(7) Let f

_{1}= s

_{1}

^{3-3}s

_{2}

^{3-0}s

_{3}

^{0}= s

_{2}

^{3}

(8) Using the definitions for s

_{1}, ..., s

_{3}, we have:

s

_{2}

^{3}= (∑ x

_{1}x

_{2})

^{3}= ∑ x

_{1}

^{3}x

_{2}

^{3}+ 3∑ x

_{1}

^{3}x

_{2}

^{2}x

_{3}+ 6x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(9) If we let S

_{2}= S

_{1}- f

_{1}, then we get:

S

_{2}= - 6∑ x

_{1}

^{3}x

_{2}

^{2}x

_{3}- 12x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(10) deg S

_{2}= (3,2,1)

(11) Let f

_{2}= s

_{1}

^{3-2}s

_{2}

^{2-1}s

_{1}

^{1}= s

_{1}s

_{2}s

_{3}

(12) Using the definitions for s

_{1}, ..., s

_{3}, we have:

s

_{1}s

_{2}s

_{3}= (∑ x

_{1})(∑ x

_{1}x

_{2})(∑ x

_{1}x

_{2}x

_{3}) = ∑x

_{1}

^{3}x

_{2}

^{2}x

_{3}+ 3x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(13) If we let S

_{3}= S

_{2}+ 6f

_{2}, then we get:

S

_{3}= 6x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(14) deg(S

_{3}) = (2,2,2)

(15) Let f

_{3}= s

_{1}

^{2-2}s

_{2}

^{2-2}s

_{3}

^{2}= s

_{3}

^{2}

(16) Using the definitions for s

_{1}, ..., s

_{3}, we have:

s

_{3}

^{2}= (∑ x

_{1}x

_{2}x

_{3})

^{2}= x

_{1}

^{2}x

_{2}

^{2}x

_{3}

^{2}

(17) We can see that S

_{3}- 6f

_{3}= 0 so we are done.

(18) The resulting function in terms of the elementary symmetric polynomials is:

S = s

_{1}

^{3}s

_{3}+ s

_{2}

^{3}- 6s

_{1}s

_{2}s

_{3}+ 6s

_{3}

^{2}

Lemma 5:

Let P,Q be polynomials such that P/Q is symmetric

Then:

P is symmetric if and only Q is symmetric

Proof:

(1) Assume that P is symmetric

(2) Assume that Q is not symmetric such that Q' is a permutation of Q and Q' ≠ Q.

(3) Let P' be the same permutation as Q'.

(4) Since P is symmetric, P' = P

(5) But P'/Q' = P/Q' ≠ P/Q

(6) But this is impossible since we assumed that P/Q is symmetric.

(7) Therefore, we reject our assumption in step #2.

(8) We can make the exact same argument if we assume that Q is symmetric and P is not.

QED

Theorem 6:

A rational fraction in n indeterminates x

_{1}, ..., x

_{n}over a field F can be expressed as a rational fraction in s

_{1}, ..., s

_{n}if it is symmetric

Proof:

(1) Let P,Q be polynomials in n indeterminates x

_{1}, ..., x

_{n}such that the rational fraction P/Q is symmetric.

(2) We can assume that P,Q are not symmetric.

If P is symmetric, then Q is too (from Lemma 5 above) and we can use Theorem 4 above to get our result. So, to prove the theorem, we need only handle the case where both P,Q are not symmetric.

(3) Since Q is not symmetric, let Q

_{1}, ..., Q

_{r}be the distinct polynomials (other than Q) obtained from Q through permutations of the indeterminates.

(4) The product QQ

_{1}*...*Q

_{r}is symmetric since any permutation of the indeterminates simply permutes the factors.

(5) Since P/Q is symmetric, it follows that P/Q = P*(Q

_{1}*...*Q

_{r})/[Q*(Q

_{1}*...*Q

_{r})] is symmetric too.

(6) It further follows that P*(Q

_{1}*...*Q

_{r}) is symmetric from Lemma 5 above.

(7) Using Theorem 4 above, we know that there exists functions f,g such that:

P*(Q

_{1}*...*Q

_{r}) = f(s

_{1}, ..., s

_{n})

and

Q*(Q

_{1}*...*Q

_{r}) = g(s

_{1}, ..., s

_{n})

(8) Thus,

P/Q = f(s

_{1}, ..., s

_{n})/g(s

_{1}, ..., s

_{n})

QED

References

- Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

## No comments:

Post a Comment