Monday, May 29, 2006

Cyclotomic Integers: Generalizing Periods

In today's blog, I continue to review results from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same chapter that I started in an earlier blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

Lemma 1: Any arbitary cyclotomic integer g(α) of degree f-1 or less can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

where g1(η), g2(η), ..., gf(η) are cyclotomic integers made up of periods of length f. [See Definition 2 here for review of cyclotomic integers made up of periods of length f]

Proof:

(1) Let g(α) be a cyclotomic integer of degree f-1 so that:

g(α) = a0 + a1α + a2α2 + ... + af-1αf-1

(2) Let's define the following polynomials made up of periods of length f [letting e = (λ-1)/f]:

Let gf(η) = a0 + (0)η0 + (0)η1 + ... + (0)ηe-1

Let gf-1(η) = a1 + (0)η0 + (0)η1 + ... + (0)ηe-1

and so on until:

Let g1(η) = af-1 + (0)η0 + (0)η1 + ... + (0)ηe-1

(3) With the values in (step #2), we see that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

QED

Lemma 2: If g(α), h(α), and i(α) are cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f,

then g(α)h(α) + j(α) is expressible in terms of cyclotomic integers made up of periods of length f.


Proof:

(1) Since g(α), h(α), and j(α) are expressible in terms of cyclotomic integers made up of periods of length f, we have:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

h(α) = h1(η)αf-1 + h2(η)αf-2 + ... + hf(η)

j(α) = j1(η)αf-1 + j2(η)αf-2 + ... + jf(η)

where where g1(η), g2(η), ..., gf(η), hi(η), ji(η) are cyclotomic integers made up of periods of length f.

(2) We know that the sum of two cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f is itself expressible in terms of cyclotomic integers made up of periods of length f.

If s(α) = g(α) + h(α) then we can define the following:

For each gi(η), hi(η), we have:

gi(η) = a0 + a1η0 + ... + afηf-1

hi(η) = b0 + b1η0 + ... + bfηf-1

And we can define si(η) such that:

si(η) = (a0 + b0) + (a1 + b10 + ... + (af + bff-1

(3) The product of g(α)*h(α) is also expressible in terms of cyclotomic integers made up of periods of length f since:

g(α)h(α) = [g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)][h1(η)αf-1 + h2(η)αf-2 + ... + hf(η)] =

= [g1(η)αf-1][h1(η)αf-1] + ... + [ gf(η) ][hf(η)]

Since the product of two cyclotomic integers made up periods of length f is itself made up of periods of length f (see Corollary 4.1 here), we can conclude that the product of g(α)h(α) is itself a sum of cyclotomic integers made up of periods of length f.

Now from this sum and from the result in step #2, we are done.

QED

Lemma 3: There exists a function p(x) such that:

p(α) = αf + φ1(η)αf-1 + ... + φf-(η)α + φf(η) = 0

where φ1(η), φ2(η), ..., φf(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let λ be an odd prime.

(2) Let α be a primitive root of unity such that λ is the least positive integer whereby αλ = 1.

(3) Let e,f be positive integers such that e is a factor of λ - 1 and f = (λ - 1)/e.

(4) Let p(x) be a function such that:



NOTE: In other words, p(x) = (x - σeα)(x - σ2eα)*...*(x - σfeα)

For review of σ notation, see here.

(5) If we multiply all of the products together, we get the following form:

p(x) = xf + φ1(η)xf-1 + ... + φf-(η)x + φf(η)

where φ(η) is a cyclotomic integer.

(6) We note that σep(x) = p(x) since:

(a) σep(x) = (x - σ2eα)(x - σ3eα)*...*(x - σefeα)

(b) σefe = σeσef = σeσλ-1 = σe [Since ef = λ - 1 by step #3 above and σλ-1 is identity from here]

(c) Combining (a) and (b) gives us:

σep(x) = (x - σ2eα)(x - σ3eα)*...*(x - σeα)

(7) From a previous result (see Lemma 4 here), we know that p(x) must consist of periods of length f so that taking our result from step #5:

p(x) = xf + φ1(η)xf-1 + ... + φf-(η)x + φf(η)

We know that φ1(η), φ2(η), ..., φf(η) must all be cyclotomic integers made up of periods of length f.

(8) Now we know that p(α) = 0 since:

(a) p(α) = (α - σeα)(α - σ2eα)*...*(α - σfeα)

(b) fe = λ - 1 (from step #3)

(c) σλ-1 is the identity (see here) so that σλ-1α = α

(d) Applying #8b and #8c to (a) gives us:

p(α) = (α - σeα)(α - σ2eα)*...*(α - σfeα) =

=(α - σeα)(α - σ2eα)*...*(α - α) =

= (α - σeα)(α - σ2eα)*...*(0) = 0

(9) So putting this all together gives us:

p(α) = αf + φ1(η)αf-1 + ... + φf-(η)α + φf(η) = 0

QED

Corollary 3.1: Every cyclotomic integer g(α) can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

where g1(η), g2(η), ..., gf(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let g(α) be a cyclotomic integer such that:

g(α) = a0 + a1α + a2α2 + ... + aλ-1αλ-1

NOTE: See Lemma 1 here for details on why all cyclotomic integers can be expressed in this form.

(2) We can restate g(α) in terms of g(x) so that:

g(x) = a0 + a1x + a2x2 + ... + aλ-1

(3) Let p(x) be a polynomial such that:

p(x) = xf + φ1(η)xf-1 + ... + φf-1(η)x + φf(η)

where φ(η) is a cyclotomic integer.

(4) Using Division by Polynomials (see here) we know that there exists q(x),r(x) such that:

g(x) = q(x)(xf) + r(x) where degree of r(x) is less than f or r(x) = 0.

(5) Now from Lemma 1 above, we know that r(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(6) Since p(α) = 0 (see Lemma 3 above), we know that αf is expressible in terms of cyclotomic integers made up of periods of length f since:

αf = 1(η)xf-1 - ... - φf-1(η)x - φf(η)

(7) For now, let's assume that q(x) is of degree less than f.

(8) Then we can apply Lemma 1 above and conclude that q(x) is expressible in terms of cyclotomic integers made up of periods of length f.

(9) Now since g(α) = q(α)(αf) + r(α), we can apply Lemma 2 above to conclude that g(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(10) Now let's assume that q(α) is of degree f.

(11) Using q(x), we can again apply the Division Algorithm for Polynomials to get:

q(x) = q1(x)(xf) + r(x)

Since we are assuming q(x) has a degree of f, it follows that q1(x) will have a degree less than f.

(12) Using Lemma 2 above, we can conclude that q(α) is expressible in terms of cyclotomic integers since q1(α), αf, and r(α) are expressible in terms of cyclotomic integers made up of periods of length f.

(13) Using the Principle of Induction, we can now conclude that this works regardless of the degree of q(α). [Since q(α) with degree f-1 works and since q(α) with degree f-1 working implies that a q(α) with degree f works]

(14) So, using Lemma 2 above, since q(α), r(α), and αf are expressible in terms of cyclotomic integers made up of periods of length f, so is g(α) since:

g(α) = q(α)αf + r(α)

QED

Example:

Let λ = 5, f = 2, and γ = 2

So e = (λ - 1)/f = 4/2 = 2

Let g(α) = α4 + 2α3 + 3α2 + 4α + 5

We note that:

21 ≡ 2 (mod 5)
22 ≡ 4 (mod 5)
23 ≡ 3 (mod 5)
24 ≡ 1 (mod 5)

In this case,

p(x) = (x - σeα)(x - σ2eα)

Now σeα = αγ2 = α4

σ2eα = αγ4 = α

So,

p(x) = x2 - x(α4 + α) + α5 = x2 - x(α4 + α) + 1.

We see that p(α) = 0 since:

p(α) = α2 - α(α4 + α) + 1 = α2 - 1 + α2 + 1 = 0

So that:

α2 = α(α4 + α) - 1

Let g(x) = x4 + 2x3 + 3x2 + 4x+ 5

Now, let's express each of these terms in terms of cyclotomic integers made up of periods of length f=2:

with:
η0 = α4 + α

η1 = α3 + α2

0)2 = α3 + α2 + 2.

0)(η1) = η0 + η1

Using the Division Algorithm for polynomials, we see that:

g(x) = q(x)(x2) + r(x)

where:

q(x) = x2 + 2x + 3

r(x) = 4x + 5

x2 = x(α4 + α) - 1

and:

q(α) = [α(α
4 + α) - 1] + [2α + 3] = α(η0 + 2) + (2)

r(α) = 4α + 5 = α(4) + (5)

α2 = [α(α4 + α) - 1] = α(η0) + (-1)

Then

g(α) = q(α)α2 + r(α) =

= α202 + 2η0) + α(2η0) + α(-η0 - 2) -2 + α(4) + (5) =

= [α(η0) -1](3η1 + 2) + α(η0 +2) + (3) =

= α(4η0 + 3η1+ 4) + (-3η1 + 1)

So, let:

g1(η) = 4η0 + 3η1 + 4

g2(η) = -3η1 + 1

And finally, this gives us:

g(α) = g1(η)α + g2(η)

No comments: