## Thursday, May 25, 2006

### Cyclotomic Integers: Periods

In today's blog, I will review the concept of periods for cyclotomic integers 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.

I will continue to use Edward's σg(α) notation that I reviewed in a previous blog.

Lemma 1:

Let e be a factor of λ - 1 where λ is an odd prime and α is a primitive root of unity where αλ = 1.

Then, for a given cyclotomic integer g(α) there exists a cyclotomic integer G(α) such that:

Ng(α) = G(α)*σG(α)*...*σe-1G(α)

Proof:

(1) Let G(α) = g(α)*σeg(α)*σ2eg(α)*...*σ-eg(α) where σ-e denotes σλ-1-e

(2) With this definition we can see that:

G(α) = g(α)*g(αγe)*g(αγ2e)*...*g(αγ(λ-1-e))

σG(α) = g(αγ)*g(αγ(e+1))*g(αγ2e+1)*...*g(αγλ-e)

...

σe-1G(α) = g(αγ(e-1))*g(αγ(2e-1))*...*g(αγ(λ-2))

(3) Putting this all together, we see that:

Ng(α) = g(α)*g(αγ)*g(αγ*γ)*...*g(αγ(λ-2))

(4) Since γ is a primitive root mod λ, we know that (3) is the same as:

Ng(α) = g(α)*g(α2)*g(α3)*..*g(αλ-1)

QED

Example 1: λ = 13, γ = 2, and e = 4

In this case, Ng(α) = G(α)G(α)G(α4)G(α8)

Each term G(α) = g(α)*g(α24)*g(α22*4) = g(α)*g(α3)*g(α9)

Since:

2 ≡ 2 (mod 13)
22 ≡ 4 (mod 13)
23 ≡ 8 (mod 13)
24 ≡ 16 ≡ 3 (mod 13)
25 ≡ 32 ≡ 6 (mod 13)
26 ≡ 64 ≡ 12 (mod 13)
27 ≡ 128 ≡ 11 (mod 13)
28 ≡ 256 ≡ 9 (mod 13)
29 ≡ 512 ≡ 5 (mod 13)
210 ≡ 1024 ≡ 10 (mod 13)
211 ≡ 2048 ≡ 7 (mod 13)
212 ≡ 4096 ≡ 1 (mod 13)

Corollary 1.1: σeG(α) = G(α)

Proof:

(1) G(α) = g(α)*g(αγe)*g(αγ2e)*...*g(αγ(λ-1-e))

(2) And we find that:

σeG(α) = g(αγe)*g(αγ2e)*g(αγ3e)*...*g(αγλ-1)

