In today's blog, I will introduce the idea of Additive Groups and talk specifically about the Additive Group of Cyclotomic Integers Mod p where p is an prime integer that is distinct from λ.
Additive groups are important because it enables us to use Lagrange's Theorem on the subgroup.
Definition 1: Additive group
An additive group is a group defined around the operation of addition. [See here for a review of the concept of a group]
Example: Z9 is an additive group
Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
It is clear that it has all the properties of a group:
(1) Closure: addition of any two integers modulo 9 results in another integer modulo 9.
(2) Identity: 0 is the identity.
(3) Inverse: For any integer, 9-i is the inverse. For example, 1 + 8 = 0 modulo 9.
(4) Associativity: For any a,b,c ∈ Z9, we see that:
a + (b + c) = (a + b) + c
In talking about the additive group of cyclotomic integers mod p, it is useful to talk about the number of elements.
Lemma 1: The additive group of cyclotomic integers mod p has pλ-1 elements.
Proof:
(1) Let λ be an odd prime and let α be a root of unity such that αλ = 1 but for all positive integers i less than λ, αi ≠ 1. [See here for review of roots of unity]
(2) All cyclotomic integers based on λ can be put into this form:
a0 + a1α + a2α2 + ... + aλ-1αλ-1
where ai are all integers [See Lemma 1 here]
(3) Since we are talking about values modulo p, we can assume that ai is between 0 and p-1.
(4) This means that there are λ-1 elements that can take values of 0 to p-1.
(5) If we count all possible values, this leads us to λ - 1 multiples:
[0..p-1]*[0..p-1]*...*[0..p-1] = pλ-1
QED
The importance of this is that we can construct an additive group of cyclotomic integers using a congruence relation ~ where p ~ 0. In other words, we can use ψ(η)p (see definition here) to define the following congruence relation:
f(α) ~ g(α) if and only if f(α)ψ(η)p ≡ g(α) mod p.
From this perspective, the congruence relation ~ can be used to construct a set of additive group of cyclotomic integers which consists of each distinct classes of f(α)ψ(η)p (mod p).
Lemma 2: if ~ is a congruence relation such that p ~ 0, then the additive group of cyclotomic integers created from ~ is a subgroup of the additive group of cyclotomic integers mod p.
Proof:
(1) We know that the set of cyclotomic integers mod p under '+' is an abelian group since:
(a) It is closed on the operation of '+'
(b) 0 mod p is the identity element.
(c) For any cyclotomic integer ≡ r (mod p), the inverse element is p-r.
(d) '+' is clearly associative in nature.
(e) It is abelian since '+' is commutative.
(2) We can make the same arguments to show that the cyclotomic integers from ~ is an abelian group on the operation of addition.
(3) To complete this proof, we only need to show that the set of cyclotomic integers ~ is a subset of the cyclotomic integers mod p.
(4) This is the case since:
(a) Let g(α) be a cyclotomic integer.
(b) Then, there exists r(α) such that g(α) ~ r(α) so that r(α) ∈ additive group of cyclotomic integers constructed through ~
(c) Now we can assume r(α) has the following form (see Lemma 1, here):
a0 + a1α + ... + aλ-1αλ-1
(d) We can further assume that all ai are between 0 and p-1 since if ai is greater than p, then there exists a' such that ai ≡ a' (mod p) where a' is less than p and further if ai ≡ a' (mod p), then ai ~ a' because p ~ 0.
(e) But if all ai are between 0 and p-1, then r(α) ∈ the additive group of cyclotomic integers mod p.
QED
Friday, August 04, 2006
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment