Tuesday, July 25, 2006

Cyclotomic Integers: Ideal Numbers

Ernst Kummer wrote a very influential paper which demonstrated that unique factorization failed for certain cyclotomic integers including those based on α23=1. This paper invalidated Gabriel Lame's proposed proof for Fermat's Last Theorem. Harold M. Edwards goes into details on the methods that Kummer used and the nature of his discoveries. In a future blog, I will show how unique factorization fails for cyclotomic integers Z[α] where α23 = 1. [See here for details].

Kummer developed the theory of ideal numbers as an effort to save unique factorization for cyclotomic integers. In today's blog, I will go into detail on Kummer's theory of ideal numbers and show a proof that ideal numbers do, in fact, save unique factorization. The content in today's blog is taken from Harold M. Edwards book Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Definition 1: Z[α] where αλ = 1

This is the set of cyclotomic integers derived from the primitive root of unity based on an odd prime λ where a cyclotomic integer f(α) can be represented as follows:

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

where ai is a standard integer, λ is an odd prime, and α is the primitive root of unity based on λ.

I use α to represent the primitive root of unity and λ to represent an odd prime. I will represent a cyclotomic integer as a function that takes α as its parameter. For example, a(α), b(α), c(α), etc. are all cyclotomic integers. These conventions are also used by Edwards in his book and was used by Kummer in his original paper. If you need a review of cyclotomic integers and roots of unity, start here. See here for a proof that all cyclotomic integers can be represented in a form a0 + a1α + ... + aλ-1αλ-1.

Definition 2: Exponent mod λ

For a given prime p where p ≠ λ, if f is the exponent mod λ, then f is the lowest positive integer where pf ≡ 1 (mod λ).

As a convention, since the exponent mod λ is a standard integer, I will represent it as f.

Lemma 1: For any given prime p where p ≠ λ, the exponent mod λ divides λ - 1.

Proof:

(1) pλ-1 ≡ 1 (mod λ) from Fermat's Little Theorem (since p,λ are distinct primes)

(2) From a previous result (see Lemma 2 here), we know if f is the least positive integer, then it must divide λ-1.

QED

Definition 3: e = (λ - 1)/f

Since the exponent mod λ divides λ - 1, as a convention, I will refer to this result as e.

The integer e is very important in the construction of ideal numbers and gives us the useful equation ef = λ - 1.

Definition 4: ψ(η)p

This is a cyclotomic integer that is constructed in the following manner:

(1) Let f be the exponent mod λ for p and e = (λ - 1)/f.

(2) Consider the list of e*p cyclotomic integers that consist of the following form:

j - ηi where j = 1, 2, ..., p and i = 1, 2, ..., e

where ηi is a cyclotomic period associated with e. [See here for details on cyclotomic periods and how they can be derived from any factor of λ - 1]

(3) Now, remove from this list all values that are divisible by p.

We know that for all ηi there is an standard integer ui such that ηi ≡ ui (mod p) [See Corollary 3.1, here]

So ui which is in the list from 1, 2, ..., p means that ηi - ui gets removed.

NOTE: We know that there are e of these values so that at the end there are ep - e remaining values.

(4) Finally, define ψ(η)p = the product of all the remaining ep - e values such that:

ψ(η)p = (1 - η1)(2 - η1)*...*(p - ηe)

Assuming, of course, that 1 - η1, 2 - η1, p - ηe, etc. are not removed.

In review, there is a different ψ(η) for each prime p. I follow the convention from Edwards of putting η as a parameter to ψ since it is based on the cyclotomic periods.

I will also need to define a function σ.

Definition 5: σ

Let σ represent the transformation α → αγ where γ is the primitive root mod λ.

This transformation is a bit tricky since it is using the primitive root (see here for review of primitive roots) for its transformation. Being the primitive root, we know that γλ ≡ γ (mod λ) so that σλ = σ and σλ-1f(α) = f(α).

I spoke about this function in a previous blog (see here for details).

Example 1: Z[α] for λ = 3.

In this case, all cyclotomic integers f(α) have the following form:

f(α) = a0 + a1α + a2α2

In this case, the primitive root is 2 since 21 ≡ 2 (mod 3), 22 ≡ 1 (mod 3), and 23 ≡ 2 (mod 3).

We can then see that σf(α) = a0 + a1α2 + a2α4 = a0 + a1α2 + a2α

We can see that σ2f(α) = σ(a0 + a1α2 + a2α) = a0 + a1α + a2α2

Now, we are ready to talk about ideal numbers. It turns out that ideal numbers are a bit unusual in their make up. They may or may not exist as real cyclotomic integers. I will talk more about this strangeness later on. The interesting point is that even when they don't exist as cyclotomic integers, it is possible to define an "action" using them. For now, I start with one form of ideal numbers called prime divisors.

I won't offer a definition of prime divisors. Instead, I will offer a definition for the "action" of "division by a prime divisor."

Definition 6: Congruent mod a prime divisor of an integer p

Congruent mod a prime divisor means that a given cyclotomic integer g(α) satisfies 1 of 2 criteria:

Case 1: p ≠ λ

g(α) is said to be congruent h(α) mod a prime divisor of p ≠ λ if and only if

g(α)σi[ψ(η)p] ≡ h(α)σi[ψ(η)p] (mod p)

Case 2: p = λ

g(α) is said to be congruent h(α) mod a prime divisor of p = λ if and only if

g(α) ≡ h(α) (mod (α - 1))

Now, based on this definition, we can also define divisible by a prime divisor of a prime p.

Definition 7: Divisible by a prime divisor of an integer p.

A cyclotomic integer g(α) is said to be divisible by a prime divisor of an integer p if and only if g(α) is congruent to 0 mod the prime divisor of an integer p.


Observation:

Now, we can show that these definitions are useful by considering the following properties:

(1) Prime divisors when they exist as real cyclotomic integers satisfy the definitions above. [See Theorem, here]

(2) Divisibility by prime divisors saves Euclid's Lemma. In other words, if the product of two cyclotomic integers, say f(α)g(α) is divisible by a prime divisor, then either f(α) is divisible by the prime divisor or g(α) is divisible by the prime divisor. [See Lemma 2, below]

(3) All standard primes where p ≠ λ have e distinct prime divisors. [See here]

(4) λ has only 1 prime divisor which is the real cyclotomic integer α - 1. [See Lemma 3, here]

Definition 8: Divisible by a prime divisor of an integer p with multiplicity n

Divisible by a prime divisor with multiplicity n means that a given cyclotomic integer g(α) satisfies 1 of 2 criteria:

Case 1: p ≠ λ

g(α) is said to be divisible by a prime divisor of p ≠ λ if and only if

g(α)σi[ψ(η)p] ≡ 0 (mod pn) where i can be any positive integer.

Case 2: p ≡ λ

g(α) is said to be divisible by a prime divisor of λ if and only if

g(α) ≡ 0 (mod (α - 1)n)

Definition 9: Divisible by an ideal number

An ideal number is a set of powers of prime divisors. A cyclotomic integer is said to be divisible by an ideal number if it is divisible by all the prime divisors which make up the ideal number. A ideal number A is divisible by an ideal number B if and only if A contains all the same prime divisors as B with a multiplicity as great. There is a special ideal number I is consists of an empty set of prime divisors.

By convention, all ideal numbers are divisible by I.

Definition 10: Divisor

An ideal number A is said to be the divisor of a cyclotomic integer g(α) if it is divisible by all the prime divisors which divide g(α).

Now, finally, we can show that this construction of ideal numbers saves unique factorization.

If you would like to see a formal definition of prime divisor and ideal number, see here.

Lemma 2: Euclid's Lemma for Prime Divisors

if g(α)h(α) is divisible by a prime divisor P then g(α) is divisible by a prime divisor P or h(α) is divisible by a prime divisor P

Proof:

(1) g(α)h(α) is divisible by a prime divisor P means that g(α)h(α)ψ(η) ≡ 0 (mod p). [See Definition 7 above]

(2) This congruence relation is prime. That is, if g(α)h(α)ψ(η) ≡ 0 (mod p), then either g(α)ψ(η) ≡ 0 (mod p) or h(α)ψ(η) ≡ 0 (mod p) [See Lemma 2, here]