(3) And since γλ-1 ≡ 1 (mod λ) (By Fermat's Little Theorem), we see that the result in step #2 is the same as the result in step #1.

QED

Corollary 1.2: σeG(α) = G(α) implies that there exists a set of e cyclotomic integers: η0, η1, ... ηe-1 such that:

(a) η0 = α + σeα + σ2eα + ... + σλ-1-eα

(b) ηi+1 = σηi

(c) G(α) = a0 + a1η0 + a2η1 + ... + aeηe-1 where ai are integers.

Proof:

(1) σeG(α) = G(α)

(2) Since G(α) is a cyclotomic integer, we know that (see Lemma 1 here):

G(α) = a0 + a1α + ... + aλ-1αλ-1

(3) Now, (#1) implies that the coefficient for any αj, αj = σeαj

(4) In order for #3 to be true, then G(α) must have the following form:

G(α) = a0 + a1(α + σeα + σ2eα + ... + σλ-1-e) + a2(σα + σσeα + ...) + ... + aee-1α + σe-1σeα + ...)

The reason being that each time all the values G(α) shifts by e, the new value must also have had the same coefficient and further, all new resulting values must be the same as values that existed before the shift. For each coefficient, the set of possible αj values must be closed.

(5) Now, we can define η0 in the following way:

η0 = α + σeα + σ2eα + ... + σλ-1-e

(6) We can likewise define ηi+1 as:

ηi+1 = σηi

(7) Putting (5) and (6) into the equation in step #4 gives us:

G(α) = a0 + a1η0 + ... + aeηe-1

QED

Definition 1: Cyclotomic Period

Let λ be a prime integer. Let α be a primitive root of unity such that αλ=1. Let γ be a primitive root modulo λ. Let e be a factor of λ - 1.

Let G(α) = g(α)*g(αγe)*g(αγ2e)*...*g(αγ(λ-1-e))

Then there exists a set of e cyclotomic integers: η0, η1, ... ηe-1 such that:

(a) η0 = α + σeα + σ2eα + ... + σλ-1-eα

(b) ηi+1 = σηi

(c) G(α) = a0 + a1η0 + a2η1 + ... + aeηe-1 where ai are integers.

The cyclotomic integers η0, η1, ... ηe-1 that meet conditions (a), (b), and (c) are called cyclotomic periods.

Note:

As a convention, ηe = η0 and η-1 = ηe-1. So one can think of ηi as an ever repeating pattern of e values such that ηi+1 = σηi

In this way, ηi is defined for all integers i.

Example 1: period for λ = 13, μ = 2, γ = 4

In this case, the cyclotomic periods are:

η0 = α + σ4α + σ8α = α + α3 + α9

η1 = σα + σα3 + σα9 = α2 + α6 + α5

η2 = σ2α + σ2α3 + σ2α9 = α4 + α12 + α10

η3 = σ3α + σ3α3 + σ3α9 = α8 + α11 + α7

Lemma 2: σeηi = ηi

Proof:

(1) For Case 0, this is given by the note in definition 1 above.

σeη0 = ηe = η0

(2) Let's assume that this is true up to i so that:

σeηi = ηi where 0 ≤ i.

(3) Then, this is also true for ηi+1 since:

σei+1) = σe(σηi) [From Definition 1 above]

Now σeσ = σe+1 = σσe

So that we get:

σeηi+1 = σ(σeηi)

By assumption at step #2, σeηi = ηi

So that we end up with:

σeηi+1 = σηi = ηi+1

(4) So, by the principle of induction, we are done.

QED

Lemma 3: Each period η consists of (λ-1)/e terms.

Proof:

(1) Let f = (λ - 1)/e.

(2) σefα = σλ-1α = α

(3) σ(λ - 1 - e)α = σe(f-1)α = (σe)f-1α

(4) So we can see that each term in α + σeα + σ2eα + ... + σλ-1-eα is σiα where i is 0*e, 1*e, 2*e, ... , (f-1)*e.

QED

Definition 2: Made up of periods of length f

A cyclotomic integer is made up of periods of length f if it can be put in the form:

a0 + a1η1 + a2η2 + ... + aeηe

where ai are integers and ηi are periods of length f.

Lemma 4: A cyclotomic integer g(α) is made up of periods of length if and only if σeg(α) = g(α)

Proof:

(1) Assume that g(α) is a cyclotomic integer made up of periods of length f.

(2) Then, there exists ai and ηi such that:

g(α) = a0 + a1η0 + a2η1 + ... + aeηe-1

(3) Applying σe to g(α) gives us:

σeg(α) = a0 + a1σeη0 + ... + aeσeηe-1

(4) Applying Lemma 2 above gives us:

σeg(α) = a0 + a1η0 + ... + aeηe-1

(5) Assume that σeg(α) = g(α)

(6) Then by Corollary 1.2 above, g(α) consists of e periods.

(7) And by Lemma 3, each period will be of length f.

QED

Corollary 4.1: The product of two cyclotomic integers made up of periods of length f is itself made up of periods of length f.

Proof:

(1) Let f(α), g(α) be cyclotomic integers made up of periods of length f so that:

σef(α) = f(α)
σeg(α) = g(α)

(2) But then:

σe[f(α)g(α)] = [σef(α)][σeg(α)] = f(α)g(α)

(3) So that by Lemma 4 above, we have proved that f(α)g(α) must itself be made up of periods of length f.

QED

Example: λ = 13, f = 3, e = 4

We note that:

0)2 = η1 + 2η2

η0η1 = η0 + η1 + η3

η0η2 = 3 + η1 + η3

Likewise, applying σ to these equations gives us:

1)2 = η2 + 2η0

η1η2 = η1 + η2 + η0

And so forth.