Monday, October 12, 2009

Galois' Memoir: Corollaries to Proposition I

Although Evariste Galois does not state it directly, there are important implications to his Proposition I which I will present.

The content that follows is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equation.

Here is the statement of Proposition I from Galois' Memoir without proof. For a proof, see here.

Proposition I:

Let f(x1, ..., xn) be a rational fraction in n indeterminates x1, ..., xn with coefficients in a field F.

For σ ∈ Gal(P/F):

f(σ(r1), ..., σ(rn)) is defined whenever f(r1, ..., rn) is defined.

and

f(r1, ..., rn) ∈ F if and only if f(σ(r1),..., σ(rn)) = f(r1, ..., rn) for all σ ∈ Gal(P/F).

Following from this proposition are the following corollaries.

Definition 1: Automorphism

An automorphism is a bijective homomorphism from a group to itself.

For details on the meaning of this definition (including the definition of bijective and the definition of a homomorphism, see here.)

Corollary 1.1:

Each permutation σ ∈ Gal(P/F) can be extended to an automorphism of F(r1, ..., rn) which leaves every element in F invariant by setting

σ(f(r1, ..., rn)) = f(σ(r1), ..., σ(rn)) for any rational fraction f(x1, ..., xn) for which
f(r1, ..., rn) is defined.

Proof:

(1) Assume that f(r1, ..., rn) is defined.

(2) Using Proposition I (see here), we know that:

f(σ(r1), ..., σ(rn)) ∈ F(r1, ..., rn) is defined.

(3) Let σ(f(r1,..., rn)) = f(σ(r1), ..., σ(rn))

(4) First, we need to show that σ(f(r1, ..., rn)) leaves every element in F invariant.

(5) Assume that f(r1, ...., rn) = g(r1, ..., rn) for two rational fractions f,g ∈ F(x1, ..., xn)

(6) Let us define a function H such that H(x1, ..., xn) = f(x1, ..., xn) - g(x1, ..., xn)

(7) By step #5 above, we know that H(r1, ..., rn) = 0

(8) So it follows that H(r1, ..., rn) ∈ F since 0 ∈ F.

(9) Using Proposition I (see here), we have:

H(r1, ..., rn) = H(σ(r1), ..., σ(rn))

(10) So:

f(σ(r1), ... σ(rn) ) - g(σ(r1), ..., σ(rn)) = 0

and further:

f(σ(r1), ..., σ(rn)) = g(σ(r1), ..., σ(rn))

(11) This proves that σ(f)=σ(g) = f(σ(r1), ..., σ(rn)) = g(σ(r1), ..., σ(rn)) if and only if
f(r1, ..., rn) = g(r1, ..., rn)

(12) To complete the proof, we show that σ is an automorphism [see Definition 1 above].

(13) We know it is bijective because σ is bijective.

(14) We know that it is a homomorphism since:

σ(f + g) = f(σ(r1), ..., σ(rn)) + g(σ(r1), ..., σ(rn)) = σ(f) + σ(g)

σ(fg) = f(σ(r1), ..., σ(rn))*g(σ(r1), ..., σ(rn)) = σ(f)*σ(g)

QED


Corollary 1.2:

The set Gal(P/F) does not depend on the choice of the Galois resolvent V.

Proof:

(1) Let V' ∈ F(r1, ..., rn) be another Galois resolvent (see Definition 2, here) for p(x)=0,

(2) Let π' be its minimum polynomial over F.

(3) Let fi' ∈ F(x) for i=1,...,n be a rational fraction such that:

ri = fi'(V') for i = 1, ..., n

(4) Using Corollary 1.1 above and using step #3 above, we have:

σ(ri) = fi'(σ(V'))

since σ leaves every element in F invariant and since it maps each ri to a unique value.

(5) Likewise, we can apply σ to both sides of:

π'(V') = 0

to get:

σ(π(V')) = π'(σ(V')) = σ(0) = 0

which gives us that:

π(σ(V')) = 0

(6) This shows that σ(V') is a root of π'.

(7) Thus we have shown that every element of Gal(P/F) as defined earlier with V is also an element of Gal(P/G) as defined with V'.

(8) We can also use the same argument to show the reverse which demonstrates that Gal(P/F) for V = Gal(P/F) for V'.

QED


Corollary 1.3:

Gal(P/F) is a subgroup of the group of all permutations of r1, ..., rn

Proof:

(1) Gal(P/F) is by definition a subset of all the permutations of r1, ..., rn. [see Definition 1, here, for definition of Gal(P/F)]

(2) So, to complete this proof (see Definition 6, here and Definition 2, here), I need to show that Gal(P/F) has closure, associativity, inversion, and identity on the operation of permutations.

(3) It has closure since for any element τ ∈ Gal(P/F), the composition τ * σ ∈ Gal(P/F) since:

(a) Let τ be the map: fi(Vj) → fi(Vk) for some k=1,..., m

(b) Let σ be the map: ri → fi(Vj)

(b) It follows that τ * σ : ri → fi(Vk)

(c) Therefore, τ * σ ∈ Gal(P/F)

(4) It has identity since the identity map is in Gal(P/F) is clear since the map is σ1 in the definition of the Galois Group since r1 = f1(V1), r2 = f2(V1), ..., and so on.

(5) It has inversion since:

(a) Let σ ∈ Gal(P/F)

(b) By definition of Gal(P/F), σ(ri) = fi(Vj)

(c) We know that Vj is also a Resolvent of P(X)=0. [see Lemma 4, here]

(d) So, we can define Gal(P/F) according to Vj and it will be the same. [see Corollary 1.2 above]

(e) So, it follows that the map:

fi(Vj) → fi(V1)

is an element of Gal(P/F)

(6) It has associativity since:

(a) Let's assume that we have three elements of Gal(P/F) so that we have:

σ, τ, φ

(b) Let's define the following maps:

φ: fi(Vk) → fi(Vl)

τ: fi(Vj) → fi(Vk)

σ: ri → fi(Vj)

(c) (φ * τ ) : fi(Vj) → fi(Vl)

(d) (φ * τ ) * σ: ri → fi(Vl)

(e) (τ * σ) : ri → fi(Vk)

(f) φ*(τ * σ): ri → fi(Vl)

QED

References
Posted by at 2 comments:

Tuesday, October 06, 2009

Galois' Memoir: Proposition 1 (Galois Group)

The following is taken from the translation of Galois' Memoir by Harold M. Edwards found in his book Galois Theory. The proof itself is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.


Definition 1: Galois Group Gal(P/F)

Let ri, ..., rn be the roots of a polynomial P with coefficients in F

Let V1, ..., Vm be the roots of the minimum polynomial for a given Galois Resolvent where the Galois Resolvent V = V1

Let σj be a map: σj: ri → fi(Vj) for i=1, ..., n

The set of all possible permutations { σ1, ..., σm } is called the Galois group of P(X)=0 over F and is denoted Gal(P/F).


Theorem: Galois' Proposition I

Let an equation be given whose m roots are a, b, c, ...

These will always be a group of permutations of the letters a,b,c,... which will have the following property:

1. That each function invariant under the substitution of this group will be known rationally

2. Conversely, that every function of the roots which can be determined rationally will be invariant under these substitutions

In other words:

Let f(x1, ..., xn) be a rational fraction in n indeterminates x1, ..., xn with coefficients in F.

Then:

f(r1, ..., rn) ∈ F if and only if for all σ ∈ Gal(P/F),

f(r1, ..., rn) = f(σ(r1), ..., σ(rn))

Proof:

(1) Let f = φ/ψ where φ, ψ ∈ F[x1, ..., xn]

(2) First, we need to prove that f is a rational function which comes down to showing that:

ψ(x1, ..., xn) ≠ 0 → ψ(σ(x1), ..., σ(xn)) ≠ 0 where σ ∈ Gal(P/F)

(3) We can show this since:

(a) Using Lemma 3 before (see Lemma 3, here), we know that there exists functions f1, ..., fn such that:

ψ(r1, ..., rn) = ψ(f1(V), ..., fn(V))

where V is the Galois Resolvent (see Definition 1, here) and fi ∈ F[X]

(b) But since each fi ∈ F[X] and ψ ∈ F[X], it follows that there exists a function g ∈ F[X] such that:

g(V) = ψ(f1(V), ..., fn(V))

(c) Let σ be a permutation in Gal(P/F)

(d) From Lemma 4 before (see Lemma 4, here), we know that each permutation corresponds to a root of the minimal irreducible polynomial of the Galois Resolvent so that there exists V' such that:

V' is a root of the minimal irreducible polynomial of the Galois Resolvent

and

σ: ri → fi(V')

(e) So that we have:

ψ(σ(r1), ..., σ(rn)) = ψ(f1(V'), ..., fn(V')) = g(V')

(f) It is clear that if ψ(σ(r1), ..., σ(rn)) = 0, then g(V')= 0

(g) So that when ψ is 0, V' is a root.

(h) Using Theorem 1, here, it clear that:

g(V') =0 if and only if g(V) is 0.

(i) So further, ψ(σ(r1), ..., σ(rn)) = 0 if and only if ψ(r1, ..., rn) = 0. [from step #3a above]

(4) This shows that f(σ(r1), ..., σ(rn)) is defined when f(r1, ..., rn) is defined.

(5) Assume that f(r1, ..., rn) ∈ F

(6) From step #3a above, we have:

f(r1, ..., rn) = f(f1(V), ..., fn(V))

(7) But since each fi ∈ F[X] and f ∈ F[X], it follows that there exists a function h ∈ F[X] such that:

h(X) = f(f1(X), ..., fn(X))

(8) So that:

h(V) = f(f1(V), ..., fn(V))

and:

h(X) - f(f1(X), ..., fn(X)) = 0

(9) If we define a function H such that:

H(X) = h(X) - f(f1(X), ..., fn(X))

It is clear that H(V)=0

(10) Using Theorem 1, here, it follows that all m roots of the minimal irreducible polynomial of the Galois Resolvent are also roots of H so that it's roots include: V1, ...., Vm

(11) So it follows for all j = 1, ..., m that:

h(Vj) = f(f1(Vj), ..., fn(Vj))

(12) Now since f(r1, ..., rn) ∈ F [by our assumption in step #5], it follows that we can define a function G such that:

G(X) = h(X) - f(r1, ..., rn)

(13) From step #6 above, we note that V is a root of G(X) and by the same logic as step #10, we conclude that all V1, ..., Vm are also roots of G(X).

(14) So that we have for all j= 1, ..., m:

h(Vj) = f(r1, ..., rn)

(15) But if this is true for all Vj, then it follows that it is true for all σ ∈ Gal(F/G) [by Lemma 4, here] so that we have:

f(σj(r1, ..., σj(rn)) = f(r1, ..., rn) for j = 1, ..., m

(16) Assume that f(σj(r1, ..., σj(rn)) = f(r1, ..., rn) for j = 1, ..., m

(17) From step #3a above, we know that:

f(r1, ..., rn) = f(f1(V), f2(V), ..., fn(V)) where f, fi ∈ F[X]

(18) So, we can define a function g(x) such that:

g(x) = f(f1(x),f2(x), ..., fn(x))

so that we have:

g(V) = f(r1, ..., rn)

(19) Since for all j, we have f(σj(r1, ..., σj(rn)) = f(r1, ..., rn), it follows that:

for all j = 1..m, g(Vj) = f(r1, ..., rn)

(20) Further we note that:

m*f(r1, ..., rn) = g(V1) + g(V2) + ... + g(Vm)

so that we have:

f(r1, ..., rn) = (1/m)*(g(V1) + ... + g(Vm))

(21) We can define the following function H such that:

H(x1, ..., xm) = (1/m)*g(x1) + ... + g(xm)

(22) H is clearly a symmetric function so it can be expressed as a rational fraction in the elementary symmetric polynomials s1, ..., sm [see Theorem 6, here]

(23) Now the elementary symmetric polynomials correspond to the coefficients of a polynomial. [see Theorem 1, here]

(24) This shows that if we substitute V1, ..., Vm for x1, ..., xm the elementary symmetric polynomial will correspond to the coefficients of the minimal irreducible polynomial for the Galois Resolvent whose coefficients are in F.

(25) Therefore H(V1, ..., Vm) ∈ F

(26) But H(V1, ..., Vm) = (1/m)*[g(V1) + g(V2) +... + g(Vm)] = f(r1, ..., rn)

(26) So we have shown that f(r1, ..., rn) ∈ F

QED

References
Posted by at No comments:

Monday, October 05, 2009

Galois' Memoir: Lemma 4

The following is taken from the translation of Galois' Memoir by Harold M. Edwards found in his book Galois Theory. The proof itself is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Lemma 4:

Suppose one has formed the equation for V and that one has taken one of its irreducible factors so that V is the root of an irreducible equation.

Let V, V', V'', ... be the roots of this irreducible equation .

If a = f(V) is one of the roots of the given equation, f(V') will also be a root of the given equation.

In fact, we can show that:

r1 = f1(V), r2 = f2(V), ..., rn = fn(V)

Then it follows that for any root V' or V'' or ... the complete set of distinct roots is:

f1(V'), f2(V'), ..., fn(V')

Proof:

(1) Let V be a Galois Resolvent of P(X) = 0. [see Lemma 2, here]

(2) Let r1, ..., rn be the roots of P(X).

(3) We know that for each ri, there exists fi [see Lemma 3, here] such that:

ri = fi(V)

with fi(X) ∈ F(X)

(4) Let V1 = V, V2, ..., Vm be the roots of the minimum polynomial of V over F [see Theorem 1, here] which are in F(r1, ..., rn) [see Corollary 1.1, here]

(5) Since ri = fi(V), we have P(fi(V)) = 0.

(6) If we view P(fi(X)) as a polynomial, then, we have P(fi(Vj)) = 0 for j = 1, ..., m since P(fi(X)) and the minimal polynomial of V over F share at least one root V. [see Theorem, here]

(7) This shows that each fi(Vj) must correspond to a root ri since P(X)=0 if and only if X is a root.

(8) Now, I will end this proof by showing that for any root Vi, that the n roots are:

f1(Vi), f2(Vi), ..., fn(Vi)

(9) Now we know that for V1, f1(V1) ≠ f2(V1) ≠ ... ≠ fn(V1) [from step #3 above]

(10) Assume that fu(Vi) = fv(Vi)

where i ≠ 1

(11) Then Vj is a root of the polynomial fu - fv.

(12) But then all V1, ..., Vm must likewise be roots of fu - fv. [see see Theorem, here]

(13) But this also means that V1 is a root of fu - fv

(14) So it follows that fu(V1) = fv(V1)

(15) But from step #9 above this is only possible if u = v.

(16) Hence, we have shown that for any Vi,

f1(Vi), ..., fn(Vi) must be the n distinct roots [since they cannot be equal and each one is equal to a root.]

QED

References
Posted by at No comments:

Sunday, October 04, 2009

Galois' Memoir: Lemma 4: Preliminary Results (Existence of Minimum Polynomial)

Before jumping into Lemma 4 by Evariste Galois, I will prove the existence of minimum polynomials.

The theorem in today's blog comes from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Definition 1: Minimum Polynomial of u over F

For a nonzero polynomials in F[X] which have u as a root, the minimum polynomial is the polynomial of least degree that divides all other nonzero polynomials and is unique, monic, and irreducible.

Theorem 1: Existence of Minimum Polynomials

(a) Every element u ∈ F(r1, ..., rn) has a polynomial expression in r1, ..., rn such that:

u = φ(r1, ..., rn)

for some polynomial φ ∈ F[x1, ..., xn]

(b) For every element u ∈ F(r1, ..., rn), there is a unique monic irreducible polynomial π ∈ F[X] such that π(u) = 0.

This polynomial π splits into a product of linear factors over F(r1, ..., rn)

Proof:

(1) Let u ∈ F(r1, ..., rn) be such that:

u = φ(r1, ..., rn)

for some polynomial φ ∈ F[x1, ..., xn]

(2) Let Θ(X,x1, ..., xn) = ∏(σ) [X - φ(σ(x1), ..., σ(xn))]

where σ runs over the set of permutations of x1, ..., xn

(3) Since Θ is symmetric in x1, ..., xn, we can write Θ as a polynomial in X and the elementary symmetric polynomials s1, ..., sn in x1, ..., xn [see Theorem 4, here]

(4) Let Θ(X,x1, ..., xn) = Ψ(X,s1, ..., sn)

for some polynomial Ψ with coefficients in F.

(5) Substituting r1, ..., rn into Θ, we get:

Θ(X,r1, ..., rn)= Ψ(X,a1, ..., an) ∈ F[X]

where ai are the coefficients of the polynomial where r1, ..., rn are the roots. [see Theorem 1, here]

(6) From the definition of Θ in step #2 above, we have:

Θ(u,r1, ..., rn) = 0

since in the permutation σ that leaves xi unchanged, the result will be 0.

(7) It follows that Ψ(X,a1, ..., an) is a polynomial in F[X] which has u as a root. [see step #5 above]

(8) We also note that Θ(X,r1, ..., rn) is a product of linear factors. [see step #2 above]

(9) Thus, we have shown that Ψ(X,a1,...,an) splits into a product of linear factors over F(r1, ..., rn) [see step #4 above]

(10) We know that we can break down Ψ(X,a1, ..., an) into a product of monic irreducible factors of Ψ [see Theorem 3, here] so that:

Ψ = cP1*...*Pr

(11) Since u is a root, it follows that u must be the root of one of these monic irreducible factors.

(12) So that there exists i such that:

Pi is a monic, irreducible polynomial over F[X] and u is a root of Pi and Pi divides Ψ.

(13) Since Ψ splits into a product of linear factors over F(r1, ..., rn), it follows that Pi must also split into a product of linear factors over F(r1, ..., rn).

(14) Finally, we note that there is only one monic irreducible polynomial Pi which has u as a root since:

(a) Assume that Q ∈ F[X] is another polynomial with the same properties.

(b) First, we note that P must divide Q. [see Lemma 2, here]

(c) But, by the same argument Q must divide P.

(d) So, then it follows that P=Q.

(15) This completes part(b) of the proof.

(16) Let V be the Galois Resolvent (see Definition 1, here) such that:

V ∈ F(r1, ..., rn)

(17) We know that r1, ..., rn are rational fractions in V. [see Lemma 3, here]

(18) Since u is a rational fraction of F(r1, ..., rn), it follows that u is also rational fraction in V and further u ∈ F(V).

(19) So, u can be expressed as a polynomial in V and:

u = Q(V)

for some polynomial Q ∈ F[X].

(20) Substituting f(r1, ..., rn) for V, we obtain:

u = Q(f(r1, ..., rn))

(21) This is a polynomial expression in r1, ..., rn since Q and f are polynomials.

(22) This completes part(a) of the proof.

QED


Corollary 1.1:

Let V be any Galois Resolvent of P(X) = 0 over F and let V1, ..., Vm be the roots of its minimum polynomial over F (among which V lies)

Then:

F(r1, ..., rn) = F(V) = F(V1, ..., Vm)

Proof:

(1) r1, ..., rn are rational fractions in V [see Lemma 3, here]

(2) So, we have:

F(r1, ..., rn) ⊂ F(V)

(3) We know that the roots V1, ..., Vm of the minimum polynomial of V are in F(r1, ..., rn) since:

(a) V is a polynomial g(x1, ..., xn) ∈ F[X] [see Definition 1, here]

(b) Applying part(b) of Theorem 1 above, we note that each Vi has g(Vi)=0 and can be expressed over linear factors of F(r1, ..., rn)

(4) So, we have:

F(V1, ..., Vm) ⊂ F(r1, ..., rn)

(5) Since V1, ..., Vm are roots of V, it follows that:

F(V) ⊂ F(V1, ..., Vm)

(6) Therefore we have:

F(r1, ..., rn) = F(V) = F(V1, ..., Vm)

QED

References
Posted by at No comments:

Friday, October 02, 2009

Galois' Memoir: Lemma 3

The following is taken from the translation of Galois' Memoir by Harold M. Edwards found in his book Galois Theory. The proof itself is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Lemma 3:

When a function V is chosen as satisfies Lemma 2 (see here), it will have the property that all the roots of the given equation can be expressed as rational functions of V.

That is:

Let P be a function of degree n with the roots: r1, ..., rn where each root is distinct.

Let V(r1, ..., rn) be the Galois resolvent where each distinct permutation has a distinct value.

Then for all roots ri ∈ F(V).

Proof:

(1) Let V be a Galois Resolvent [see Definition 2, here]

(2) Let r1 be any root of an equation P

Since r1 is any root, the proof is done if we can show that ri ∈ F(V).

(3) Let:

g(x1, ..., xn) = ∏ (for each permutation σ) [V - f(x1, σ(x2), ..., σ(xn)) ] ∈ F(V)[x1, ..., xn]

where σ runs over all permutations of x2, ..., xn

(4) Since g is symmetric in x2, ..., xn, g can be written as a polynomial in x1 and the elementary polynomials s1, ..., sn-1. (see Lemma, here)

(5) Let:

g(x1, x2, ..., xn) = h(x1, ..., sn-1)

for some polynomial h with coefficients in F(V).

(6) Substituting in various ways the roots r1, ..., rn of P for the indeterminates x1, ..., xn which has the effect of substituting a1, ..., an-1 ∈ F for s1, ..., sn-1 [see Theorem 1, here, for details on the mapping between elementary symmetric polynomials and the coefficents of a polynomial], we obtain:

g(r1, r2, ..., rn) = h(r1, a1, ..., an-1)

and generalizing this, we get:

g(ri, r1, ...., ri-1, ri+1, ..., rn) = h(ri, a1, ..., an-1)

(7) Since V is a Galois Resolvent for a function f such that V = f(r1, ..., rn), we have:

V ≠ f(ri, σ(r1), σ(r2), ..., σ(ri-1), σ(ri+1), ..., σ(rn))

for i ≠ 1 and for any permutation σ of { r1, ..., ri-1, ri+1, ..., rn }. [see Lemma 2, here]

(8) Therefore:

g(ri, r1, r2, ..., ri-1, ri+1, ...., rn) ≠ 0 for i ≠ 1.

(9) On the other hand, the definition of g and V show that [see definition of g in step #3 above]:

g(r1, ..., rn) = 0

(10) From step #9 above and step #6 above, we know that:

h(X,a1, ..., an-1) ∈ F(V)[X]

vanishes for X = r1 but not for X = ri with i ≠ 1.

(11) Therefore, it is divisible by X - r1 but not by X - ri for i ≠ 1. [This follows from Girard's Theorem, see here]

(12) We then consider the monic greatest common divisor D(X) of P(X) and h(X,a1, ..., an-1) in F(V)[X]. [see Theorem 1, here for proof of the existence of a greatest common divisor for polynomials]

(13) Since P(X) = (X - r1)*...*(X - rn), we know that X - r1 divides P(X).

(14) From step #11 above, we know that X - r1 divides h.

(15) Since x - r1 divides both P(X) and h(X,a1, ..., an-1), it divides D.

(15) On the other hand, h(X,a1, ..., an-1) is not divisible by X - ri for i ≠ 1. [see step #10 above]

(16) Hence, D has no other factor than X - r1.

(17) Thus, D = X - r1 whence r1 ∈ F(V) since D ∈ F(V)[X].

QED

References
Posted by at 1 comment:

Monday, September 28, 2009

Galois' Memoir: Lemma 2 (Galois Resolvent)

The following is taken from the translation of Galois' Memoir by Harold M. Edwards found in his book Galois Theory. The proof itself is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Definition 1: Galois Resolvent Function

For any equation f(x) with distinct roots, the Galois Resolvent Function is a function g(x1, ..., xn) of the roots that no matter how the roots are permuted on the function, no two of the values are equal.

Definition 2: Galois Resolvent

The Galois Resolvent is a value of the Galois Resolvent Function where the roots of the equation f(x) are passed in as parameters.

Lemma 2: Galois Resolvent Function Exists

Given any equation f(x) with distinct roots a,b,c,... one can always form a function V of the roots such that no two of the values one obtains by permuting the roots in this function are equal.

For example, one can take:

V = Aa + Bb + Cc + ...

A, B, C, ... being suitably chosen whole numbers.

Proof:

(1) Let the n distinct roots of f(x) be denoted a,b,c, ...

(2) Since these roots are distinct, the discriminant (a - b)2(a - c)2(b - c)2*... = D is not zero [For review of the discriminant, see here].

(3) What needs to be shown is that n integers A,B,C, ... can be chosen so that the n! numbers AS(a) + BS(b) + CS(c) + ... + are distinct where S ranges over all n! permutations of the roots a,b,c,...

[for details on why count(n permutations) = n!, see Corollary 1.1, here]

(4) Let P be the product of the squares of the differences of these n! numbers that is:

P = ∏ (S,T) [ A(S(a) - T(a)) + B(S(b) - T(b)) + ... ]2

where the product is all over n!(n! - 1)/2 pairs (unordered) of permutations S and T in which S≠ T.

Note: The purpose of this equation is to verify that all n! numbers are distinct. P is the product of all possible differences between any two permutations.

We know that there are n! possible permutations (see step #3 above).

We pick one of these permutations (1 out of n!) and call it S. Then, we pick a second one (1 out of n! - 1) and call it T. Since ordering doesn't matter and there are two ways to pick the same combination, we only need to deal with n!*(n!-1)/2 comparisons between S and T.

(5) To complete the proof, we only need to show that we can pick A,B,C, ... etc. such that P is nonzero.

If any of the permutations are not distinct, then the difference between S and T will be 0. If any of the differences are 0, then P = 0. So if P ≠ 0, it follows that we have found values for A,B,C,... such that all permutations are distinct.

(6) Let A, B, C, ..., be regarded at first as variables.

(7) Then P is a polynomial in variables A, B, C,... whose coefficients are polynomials in the roots a,b,c,...

(8) P is symmetric in the roots (this follows directly from the definition of P and the definition of symmetric polynomials, see Definition 1, here).

(9) Since P is symmetric, the coefficients are symmetric in the roots so using Waring's Method (see Theorem 4, here), P is a polynomial in A, B, C, ... with the coefficients symmetric in roots.

(10) So, we can determine the coefficients of P based on the elementary symmetric polynomials using the roots [see Theorem 1, here].

(11) We can therefore assume that the coefficients are known since we are assuming that the roots are known.

(12) Since P is a product of nonzero polynomials, it is nonzero. [see Theorem, here]

(13) Therefore once can assign integer values to A,B,C,... in such a way as to make P ≠ 0 [see Theorem, here].

QED

References
Posted by at 9 comments:
Subscribe to: Posts (Atom)