Friday, August 19, 2005

Proof for n=3: Eistenstein Integers: Step Two

If you are not familiar with Eisenstein Integers, please start here. The details of today's blog are based on an English translation of Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.

Lemma: There is no Eisenstein integer whose norm is 2.

(1) The norm of a G-number aJ + bO is a2 + b2 - ab.

(2) We note first that both abs(a) and abs(b) need to be greater than 1.

Case I: 0,0 --> 02 + o2 - (0)(0) = 0

Case II: 1,0 --> 12 + o2 - (1)(0) = 1

Case III: 0,1 --> 02 + 12 - (0)(1) = 1

(3) There is no solution where the min(a,b) ≥ 2.

(a) In all cases, a2 + b2 - ab ≥ min(a,b)2

Case I: a=b: a2 + b2 - ab = a2 + a2 - a2 = a2

Case II: b greater than a: this implies that b2 is greater than ab and therefore: a2 + (b2 - ab) is at least equal or greater than a2

Case III: The same argument applies only swap a for b.

(b) So, in this case, if min(a,b) ≥ 2 → Norm ≥ 4.

(4) But there is also no solution for max(a,b) ≥ 2.

Assume b greater than a: this implies that 2b + 1 is greater than a which implies that 2b + 1 - a is greater than 0. Adding the equation to both sides, this gives us that a2 + (b+1)2 - a(b+1) is greater than a2 + b2 - ab.

So all we need to do is to show that the equation doesn't hold for b=2, a=0 and b=2,a=1. We know that any other value of b will be greater than our result here and a must be less than 2.

Case I: b=2,a=0 (0)2 + (2)2 - (0)(2) = 4.

Case II: b=2,a=1 (1)2 + (2)2 - (1)(2) = 3.

QED

Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.

(1) Let us suppose that J-O divides α. [We can apply the same argument where it divides β or γ since we are assuming a form where α3 + β3 + γ3 = 0]

(2) We can assume that J-O does not divide β nor γ since all three are relatively prime to each other.

(3) For purposes of clarity, let's let ζ = J - O.

(4) So, α3 ≡ 0 (mod ζ3). [J-O divides ζ implies (J-O)3 divides ζ3; Start here if you unfamiliar with the '' symbol.]

(5) We also know that β3 + γ3 ≡ 0 (mod ζ3) [See Definition 1, here if this point is not clear]

(6) Since J-O doesn't divide β3 or γ3, we can conclude that:

β3 ≡ e (mod 9), γ3 ≡ f (mod 9) where e=±1 and f= ±1. [See Lemma 8, here for proof]

(7) Now since ζ3 divides 9 (see Corollary 9.1 here), we also have:

β3 ≡ e (mod ζ3), γ3 ≡ f (mod ζ3) [From step #6 above]

(8) Now e + f ≡ 0 (mod ζ3). [From Step #5 above since f + e ≡ β3 + γ3 ≡ -α3 ≡ 0 (mod ζ3)]

(9) So, f = -e . [From step #8 above and step #6]

(10) But then e + f = 0 and e + f ≡ 0 (mod 9); and therefore β3 + γ3 ≡ 0 (mod 9). [Since from step #6, e + f ≡ β3 + γ3 (mod 9)

(11) Which gives us that α ≡ 0 (mod 9) [since -α = β3 + γ3] and since 9 = ζ4:
α3 ≡ 0 (mod ζ4). [See here for proof of 9 = (J-O)4]

(12) And since J-O divides α, we know that:
α ≡ 0 (mod ζ2).

(13) Let us now define 3 values: η, μ, χ where:
η = βJ + γO
μ = βO + γJ
χ = β + γ

(14) Now, it follows that: β3 + γ3 = ημχ since:

(a) (βJ + γO)(βO + γJ)(β + γ) =
2OJ + βγJ2 + βγO2 + γ2OJ)(β + γ) = [β2 + γ2 + βγ(-O) + βγ(-J)](β + γ) =
2 + γ2 - βγ)(β + γ)

(b) 2 + γ2 - βγ)(β + γ) =
β3 + β2γ + βγ2 + γ3 - β2γ - βγ2 = β3 + γ3

(15) Now, it also follows that each value η, μ, χ is divisible by J-O since:

(a) (J-O)3 divides ημχ. [Since J-O divides α and α3 = ημχ]

(b) J - O divides μ - η since μ - η = ( βO + γJ) - (βJ + γO)=(J-O)(γ - β)

(c) Also note that μ + η = βO + γJ + βJ + γO = β + γ = χ

(d) From (a), we know that J-O divides μ, η, or χ. [See Euclid's Generalized Lemma for details since J-O is a prime.]

(e) This is enough to show that J-O divides all three since:

Case I: J-O divides μ

(i) Step 15b gives us that J - O divides μ - η

(ii) Since J-O divides μ, it must also divide η.

(iii) Then J-O divides χ, since χ = μ + η from step #c above.

Case II: J-O divides η,

(i) Step 15b gives us that J - O divides μ - η

(ii) Since J-O divides η, it must also divide μ.

(iii) Then J-O divides χ, since χ = μ + η from step #c above.

Case III: J-O divides χ

(i) Then J-O divides μ + η since χ = μ + η from step #c above.

(ii) But J-O divides μ - η from step 15b above.

(iii) This means that J-O divides both 2μ = (μ + η) + (μ - η) and 2η = (μ + η) - (μ - η).

(iv) Now, J-O is prime (see Lemma 5, here), we can apply Euclid's Lemma for Gaussian Integers (see Corollary 3.3, here) to establish that for each J-O divides 2 or J-O divides both μ and η.

(v) J-O does not divide 2.

In order for J-O to divide 2, then N(J-O) must divide N(2) [This is the same as the argument for norms for Gaussian Integers, see Corollary 7.1, here ]. N(J-O) = 3 [See Lemma 5, here] and N(2) = a2 + b2 - ab = 22 + 0 - 0 = 4 [See Lemma 3, here] And clearly, 3 does not divide 4.

(16) So, there exists: μ', η', χ' such that:
μ = μ'(J-O)
η = η'(J-O)
χ = χ'(J-O)

(17) And we can further show that μ', η', χ' are all coprime since:

(a) If any two have a common divisor, then μ', η' would have a common divisor.

Case I: μ', χ' have common divisor δ: μ' = μ''δ, χ' = χ''δ. (η')(J-O) + (μ')(J-O) =(χ')(J-O) so η' + μ' = χ' so that η' = χ' - μ' = δ(χ'' - μ'').

Case II: η', χ' have common divisor. You can apply the same argument as above.

(b) Assume η', μ' have a common divisor δ which is not a unit.

(c) Then δ divides β - γ since:
μ' - η' = (β - γ) [From 13b above]

(d) And δ divides β + γ since:
μ + η = β + γ [From 13c above and the fact that δ divides μ + η]

(e) So, δ divides both and since:
2β = (β + γ) + (β - γ)
2γ = (β + γ) - (β - γ)

(f) Now, since β, γ are relatively prime and 2 is an Eisenstein prime (see below), we can conclude that δ = 2.

We know that any number that is only divisible by itself and 1 is a prime. We also know that if a number is divisible by another number, then its norm is likewise divisible by the norm of the other number.

The norm(2) = 2J+2O = 22 + 22 - (2)(2) = 4.

4 is divisible by 1,2,4. So, to prove that 2 is a prime, we only need to prove that there is no Eisenstein integer whose norm is 2.

We already proved this in the lemma above.

(g) But the we have a contradiction since η is not divisible by 2. Here is the details:

Since δ = 2, both β + γ and β - γ are divisible by 2.

This means that there are four possible states where λ, θ are half the value - a unit.:

Case I: β has a form 2λ + unit, γ has a form 2θ + unit.
Case II: β has a form 2λ + unit, γ has a form 2θ - unit.
Case III: β has a form 2λ - unit, γ has a form 2θ + unit.
Case IV: β has a form 2λ - unit, γ has a form 2θ - unit.

Let's look at η = βJ + γO. So:

CaseI: μ = (2λ + unit)J + (2θ + unit)O = 2λJ + (unit)*J + 2θO + (unit)*O = 2(λJ + θO) + unit.

Case II: gets us: 2λJ + unitJ + 2θO = unitO = 2(λJ + θO) + unit(J-O)

Case III: gets us: 2λJ - unitJ + 2θO = unitO = 2(λJ + θO) - unit(J-O).

Case IV. gets us: 2(λJ + θO) - unit.

(h) So we reject our assumption (b).

(18) Since J-O divides α, we know that there exists a value ω such that:

α = (J-O)*ω

Which also gives us that:

(α)3 = (J-O)3(ω)3 = -ημχ

And dividing both sides by (J-O)3 gives us:

(ω)3 = -η'μ'χ'

(19) Since η', μ', and χ' are coprime, we can know that they are equal to a cube multiplied to a unit. [See here for the proof on this.]

So we could suppose that there exist: ι, ν, ξ which are Eisenstein Integers and ο, ρ, τ which will represent units. With this, we can assume:

μ' = ο * ι3
η' = ρ * ν3
-χ' = τ * ξ3

(20) Putting it all together, gives:

ω3 = ορτ*ι3ν3ξ3 where ορτ = a unit.

(21) Since μ' + η' = χ', we also have:

ο * ι3 + ρ * ν3 + τ * ξ3 = 0.

(22) Since μ', η', and χ' are coprime so: ι, ν, ξ must be coprime.

(23) Now, we also know that there exists κ such that:
ω = κ * ινξ.

So that κ3 = ορτ = a G-unit. Since J-O is not a unit, we know it doesn't divide κ and we have κ ≡ E (mod 9) which means that ορτ ≡ E (mod 9).

So that ορτ = E and E2 = 1.

(24) Since we know that from step (10) that α ≡ 0 (mod ζ2), we know that:

ω ≡ 0 (mod J-O).

So we know that J-O divides ι, ν, or ξ. Let us suppose that it divides ι so that we have:

ι ≡ 0 (mod J-O)
ν not ≡ 0 (mod J-O)
ξ not ≡ 0 (mod J-O)

So that we have:

ν3 ≡ e (mod 9)
where e2 = 1
ξ3 ≡ f (mod 9)
where f2 = 1.

And then since ρ * ν3 + τ * ξ3 ≡ 0 (mod [J-O]3), and since (J-O)3 equals 9, we know that:

ρ *ν3 + τ * ξ3 ≡ 0 (mod 9) and applying above, we he have: e*ρ + f*τ ≡ 0 (mod 9) and since e*ρ + f*τ is less than 9, we know that e*ρ + f*τ = 0.

If we set F = -e/f then we have:
τ = Fρ

Combining this with E = ορτ, we get:
E = ορ2F.

And we know that F2 = (-e/f)2 = e2/f2 = 1.

Multiplying Fρ2 to both sides of ο * ι3 + ρ * ν3 + τ * ξ3 = 0, we get:

E* ι3 + Fρ3* ν3 + (F2)τ3 * ξ3 = E* ι3 + Fρ3* ν3 +τ3 * ξ3 = 0

(25) Now, if we set α' = Fρν, β' = τξ, γ' = Eι, then we get:

α'3 + β'3 + γ3 = (F2)Fρ3* ν3 + τ3 * ξ3 + (E2)Eι3.

(26) But, we know that α'*β'*γ' is divisible fewer times by J-O than α*β*γ is since:

α3 = (J-O)3(μ'η'χ') and
μ'η'χ' = ε(α'3*β'3*γ'3) where ε is a unit.

(27) We can then apply the same reasoning to these values which prove infinite descent.

QED

14 comments:

Scouse Rob said...

In Lemma: There is no Eisenstein integer whose norm is 2.

Step (2) should be:
either absolute(a) or absolute(b) needs to be greater than 1.

Instead of:
both absolute(a) and absolute(b) need to be greater than 1.

Scouse Rob said...

In Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.

Step (1): α^3 + β^3 + γ^3 = 0 instead of α + β + γ = 0?

Step (6) would be easier to understand with a reminder that ζ^3 divides 9, or is there some easier way of getting this step?

Step (12a): I get:
[β^2 + γ^2 + βγ(-O) + βγ(-J)](β + γ)
in the third part of the equality, instead of:
[β^2 + γ^2 + βγ(-O) + βγ(-J)](β + γ)

Step (13b): Should it be:
μ - η = (J-O)(γ - β)
Instead of:
μ - η = (J-O)(β - γ)

Step (13e III):
Do you not need J-O does not divide 2 [proved in 15f], for this?

Step (15g): λ, θ are half the value - a unit (why not J-O as well as units?)

Step (21): Should it be:
κ^3 ≡ E (mod 9)
Instead of:
κ ≡ E (mod 9) ?

Step (22): (J-O)^3 equals 9!?!
I thought (J-O)^4 equals 9.
Now I can't get:
ρ *ν3 + τ * ξ3 ≡ 0 (mod 9)
Which leaves me stuck!
Help.

Rob

Scouse Rob said...

In step (22):
Fρ^2 * (τξ^3) = Fτ^2 * (τξ^3)
=F*τ^3*ξ^3
and not:
τ^3*ξ^3

Rob

Scouse Rob said...

In Step (17):
Should be:
μ' = ο * ι^3
η' = ρ * ν^3
-χ' = τ * ξ^3
Instead of:
μ = ο * ι^3
η = ρ * ν^3
-χ = τ * ξ^3 ?

In Step (24):
Should be:
α^3 = (J-O)^3(μ'η'χ') and
μ'η'χ' = ε(α'^3*β'^3*γ'^3)
Instead of:
α = (J-O)^3(μ'η',χ') and
μ'η'χ' = ε(α'*β'*γ') ?

Rob

Scouse Rob said...
This comment has been removed by the author.
Scouse Rob said...

In step (2) of Lemma: There is no Eisenstein integer whose norm is 2. you prove only that at least one of abs(a), abs(b) have to be greater than 1.

Rob

Scouse Rob said...

I don't quite follow the proof for Lemma: There is no Eisenstein integer whose norm is 2.

First you prove in step (2)(I think this is stated incorrectly):
max(abs(a),abs(b))<1

Then in step (3) that min(a,b) ≥ 2.

Then in step (4) that max(a,b) ≥ 2.

Which only proves all cases if a,b≥0.

I think the negative value cases need to be explained more.

Rob

Scouse Rob said...

Perhaps a further lemma/step that

Norm(aJ + bO)<=Norm(abs(a)J + abs(b)O)

Would solve the problems of the Lemma: There is no Eisenstein integer whose norm is 2..


P.S. I meant max(abs(a),abs(b))<=1 in my previous comment.

Rob

Scouse Rob said...

In step (15a) of Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.:

α^3=ημχ

should be:
α^3=-ημχ

Scouse Rob said...

In step (17) of Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent..

The references should be to steps 15b and 15c not 13b and 13c.

Rob

Scouse Rob said...

In step (17g) of Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.:

Case II: gets us: 2λJ + unitJ + 2θO = unitO

Should be:
Case II: gets us: 2λJ + unitJ + 2θO - unitO



Case III: gets us: 2λJ - unitJ + 2θO = unitO

Should be:
Case III: gets us: 2λJ - unitJ + 2θO + unitO

Scouse Rob said...

In step (24) of Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.

The reference to step 10 should be a reference to step 12.

Rob

Scouse Rob said...

In step (24) of Lemma: If J - O divides αβγ where αβγ ≠ 0, then we have reached a position of infinite descent.

Multiplying Fρ2 to both sides of ο*ι^3+ρ*ν^3+τ*ξ^3=0, we get:

E*ι^3+Fρ^3*ν^3+(F^2)τ^3*ξ^3


should be:

Multiplying Fρ2 to both sides of ο*ι^3+ρ*ν^3+τ*ξ^3=0, we get:

E*ι^3+Fρ^3*ν^3+(F^2)p^3*ξ^3

Zuzana said...

In Lemma: There is no Eisenstein integer whose norm is 2.

I suggest to use the fact that every Eisenstein integer is of the form (a+b sqrt(-3))/2 where a,b are integers of the same parity. Then the norm is

N(((a+b sqrt(-3))/2) = (a^2+3b^2)/4

and studying if the norm can be equal to 2 reduces to exclude integer solutions of

a^2 + 3b^2 = 8

which is easy.