Math Refresher

Bertrand's Postulate (Theorem)

2009-11-18T22:30:00.000-08:00

In today's blog, I will present a proof for Bertrand's Postulate which is really a theorem.

The content is taken primarily from an excellent Wikipedia article.

Lemma 1:

If n is greater than 5, then 2n/3 is greater than √2n

Proof:

(1) For n ≥ 5, 2n(2n-9) is greater than 0 since 2n ≥ 10 and 2n-9 ≥ 1.

(2) 2n(2n - 9) = 4n² - 18n.

(3) Since 4n² - 18n is greater than 0, 4n² is greater than 18n.

(4) Dividing both sides by 9 gives us 4n²/9 is greater than 2n.

(5) Taking the square root of both sides gives us 2n/3 is greater than √2n

QED

Lemma 2:

Let p be a prime number that is greater than √2n

Let x be the highest nonnegative integer such that p^x divides 2n!/[(n!)(n!)]

then:

Proof:

(1) We know that in general, the maximum power of p that divides n! is (see Theorem, here):

(2) So the highest power of p that divides (2n)!/[(n!)(n!)] is:

(3) Since p is greater than √2n, it follows that p² is greater than 2n. So we only need to consider the case where i=1.

(4) This leaves us with:

QED

Lemma 3:

Bertrand's Posulate is true for n less than 2048

Proof:

Between any n less than 2048 and its double, one will find one of the following primes:

3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503

since:

n = 2 --> 3

n between 3 and 4 --> 5

n between 5 and 6 --> 7

n between 7 and 12 --> 13

n between 13 and 22 --> 23

n between 23 and 42 --> 43

n between 43 and 82 --> 83

n between 83 and 162 --> 163

n between 163 and 316 --> 317

n between 317 and 630 --> 631

n between 631 and 1258 --> 1259

n between 1259 and 2047 --> 2503

QED

Definition 1: R(p,n): maximum divisor of 2n!/(n!)(n!)

Let R(p,n) be the function that returns the maximum power of a given prime that divides 2n!/(n!)(n!)

For any prime p, p^R(p,n) divides 2n!/(n!)(n!) but p^R(p,n)+1 does not.

Example 1: R(3,5)

(2*5)!/(5!)(5!) = 10*9*8*7*6/5*4*3*2 = 2*9*2*7*2*2 = 2⁴*3²*7.

R(3,5) = 2 since 3² divides 2⁴*3²*7 but 3³ = 27 does not.

Lemma 4:

For all p, R(p,n) ≤ 2n

Proof:

(1) The multiplicity m of p in a factorial n! (see Theorem 1, here) is:

so that p^m divides n! but p^m+1 does not.

(2) Based on this, the formula for R(p,n) is:

which is equivalent to:

(3) We can see that if pⁱ is greater than 2n, then:

floor(2n/pⁱ) = 0 and floor(n/pⁱ) = 0 so that we have:

floor(2n/pⁱ) - 2*(n/pⁱ) = 0

so that we have:

(4) Using the Division Algorithm (see Theorem 1, here), there exists q,r such that:

n = qpⁱ + r

where r is less than pⁱ

(5) From this, we can see that:

since:

Case 1: r = 0

In this case, floor(2n/pⁱ) = 2q and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 0

Case 2: r is less than (1/2)pⁱ

In this case, floor(2n/pⁱ) = 2q and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 0

Case 3: r ≥ (1/2)pⁱ

In this case, floor(2n/pⁱ) = 2q+1 and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 1

(5) So that we have:

pⁱ ≤ p^log_p(2n) = 2n.

QED

Lemma 5:

For all i:

0 ≤ i ≤ 2n → (2n!)/(n!)(n!) ≥ (2n!)/(i!)(2n-i)!

Proof:

(1) We know that (see Definition 3, here for review of C(n,r) if needed):

C(2n,i-1) = (2n!)/(i-1)!(2n-i+1)!

C(2n,i) = (2n!)/(i!)(2n-i)!

(2) So, we see that:

C(2n,i) = (2n-i+1)/(i)*C(2n,i-1)

and

C(2n,i-1) = (i)/(2n-i+1)*C(2n,i)

(3) If i ≤ n, it follows that:

2n - i + 1 is greater than i since 2n - i + 1 ≥ n+1

So up to i=n, C(2n,i) is greater than C(2n,i-1)

(5) If i ≥ n+1, it follows that:

i is greater than 2n - i + 1 since 2n - i + 1 ≤ n

So down to i=n+1, C(2n,i-1) is greater than C(2n,i)

(6) So, we have shown that C(2n,n) is greater than C(2n,i) for i less than n and C(2n,n) is greater than C(2n,i) for i greater than n.

QED

Corollary 5.1:

Proof:

(1) Using the Binomial Theorem (see Theorem, here):

(2) Using Lemma 5 above, we know that:

(3) So that we have:

(4) And dividing both sides by (2n+1) finishes the proof.

QED

Lemma 6:

If 2^t is less than 8t, then t is less than 6

Proof:

(1) If t=6, then 2^t is greater than 8t since:

2⁶ = 64

8(6) = 48

(2) Assume it is true up to some t ≥ 6 so that: 2^t is greater than 8t.

(3) Then 2*(2^t)=2^t+1 is greater than 2*8t = 16t

(4) 16t is greater than 8t+8 since 16=8t + 8t and for t ≥ 6, 8t is greater than 8.

(5) So that we have 2^t+1 is greater than 8t+8 = 8(t+1).

QED

Lemma 7:

If:

Then:

n is less than 2048.

Proof:

(1) Let n = 2^2t-1

(2) So 2n = 2^2t

(3) √2^2t = 2^t

(4) So √2nln(2) = 2^tln(2)

(5) (4)ln(2n) = 4ln(2^2t) = 2t*4*ln(2)

(6) Dividing both sides by ln(2) gives us:

2^t is less than 8t

(7) Using Lemma 6 above, we conclude that t is less than 6.

(8) So, it follows that n is less than 2^2(6)-1 = 2¹¹ = 2048.

QED

Theorem: Bertrand's Postulate

For any n, there exists a prime p such that p is greater than n and less than 2n.

Proof:

(1) We know that Bertrand's Postulate is true for n less than 2048 [see Lemma 3 above]

(2) Assume for some n ≥ 2048, there is no prime between n and 2n.

(3) Let p be the largest prime factor of (2n!)/[(n!)(n!)] that is less than or equal to n.

(4) Using Lemma 1 above, we know that p ≤ 2n/3 since:

(a) Assume that that p is greater than 2n/3.

(b) Since n ≥ 2048, using Lemma 1 above, p is also greater than √2n

(c) This means that the highest power of x is given by (see Lemma 2 above):

(d) Since 2n/3 is less than p, it follows that 2n is less than 3p, and further that 2n/p is less than 3 so that 2n/p ≤ 2.

(e) But from step #3 above, we know that n ≥ p so that we have n/p ≥ 1.

(f) This gives us that 2n/p ≤ 2 and n/p ≥ 1 so that we have:

x = floor(2n/p) - 2*floor(n/p) ≤ 2 - 2*1 = 0.

(g) So, under these circumstances, the highest power of x is 0 which means that there is no such p and we can conclude that p ≤ 2n/3.

(5) From step #4, we have:

(2n!)/(n!n!) = ∏ (p ≤ 2n/3) p^R(p,n)

where R(p,n) is a function on p,n such that p^R(p,n) divides (2n!)/(n!n!) but p^R(p,n)+1 does not. [see Definition 1 above]

(6) From Lemma 2 above, we know that if p is greater than √2n, then R(p,n)=1 so that we have:

(7) Since there are less than √2n primes less than √2n, using Lemma 4 above, we have:

(8) If we use a limit for primorials (see Theorem, here), we have:

(9) Using Corollary 5.1 above, we also have:

(10) So, putting it all together, we have:

(11) If we multiply 4^(-2n/3) to both sides we get:

(12) Now, since n ≥ 1, we note that 4n² is greater than 2n+1

(a) For n=1, 4(1)² is greater than 2(1)+1

(b) Assume that 4n² is greater than 2n+1

(c) Since n ≥ 1, 4n² + 8n is greater than 2n+1+2

(d) 4n² + 8n + 1 is greater than 2(n+1) + 1

(e) And:

4(n+1)² is greater than 2(n+1)+1

(13) So it follows that:

(14) Since n is greater than 18, it follows that (4/3)√2n is greater than 2 + √2n since:

(a) √2(n) is greater than 6

(b) (4/3)√2n = (1/3)√2n + √2n

(c) And (1/3)√2n is greater than (1/3)*6 = 2.

(15) This gives us:

(16) Putting it all together gives us:

(17) Taking the logarithm of both sides, gives us:

(18) We can simplify this further by multiplying 3 to both sides and noting that 4=2² so that we get:

(19) We can further simplify it by dividing both sides by √2n to get:

(20) But now we use Lemma 7 above to reach a contradiction.

QED

References

"Proof of Bertrand's Postulate", Wikipedia.org

Primorial

2009-11-18T01:30:00.000-08:00

The primorial is the product of primes less than or equal to a number n.

Definition: Primorial: n#

The primorial n# is defined as follows:

Example:

1# = 1

3# = 3*(2#) = 3*2*(1#)=3*2

6# = 5# = 5*3*2

Theorem: if n≥ 1, then n# is less than 4ⁿ

Proof:

(1) It is true for (n=1 and n=2)

For n=1, 1#=1 is less than 4.

For n=2, 2#=2 is less than 4² = 16

(2) If n is even and n is greater than 2, then n is composite and we have:

n# = (n-1)# which is proven if we show that (n-1)# is less than 4^n-1 since 4^n-1 is less than 4ⁿ.

(3) To complete the proof, we show that n# is less than 4ⁿ if n is odd:

(a) By the inductive hypothesis, we can assume that it is true for all integers less than n and we assume that n is an odd integer where n=2x+1 and x ≥ 1 so that n ≥ 3.

(b) Now, we note that 4^m = (1+1)^2m = (2^-1)*(1+1)^2m+1 = (1/2)(1+1)^2m+1

(c) Using the Binomial Theorem (see here), we note that:

(1+1)^2m+1 = ∑ (i=0, 2m+1) (2m+1!)/[(i!)(2m+1-i)!]

(d) So,

(1/2)(1+1)^2m+1 = (1/2) ∑ (i=0, 2m+1) (2m+1)!/[(i!)(2m+1-i)!]

is greater than:

(1/2) [(2m+1)!/(m!)(m+1)! + (2m+1)!/(m+1)!(m)!] = (2m+1)!/(m!)(m+1)!

(e) So, from (b) and (d), we can conclude that:

4^m is greater than (2m+1)!/(m!)(m+1)!

since 4^m = (1/2)(1+1)^2m+1 which is greater than (2m+1)!/(m!)(m+1)!

(f) Each prime p that is greater than m+1 and less than 2m+1 divides (2m+1)!/(m+1)!(m!) since:

(2m+1)!/(m+1)!(m!) is an integer. [see Lemma 5, here]

Let u = (2m+1)!/(m+1)!(m!)

(2m+1)! = u(m+1)!(m!)

Since p does not divide (m+1)! and does not divide (m!), by Euclid's Generalized Lemma (see Corollary 2.1, here), p must divide u.

(g) This gives us:

From the definition of primorial [see Definition above], step #3f above, and step #3e above.

(h) From the inductive hypothesis in step #3a, we can assume that:

(m+1)# is less than 4^m+1

(i) So, we have (using step #3g above):

n# = (2m+1)# which is less (m+1)#*4^m

(j) Using step #3h above, we have:

(2m+1)# is less than 4^m+1*4^m = 4^2m+1

QED

References

"Primorial", Wikipedia.org
"Proof of Bertrand's Postulate", Wikipedia.org

Pascal's Rule

2009-11-18T01:16:00.000-08:00

Theorem: Pascal's Rule

C(n,k) + C(n,k-1) = C(n+1,k)

where:

Proof:

(1) We can find a common denominator for C(n,k) and C(n,k-1) so that we have:

(2) So that:

(3) To complete the proof, we note that: n-k+1 = n+1-k so that we have:

= C(n,k+1)

QED

References

"Pascal's Rule", Wikipedia.org

Multiplicity of a Prime Factor

2009-11-16T16:47:00.000-08:00

Definition 1: Multiplicity of a prime factor

The multiplicity of a prime factor of a given integer is the highest power of that factor that divides the integer.

Example 1: 60

The prime factorization of is 2*2*3*5

The multiplicity of 3 is 1. The multiplicity of 5 is 1. The multiplicity of 2 is 2.

Adrien-Marie Legendre came up with the following theorem regarding the multiplicity of a prime for n!. (For review of factorials (n!), see here)

Theorem 1: The multiplicity of a given prime p in n! is:

That is, let x = the multiplicity of a prime p.

Then p^x divides n! but p^x+1 does not.

Proof:

(1) If p is greater than n, then p doesn't divide n! and the answer is 0.

(2) So, we can assume p ≤ n.

(3) Let k be the largest power of p such that p^k ≤ n.

(4) For each 1 ≤ i ≤ k, the number of integers from 1 to n that are divisible by pⁱ but not divisible by pⁱ⁺¹ is:

If no numbers are divisible by pⁱ, then floor(n/pⁱ) = 0 [as does floor(n/pⁱ⁺¹)].

floor(n/pⁱ⁺¹) equals the number of integers that are greater than pⁱ⁺¹ and divisible by pⁱ⁺¹.

So the number of integers that are uniquely divisible by pⁱ is the difference of these two floor functions.

(5) The value of p^x which divides n! is equal to the product of all the powers of p that divide any of the integers in the sequence from 1 .. n.

(6) So, the we can compute the value of x with:

(7) Putting this together, we see the following pattern:

(8) We can see for i=1, we have floor(n/p¹), for i=2, we have 2*floor(n/p²) - 1*floor(n/p²), and for i=3, we have 3*floor(n/p³) - 2*floor(n/p³) and so on.

(9) The net result of this is that we rewrite the equation in step #7 to the following:

QED

References:

"Prime Power Dividing a Factorial", PlanetMath.Org
"Multiplicity", Wikipedia.Org

Common roots with an irreducible polynomial

2009-10-05T14:22:00.000-07:00

Theorem:

Let f(x) be a rational function in one indeterminate over a field F.

Let V be a root of an irreducible polynomial R(x) ∈ F[X]

If f(V) = 0, then all roots of P are also roots of f.

Proof:

(1) Let f = P/Q where P,Q are polynomials and ∈ F[X] and Q(V) ≠ 0 and P(V) = 0.

(2) Since V is a root an irreducible polynomial R, it follows that R divides P. [see Lemma 2, here]

(3) Let W be any root of R.

(4) It follows that W is also a root of P since:

(a) If W is a root a R, then x - W divides R.

(b) Then it follows that x - W must also divide P since R divides P.

(4) It also follows that if W is a root of R, then W is not a root of Q since:

(a) Assume that W is a root of Q so that Q(W)=0

(b) Then it would follow that R divides Q.

(c) But then Q(V)=0 since R(V)=0

(d) But this is not true since Q(V) ≠ 0.

(e) Therefore, we reject our assumption in step #4a.

(5) Therefore, we have shown that P(W)=0 and Q(W) ≠ 0

(6) Hence f(W)=0 for any root W of the irreducible polynomial R.

QED

References

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

A polynomial invariant on all but one variable

2009-10-03T21:29:00.000-07:00

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 x₁, ..., x_n over some field K.

Let g be invariant under every permutation of x₂, ..., x_n

Then:

g can be written as a polynomial in x₁ and the elementary symmetric polynomials s₁, ..., s_n-1 in x₁, ..., x_n

Proof:

(1) We can view g as a polynomial in x₂, ..., x_n with coefficients in K[x₁].

(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'₁, ..., s'_n-1 in x₂, ..., x_n with coefficients in K[x₁]

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

g(x₁, ..., x_n) = g'(x₁, s'₁, ..., s'_n-1)

where:

s'₁ = x₂ + ... + x_n

s'₂ = x₂x₃ + ... + x_n-1x_n

...

s'_n-1 = x₂*...*x_n

(4) To complete the proof, we need to show that s'₁, s'₂, ..., s'_n-1 can be restated in terms of s₁, s₂, ..., s_n where:

s₁ = x₁ + ... + x_n

s₂ = x₁x₂ + ... + x_n-1x_n

...

s_n = x₁*...*x_n

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

(X - x₁)*...*(X - x_n) = Xⁿ - s₁X^n-1 + ... + (-1)ⁿs_n

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

(X - x₂)*...*(X - x_n) = X^n-1 - s'₁X^n-2 + ... + (-1)^n-1s'_n-1

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

(X - x₁)*...*(X - x_n) = (X - x₁)X^n-1 - (X - x₁)s'₁X^n-2 + ... + (X - x₁)(-1)^n-1s'_n-1 =

Xⁿ - (x₁+s'₁)X^n-1 + (x₁s'₁ + s'₂)X^n-2 - (x₁s'₂ + s'₃)X^n-3 + ... + (-1)ⁿ(x₁s'_n-1)

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

s₁ = x₁ + s'₁

so that:

s'₁ = s₁ - x₁

s₂ = x₁s'₁ + s'₂

so that:

s'₂ = s₂ - x₁s'₁ = s₂ - x₁(s₁ - x₁) = s₂ - x₁s₁ + x₁²

and so on...

(9) Since we can subtitute all values s'_i in terms of x₁ and s₁, ..., s_n, we can use the equation in step #3 to get:

g(x₁, ..., x_n) = g'(x₁, s'₁, ..., s'_n-1) = g'(x₁, s₁ - x₁, s₂ - s₁x₁ + x₁², ... )

QED

References

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

Nonzero Polynomials with Distinct Parameters

2009-10-01T02:00:00.000-07:00

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

Theorem:

Let K be a field.

Let x₁, x₂, x₃, ... 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=x_j, B = x_k, C = x_m for the variables A,B,C from the sequence x₁, x₂, x₃, ... so that F( x_j, x_k, x_m, ...) ≠ 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 x_r) will not be a root.

(4) So that f(x_r) ≠ 0

(5) Assume that this is true up to n-1 variables for F(A,B,C...,Y) so that we know that F(x_i, x_j, ..., x_y) ≠ 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 x_i, x_j, ... x_y such that:

H(x_i, x_j, ..., x_y) ≠ 0

(9) But then G(x_i, x_j, ..., x_y, 1) ≠ 0.

QED

References

Harold M. Edwards, Galois Theory, Springer, 1984

Products of Nonzero Polynomials

2009-10-01T01:48:00.000-07:00

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) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n

where a₀ is nonzero.

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

f(x) = b₀x^m + b₁x^m-1 + ... + b_m-1x + b_m

where b₀ is nonzero

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

the only term with degree m+n is a₀*b₀ which cannot be 0.

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

QED

References

Harold M. Edwards, Galois Theory, Springer, 1984

The Discriminant

2009-09-29T22:22:00.000-07:00

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:

Δ(x₁, ..., x_n)² is a symmetric polynomial

Proof:

(1) Let P = ∏ (x_i - x_j)

(2) If any x_i = x_j, 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 ∏ (x_i - x_j) is not symmetric.

(7) If we permutate the values of [∏ (x_i - x_j)]², it is clear that the result is always P² = P² = (-P)²

QED

Using Waring's Method (see Theorem 4, here), we know that [∏ (x_i - x_j)]²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(s₁, ..., s_n) = Δ(x₁, ..., x_n)²

where s₁, ..., s_n are the elementary symmetric polynomials.

Example 1: Discriminant of a generic polynomial of degree 2

D(s₁,s₂) = s₁² - 4s₂

First, we carry out the multiplication:

Δ(x₁,x₂)² = (x₁ - x₂)² = x₁² + x₂² - 2x₁x₂

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

x₁² + x₂² - 2x₁x₂ = (x₁ + x₂)² - 4x₁x₂=s₁² - 4s₂

Example 2: Discriminant of a generic polynomial of degree 3

D(s₁,s₂,s₃) = s₁²s₂² + 18s₁s₂s₃ - 27s₃² -4s₁³s₃ - 4s₂³

We note that:

Δ(x₁,x₂,x₃) = (x₁ - x₂)(x₁ - x₃)(x₂ - x₃)

We can simplify this by restating Δ(x₁,x₂,x₃) as:

Δ(x₁,x₂,x₃) = A - B

where:

A = x₁²x₂ + x₂²x₃ + x₃²x₁

and

B = x₁x₂² + x₂x₃² + x₃x₁²

So that:

Δ(x₁,x₂,x₃)² = (A - B)² = A² + B² - 2AB = (A + B)² - 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 = ∑ x₁²x₂ = s₁s₂ - 3s₃

AB = ∑ x₁⁴x₂x₃ + ∑ x₁³x₂³ + 3x₁²x₂²x₃² = s₁³s₃ + s₂³ - 6s₁s₂s₃ + 9s₃²

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

(A + B)² - 4AB = ( s₁s₂ - 3s₃)² - 4( s₁³s₃ + s₂³ - 6s₁s₂s₃ + 9s₃²) =

= s₁²s₂² + 18s₁s₂s₃ - 27s₃² -4s₁³s₃ - 4s₂³

Example 3: Discriminant of x³ + px + q

D(s₁,s₂,s₃) = -27q² - 4p³

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:

s₁ = 0

s₂ = p

s₃ = -q

So that:

s₁²s₂² + 18s₁s₂s₃ - 27s₃² -4s₁³s₃ - 4s₂³= 0 + 0 - 27(-q)² - 0 - 4p³ = -27q² - 4p³

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 - u₁)*...*(x - u_n)

for some u₁, ..., u_n ∈ 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 = ∏ (u_i - u_j)² 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 u_i = u_j

(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 = (u₁ - u₂)² [see Definition 1 above]

(6) If u₁ is not real, then u₂ = u₁ [see Theorem 5, here]

(7) Let u₁ = a + bi

(8) Let u₂ = a - bi

(9) (u₁ - u₂)² = (a + bi - [a - bi])² = (2bi)² = -4b² = -abs(4*b²)

(10) So that d ≤ 0.

(11) Assume that n = 3

(12) Then, d = (u₁ - u₂)²(u₁ - u₃)²(u₂ - u₃)²

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

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

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

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

u₁ = a + bi

u₂ = a - bi

u₃ = c

And we have:

(u₁ - u₂)(u₁-u₃)(u₂ - u₃) = [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]² + b²

Combining this with the above we get:

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

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

So d = (is)² = -(s²) = -abs(s²)

(17) So, d ≤ 0.

QED

Corollary 2.1:

x³ + px +q = 0

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

Proof:

(1) By Exercise 3 above, the discriminant of x³ + px +q is d = -27q² - 4p³

We further note that:

d = -27q² - 4p³= -2²3³[(p/3)³ + (q/2)²]

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

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

QED

References

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

Irreducible Polynomials and Relatively Prime Polynomials

2009-09-28T22:39:00.000-07:00

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

The Conjugate of a Complex Number

2009-09-24T23:20:00.001-07:00

Definition 1: conjugate of complex number

Let z=(a,b) be a complex number. Then z = (a,-b)

For a review of complex numbers, see here.

Theorem 1: x is a real number if and only x = x

Proof:

(1) Assume that x is a real number such that x = (x,0)

(2) x = (x,-0) = (x,0) = x

(3) Assume that x = x

(4) Let x = (a,b) so that we have:

(a,b) = (a,-b)

(5) But by the definition of equality for complex numbers (see definition 4, here), this is only true if a=a and b=-b

(6) But b=-b only if b+b=2b=0 so b = 0.

(7) So x must be a real number.

QED

Theorem 2:

Let ηⁱ be an nth root of unity that is not real.

Then:

ηⁱ = η^-i

Proof:

(1) Any root of unity has the following form (see Corollary 1.1, here):

(2) So, there exists an integer k such that:

ηⁱ = cos [(2kπ)/n] + isin[(2kπ)/n]

(3) The conjugate of this value is (see Definition 1 above):

cos[(2kπ)/n] - isin[(2kπ)/n]
(4) We note that:

(5) Using the well known cos²(x) + sin²(x) = 1 [see Corollary 2, here], we get:

1/(cos[(2kπ)/n] - isin[(2kπ)/n]) = cos [(2kπ)/n] + isin[(2kπ)/n]

(6) Which shows that:

cos[(2kπ)/n] - isin[(2kπ)/n] = 1/ηⁱ = η^-i

QED

Lemma 3: (a + b) = a + b

Proof:

(1) Let a = s + ti

(2) Let b = u + vi

(3) a + b = (s + u) + (t+v)i

(4) a + b = (s + u) - (t+v)i

(5) a + b = s - ti + u - vi = (s + u) - (t+v)i

QED

Lemma 4: (ab) = a * b

Proof:

(1) Let a = s + ti

(2) Let b = u + vi

(3) a * b = (s*u - t*v) + (s*v + u*t)i

(4) a * b = (s*u - t*v) - (s*v+u*t)i

(5) a * b = (s - ti)*(u - vi) = (s*u - t*v) - (s*v + u*t)i

QED

Theorem 5:

Let f(x) be a polynomial with real coefficients.

if r is a root of f(x), then r is also a root

Proof:

(1) Let f(x) = a₀xⁿ + a₁x^n-1 + ... + a_n

(2) Since r is a root, we have:

a₀rⁿ + a₁r^n-1 + ... + a_n = 0

(3) But then taking the complex conjugate of both sides, we get (using Theorem 1 above as well as Lemma 3 and Lemma 4 above):

a₀rⁿ + a₁r^n-1 + ... + a_n = 0

(4) Which shows that f(r) = 0.

QED

Complex Conjugates and Properties of Complex Numbers

2009-09-22T22:07:00.000-07:00

The content in today's blog is taken from Bruce E. Meserve's Fundamental Concepts of Algebra.

The presentation builds on a previous blog I did on the definitions needed to build the complex numbers from the real numbers.

Definition 1: Complex Conjugate

For any complex number a+bi (see Definition 6, here), the complex conjugate is the form a-bi.

In other words, for the complex number (a,b), its complex conjugate is (a,-b). The complex conjugate of (a,-b) is likewise (a,b).

Definition 2: Norm of complex number: n(z)

The norm of a complex number which is represented as n(z) is the product of a complex number with its conjugate.

This definition is demonstrated in the following lemma:

Lemma 1: For any complex number (a,b), its norm is a real number: (a² + b²,0)

Proof:

(1) Let (a,b) be any complex number.

(2) It's complex conjugate is (a,-b) [see Definition 1 above]

(3) Using the definition for multiplication of complex numbers (see Definition 3, here) and the definition for norms (see Definition 2 above):

It's norm is (a,b)*(a,-b) = (a*a - (b*-b),a*(-b) + (b*a)) = (a² + b²,0)

(4) We can see that this is a real number (see Theorem 15, here)

QED

Definition 3: Absolute value of a complex number (the modulus)

The absolute value of a complex number is the nonnegative square root of the norm so that:

if z = (a,b), then abs(z) = √a² + b²

Definition 4: Division of complex numbers

(a,b) / (c,d) = (p,q) if and only if (a,b) = (c,d)*(p,q)

That this definition is well-defined is established in the next theorem.

Theorem 2: For the set of complex numbers, division by an nonzero number is well-defined.

Proof:

(1) Let (a,b), (c,d) be two complex numbers.

(2) Using the Definition of Multiplication (see Definition 3, here):

(c,d)*(p,q) = (cp - dq,cq + dp)

(3) So, if (a,b) = (c,d)*(p,q), then we have (see Definition 4, here):

a = cp - dq b = cq + dp

(4) Solving the first equation in terms of p and the second equation in terms of q gives us:

p = (a + dq)/c q = (b - dp)/c

(5) Combining the equations for p, we have:

(6) Now, rearranging the equation gives us:

And solving for p gives us:

which results in:

(7) Combining the equations for q, we have:

(8) Now, rearranging the equation gives us:

And solving for q gives us:

which results in:

(9) By assumption (c,d) is not nonzero so c² + d² is nonzero

(8) Since a,b,c,d are real numbers and the operations on real numbers are well-defined, it follows that p,q are well-defined and therefore division of (a,b) by (c,d) is well-defined.

QED

Theorem 3: The norm of a product is equal to the product of the norms.

Proof:

(1) Using Lemma 1 above, the norm for (a,b) is (a² +b²,0)

(2) Likewise, the norm for (c,d) is (c² + d²,0)

(3) Using the definition of multiplication for complex numbers (see Definition 3, here),

(a,b)*(c,d) = (a*c -b*d,a*d + b*c)

(4) Norm(a*c - b*d,a*d + b*c) is ([ac-bd]² + [ad+bc]²,0)

(5) Finally:

(ac - bd)² + (ad + bc)² = a²c² - 2abcd + b²d² + a²d² + 2abcd + b²c² =

= a²c² + b²d² + a²d² + b²c² = (a² + b²)(c² + d²)

which shows that:

Norm[(a,b)*(c,d)] = Norm(a,b)*Norm(c,d)

QED

Theorem 4:

The absolute value of a sum of complex numbers is less than or equal to the sum of the absolute values:

abs(z₁ + z₂) ≤ abs(z₁) + abs(z₂)

Proof:

(1) Assume that abs(z₁ + z₂) is greater than abs(z₁) + abs(z₂)

(2) Let:

z₁ = a + bi

z₂ = c + di

(3) Using the definition of absolute values for complex numbers (see Definition 3 above):

√(a + c)² + (b + d)² is greater than √a² + b² + √c² + d²

(4) Squaring both sides gives us:

(a + c)² + (b+d)² is greater than a² + b² + 2√(a² + b²)(c² + d²) + c² + d²

So that:

a² + c² + b² + d² + 2ac + 2bd is greater than a² + b² + c² + d² + 2√(a² + b²)(c² + d²)

So that:

ac + bd is greater than √(a² + b²)(c² + d²)

(5) Squaring both sides gives us:

a²c² + b²d² + 2abcd is greater than a²c² + b²d² + a²d² + b²c²

So that:

0 is greater than a²d² + b²c²+-2abcd

So that:

0 is greater than (bc - ad)²

(6) But this is impossible since (bc -ad)² ≥ 0.

(7) So, we reject our assumption in step #1.

QED

References

Bruce E. Meserve, Fundamental Concepts of Algebra, Dover Books, 1981.

The Set of Complex Numbers

2009-09-21T21:39:00.000-07:00

In today's blog I go over the definition of complex numbers and show how this definition can be used to prove that the set of complex numbers forms a field.

Definition 1: Complex Number

A complex number is an ordered pair of real numbers: (x,y) where x,y are real numbers.

Definition 2: Addition of Complex Numbers

(a,b) + (c,d) = (a+c,b+d)

Definition 3: Multiplication of Complex Numbers

(a,b)*(c,d) = (a*c - b*d,a*d + b*c)

Definition 4: Equality

(a,b) = (c,d) if and only if a = c and b = d

Lemma 1: The set of complex numbers is closed on addition

Proof:

This follows directly from the fact that the real numbers are closed on addition [see Lemma 1, here] and Definition 2 above.

QED

Lemma 2: The set of complex numbers is closed on multiplication.

Proof:

This follows directly form the fact that the real numbers are closed on multiplication [see Lemma 2, here] and Definition 3 above.

QED

Lemma 3: The set of complex numbers supports the commutative rule for addition

Proof:

(1) By Definition 2 above:

(a,b) + (c,d) = (a+c,b+d)

(2) Since the real numbers support the commutative rule for addition [see Lemma 3, here]:

(a+c,b+d) = (c+a,d+b) = (c,d) + (a,b)

QED

Lemma 4: The set of complex numbers supports the associative rule for addition

Proof:

(1) By Definition 2 above:

[(a,b) + (c,d)] + (e,f) = (a+c,b+d) + (e,f) = ([a+c]+e,[b+d]+f)

(2) Since the real numbers support the associative rule for addition [see Lemma 4, here]:

([a+c]+e,[b+d]+f) = (a+[c+e],b+[d+f]) = (a,b) + [(c,d) + (e,f)]

QED

Lemma 5: The set of complex numbers support the commutative rule for multiplication

Proof:

(1) By definition 3 above, we have:

(a,b)*(c,d) = (a*c - b*d,a*d + b*c)

(2) Since the real numbers support the commutative rule for multiplication (see Lemma 5, here):

(a*c - b*d,a*d + b*c) = (c*a - d*b,d*a + c*b)

(3) Since the real numbers support the commutative rule for addition (see Lemma 3, here):

(c*a - d*b,d*a + c*b) = (c*a - d*b,c*b + d*a)

(4) Using Definition 3 above again:

(c,d)*(a,b) = (c*a - d*b,c*b + d*a)

QED

Lemma 6: The set of complex numbers support the associative rule for multiplication

Proof:

By definition 3 above, we have:

[(a,b)*(c,d)]*(e,f) = ([a*c - b*d],[a*d + b*c])*(e,f) =

= ([a*c-b*d]*e - [a*d+b*c]*f,[a*c - b*d]*f + [a*d+b*c]*e) =

= (a*c*e - b*d*e -a*d*f + b*c*f, a*c*f - b*d*f + a*d*e + b*c*e) =

= (a*[c*e - d*f] - b*[c*f + d*e],a*[c*f + d*e] + b*[c*e - d*f]) =

= (a,b)*([c*e - d*f],[c*f + d*e]) = (a,b)*[(c,d)*(e,f)]

QED

Lemma 7: The set of complex numbers support the distributive rule

Proof:

(1) By Definition 2 above:

(a,b)*[(c,d) + (e,f)] = (a,b)*(c+e,d+f)

(2) By Definition 3 above:

(a,b)*(c+e,d+f) = (a*(c+e) - b*(d+f),a*(d+f) + b*(c+e)) =

= (a*c+a*e - b*d -b*f, a*d+a*f +b*c+b*e) =

= ([a*c - b*d] + [a*e - b*f],[a*d + b*c] + [a*f + b*e]) =

= (a*c-b*d,a*d + b*c) + (a*e-b*f,a*f + b*e) =

= (a,b)*(c,d) + (a,b)*(e,f)

QED

Lemma 8: The set of complex numbers have an additive identity (0,0)

Proof:

(a,b) + (0,0) = (a+0,b+0) = (a,b)

QED

Lemma 9: Every element of the set of complex numbers has an additive inverse (-a,-b)

Proof:

(a,b) + (-a,-b) = (a+-a,b+-b) = (0,0)

QED

Lemma 10: The set of complex numbers has a multiplicative identity (1,0)

Proof:

(a,b)*(1,0) = (a*1 - b*0, a*0 + b*1) = (a,b)

QED

Lemma 11: If (a,b) ≠ (0,0) then a² + b² ≠ 0

Proof:

(1) From Definition 4 above:

(a,b) ≠ (0,0) implies either a ≠ 0 or b ≠ 0.

(2) a≠ 0 → a² is greater than 0

(3) b≠ 0 → b² is greater than 0

(4) So a² is 0 or positive and b² is 0 or positive

(5) In all cases, a² + b² is positive since:

position + 0 = positive

0 + positive = positive

positive + positive = positive

QED

Lemma 12: Every nonzero element of the set of complex numbers has a multiplicative inverse

Proof:

(1) Let (a,b) be any nonzero element of the set of complex numbers

(2) Let c =1/(a² + b²)

We know that a² + b² is nonzero from Lemma 11 above.

(3) The multiplicative inverse is (a*c,-b*c)

(4) And we see that:

(a,b)*(a*c,-b*c) = (a*a*c - b*(-b*c),a*(-b*c) + b*(a*c)) =

= (a*a*c +b*b*c,-a*b*c + a*b*c) = (a*a*c + b*b*c,0)

(5) a*a*c + b*b*c = a*a/(a*a + b*b) + b*b/(a*a + b*b) =

= (a*a + b*b)/(a*a + b*b) = 1

QED

Theorem 13: The complex numbers form a field

Proof:

(1) The complex numbers are closed on addition [see Lemma 1 above] and multiplication [see Lemma 2 above].

(2) The complex numbers support the commutative property of addition [see Lemma 3 above], the associative property of addition [see Lemma 4 above], the commutative property of multiplication [see Lemma 5 above], an associative property of multiplication [see Lemma 6 above], and a distributive property [see Lemma 7 above].

(3) The set of complex numbers has an additive identity property [see Lemma 8 above], an additive inverse property [see Lemma 9 above], a multiplicative identity property [see Lemma 10 above], and a multiplicative inverse property [see Lemma 12 above].

(4) From all these properties, the complex numbers form a field. [see Definition 3, here]

QED

Definition 5: i

i = (0,1)

Theorem 14: i² = (-1,0)

Proof:

The result follows directly from Definition 3 above:

(0,1)*(0,1) = (0*0 - 1*1,0*1 - 1*0) = (-1,0)

QED

Theorem 15: All real numbers can be represented as complex numbers

(1) Any real number x can be represented as (x,0) [see definition 1 above]

(2) This correspondence holds over addition

x + y = z if and only if (x,0) + (y,0) = (x+y,0) = (z,0)

(3) This correspondence holds over multiplication

x*y = z if and only if (x,0)*(y,0) = (x*y - 0*0,x*0 + 0*y) = (x*y,0) = (z,0)

QED

Definition 6: a+bi

a+bi = (a,b)

References

H.A. Thurston, The Number System, Dover Publications, 1967
Bruce E. Meserve, Fundamental Concepts of Algebra, Dover Books, 1981.

The Set of Real Numbers

2009-09-21T01:00:00.000-07:00

In a previous blog, I showed how the Dedekind cut could be used to define the real numbers.

In today's blog, I will show that the real numbers form a field.

Lemma 1: The real numbers are closed on addition.

Proof:

(1) We can define the real numbers based on a Dedekind cut. [see Definition 2, here]

(2) Let x,y be the real numbers.

(3) From the definition of the Dedekind cut, x is the set of rational numbers that are less than x and y is the set of rational numbers that are less than y.

(4) x+y is defined as the set of rational numbers in x added to the set of rational numbers in y so that x+y is the set of all of possible sums.

(5) Since the rational numbers are closed on addition [see Lemma 2, here], it follows that x+y is also closed on addition.

QED

Lemma 2: The real numbers are closed on multiplication

Proof:

(1) We can define the real numbers based on a Dedekind cut. [see Definition 2, here]

(2) Let x,y be the real numbers.

(3) From the definition of the Dedekind cut, x is the set of rational numbers that are less than x and y is the set of rational numbers that are less than y.

(4) xy is defined as the set of rational numbers in x multiplied to the set of rational numbers in y so that xy is the set of all of possible products.

(5) Since the rational numbers are closed on multiplication [see Lemma 3, here], it follows that xy is also closed on multiplication.

QED

Lemma 3: The set of real numbers support the commutative rule for addition

Proof:

(1) By the definition of addition for real numbers, addition follows the properties of the set of rationals. [see Definition 5, here]

(2) So, the conclusion follows from the fact that the rational numbers support the commutative rule for addition. [see Lemma 4, here]

QED

Lemma 4: The set of real numbers support the associative rule for addition

Proof:

(1) By the definition of addition for real numbers, addition follows the properties of the set of rationals. [see Definition 5, here]

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for addition. [see Lemma 5, here]

QED

Lemma 5: The set of real numbers support the commutative rule for multiplication.

Proof:

(1) By the definition of multiplication for real numbers, multiplication follows the properties of the set of rationals. [see Definition 7, here]

(2) So, the conclusion follows from the fact that the rational numbers support the commutative rule for multiplication. [see Lemma 11, here]

QED

Lemma 6: The set of real numbers support the associative rule for multiplication

Proof:

(1) By the definition of multiplication for real numbers, multiplication follows the properties of the set of rationals. [see Definition 7, here]

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for multiplication. [see Lemma 8, here]

QED

Lemma 7: The set of real numbers support the distributive rule

Proof:

(1) The properties of multiplication of reals is based on the properties of rational numbers [see Definition 7, here] and the properties of addition of reals is based on the properties of rational numbers [see Definition 5, here].

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for multiplication. [see Lemma 10, here]

QED

Lemma 8: The set of real numbers have an additive identity

Proof:

(1) The additive identity is the set of all rational numbers less than 0.

(2) Let x be any real number.

(3) The x+0 be the set of all rational numbers less than x added to all rational numbers less than 0.

(4) Let a be any rational number less than x.

(5) Let b be any rational number less than 0 so that be must be negative.

(6) a + b is thus less than a which is less than x.

(7) Since b can be as close to 0 as we want, a+b can be as close to x as we want.

QED

Lemma 9: The real numbers support an additive inverse property

Proof:

(1) Let x be any real number

(2) Let -x be the set of rational numbers that are less than -x.

(3) Using the definition for addition (see Definition 5, here):

x+-x is the set of all rational numbers less than 0.

QED

Lemma 10: The set of real numbers supports a multiplicative identity property

Proof:

(1) Let x be any real number

(2) The multiplicative inverse is 1 which is the set of rational numbers less than 1.

(3) It is clear that x*1 = {the set of rational numbers less than x } = x.

QED

Lemma 11: The set of real numbers supports a multiplicative inverse property

Proof:

(1) Let x = be any nonzero real number

(2) The multiplicative inverse is 1/x

(3) This is clear since the set defined by x*1/x is the set of all rational numbers less than 1.

QED

Theorem 12: The real numbers form a field

(1) The real numbers are closed on addition [see Lemma 1 above] and multiplication [see Lemma 2 above].

(2) The real numbers support the commutative property of addition [see Lemma 3 above], the associative property of addition [see Lemma 4 above], the commutative property of multiplication [see Lemma 5 above], an associative property of multiplication [see Lemma 6 above], and a distributive property [see Lemma 7 above].

(3) The set of real numbers has an additive identity property [see Lemma 8 above], an additive inverse property [see Lemma 9 above], a multiplicative identity property [see Lemma 10 above], and a multiplicative inverse property [see Lemma 11 above].

(4) From all these properties, the real numbers form a field. [see Definition 3, here]

QED

The Set of Rational Numbers

2009-09-20T22:32:00.000-07:00

In today's blog, I show how to formally construct the set of rational numbers from the set of integers.

I will then give a proof that the set of rational numbers forms a field. If you need a review of fields, check out here.

Definition 1: Set of rational numbers

We can define the set of rational numbers as the ordered pair of integers (a,b) where a,b are integers and b ≠ 0.

Definition 2: Addition of rationals

(a,b) + (c,d) = (ad + bc, bd)

Definition 3: Multiplication of rationals

(a,b) * (c,d) = (ac,bd)

Definition 4: Equality of rationals

Two rational numbers (a,b) and (c,d) are equal if and only if ad=bc.

Definition 5: Comparison of rationals

(a,b) is less than (c,d) if and only if abd² is less than b²cd.

Lemma 1: All integers can be represented as rational numbers

(1) Any integer x can be represented as (x,1) [see definition 1 above]

(2) This correspondence holds over addition

x + y = z if and only if (x,1) + (y,1) = (x*1+y*1,1*1) = (x+y,1) = (z,1)

(3) This correspondence holds over multiplication

x*y = z if and only if (x,1)*(y,1) = (xy,1*1) = (xy,1) = (z,1)

QED

Lemma 2: The set of rational numbers is closed on addition

Proof:

(1) The integers are closed on addition [see Lemma 1, here] and multiplication [see Lemma 2, here].

(2) So, it follows from Definition 2 above that the rational numbers are closed on addition.

QED

Lemma 3: The set of rational numbers is closed on multiplication

Proof:

The follows directly from Definition 3 and the fact that the integers are closed on multiplication [see Lemma 2, here].

QED

Lemma 4: The set of rational numbers satisfy the Commutative Rule for Addition

Proof:

(1) From Definition 2 above:

(a,b) + (c,d) = (ad + bc, bd)

(2) Since integers are commutative by addition (see Lemma 7, here):

(ad + bc, bd) = (bc + ad, bd)

(3) From Definition 2 again, we get:

(bc + ad,bd) = (c,d) + (a,b)

QED

Lemma 5: The set of rational numbers satisfy the Associative Rule for Addition

Proof:

From Definition 2 above:

[(a,b) + (c,d)] + (e,f) = (ad+bc,bd) + (e,f) = (adf+bcf + bde,bdf) = (a,b) + (cf + de,df) =

= (a,b) + [(cf + de,df)] = (a,b) + [(c,d) + (e,f)]

QED

Lemma 6: The set of rational numbers has an Additive Identity for all elements.

Proof:

(1) Using Definition 2 above, we have:

(a,b) + (0,c) = (a*c + 0*b,b*c) = (ac,bc)

(2) Using Definition 4 above, we note that:

(ac,bc) = (a,b) since acb = bca [using the commutative property multiplication for integers, see Lemma 8, here]

QED

Lemma 7: The set of rational numbers has an Additive Inverse for all elements.

Proof:

(1) Let (a,b) be a rational number.

(2) Then, it's additive inverse is (-a,b) since:

(a,b) + (-a,b) = (a*b + -a*b,b*b) = (ab-ab,b*b) = (0,b*b)

QED

Lemma 8: The set of rational numbers supports the Associative Rule for Multiplication

Proof:

Using Definition 3 above, we have:

[(a,b)*(c,d)]*(e,f) = [(ac,bd)]*(e,f) = (ace,bdf) = (a,b)*[(ce,df)] = (a,b)*[(c,d)*(e,f)]

QED

Lemma 9: (c,c) = (1,1)

Proof:

The follows directly from definition 4 above since:

c*1 = 1*c

QED

Lemma 10: The set of rational numbers supports the Distributive Rule

Proof:

(1) Using Definition 2 and Definition 3 above, we have:

(a,b)[(c,d) + (e,f)] = (a,b)*(cf+de,df) = (acf + ade,bdf)

(2) Using Definition 3 above and Lemma 8 above, we have:

(acbf + aebd,bdbf) = (b,b)*(acf + aed,bdf) = (1,1)*(acf + aed,bdf) = (acf + aed,bdf)

(3) Using Definition 2 above, we have:

(ac,bd) + (ae,bf) = (acbf + aebd,bdbf)

QED

Lemma 11: The set of rational numbers supports the Commutative Rule for Multiplication

Proof:

(1) Using Definition 3 above, we have:

(a,b)*(c,d) = (ac,bd)

(2) Using the Commutative Property of Multiplication for Integers (see Lemma 8, here):

(ac,bd) = (ca,db)

(3) Using Definition 3 above, we have:

(ca,db) = (c,d)*(a,b)

QED

Lemma 12: The set of rational numbers has a Multiplicative Identity

Proof:

For any rational number (a,b), we have (see Definition 3 above):

(a,b)*(1,1) = (a*1,b*1) = (a,b)

QED

Lemma 13: For every nonzero element, the set of rational numbers has a Multiplicative Inverse

Proof:

(1) Let (a,b) be any rational number.

(2) Then (b,a) will be its multiplicative inverse since:

(a,b)*(b,a) = (ab,ba)

(3) Using the Commutative Property of Multiplication of Integers (see Lemma 8, here), we have:

(ab,ba) = (ab,ab)

(4) Using Lemma 8 above, we have (ab,ab)=1.

QED

Theorem 14: The set of rational numbers forms a field

Proof:

This follows directly from Lemma 2 through Lemma 13 above and from Definition 3, here.

QED

References

"Rational Numbers", Wikipedia.Org
Bruce E. Meserve, Fundamental Concepts of Algebra, Dover Books, 1981.

Polynomials of an odd degree have at least one real root

2009-09-19T09:49:00.001-07:00

Today, I present a proof taken from Edwards & Penney's Calculus and Analytic Geometry and PlanetMath.org.

I show that any polynomial of odd degree must have at least one root that is real.

Lemma 1:

lim (x → ∞) c/x = 0

where c is a nonzero constant

NOTE: This means that for any positive number ε, we can find a number δ such that:

for all abs(x) ≥ δ, abs(c/x) is less than ε

[See Definition 1, here for definition of mathematical limits]

Proof:

(1) Let ε be any positive number

(2) Assume c is positive.

(3) Let δ = 1 + c/ε

(4) So, then δ is greater than c/ε

(5) Which means that 1/δ is less than ε/c

(6) Which means that c/δ is less than ε

(7) For all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #5 above]

(8) -c/δ is greater than -ε [this follows directly from step #5 from multiplying -1 to both sides]

(9) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #7 above]

(10) Assume that c is negative

(11) Let δ = c/ε - 1

(12) So δ is less than c/ε

(13) So 1/δ is greater than ε/c

(14) Since c is negative, c/δ is less than ε [from multiplying a negative number to both sides]

(15) So for all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #14 above]

(16) -c/δ is greater than -ε [this follows directly from step #14 from multiplying -1 to both sides]

(17) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #16 above]

QED

Corollary 1.1:

limit (c/xⁱ) = 0

where c is a constant and i is a positive integer

Proof:

(1) For i=1, it is true from Lemma 1 above

(2) Let δ be the same δ from Lemma 1 above which depends on the sign of c.

(3) For all n ≥ δ, we have:

c/nⁱ ≤ c/n ≤ c/δ which is less than ε

(4) For all -n ≤ -δ, we have:

c/nⁱ ≥ c/n ≥ -c/δ which is greater than -ε

QED

Corollary 1.2:

Let g(x) = a₁/x + a₂/x² + ... + a_n-1/xⁿ

limit (x → ∞) g(x) = 0

Proof:

(1) For each a_i/xⁱ, the limit is 0. [From Corollary 1.1 above]

(2) Since g(x) is the sum of these values, we apply the Addition Rule [see Corollary 8.1, here] to get:

limit (x → ∞) g(x) = 0

QED

Lemma 2:

If f(x) is a polynomial of odd degree, there exists values a,b such that:

f(a) is less than 0 and f(b) is greater than 0

Proof:

(1) Let f(x) be a polynomial of an odd degree n such that:

f(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(2) We can make f(x) monic (where xⁿ does not have a coefficient) by dividing both sides by a₀.

So, we can assume the following monic form:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(3) Let g(x) = (1/xⁿ)[a₁x^n-1 + ... + a_n-1x + a_n] =

= a₁/x + a₂/x² + ... + a_n-1/x^n-1 + a_n/xⁿ

(4) Then:

f(x) = xⁿ[1 + g(x)]

(5) Using Corollary 1.2 above, we know that there exists δ such that:

for all abs(x) ≥ δ, abs(g(x)) is less than 1 [where ε = 1]

(6) So, it follows that 1 + g(x) is greater than 0.

(7) Let b be any positive number greater than δ.

(8) It follows that f(b) is greater than 0 since bⁿ*[1 + g(x)] is greater than 0.

(9) Let a be any negative number where a is less than -δ.

(10) It follows that f(a) is less than 0 since aⁿ*[1 + g(x)] is less than 0.

QED

Theorem 3: A polynomial of odd degree has at least one real root

Proof:

(1) Let f(x) be a polynomial of odd degree.

(2) All polynomials are continuous [see Corollary 1.1, here], so f(x) is continuous.

(3) There exists a number a such that f(a) is less than 0. [see Lemma 2 above]

(4) There exists a number b such that f(b) is greater than 0. [see Lemma 2 above]

(5) Therefore, there exists at least one real root [see Weierstrass Intermediate Value Theorem, here]

QED

References

"polynomial equation of odd degree", PlanetMath.Org
Edwards, Jr. C. H. & Penney, David E., Calculus and Analytic Geometry, Prentice Hall, 1990

Elementary Symmetric Polynomials

2009-09-09T08:01:00.000-07:00

If we look at Girard's Theorem, we see that:

xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n)

Now if we solve for each a_i in terms of x_i, we can restate the equation in terms of the elementary symmetric polynomials. In today's blog, I will show a proof of this using induction.

Definition 1: Elementary Symmetric Polynomials

s₁, ..., s_n such that:

s₁ = x₁ + ... + x_n

s₂ = x₁x₂ + ... + x_n-1x_n

s₃ = x₁x₂x₃ + ... + x_n-2x_n-1x_n

...

s_n = x₁x₂*...*x_n

So, let get down to showing the theorem.

Theorem 1: Restatement of Girard's Theorem in terms of the Elementary Symmetric Polynomials:

Xⁿ - s₁X^n-1 + s₂X^n-2 - ... + (-1)ⁿs_n = (X - x₁)(X - x₂)*...*(X-x_n)

Proof:

(1) xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n) [see Girard's Theorem]

(2) Assume n=1

(3) x + a₁ = x - x₁ = x - s₁

(4) Assume that the theorem holds true up until n.

(5) So that we have:

Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n) = (X - x₁)(X - x₂)*...*(X-x_n)

(6) Multiplying (X - x_n+1) to both sides gives us:

(X - x₁)(X - x₂)*...*(X-x_n)*(X - x_n+1) = (X - x_n+1)[Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n)] =

[Xⁿ⁺¹ - (x₁ + ... + x_n)Xⁿ + (x₁x₂ + ... + x_n-1x_n)X^n-1 - ... + (-1)ⁿX(x₁x₂*...*x_n)] - [Xⁿ(x_n+1) - (x_n+1)(x₁ + ... + x_n)X^n-1 + (x_n+1)(x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n*x_n+1)]

= Xⁿ⁺¹ - (x₁ + ... + x_n + x_n+1)Xⁿ + (x₁x₂ + ... + x_nx_n+1)X^n-1 ... + (-1)ⁿ⁺¹(x₁*...*x_n+1) =

= Xⁿ⁺¹ - s₁Xⁿ + s₂X^n-1 - ... + (-1)ⁿ⁺¹s_n+1

QED

Quotient Rings

2009-09-01T00:25:00.000-07:00

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

In a previous blogs, I wrote about cosets and ideals. In today's blog, I will show how we can bring these ideas together to define quotient rings. Here are links to review the properties of groups, subgroups, or commutative rings.

Definition 1: A/I

A/I = { a + I such that a ∈ A}

Note: This is a set of sets. For example, if a + I is a coset, then A/I is the set of distinct cosets. For review of the a + I notation, see here.

Example 1.1: Modular sets

The sets Z/nZ are all examples of A/I.

Z/2Z = { 0+2z, 1+2z } since { 0 + 2z = 2 + 2z = 2z + 2z, 1 + 2z = 3 + 2z = ... }

Z/3Z = { 0 + 3z, 1 + 3z, 2 + 3z }

A/I becomes especially interesting when A is a Commutative Ring and I is in an Ideal. I will assume both of these properties for the rest of this article.

Definition 2: Addition for A/I

(a + I) + (b + I) = (a + b) + I

Definition 3: Multiplication for A/I

(a + I) * (b + I) = ab + I

Lemma 1: Addition for A/I is well defined

Proof:

(1) Let:

s + I = s' + I

t + I = t' + I

(2) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(3) So, there exists a,b such that a, b ∈ I and:

s = s' + a

t = t' + b

(4) s + t = (s' + a) + (t' + b) = s' + a + t' + b

(5) s + t + I = s' + t' + (a + b) + I

(6) Since a ∈ I and b ∈ I, it follows that a + b ∈ I (from Closure)

(7) Using Lemma 2, here, we then have:

(a+b) + I = I

(8) So that:

s + t + I = s' + t' + I

QED

Lemma 2: Multiplication for A/I is well defined

Proof:

(1) Assume that I is an ideal.

(2) Let:

s + I = s' + I t + I = t' + I

(3) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(4) There exists a,b such that a, b ∈ I and:

s = s' + a t = t' + b

(5) st = (s' + a)(t' + b) = s't' + at' + s'b + ab

(6) st + I = s't' + at' + s'b + ab + I

(7) Since a,t',s',b ∈ I, we have (see Definition 2, here, and Definition 1, here for details):

at' ∈ I

s'b ∈ I

ab ∈ I

(8) So, at' + s'b + ab + I = I [See Lemma 2, here]

(9) And:

st + I = s't' + I

QED

Lemma 3: If A is a Commutative Ring and I is an Ideal, then A/I is a ring

Proof:

(1) Commutative Rule for Addition

(a + I) + (b + I) = (a + b) + I = (b + a) + I = (b + I) + (a + I)

(2) Associative Rule for Addition

[(a + I) + (b + I)] + (c + I) = (a + b) + I + c + I = (a + b + c) + I = a + I + (b + c) + I = (a + I) + [(b + I) + (c + I)]

(3) Additive Identity

0+I is the additive identity since 0 ∈ A and for all a, (a + I) + (0 + I) = (a + 0) + I = a + I

(4) Additive Inverse

-a+I is the additive inverse since a ∈ A → -a ∈ A and (a + I) + (-a + I) = (a + -a) + I = 0 + I

(5) Associative Rule for Multiplication

[(a + I)*(b+I)](c + I) = (ab + I)(c + I) = (abc + I) = (a + I)(bc + I) = (a+I)[(b+I)(c+I)]

(6) Distributive Rule

(a + I)[(b + I) + (c + I) ] = [(a + I)(b+I)] + [(a+I)(c+I)] = (ab + I) + (ac + I)

QED

Definition 5: Quotient Ring

The ring A/I is called the quotient ring of A by the ideal I.

Example 5.1: Sets that form quotient rings

Z/2Z and Z/3Z are factor rings [See Example 1.1 above for details]

Reference

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

Cosets

2009-08-31T01:00:00.000-07:00

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: g + H

Let g + H = { g + h such that h ∈ H }.

Example 1.1:

Let G be the set { 0, 1, 2, 3 }

Let H be the set { 9, 10, 11 }

Then:

0 + H = { 9, 10, 11 }

1 + H = { 10, 11, 12 }

2 + H = { 11, 12, 13 }

3 + H = { 12, 13, 14 }

Definition 2: coset of H in G

The set g + H is a coset if and only if there exists a group G such that g ∈ G and H is a subgroup of G.

Note: Technically, definition 3 above describes a left coset. A coset can also be defined as H + g which is called a right coset. The notation of g + H defines a coset based on addition. Cosets can also be defined on multiplication and represented as gH or Hg.

Example 2.1:

Let G = the set of integers Z
Let H = 2Z = the set of even integers

1 ∈ Z
1+H = odd integers = { ... -3, -1, 1, 3, ... }

Example 2.2: Cyclic Group Z₄

Z₄ = { 0, 1, 2, 3}

It is a group since:

(1) Closure

Since Z₄ is always modulo 4, it is clear that that operation of addition is closed (for example: 3 + 2 = 1)

(2) Associativity

For any elements a,b,c ∈ Z₄, (a + b) + c = a + (b + c)

(3) Identity Element

0 is the identity element

(4) Inverse Element

Since it is modulo 4, each element has an inverse: 0+0=0, 1+3=0, 2+2=0

Let H = { 0 , 2 }

H is a subset and H is itself a group since:

(1) It has closure: 0+2=2, 0+0=0, 2+2=0

(2) It has associativity.

(3) It has a identity element: 0

(4) From #1, it is clear that each element is its own inverse.

From Z₄ and H, there are 2 distinct cosets:

0 + H = { 0, 2}
1 + H = { 1, 3}
2 + H = { 2, 0} = 0 + H
3 + H = { 3, 1} = 1 + H

Lemma 1:

For the coset H in G:

For all a,b ∈ G:

a + H = b + H if and only if a - b ∈ H

Proof:

(1) Assume that a + H = b + H

(2) So, for all x ∈ (a + H) → x ∈ (b + H)

(3) a ∈ a + H, b ∈ b + H [since H is a group and therefore 0 ∈ H]

(4) a ∈ b + H [follows directly from step #2]

(5) Let c = a - b

(6) b + c ∈ b + H [since b + c = a and a ∈ b + H]

(7) So c ∈ H [from step #6 and Definition 3 above]

(8) Assume that (a-b) ∈ H

(9) Assume that x ∈ a + H

(10) Let y = x - a

(11) y ∈ H [since x = a + y]

(12) y + (a - b) ∈ H since H is a group

(13) x - b ∈ H [since y + (a - b) = (x - a) + (a - b) = x - b]

(14) Then x ∈ b + H since [b + x-b = x]

(15) We can make the same argument if x ∈ b + H so this shows that a + H = b + H.

QED

Lemma 2:

For the coset H in G:

a ∈ H → a + H = H

Proof:

(1) Assume that a ∈ H

(2) Assume that x ∈ a + H

(3) Then there exists h such that x = a + h where h ∈ H [See Definition 1 above]

(4) But if a ∈ H and h ∈ H, then a + h ∈ H. [since H is a group, see Definition 2 above and the Closure property of groups]

(5) So x ∈ H

(6) Assume that x ∈ H

(7) Let b = x - a

(8) Since a ∈ H, it follows that -a ∈ H [See Definition 2 above and the Inverse property of groups]

(9) Since x ∈ H and -a ∈ H, it follows that b ∈ H [from the Closure property of groups]

(10) So then, x ∈ a + H [since b ∈ H and x = a + b from Definition 1 above]

QED

Reference

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

Ideals

2009-08-30T15:13:00.000-07:00

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: stable under multiplication

a set I is stable under multiplication by the elements in A if and only if:

a ∈ A and x ∈ I ↔ ax ∈ I.

Example 1.1: set that is stable under multiplication

A = {1}

I = {1}

Example 1.2: set that is not stable under multiplication

A= {1,2}

I = {2}

2 ∈ A and 2 ∈ I but 2*2=4 is not in I.

Definition 2: An ideal I

Let A be a commutative ring.

a set I is an ideal if and only if I is a subgroup of the additive group of A which is stable under multiplication by the elements in A (see Definition 1 above).

Example 2.1: Example of a set that is an ideal: 2Z

The set 2Z is the set of even integers.

2Z = { ... -2, 0, 2, 4, 6, ... }

2Z is a subset of the set of integers Z and Z is a commutative ring and a group.

2Z is a group on the operation of addition so it is a subgroup of Z.

2Z is stable under multiplication by elements of Z since an even integer multiplied by any integer is an even integer.

Example 2.2: Example of a set that is not an ideal: 2W

Let 2W be the set of even whole numbers = { 0, 2, 4, ... }

2W is a subset of the set of integers Z which is a commutative ring and a group.

2W is not a group on the operation of addition since there is no inverse element.

2W is not stable under multiplication by the elements of Z since -1 ∈ Z and 2 ∈ 2W but -2 is not in 2W.

Lemma 1:

The set of multiples for a given polynomial is an ideal of the set of all polynomials for a given field

Proof:

(1) Let F[X] be the set of all polynomials in the field F

(2) Let (P) be the set of multiples of polynomials for a given polynomial P so that:

(P) = { PQ where Q ∈ F[X] }

(3) All fields are commutative rings so F[X] is a Commutative Ring. [See Definition 3, here for Fields]

(4) (P) is itself a group since:

(a) Closure on addition

If pq, pq' ∈ (P), then (pq+pq')=p(q+q') ∈ (P) since (q+q') ∈ F[X]

(b) Associativity on Addition

(pq + pq') + pq'' = p([q + q'] + q'') = p(q + [q' + q'']) = pq + (pq' + pq'')

(c) Identity Element

0 = P*0 ∈ (P) since 0 ∈ F[X]

(d) Inverse Element

For all pq, there exists -pq since -pq = p(-q) and -q ∈ F[X] if q ∈ F[X]

(5) Finally, (P) is stable under multiplication since:

(a) Assume pq, pq' ∈ (P)

(b) Then q,q' ∈ F[X]

(c) p ∈ F[X]

(d) So pqq' ∈ F[X] since F[X] is closed on multiplication.

(e) So p*(pqq') ∈ (P)

QED

Reference

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

Derivative of Increasing and Decreasing Functions

2009-02-07T19:31:00.000-08:00

Lemma: Derivative of Increasing and Decreasing Functions

Let f be a continuous function on (a,b) where the at no point f'(x)=0.

If for all x on [a,b], f(x) is increasing, then f'(x) is positive.

If for all x on [a,b], f(x) is decreasing, then f'(x) is negative.

Proof:

(1) From the definition of derivatives (see Definition 1, here):

f'(x) = lim (Δx → 0) [f(x + Δx) - f(x)]/(Δx)

So, the sign of f'(x) is the sign of [f(x + Δx) - f(x)]/Δx and we can assume that is is nonzero.

(2) Case I: Δx is positive

If f(x) is strictly increasing, then f(x + Δx) - f(x) is positive and f'(x) is positive.

If f(x) is striclty decreasing, then f(x + Δx) - f(x) is negative and f'(x) is negative.

(3) Case II: Δx is negative

If f(x) is strictly increasing, then f(x + Δx) - f(x) is negative and f'(x) is positive

If f(x) is strictly decreasing, then f(x + Δx) - f(x) is positive and f'(x) is negative.

QED

An Inequality Lemma for the Cauchy Bound of Real Roots

2009-02-03T21:28:00.000-08:00

The following result is used my proof of Cauchy's Bound for real roots.

Lemma 1: abs(c)ⁿ = abs(cⁿ)

Proof:

(1) Assume that c is nonnegative

(2) Then, cⁿ is nonnegative

(3) Then, abs(cⁿ) = cⁿ

(4) Since abs(c) = c, it follows that: cⁿ = abs(c)ⁿ

(5) Assume that c is negative

(6) We can assume that n is odd

[Otherwise, cⁿ = (-c)ⁿ = abs(c)ⁿ = abs(cⁿ) ]

(8) abs(cⁿ) = -cⁿ = (-1)ⁿ*cⁿ = (-c)ⁿ = abs(c)ⁿ

QED

Lemma 2:

Let:

a_ncⁿ = -a_n-1c^n-1 + .... + -a₀Then:abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

Proof:

(1) Using the Triangle Inequality (see Lemma 4, here), we know that:

abs(-a_n-1c^n-1 + .... + -a₀) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

so that:

abs(a_ncⁿ) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

(2) Using a basic property of inequalities (see Lemma 1, here):

abs(a_n)*abs(cⁿ) = abs(a_ncⁿ)

and likewise:

abs(-a_n-1)*abs(c^n-1) = abs(-a_n-1c^n-1)

...

(3) So we have:

abs(a_n)*abs(cⁿ) ≤ abs(-a_n-1)*abs(c^n-1) + ... + abs(-a₀)

(4) Using Lemma 1 above, we have:

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

QED

Triangle Inequality

2009-02-03T10:09:00.000-08:00

Definition 1: Absolute Value

abs(a) = a if a is nonnegative or abs(a)=-a if a is negative.

So for example:

abs(5) = 5

abs(0) = 0

abs(-1) = 1

Now, let's look at some basic properties

Lemma 1: abs(ab) = abs(a)*abs(b)

Proof:

Case I: both a,b positive

abs(ab) = ab = abs(a)*abs(b)

Case II: both a,b negative

abs(ab) = ab = (-a)*(-b) = abs(a)*abs(b)

Case III: one negative, one positive

Assume a is positive, b is negative (since a,b are symmetrical, we can switch them as necessary)

abs(ab) = -ab = a*(-b) = abs(a)*abs(b)

QED

Lemma 2: -abs(a) ≤ a ≤ abs(a)

Proof:

Case I: a is nonnegative

-a ≤ a ≤ a

so

-abs(a) ≤ a ≤ abs(a)

Case II: a is negative

a ≤ a ≤ -a

so

-abs(a) ≤ a ≤ abs(a)

QED

Lemma 3: abs(a) ≤ b if and only if -b ≤ a and a ≤ b.

Proof:

(1) Assume abs(a) ≤ b

Case I: a is nonnegative

abs(a) = a

Since abs(a) ≤ b, it follows that a ≤ b and b is nonnegative

Since b is nonnegative and a is nonnegative, then it -b ≤ a.

Case II: a is negative

Since abs(a) ≤ b, it follows that -a ≤ b which is the same as -b ≤ a and therefore b must be nonnegative.

Since b is nonnegative, it follows that a ≤ b.

(2) Assume that -b ≤ a and a ≤ b.

Case I: a is nonnegative

Since a ≤ b, it follows that b is nonnegative

So abs(a) ≤ b.

Case II: a is negative

Since -b ≤ a, it follows that b ≥ -a.

Since a is negative, -a is positive, and we have:

abs(a) ≤ b.

QED

Lemma 4: Triangle Inequality

For all real numbers a,b

abs(a + b) ≤ abs(a) + abs(b)

Proof:

(1) For all real numbers a,b (from Lemma 1 above)

-abs(a) ≤ a ≤ abs(a)

-abs(b) ≤ b ≤ abs(b)

(2) Adding these two conditions together gives us:

-[abs(a) + abs(b)] ≤ a + b ≤ abs(a) + abs(b)

(3) Let c = a+b and d =abs(a) + abs(b)

(4) Using Lemma 3, we know that:

abs(c) ≤ d if and only if -d ≤ c and c ≤ d.

(5) But using step #2, we know that:

-d = -[abs(a) + abs(b)] ≤ c = a + b

and

c = a + b ≤ d = abs(a) + abs(b)

(6) So, using step #4 we get:

abs(c) ≤ d

which is equivalent to:

abs(a + b) ≤ abs(a) + abs(b)

QED

Polynomials are continuous

2009-02-01T19:58:00.000-08:00

For a definition of polynomials, see Definition 1, here. For a definition of continuous functions, see Definition 1, here.

Lemma 1: f(x)=x is continuous

Proof:

(1) Let ε be any arbitrary value.

(2) Let δ = ε

(3) For any point c, it is clear that if x lies in (c - δ, c + δ), then f(x)=x lies in (f(c) - ε, f(c) + ε )

QED

Corollary 1.1 : Polynomials are continuous

Proof:

(1) The function f(x)=x is continuous. [See Lemma 1 above]

(2) Since the product of continuous functions is continuous [See Lemma 3, here], then f(x)=xⁿ where n is a positive integer is also continuous.

(3) Since f(x)=C is continuous [See Lemma 1, here], it follows that any function of the form cxⁿ is also continuous.

(4) Since the addition of continuous functions is continuous [See Lemma 2, here], it follows that any polynomial function is continuous since it consists of the form:

f(x) = c₀ + c₁x + c₂x² + ... + c_nxⁿ

where each c_i is a constant.

QED

Lemma 2: The Derivative of a polynomial is itself a polynomial

Proof

(1) The derivative of each term of a polynomial is itself a term of a polynomial [See the Lemma 2, here]

(2) So, it follows that the derivative itself is also a polynomial. [See Definition 1, here]

QED

Corollary 2.1: The derivative of a polynomial is a continuous function.

Proof:

This follows directly from Lemma 2 above and Corollary 1.1 above.

QED

Interval of a Function with Simple Roots

2009-02-01T17:44:00.000-08:00

Lemma: Interval of a Function with Simple Roots

Let f be a function with simple roots such that f(c)=0

Then there exists an interval (a,b) such that:

c is in (a,b)

for all x in (a,b), f'(x) is all positive or all negative

Proof:

(1) Since f has only simple roots and f(c)=0, then it follows that f'(c) ≠ 0. [See Corollary 1.1, here]

(2) Since f is a polynomial, we know that f'(x) is continuous. [See Corollary 2.1, here]

(3) Since f'(c) is nonzero, let ε be nonzero and less than abs{ f'(c) }.

(4) Since f'(x) is continuous at c, there exists a number δ such that if x is in the (c - δ, c + δ), then f'(x) is in (f'(c)-ε, f'(c)+ε). [By the definition of a continuous function]

(5) Since ε is less than abs{f'(c) }, it follows that for x in (c -δ, c + δ), f'(x) is either entirely positive or entirely negative.

QED

Greatest Common Divisor of a Polynomial and its First Derivative

2009-01-31T12:16:00.000-08:00

Lemma 1:

Let a be a root of a polynomial P.

Then:

a is a multiple root of P if and only if a is also a root of P' (the first derivative of P)

Proof:

(1) Since a is a root of P, there exists a polynomial Q such that (see Theorem, here):

P = (x - a)Q

(2) Using the Product Rule of Derivatives (see Lemma 4, here), we know that:

P' = Q + (x-a)Q'

(3) But then (x-a) only divides P' if and only if it also divides Q.

QED

Corollary 1.1:

If a polynomial has only simple roots

Then:

Its first derivative does not share any of those roots.

Proof

(1) Assume that a polynomial P has only simple roots.

(2) Assume that a root a divides both P and P'

(3) Then by Lemma 1 above, a is a multiple root of P.

(4) But by step #1 this is impossible so we reject our assumption in step #2.

QED

Lemma 2:

If a polynomial P has only simple roots

Then P,P' are relatively prime.

Proof:

(1) Assume that P,P' are not relatively prime.

(2) Then, they have a common irreducible factor of degree 1.

[Since by definition, two polynomials are relatively prime if their only common factor is of degree 0]

(3) Then there exists a polynomial of the form X-a that divides both P and P' (See Thereom, here)

(4) Then from Lemma 1 above, a is a multiple root of P

(5) But this is impossible, so we reject our assumption in step #1.

QED

References

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

Alternate Form of the Greatest Common Divisor Algorithm for Polynomials

2009-01-31T11:56:00.000-08:00

The usual form of the Greatest Common Divisor for Polynomials uses a series of steps of the form (see the proof for the usual form, here):

(a) R₁ = Q₃R₂ + R₃

(b) R₂ = Q₄R₃ + R₄

...

(c) R_n-2 = Q_nR_n-1 + R_n

(d) R_n-1 = Q_n+1R_n + R_n+1

But for Sturm's Theorem, I need to use an alternate form.

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

Definition 1: Divisor for Polynomials

Let P₁, P₂ ∈ F[X].

We say that P₂ divides P₁ if there exists Q ∈ F[X] such that P₁ = P₂Q

Definition 2: GCD for Polynomials

A greatest common divisor (GCD) of P₁, P₂ is a polynomial D ∈ F[X] which has the following properties:

(a) D divides P₁ and P₂
(b) If S is a polynomial which divides P₁ and P₂, then S divides D.

Definition 3: Relatively prime polynomials

If 1 is the GCD for polynomials P₁, P₂, then P₁, P₂ are said to relatively prime polynomials.

Definition 4: degree: deg

The deg of a polynomial P is the greatest integer n for which the coefficient Xⁿ in the expression of P is not zero.

Theorem 1: Alternate Form of Euclid's Algorithm for Greatest Common Divisor for Polynomials

For any two polynomials P₁, P₂, there exists a GCD

Proof:

(1) Let P₁, P₂ be any two polynomials such that deg P₁ ≥ deg P₂

(2) If P₂ = 0, then P₁ is the GCD of P₁, P₂ [See Definition 2 above]

(3) Otherwise, we divide P₁ by P₂ using the the alternate form of Euclidean Division Algorithm for Polynomials. [See Theorem, here]

(4) Then there exists two polynomials Q₁, R₁ such that:

P₁ = Q₁P₂ - R₁

and deg R₁ is less than deg P₂.

(5) If R₁ = 0, then P₂ is the GCD of P₁, P₂

(6) Next, we divide P₂ by R₁ to get:

P₂ = Q₂R₁ - R₂

and deg R₂ is less than deg R₁

(7) If R₂ ≠ 0, then we can set up the following equations:

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

(8) Since deg P₂ is greater than deg R₁ which is greater than deg R₂ which is greater than ... deg R_n which is greater deg R_n+1, this sequence cannot extend indefinitely.

(9) Therefore, R_n+1 = 0 for some n.

(10) R_n divides P₁, P₂ since:

Because R_n+1=0, R_n divides R_n-1

Because R_n divides R_n-1, from equation 7c, R_n divides R_n+1

We can now proceed up each of these implied equations in the same way until we get to 7b.

Since we have shown that R_n divides R₂ and R₃ before it, it is clear from 7a, that R_n divides R₁

It is clear from step #6 that R_n divides P₂ and clear from step #4 that R_n divides P₁

(11) Assume that P₁ and P₂ are both divisible by a polynomial S.

(12) Then by step #4, S must divide R₁.

(13) By step #6, S must divide R₂

(14) We can now use the same argument to go through the equations in step #7 to conclude that S must likewise divide R_n.

(15) This proves that R_n is the GCD for P₁,P₂ [See Definition 2 above]

QED

References

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

Ring of Polynomials

2009-01-29T23:37:00.000-08:00

If you are not comfortable with the idea of rings, start here.

Definition 1: Polynomial in one indeterminate with coefficients in a ring A

P : N → A such that P = { n ∈ N : P_n ≠ 0 }

where N is the set of natural numbers (that is, 0, 1, 2, ... )

As a convention, this mapping is usually represented in the form:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

where n ∈ N.

Example 1:

5x² + 3x + 2 is a polynomial.

5,3,2 are all integers which is a ring (see here for details on integers)

{ 2 → 5, 1 → 3, 0 → 2 }

Definition 2: Polynomial Addition

(P + Q)_n = P_n + Q_n

Example 2:

(5x² + 3x + 2) + (3x² + x + 5) = (5 + 3)x² + (3+1)x + (2+5) = 8x² + 4x + 7

Definition 3: Polynomial Multiplication

(PQ)_n = ∑(i+j=n) P_i*Q_j

Example 3:

(5x² + 3x + 2)(3x² + x + 5) = (5*3)x⁽²⁺²⁾ + (5*1 + 3*3)x⁽²⁺¹⁾ + (5*5 + 3*1 + 2*3)x⁽²⁺⁰⁾ + (3*5 + 2*1)x⁽¹⁺⁰⁾ + (2*5)x⁰

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x² + 3x + 2 ∈ Z[X] where Z is the set of all integers.

Lemma 1:

If A is a ring, then A[X] is a ring. If A is a commutative ring, then A[X] is a commutative ring.

Proof:

(1) I will show that A[X] has all the properties of a ring.

(2) Commutative Property for Addition:

P_n + Q_n = (P + Q)_n = (Q + P)_n = Q_n + P_n

(3) Associative Property for Addition

(P_n + Q_n) + R_n = (P + Q)_n + R_n = ([P + Q] + R)_n = (P + [Q + R])_n

= P_n + (Q + R)_n = P_n + (Q_n + R_n)

(4) Additive Identity

This is the 0 polynomial. P_n + 0 = (P + 0)_n = P_n

(5) Additive Inverse

P_n + -P_n = (P + -P)_n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (P_i*Q_j)*R_k = [(P*Q)*R]_n = [P*(Q*R)]_n = ∑ (i+j+k=n)P_i*(Q_j*R_k)

(7) Distributive Property for Multiplication

∑(i+j=n) P_i(Q_j + R_j) = ∑(i+j=n)P_i(Q + R)_j = [P(Q+R)]_n
= (PQ + PR)_n = ∑(i+j=n)(P_iQ_j) + ∑(i+j=n)(P_iR_j)

We can use the same argument to prove:

∑(i+j=n) (Q_j + R_j)P_i = ∑(i+j=n)(Q_jP_i) + ∑(i+j=n)(R_jP_i)

(8) Commutative Property for Multiplication is true if A has the Commutative Property for Multiplication

Assume that A is commutative.

∑(i+j=n)P_iQ_j = (PQ)_n = (QP)_n = ∑(i+j=n)Q_jP_i

QED

References

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

Degree of a Polynomial

2009-01-29T21:42:00.000-08:00

Definition 1: Degree of a polynomial

The highest nonzero exponent is the degree of the polynomial.

As a convention, the degree of a zero polynomial is said to be -∞.

Lemma 1: deg(A+B) ≤ max(degA,degB)

Proof:

(1) We start with with deg A = 0, deg B=0 where A ≠ -B [We can ignore deg = - ∞ since by the Additive Identity Property (see here), it is true]

(2) A+B ≠ 0, so deg(A+B) = 0

(3) Assume that this is true up to deg A, deg B ≤ n-1.

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) We can assume that a_n ≠ -b_n [Since if this is the case, the n degrees cancels out and the proposition is true by the inductive hypothesis.]

(6) a_n + b_n = (a+b)_n [See here for Additive Rule for Polynomials]

(7) So the deg(A+B) = n

QED

Lemma 2: deg(AB) = deg(A) + deg(B)

Proof:

(1) Assume deg A = 0, deg B = 0

(2) Then deg(AB) = 0 = 0 + 0

(3) Assume that the proposition is true up to n-1

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) The highest exponent will be a_n*b_n = (a*b)_n+n

(6) deg(a*b)_n+n = 2n = deg(a) + deg(b)

QED

References

"Degree of a Polynomial", Wikipedia.org

Alternate Form of the Division Algorithm for Polynomials

2009-01-29T21:08:00.000-08:00

Theorem: Alternative Form of the Division Algorithm for Polynomials

Let F be a field

Let f(x),g(x) be polynomials of F[x] where g(x) ≠ 0

Then:

There exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) - r(x) and r(x)=0 or deg r(x) is less than deg g(x)

Proof:

(1) Let f(x),g(x) be two polynomials such that g(x) ≠ 0

(2) We can assume that deg f(x) ≥ deg g(x) since:

if deg f(x) = 0, then f(x) = g(x)(0) - 0.

if deg f(x) is less than deg g(x), then f(x) = g(x)(0) - [-f(x)]

(3) Let:

f(x) = a_nxⁿ + ... + a₀

g(x) = b_mx^m + ... + b₀

where a_n and b_m are nonzero.

[We can make this assumption since g(x) ≠ 0 and deg f(x) ≥ deg g(x).]

(4) I will use induction to establish the existence of q(x), r(x).

(5) q(x),r(x) exist if deg f(x) = 0 since:

(a) Assume deg f(x) = 0

(b) Then there exists C such that f(x)=C

(c) Since deg f(x) ≥ deg g(x), it follows that deg g(x)= 0 and there exists D such that g(x)=D

(d) Let q(x) = C/D

(e) Then it follows that f(x) = g(x)*q(x) - 0

(6) Assume that our assumption holds true up to deg f(x) = n-1

(7) Let:

f₁(x) = f(x) - a_nb_m^-1x^n-mg(x)

(8) So, deg f₁(x) is less than deg f(x)

(9) By the induction hypothesis, there exists q₁(x) and r₁(x) such that:

f₁(x) = q₁(x)g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(10) So, then:

f₁(x) + a_nb_m^-1x^n-mg(x) = a_nb_m^-1x^n-mg(x) + q₁(x)g(x) - r₁(x)

= [a_nb_m^-1x^n-m + q₁(x)]g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(11) This proves the first part of the theorem. To complete it, we need to prove uniqueness.

(12) Assume that:

f(x) = g(x)q(x) - r(x) = g(x)q'(x) - r'(x)

where deg r(x), deg r'(x) = 0 or is less then deg g(x)

(13) So that:

0 = g(x)q(x) - r(x) - g(x)q'(x) + r'(x)

(14) Then:

r(x) - r'(x) = g(x)[q(x) - q'(x)]

(15) Assume that q(x) - q'(x) is nonzero.

(16) Then, deg g(x)[q(x)-q'(x)] = deg g(x) + deg (q(x) - q'(x)) [See Lemma 2, here]

(17) And, deg(r(x) - r'(x)) ≤ max(deg r(x),deg r'(x)) [See Lemma 1, here]

(18) But this is impossible since deg(r(x)) is less than deg g(x)

(19) So, we have a contradiction and we reject our assumption in step #15.

(20) So, if q(x) - q'(x) is 0, then it follows that r(x) - r'(x) is also 0.

(21) Then q(x) = q'(x) and r(x) = r'(x)

QED

Reference

Joseph A. Gallian, Contemporary Abstract Algebra.

Inequality lemmas

2009-01-28T22:42:00.000-08:00

Lemma 1: abs(a/b) ≤ 1 if and only if abs(a) ≤ abs(b)

Proof:

Case I: a,b are both positive

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) a ≤ b

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) a ≤ b

(7) a/b ≤ 1

(8) abs(a/b) ≤ 1

Case II: a,b are both negative

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) -a ≤ -b [since -b is positive]

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ -b

(7) a/b ≤ 1 [since -b is positive]

(8) abs(a/b) ≤ 1

Case III: Only b is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) (a/b) ≤ -1

(4) a ≤ -b [since b is negative and -b is positive]

(5) abs(a) ≤ abs(b) [ since abs(b) = -b ]

(6) Assume abs(a) ≤ abs(b)

(7) a ≤ -b

(8) a/b ≥ -1 [since b is negative]

(9) -(a/b) ≤ 1

(10) abs(a/b) ≤ 1

Case IV: Only a is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) -a ≤ b [since b is positive]

(4) abs(a) ≤ abs(b) [since abs(a) = -a and abs(b) = b]

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ b

(7) -a/b ≤ 1

(8) abs(a/b) ≤ 1

QED

Corollary 1.1: abs(a) is greater than abs(b) if and only if abs(a/b) greater than 1

Proof:

(1) Assume that abs(a) is greater than abs(b)

(2) Assume that abs(a/b) is not greater than 1

(3) Then abs(a/b) ≤ 1

(4) Then abs(a) ≤ abs(b) [From Lemma 1 above]

(5) But this contradicts step #1 so we reject our assumption in step #2.

(6) Assume that abs(a/b) is greater than 1.

(7) Assume that abs(a) is not greater than abs(b)

(8) Then abs(a) ≤ abs(b)

(9) Then abs(a/b) ≤ 1 [From Lemma 1 above]

(10) But this contradicts step #6 so we reject our assumption in step #7.

QED

Lemma 2:

if a,b,q are integers such that abs(a/b - q) is less than 1

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a/b - q) is greater than (1/2) [Otherwise, set c = q and we are done]

(2) if (a/b - q) is less than -1/2, then [a/b - (q-1)] is less than 1/2 and [a/b - (q-1)] is greater than 0

(3) if (a/b - q) is greater than 1/2, then [a/b - (q+1)] is greater than -1/2 and [a/b - (q+1)] is less than 0

QED

Corollary 2.1:

Let a,b be integers

if abs(a) ≤ abs(b)

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a) ≤ abs(b)

(2) Then abs(a/b) ≤ 1. [See Lemma 1 above]

(3) If (a/b) = 0, then c = 0 and the conclusion follows.

(4) if (a/b) ≥ -1, then abs(a/b + 1) is less than 1.

(5) if (a/b) ≤ 1, then abs(a/b - 1) is greater than -1.

(6) So, the conclusion follows from Lemma 2 above.

QED

A Simple Lemma Based on Calculus

2009-01-16T08:35:00.000-08:00

The lemma in today's proof is used in my proof of Sturm's Problem of the Number of Roots. I will add a link to this proof when it is available.

Lemma 1:

Let F(x) = A*B

Then:

F'(x)/F(x) = A'/A + B'/B

Proof:

(1) Using the Product Rule (see Lemma 4, here):

F'(x) = A'B + B'A

(2) So:

F'(x)/F(x) = (A'B + B'A)/AB = A'B/AB + B'A/AB = A'/A + B'/B

QED

Corollary 1.1:

Let: F(x) = A₁*A₂*...*A_n

Then:

F'(x)/F(x) = A'₁/A₁ + A'₂/A₂ + ... + A'_n/A_n

Proof:

(1) Let F(x)=AB

Using Lemma 1 above, we know that F'(x)/F(x) = A'/A + B'/B

(2) Assume that this is true up to n-1 so that:

if F(x) = U₁*...*U_n-1

Then:

F'(x)/F(x) = U'₁/U₁ + U'₂/U₂ + ... + U'_n-1/U_n-1

(3) Let G(x) = U_n*(U₁*...*U_n-1)

(4) Using the Product Rule (see Lemma 4, here):

G'(x) = U'_n*(U₁*....*U_n-1) + U_n*(U₁*...*U_n-1)'

(5) Then G'(x)/G(x) = U'_n/U_n + (U₁*...*U_n-1)'/(U₁*...*U_n-1)

(6) From our assumption in step #2, this gives us:

G'(x)/G(x) = U'_n/U_n + U'₁/U₁ + ... + U'_n-1/U_n-1

(7) By Induction, we are done.

QED

Lemma 2:

Let F(x) = (x - α)^a

Then:

F'(x) = a(x - α)^a-1

Proof:

(1) Let U = x - α

(2) Using the power rule (see Lemma 2, here):

(d/dx)U^a = aU^a-1dU

(3) So, we have:

F'(x) = aU^a-1dU = a(x-α)^a-1*1 = a(x-α)^a-1

QED

Corollary 2.1:

Let F(x) = (x - α)^a

Then:

F'(x)/F(x) = a/(x - α)

Proof:

(1) From Lemma 1 above, F'(x) = a(x - α)^a-1

(2) Then F'(x)/F(x) = a(x-α)^a-1/(x - α)^a = a/(x - α)

QED

Corollary 2.2:

Let F(x) = (x - α)^a(x - β)^b(x - γ)^c*...

Then:

F'(x)/F(x) = a/(x - α) + b/(x - β) + c/(x - γ) + ...

Proof:

(1) Let A = (x - α)^a, B = (x - β)^b, C= (x - γ)^c, etc.

(2) So, we have: F(x) = A*B*C*...

(3) Using Corollary 1.1 above, this gives us that:

F'(x)/F(x) = A'/A + B'/B + C'/C + ...

(4) Using Corollary 2.1 and step #1, this gives us:

F'(x)/F(x) = a/(x - α) + b/(x - β) + c/(x - γ) + ...

QED

Complete Residue System

2008-10-20T23:17:00.000-07:00

Definition 1: Complete Residue System (from Stark's Introduction to Number Theory)

A set of n integers a₁, a₂, ..., a_n is a complete residue system if every integer is congruent (mod n) to exactly one of the a_j's.

In other words, a complete residue system is a one-to-one correspondence (bijection) between a set of elements the different congruence classes modulo n.

Lemma 1:

Any set of n consecutive integers is a complete residue system modulo n.

That is for any integer i, {i+0, i+1, ..., i+n-1} is a complete residue system

Proof:

(1) 0, 1, ..., n-1 is a complete residue system modulo n.

(2) Let i be any integer.

(3) For any integer a, there exists an integer j such that:

a - i ≡ j (mod n) and j ∈ {0, 1, ..., n-1}

so that:

a ≡ j + i (mod n)

(4) Since a can be any integer, this shows that j+i is "onto" the complete residue system.

(5) To complete the proof, we have to show that j+i is also "one-to-one" with the complete residue system.

(6) Suppose that j₁ and j₂ are different integers such that:

a ≡ j₁ + i (mod n)

a ≡ j₂ + i (mod n)

(7) Then:

a - i ≡ j₁ (mod n)

a - i ≡ j₂ (mod n)

(8) But then a -i is congruent to two distinct elements of the complete residue system which is impossible.

(9) Hence, every integer i + j is a distinct congruence class.

QED

Lemma 2:

If gcd(a,n)=1, then there exists an integer c such that ac ≡ 1 (mod n)

Proof:

(1) By Bezout's Identity (see Lemma 1, here), thre exists integers c,d such that:

ac + nd = 1.

(2) Which means that:

ac - 1 = -nd

(3) And therefore:

ac ≡ 1 (mod n)

QED

Lemma 3:

If gcd(b,n)=1 and the numbers a₁, ..., a_n form a complete residue system (mod n), then for all integers c, the numbers b*a₁+c, ..., b*a_n + c also form a complete residue system (mod n).

Proof:

(1) By Lemma 2 above, since gcd(b,n)=1, there exists an integer e such that:

b*e ≡ 1 (mod n)

(2) Let a₁, ..., a_n be a complete residue system (mod n). [See Definition 1 above]

(3) Since a_i is a complete residue system, For any integers c,d it follows that there exists an integer k such that 1 ≤ k ≤ n and:

e(d - c) ≡ a_k (mod n)

(4) Multiplying both sides by b gives us:

b*e(d-c) ≡ (d-c) ≡ b*a_k (mod n)

(5) This gives us:

d ≡ b*a_k + c (mod n)

(6) Since d can take on any value, it is clear that b*a_k + c is onto the complete residue set. That is, for any residue (d), we can find an expression of the form b*a_k + c that is congruent to it.

(7) To complete the proof, we need to show that each b*a_k + c is also one-to-one with the complete residue system.

(8) Assume that there exists an integer i such that 1 ≤ i ≤ n and:

d ≡ b*a_i + c (mod n)

(9) Subtracting c from both sides gives:

d - c ≡ b*a_i (mod n)

(10) Multiplying e to both sides gives us:

e(d-c) ≡ e*b*a_i ≡ a_i (mod n)

(11) But using step #3, we have:

e(d-c) ≡ a_i ≡ a_k (mod n)

(12) This demonstrates that i = k.

(13) Thus, every integer is congruent to exactly one of the n integers b*a₁ + c, ..., b*a_n + c.

(14) So, we have shown that this is a complete residue system (mod n).

QED

References

Harold M. Stark, An Introduction to Number Theory (MIT Press, 1978)

Field Extension

2008-10-20T21:52:00.000-07:00

The content in today's blog, assumes that you feel comfortable with the idea of fields. For review of this concept, start here.

Definition 1: subfield

A set B is a subfield of a set A if both A,B are fields and B is a subset of A.

Definition 2: field extension

A set A is a field extension of a set B if B is a subfield of A.

Definition 3: R=F(u)

A field R = F(u) if and only if the following is true:

(i) u is a number that may or may not be part of the field F

(ii) For any numbers x ∈ R, there exists coefficients a₀, ..., a_n such that all a_i ∈ F and x = a₀uⁿ + a₁u^n-1 + ... + a_n.

The important idea behind Definittion 3 above is that F(u) is a field extension of F.

References

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

field automorphism

2008-03-01T23:49:00.001-08:00

Definition 1: Bijective

A bijective map is a map f from set X to a set Y with the property that for every y in Y, there is exactly one x in X such that f(x) = y.

Definition 2: Homomorphism

A homomorphism is a map from one algebraic structure to another of the same type that preserves certain properties.

Definition 3: Isomorphism

An isomorphism is a bijective map f such that both f and its inverse f^-1 are homomorphisms.

Definition 4: Automorphism

An automorphism is an isomorphism from a mathematical object to itself.

Definition 5: Ring Homomorphism

A ring homomorphism is a mapping between two rings which preserves the operations of addition and multiplication.

If R,S are rings and f: is the mapping R → S, the the following properties hold:

(1) f(a+b) = f(a) + f(b) for all a,b ∈ R

(2) f(ab) = f(a)f(b) for all a,b ∈ R

(3) f(1) = 1

Definition 6: Field Automorphism

A field automorphism is a bijective ring homomorphism from a field to itself.

References

"Automorphism", Wikipedia.org
"Bijection", Wikipedia.org
"Homomorphism", Wikipedia.org
"Isomorphism", Wikipedia.org
"Ring Homomorphism", Wikipedia.org

(a + b)p ≡ ap + bp (mod p)

2008-03-01T04:01:00.000-08:00

Lemma 1:

if p is prime, then:

(a + b)^p ≡ a^p + b^p (mod p)

Proof:

(1) Using the Binomial Theorem (see Theorem here), we know that:

(2) Now, since p is a prime, it is clear that for each term p!/(m!)(p-m)!, p is not divisible by any term ≤ m or by any term ≤ p-m so that we have:

p!/(m!)(p-m)! = p*([(p-1)*...*p-m+1]/[m!])

(3) This shows that each of these terms is divisible by p and therefore:

[p!/(m!)(p-m)!]a^p-mb^m ≡ 0 (mod p)

(4) So that there exists an integer n such that:

(a + b)^p = a^p + np + b^p

(5) Since a^p + nb + b^p ≡ a^p + b^p (mod p), it follows that:

(a + b)^p ≡ a^p + b^p (mod p)

QED

The set of congruence classes modulo n: Z/nZ

2008-03-01T02:20:00.000-08:00

In considering modular arithmetic (see here for review if needed), we can divide all integers into congruence classes modulo n.

Definition 1: Congruence class modulo n: [i]

Let [i] represent the set of all integers such that [i] = { ..., i-2n, i-n, i, i+n, i+2n, ... }

To make this definition even clearer, let's consider the following lemma.

Lemma 1: x ∈ [i] if and only if x ≡ i (mod n)

Proof:

(1) Assume x ≡ i (mod n)

(2) Then n divides x - i

(3) So, there exists an integer a such that an = x - i

(4) So that x = an + i

(5) Assume that x ∈ [i]

(6) Then, there exists a such that x = i + an

(7) This shows that an = x - i and further that n divides x - i.

(8) Therefore, we have x ≡ i (mod n)

QED

Lemma 2: There are only n distinct congruence classes modulo n

Proof:

(1) To prove this, I will show that for all x ∈ Z, there exists i such that:

x ≡ i (mod n)

and

0 ≤ i ≤ n-1

(2) For x ∈ Z, there exists k such that x ≡ k (mod n)

(3) We can assume that k is positive since if k is negative, k ≡ -k (mod n) since n divides k + -k.

(4) We can further assume that k ≤ n-1, since if k ≥ n, it follows that k ≡ (k-n) (mod n) since n divides (k - [k-n]) = k -k + n = n.

QED

We can now consider the set of congruence classes modulo n as the set Z/nZ.

Definition 2: set of congruence classes modulo n: Z/nZ

Z/nZ = { [0], ..., [n-1]}

Example 1: Z/3Z

Z/3Z = { [0], [1], [2] }

For purposes of showing the relationship between Z and Z/nZ, I will from this point on view Z/nZ = {0, ..., n-1}.

So that Z/3Z will also be represented as {0, 1, 2}

Lemma 3: Z/nZ is a commutative ring

Proof:

(1) Z/nZ has commutative rule for addition

For all a,b ∈ Z/nZ: a+b ≡ b + a (mod n)

(2) Z/nZ has associative rule for addition

For all a,b,c ∈ Z/nZ: (a + b) + c ≡ a + (b + c) (mod n)

(3) Z/nZ has additive identity rule

0 ∈ Z/nZ and for all a ∈ Z/nZ: a ≡ a + 0 (mod n)

(4) Z/nZ has additive inverse rule:

(a) Let a be any congruence class modulo n such that a ∈ Z/nZ

(b) Assume a ≠ 0 for if a = 0, then a + a ≡ 0 (mod n) and a is its own additive inverse.

(c) Let b = n - a

(d) b ∈ Z/nZ since 1 ≤ b ≤ n-1

(e) a + b ≡ n ≡ 0 (mod n)

(5) Z/nZ has an associative rule for multiplication:

For all a,b,c ∈ Z/nZ: (ab)c ≡ a(bc) (mod n)

(6) Z/nZ has a distributive rule:

For all a,b,c ∈ Z/nZ: a(b+c) ≡ ab + ac ≡ (b + c)a (mod n)

(7) Z/nZ has a commutative rule for multiplication

For all a,b ∈ Z/nZ: ab ≡ ba (mod n)

(8) Thus, Z/nZ is a commutative ring. [See Definition 2, here]

QED

Lemma 4: if p is a prime, then Z/pZ is a field

Proof:

(1) Z/pZ has a multiplicative identity rule.

1 ∈ Z/pZ and for all a ∈ Z/pZ 1*a ≡ a*1 ≡ a (mod p)

(2) Z/pZ has a multiplicative inverse rule since:

(a) Let a be any nonzero element of Z/pZ

(b) If p = 2, then a is its own inverse and a*a ≡ 1*1 ≡ 1 (mod 2).

(c) If p ≥ 3, then let b = a^p-2

(d) Then a*b ≡ a*(a^p-2) ≡ a^p-1 ≡ 1 (mod p). [See Fermat's Little Theorem, here]

(3) Thus, Z/pZ is a field. [See Definition 3, here]

QED

Lemma 5:

if p is prime and ab ≡ 0 (mod p), then a ≡ 0 (mod p) or b ≡ 0 (mod p)

Proof:

(1) Assume a is not ≡ 0 (mod p)

(2) Since ab ≡ 0 (mod p), it follows that p divides ab.

(3) If a is not ≡ 0 (mod p), then it follows that p does not divide a.

(4) So, using Euclid's Lemma (see Lemma 2, here), it follows that p divides b.

(5) And equivalently, b ≡ 0 (mod p)

QED

References

Gareth A. Jones, J. Mary Jones, Elementary Number Theory, Springer, 2002.

monic polynomials

2008-01-28T21:31:00.001-08:00

In today's blog, I will present a property of monic polynomials. A monic polynomial is a polynomial of degree n where the coefficient of xⁿ is 1.

Lemma 1: Division by a monic polynomial

If f,g,h are polynomials such that f = g/h and g,h are monic. Then f is also monic.

Proof:

(1) Let g(x) = a₀x^r + a₁x^r-1 + ... + a_r-1x + a_r

(2) Let h(x) = b₀x^s + b₁x^s-1 + ... + b_s-1x + b_s

(3) Let f(x) = c₀x^t + c₁x^t-1 + ... + c_t-1x + c_t
(4) Since g(x) = h(x)*f(x), it follows that:

r = s + t

and

a₀ = b₀*c₀

(5) Since a₀ = b₀*c₀, it follows that:

c₀ = a₀/b₀

(5) Since g(x) is monic and h(x) is monic, it follows that a₀ = 1 and b₀= 1.

(6) It therefore follows that f(x) is monic since:

c₀ = a₀/b₀ = 1/1 = 1

QED

Roots of Polynomials

2008-01-27T23:22:00.000-08:00

The following proof is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Theorem: An element a ∈ F is a root of polynomial P ∈ F[X] if and only if (X-a) divides P.

Proof:

(1) deg(X - a) =1 [See Definition 4, here for definition of degree]

(2) Therefore, the remainder R of the division of P by (X - a) is a constant polynomial. [See Theorem, here]

(3) So, from the Division Algorithm for Polynomials (see Theorem, here), there exists Q,R such that:

P = (X - a)Q + R

(4) Further:

P(a) = (a -a)Q + R = R

(5) This shows that P(a) = 0 if and only if R = 0. That is, P(a) = 0 if and and only if P is divisible by (X - a).

QED

References

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

tan(π/4) = 1

2008-01-25T08:18:00.000-08:00

Lemma: tan π/4 = 1

Proof:

(1) Using definition:

tan(π/4) = sin(π/4)/cos(π/4)

(2) Using the triangle definition of sin and cosine (see here), we know that:

sin (x) = cos (π/2 - x)

(3) This then gives us that:

sin (π/4) = cos(π/2 - π/4) = cos(2π/4 - π/4) = cos(π/4)

(4) So that:

tan(π/4) = cos(π/4)/cos(π/4) = 1

QED

cot 2x = (1/2) [cot x - tan x]

2008-01-24T00:59:00.000-08:00

Lemma 1: cot 2x = (1/2)[cot x - tan x]

Proof:

(1) cot 2x = 1/tan(2x) = cos(2x)/sin(2x) [See here for definition of tan]

(2) cos(2x) = cos²(x) - sin²(x) [See Lemma 3, here]

(3) sin(2x) = 2(sin x)(cos x) [See Lemma 2, here]

(4) cos(2x)/sin(2x) = [cos²(x) - sin²(x)]/2(sin x)(cos x) =

= (1/2)[cos(x)/sin(x) - sin(x)/cos(x)] = (1/2)[cot(x) - tan(x)]

QED

Lemma 2: tan(-b) = -tan b

Proof:

(1) tan(-b) = sin(-b)/cos(-b) [See here for definition of tangent]

(2) sin(-b) = -sin b [See Property 4, here]

(3) cos(-b) = cos b [See Property 9, here]

(4) So, tan(-b) = (-sin b)/(cos b) = (-1)(sin b)/(cos b) = (-1)tan b = -tan b.

QED

Lemma 3: tan(a + b) = [tan a + tan b]/[1 - (tan a)(tan b)]

Proof:

(1) tan(a + b) = sin(a + b)/cos(a + b) [See here for definition of tangent]

(2) sin(a + b) = (sin a)(cos b) + (cos a)(sin b) [See Theorem 1, here]

(3) cos(a + b) = (cos a)(cos b) - (sin a)(sin b) [See Theorem 2, here]

(4) So that:

sin(a + b)/cos(a + b) = [(sin a)(cos b) + (cos a)(sin b)]/[(cos a)(cos b) - (sin a)(sin b)] =

(sin a)(cos b)/[(cos a)(cos b) - (sin a)(sin b)] + (cos a)(sin b)/[(cos a)(cos b) - (sin a)(sin b)]

(5) Multiplying both sides of the fractions by 1/(cos a)(cos b) gives us:

(tan a)/[1 - (tan a)(tan b)] + (tan b)/[1 - (tan a)(tan b)] =

= [tan a + tan b ]/[1 - (tan a)(tan b)]

QED

Corollary 3.1: tan(a - b) = [tan a - tan b]/[1 + (tan a)(tan b)]

Proof:

(1) tan(a - b) = tan (a + (-b)) = [tan a + tan (-b)]/[1 - (tan a)(tan -b)]

(2) Using Theorem 2 above, we have:

[tan a + tan (-b)]/[1 - (tan a)(tan -b)] = [tan a - tan b]/[1 + (tan a)(tan b)]

QED

Lemma 4: tan (2x) = (2 tan x)/(1 - tan² x)

Proof:

(1) tan(2x) = tan(x + x)

(2) Using Theorem 3 above:

tan(x + x) = [tan x + tan x]/[1 - (tan x)(tan x)] =

= (2 tan x)/(1 - tan² x)

QED

Lemma 5: 2 cos mx cos nx = cos(m + n)x + cos(m -n)x

Proof:

(1) Using cos(a + b) = cos(a)cos(b) - sin(a)sin(b) [See Theorem 2, here]

cos(m+n)x = cos(mx + nx) = cos(mx)cos(nx) - sin(mx)sin(nx)

cos(m-n)x = cos(mx - nx) = cos(mx)cos(-nx) - sin(mx)sin(-nx)

(2) Using cos(-x) = cos(x) [see Property 9, here] and sin(-x) = -sin(x) [see Property 4, here], we have:

cos(m - n)x = cos(mx)cos(nx) + sin(mx)sin(nx)

(3) So:

cos(m+n)x + cos(m-n)x = cos(mx)cos(nx) - sin(mx)sin(nx) + cos(mx)cos(nx) + sin(mx)sin(nx) =
2 cos(mx)cos(nx)

QED

Equation for a circle

2008-01-08T00:56:00.000-08:00

Postulate 1: The distance d between two points (x1,x2) and (y1,y2)

d = √(x2 - x1)² + (y2 - y1)²

This postulate assumes all the postulates from Euclid but that works fine for the standard Cartesian coordinates.

Definition 1: A circle

A circle is the set of points equidistant from a given point. This given point is called the center. The distance from the center to any point in the set of points is called the radius.

Theorem 1: Equation of a circle

For any given circle with center at (centerX, centerY) and radius r, the equation is:

(x - centerX)² + (y - centerY)² = r²

Proof:

(1) By Definition 1 above and Postulate 1 above, we have:

r = √(x - centerX)² + (y - centerY)²

(2) Squaring both sides gives us:

r² = (x - centerX)² + (y - centerY)²

QED

Geometric Interpretation of Roots of Unity

2008-01-07T19:15:00.001-08:00

The nth roots of unity can be thought of as n points evenly dividing up a circle.

Wolfram's MathWorld web site has a wonderful graphic that demonstrates this:

Here's the reason that it's true:

Theorem: The N-th Roots of Unity correspond to n points evenly dividing up a circle

Proof:

(1) The number of radians in a circle is 2π [See here for review of radians, if needed]

(2) The equation for roots of unity is (see Corollary 1.1, here):

where 0 ≤ k ≤ n-1.

(3) So each root of unity is:

cos[ (2kπ)/n] + isin[(2kπ)/n]

where 0 ≤ k ≤ n-1

(4) Which is the same as:

cos[(k/n)2π] + isin[(k/n)2π]

where 0 ≤ k ≤ n -1

(5) Now, complex values can be graphed on the Cartesian coordinate system on x + iy [this is called the complex plane].

(6) Each of the roots above maps to a point on the circumference of a unit circle since:

(a) The equation for a unit circle at (0,0) is [See Theorem 1, here]:

x² + y² = 1

(b) Since we are mapping cos[(k/n)2π] + isin[(k/n)2π] to x + iy, this gives us:

x = cos[(k/n)2π]

y = sin[(k/n)2π]

(c) From a previous result (see Corollary 2, here), we have:

cos²[(k/n)2π] + sin²[(k/n)2π] = 1

(d) So, applying step #6b above gives us:

x² + y² = 1

(7) So, all we have left to prove is that each of these n points is equidistant from the adjacent points on the circle.

(8) Clearly, we have points at based on the following n values:

(0/n)2π, (1/n)2π, (2/n)2π, ..., [(n-1)/n]2π

where

y = cos[(k/n)2π]

x = sin[(k/n)2π]

(9) Now, if we use a unit circle, it is clear that each of these points is equidistant from each other since:

Consider a circle which has the radius r = 1.

It is clear that plotting lines at (0/n)2π, (1/n)2π. ... ([n-1]/n)2π divides up the total circle (2π radians) into n equal portions.

Using a unit circle, it is clear that x=[cos(k/n)2π] and y = [sin(k/n)2π] are the places of intersection when the circle is evenly divided since:

sin θ = y/r = y

cos θ = x/r = x

In other words, each y=cos[(k/n)2π] and x=sin[(k/n)2π] is a point at the place where the (k/n)th part of the circle sweeps out against the circumference of the circle.

Since the length of the circumference is πD=(2r)πr = 2(1)π, [see Corollary 1, here], this means that the length of each subtended arc is (k/n)*2π.

This results in the patterns above depending upon the value of n.

QED

For example, if we graph the third roots of unity. Then, we have:

lines sweeping out at:

0, (1/3)2π, and (2/3)2π.

which results in the following graph:

References

Rowland, Todd and Weisstein, Eric W. "Root of Unity." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RootofUnity.html
"Complex Plane", Wikipedia.com
"Roots of Unity", Wikipedia.com