Bertrand's Postulate (Theorem)

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, 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

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

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

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

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

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

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

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

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

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