(3) But if g(α)ψ(η) ≡ 0 (mod p), then by definition 7 above, g(α) is divisible by a prime divisor P.

(4) On the other hand, if h(α)ψ(η) ≡ 0 (mod p), then by definition 7 above, h(α) is divisible by a prime divisor P.

(5) Either way we see that g(α)h(α) is divisible by a prime divisor P implies that either g(α) is divisible by a prime divisor P or h(α) is divisible by a prime divisor P.

QED

Theorem: Fundamental Theorem

A cyclotomic integer g(α) divides a cyclotomic integer h(α) if and only if every prime divisor which divides g(α) also divides h(α) with a multiplicity at least as great.

Proof:

Let λ be a given prime greater than 2 and let g(α), h(α) be nonzero cyclotomic integers built up from a λth root of unity α ≠ 1.

Then g(α) divides h(α) if and only if every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

Proof:

(1) Let h(α) be divisible by g(α) such that h(α) = q(α)g(α)

(2) Certainly every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

(3) Now g(α) divides h(α) if and only if Ng(α) = g(α)*g(α2)*...*g(αλ-1) divides h(α)*g(α2)*...*g(αλ-1)

(4) If every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great then every prime divisor which divides Ng(α) also divides h(α)*g(α2)*...*g(αλ-1) with the multiplicity at least as great.

(5) Since Ng(α) is an integer, from this point on we can assume that g(α) is a rational integer and that h(α) = h(α)*g(α2)*...*g(αλ-1).

NOTE: The justification is that every cyclotomic integer can be made to depend on this equation where we show that every prime divisor that divides its norm necessarily divides the cyclotomic integer h(α)*g(α2)*...*g(αλ-1)

(6) Now, we will proceed to prove this theorem for 3 cases:

Case I: g(α) is a prime integer p ≠ λ

Case II: g(α) is a prime integer p = λ

Case III: g(α) is not a prime integer

(7) Assume g(α) is a prime integer p ≠ λ

(8) From a previous result (See Theorem 4, here), we know that if h(α) is divisible by each of the e prime divisors of p, then h(α) is divisible by p.

(9) Assume g(α) is a prime integer p = λ

(10) From a previous result (See Proposition 2, here), we know that if h(α) is divisible by (α - 1)λ - 1, then it is divisible by p = λ

(11) To prove case III, we will show that if the thereom is true for g1(α) and g2(α), then it is true for the product, g1(α)*g2(α)

(12) So, let us assume that all the prime divisors which divide g1(α)*g2(α) also divide h(α)

(13) Since all the prime divisors g1(α) divide h(α), then it follows that g1(α) divides h(α) and there exists h1(α) such that:

h(α) = g1(α)*h1(α)

(14) By assumption, every divisor of g2(α) divides h1(α).

(15) Since we are assuming that the theorem holds true for g2(α), then it follows that g2(α) divides h1(α) and there exists h2(α) such that:

h1(α) = g2(α)*h2(α)

(16) Therefore h(α) = g1(α)g2(α)h2(α) we have shown that h(α) is divisible by g1(α)g2(α)

QED

Corollary: Unique Factorization is "saved"

If two cyclotomic integers g(α) and h(α) are divisible by exactly the same prime divisors with exactly the same multiplicities, then they differ only by a unit multiple, g(α) = unit * h(α)

Proof:

(1) By the fundamental theorem above, g(α) divides h(α) and h(α) divides g(α)

(2) Therefore, h(α)/g(α) and g(α)/h(α) are cyclotomic integers.

(3) Since their product is 1, they must both be units. (See here for more details if needed)

QED

NOTE: On the Fundamental Theorem and Unique Factorization.

The use of the fundamental theorem "saves" the property of unique factorization for primes as shown by the corollary but there is a price to pay. With the integers, we can arbitrarily organize any combination of primes into numbers. For prime divisors, this is no longer the case. For example, for λ = 23, there is no cyclotomic integer which is divisible once by one prime divisor of 47 and not divisible by any other prime divisor.

I go into more detail about this in my blog on divisors.

No comments: