Friday, August 11, 2006

Ideal Numbers: Class Number

In a previous blog, I have talked about Kummer's theory of ideal numbers in relation to his concepts of principal divisors and equivalent divisors. In today's blog, I will show how these ideas lead to the concept of the class number.

The idea of class number comes directly from the idea of equivalent divisors. In my previous blog, I showed how certain divisors can be said to be equivalent to each other. In other words, if A,B are equivalent divisors, then for a given divisor C, AC is principal if and only if AB is principal.

Kummer's further insight is that for each type of ideal number (that is, derived from an odd prime λ), there is a finite set of equivalence classes. I will show the proof for this in today's blog. The class number is the size of this minimum set of equivalence classes.

Lemma 1: If n is an odd integer, we can order 1, ..., n-1 into (n-1)/2 pairs that each add up to n.

Proof:

(1) We know this is true where n = 3

In this case, there is (3-1)/2 = 1 pair (1,2) which adds up to 3.

(2) Assume that this lemma is true up to n.

(3) So that we can divide up 1, .., n-1 into (n-1)/2 pairs that each add up to n so that we have:

(1,n-1)
(2,n-2)
...
([n-1]/2,[n-1]/2+1)

(4) If we add 2 to each the second element of each pair, we have (n-1)/2 pairs that each add up to n+2.

(1,n+1)
(2,n)
...
([n-1]/2,[n-1]/2+3)

(5) Since every first element of the pairs is between 1 and [n-1]/2 and since every second pair is between [n-1]/2+3 and n+1, we can see that [n-1]/2+1 and [n-1]/2+2 are not included in any of the pairs.

(6) So we can add the following pair ([n-1]/2+1,[n-1]/2+2) to get:

(1,n+1)
(2,n)
...
([n-1]/2,[n-1]/2+3)
([n-1]2+1,[n-1]/2+2)

(7) Now, we can see that we have (n+1)/2 pairs that each add up to n+2. In other words, we have shown that if this lemma is true for n, then it is also true for n+2.

(8) Using the principle of induction (see Theorem, here), we are done.

QED

Lemma 2: g(αj)*g(α-j) ≤ [abs(a0) + abs(a1) + .. + abs(aλ-1)]2.

Proof:

(1) g(α) = a0 + a1α + ... + aλ-1αλ-1. [See Lemma 1, here]

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

(3) g(α-j) = a0 + a1α-j + ... + aλ-1α-j(λ-1).

(4) We can assume that each αj cancels out (since each Norm is a positive rational integer, see Lemma 5, here), so that we have:

g(αj)g(α-j) is less than [abs(a0) + abs(a1) + .. abs(aλ-1)]2

QED

Lemma 3: For any divisor A, there exists a cyclotomic integer g(α) such that A divides g(α) and the Ng(α) is less than or equal to Kn where K = λλ-1 and n = N(A)

Proof:

(1) Let g(α) = a0 + a1α + ... + aλ-1αλ-1. [See Lemma 1, here]

(2) Ng(α) = g(α)*g(α2)*...*g(αλ-1) [See definition of norm, here]

(3) Using Lemma 1 above, we can order all the elements of Ng(α) into the following pairs:

Ng(α) = [g(α)g(α-1)][g(α2)g(α-2)]...

(4) Using Lemma 2 above, we can assume that each g(αj)g(α-j) ≤ [abs(a0) + abs(a1) + ... + abs(aλ-1)]2

(5) Therefore, if each abs(ai) ≤ c, then

g(αj)g(α-j) ≤ [λ*c]2 = λ2c2

and

Ng(α) ≤ (λ2c2)(λ-1)/2 = λλ-1cλ-1

(6) The set of all g(α) in which a0 = 0 and 0 ≤ ai ≤ c for i greater than 0 contains more than n elements provided that (c+1)λ-1 is greater than n.

If we set c = 1, then we have a total of (1+1)λ-1 possible elements.

For example if λ = 3, these would include (1+1)2 = 4 elements which consist of:

0
α
α2
α + α2

(7) Then, the difference of two of them is divisible by A (see explanation below) and has the norm at most λλ-1cλ-1 (from step #5 above).

We know that there are at most Norm(A) distinct congruence classes modulo A (see Theorem here for details). For this reason, if we have a set of distinct cyclotomic integers that are greater than Norm(A), we know that the difference of two of them must be divisible by A.

The proof on this is very straight forward.

(a) Let n be the set of distinct congruence classes modulo A.

(b) Let m be a set of distinct cyclotomic integers where m is greater than n.

(c) Let's assume that we go through the first n of the m distinct cyclotomic integers. If any of two of them are in the same congruence class modulo A, then A will divide the difference. Let's assume that none are.

(d) Now, when we get to the (n+1)th distinct cyclotomic integer out of the m, we know that it must match one of the existing congruence classes since there are only n of them.

(8) If c is as small as possible subject to the assumption that (c+1)λ-1 is greater n, then cλ-1 ≤ n.

(9) Then, a cyclotomic integer has been found that is divisible by A and has a norm at most λλ-1n.

QED

Lemma 4: Let k be a positive, rational integer. Then there is only a finite set of divisors whose norm is less than k.

Proof:

(1) There is no maximum prime. [See Theorem, here]

(2) Let p* be a prime that is greater than k.

(3) The norm of a prime divisor that divides a rational integer p is pf where f ≥ 1. [Details to be added here]

(4) So, no prime divisor of p* has a norm less than k.

(5) Further, no prime divisor of a prime greater than p* has a norm less than k.

(6) Finally, the total number of primes less than p* is less than p*.

(7) For each prime, there are at most e distinct prime divisors (see Lemma 1, here), and since e ≤ λ - 1, we know that there are at most (p*)*(λ-1) prime divisors that divides rational primes less than p*.

(8) The norm for each prime divisor is pf where f ≥ 1 so from this, we know that the maximum number of prime divisors that have a norm less than p* is (p*)*(λ-1).

(9) To finish this proof, we need to show that there are only a finite number of ideal numbers (composed of prime divisors) that have a norm less than p*.

(10) Now, for any prime divisor P, the norm(P*P) = norm(P)*norm(P) [Detail to be added later], so norm(Px) = (norm(P)x).

(11) Let l = log2(k) [See here for an explanation of logarithm if needed; this gives a solution to 2l = k.]

(12) We know for all divisors whose norm is less than k, they cannot be divisible by a prime divisor with a power greater than l.

If they are divisible by a prime divisor with a power greater than l, then the norm of this divisor will necessarily be greater than k.

(13) This means then that the maximum number of divisors with a norm less than k is floor(l)*(p*)*(λ-1) [where floor(x) is the maximum integer that is less than or equal to x]

This is the answer because we can think of each divisor as consisting of all prime divisors with each prime divisor having a value between 0 and floor(l).

QED

Theorem: For all cases of cyclotomic integers (where λ is a prime > 2), there exists a finite set of divisors A1, ..., Ak such that every divisor is equivalent to one of the Ai

Proof:

(1) Let A be any divisor.

(2) Let K = λλ-1

(3) Let A1, ..., An be the the set of divisors whose N(Ai) is less than K.

(4) We can see that there are only a finite set of divisors that make up Ai [ See Lemma 4 above]

(5) There exists a divisor B such that N(B) is less than K such that AB is principal. [This follows from Lemma 3 above]

(6) For B, there exists a divisor C such that N(C) is less than K and BC is principal. [This also follows from Lemma 3 above]

(7) We can see that A ~ C [See Lemma 8, here]

(8) It also follows from step #3, that C = Ai where i is one of the elements 1 ... n.

(9) In this way, we have shown that for any A, there exists an Ai such that A ~ Ai and further, that this set A1, ..., An is a finite set.

QED

Definition: Class Number

For a given set of cyclotomic integers based on an odd prime λ, the class number is the number of elements in the finite set of divisors A that is described in the theorem above.

Example: cyclotomic integers for λ = 3

In this case, the cyclotomic integers are characterized by unique factorization. This means that all combinations of prime divisors result in real cyclotomic integers (in other words, all divisors are principal). In this case, all divisors are equivalent to I which means that the class number is 1.

Note:

S0 far, we have shown that a class number exists for each value of λ and that in the case of unique factorization, the class number is 1. Ernst Kummer was able to use the work of Johann Dirichlet to establish a method for determinining class number. I will talk about this more in a future blog.

No comments: