Question: what integers will we be able to reach by this process?
Answer: all of them.
To get to 17 simply add 1 16 times. To get to -42 simply subtract 1 43 times. The fact that the integers can be "built" by adding and subtracting 1 means that the additive group of integers is a cyclic group.
Now let's look at the Attayun-HOOT! group. The entire
Attayun-HOOT! group can be "built" from repeated applications
of R:
1) = R
Theorem: If a finite group G can be generated from one of its elements, a together with its inverse a-1 then it can be generated from a alone.
Proof:
The strategy of the proof is to show that we can generate a-1 from repeated applications of a.
If G is finite then the various powers of a cannot all be distinct [note that this would not necessarily follow if G is infinite]. Therefore for some two different positive integers, j and k
Assume without loss of generality that j is greater than k (Why can we do this?). Now if we multiply both sides of the equation by a-1 • a-1 • a-1 • . . . • a-1 • a-1(k times) then we end up with
That means that a-1 = a • a • . . . • a(j-k-1 times).
Let's get away from all the " . . . " and "(j-k times)" by using exponential notation. Just as we do for multiplication of regular old numbers we can express repeated application of the group operation by a given element with exponential notation. So we'll agree that for an element a of a group G with operation •
We find that with this notation the basic law of exponents all work as in regular arithmetic namely
With this notation we mean that a power of a is an where n is any integer: positive, negative or zero.
If we pick some element a from a group G then we can consider the subset of all elements of G that are powers of a. This subset forms a subgroup of G and is called the cyclic subgroup generated by a. It forms a subgroup since it is
But this is the long way of proving subgrouphood. Let's use our theorem that says if x and y are in the subset implies that x • y-1 is in the subset then the subset is a group. This is simple here. If y is a power of a then so is y-1 and so, therefore, is x • y-1 .
A few facts about cyclic groups and cyclic subgroups:
The second fact is a result of Lagrange's theorem. If G is a group of prime order p then take any non-identity element a and look at the subgroup generated by it. The order of the subgroup must be a divisor of the order of G (Lagrange's Theorem) but since G is of prime p order the only divisors of p are 1 and p itself. Since a isn't the identity the subgroup it generates must have more than one element. Therefore its order must be p and it must be G itself -- G is cyclic. Furthermore since the choice of a was only limited by its not being the identity it follows that G can be generated by any of its elements other than e.
The third fact is rather simple. Any subgroup containing a contains a-1 and therefore contains any products of a's and a-1 . Thus any subgroup containing a contains the cyclic subgroup generated by a. Since the cyclic subgroup generated by a is a subroup the fact follows.
The fourth fact is poorly stated. "looks like" is not a well understood piece of mathematical terminology. We'll tighten things up as we go along.
Suppose I is an infinite cyclic group generated by the element a. Then any element of the group is of the form an where n is an integer. Then the multiplication rule for this group ends up being
We can tighten up the notation of this group by letting the integer n stand for the element an . Then the "multiplication" rule for the group becomes
But this is just the behavior of the additive group of integers.
We have a one to one correspondence [an corresponds to n] which is preserved by the group operation [You can either perform the operation in one group and then find the corresponding element in the other or you can first find the corresponding elements in the other group and then perform the operation on them. The result is the same. And it works both ways. This is a group isomorphism, a concept we have looked at but haven't rigorously defined yet.]
Definition: Two groups G and H are isomorphic if there exists a one-to-one relation f : G –> H between them such that for any x and y in G, f(x) • f(y) = f(x * y). The one-to-one relation f is called an isomorphism. Thus two groups are said to be isomorphic if an isomorphism exists between them.
[Note on my notation I've used two different symbols for the group operations in that last passage. • represents the group operation in H and * represents the group operation in G This was to emphasize that we are dealing with two different groups each with its own group operation.]
[Exercise: show that the inverse relation works too. That is, show that if g : H –> G is the inverse of f then for any u and v in H it is true that g(u) * g(v) = g(u • v).]
One of the most common examples of a group isomorphism is found in the theory of logarithms. Let f : G –>H be the logarithm function and let G be the group of positive real numbers under multiplication and let H be the real numbers under addition. It turns out that
This together with the fact that Log is a one-to-one function (it has an inverse -- the exponential or "antilog" function) makes this a group isomorphism. This used to have great practical importance back in the days before pocket calculators. Long numerical calculations involving multiplication (and taking of roots and powers) could be simplified by doing addition of the Logs of the numbers. In those days no scientist or engineer was far from his table of Logarithms.
The following are basic facts about group isomorphism:
If f: G –> H is a group isomorphism then:
4. All infinite cyclic groups are isomorphic to the additive group of integers.
The isomorphism is simply an –> n as we have already seen.
The main point about cyclic groups and isomorphism is that all finite cyclic groups of the same order are isomorphic. Thus there is only one cyclic group (up to isomorphism) of order, say, 6. If we let a be a generator then the elements of the cyclic group of order 6 are a, a2, a3, a4, a5, and a6 = e.
The canonical example of a cyclic group of order n is the additive group of integers mod n: Z/nZ. The cayley table for Z/6Z is
| + | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 2 | 3 | 4 | 5 | 0 |
| 2 | 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 3 | 4 | 5 | 0 | 1 | 2 |
| 4 | 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 5 | 0 | 1 | 2 | 3 | 4 |
Note how each row (or column) is simply the previous row (or column) cycled forward one space.
The set of integers mod n is not a group under multiplication because 0 has no inverse – there is nothing that multiplies 0 to give 1, the identity element for multiplication. If n is a prime number and we throw out zero the remaining elements of Z/nZ does form a group – a cyclic group. Here's the Cayley table for the non-zero elements of Z (mod 7)
| × | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
The cyclic nature of the group isn't apparent from a glance at the table. However if we consider the powers of 5 then we find that 5 generates the entire group. Similarly 3 also generates the group. By rearranging the elements of the Cayley table the cyclic nature is readily seen.
| × | 1 | 5 | 4 | 6 | 2 | 3 |
|---|---|---|---|---|---|---|
| 1 | 1 | 5 | 4 | 6 | 2 | 3 |
| 5 | 5 | 4 | 6 | 2 | 3 | 1 |
| 4 | 4 | 6 | 2 | 3 | 1 | 5 |
| 6 | 6 | 2 | 3 | 1 | 5 | 4 |
| 2 | 2 | 3 | 1 | 5 | 4 | 6 |
| 3 | 3 | 1 | 5 | 4 | 6 | 2 |
[Exercise: The above table was rearranged by listing the 0th power of 5 first, then the first power of 5 then the 2nd power of 5 etc. Rearrange the table in order of powers of 3 such that its cyclic structure is evident.]
We can form a cyclic subgroup of any group by grabbing an element a of the group and looking at the set of all its powers. This gives the subgroup generated by a notated as < a >. Now by Lagrange's theorem the number of elements in < a > (the order of the subgroup) must be a divisor of the order of the group. Also if k is the order of < a > then k is the least positive integer with ak = e. For any element of a group the least positive integer that gives the identity when the element is raised to that power is called the order of the element. Thus the order of a cyclic subgroup and the order of its generator are the same number.
We might remark at this point that any subgroup of a cyclic group must itself be cyclic. If G is generated by a and S is a subgroup of G then S must be cyclic. To see this consider all the elements of S. They can all be expressed as powers of a. Let k be the least positive power of a that is in S. If every element is not a power of ak then there is some element am where m is positive and not a mulitple of k. Let p be the greatest multiple of k that is less than m. Then m - p is less than k. But this means that am • a-p = am-p is in S. This contradicts the choice of k as the smallest positive power of a in the subgroup. Thus all elements of S are generated by ak and S is cyclic.
Now if for any element its order divides the order of the group then it follows that if n is the order of the group then an = e for any element a of any finite group. [Why must this be so?]
Now we have a constrained converse of Lagrange's theorem. It is true that for cyclic groups if n is a divisor of the order of the group then the group has a subgroup of order n. To see why this must be so recall that a cyclic group is generated by the powers of one of its elements. Let's see why this must be for the cyclic group of order 12.
Since 3 divides 12 (i.e. 3 × 4 = 12) then (a3)4 = a12 = e. Thus a3 is an element with order 4. (If it were less then a power of a less than 12 would equal e). Thus a3 generates a subgroup of order 4. Similarly a4 generates a subgroup of order 3 and a2 generates a subgroup of order 6 while a6 generates a subgroup of order 2. There are always the trivial subgroups of orders 1 and 12 (The subgroup containing only the identity and the whole group considered as a subgroup of itself).
There is nothing special about the number 12. Let a cyclic group have order n. If r is a divisor of n then there is some number s such that rs = n. Let a be an element of the group with order n. (it must have one if it is cyclic) Then ar is of order s and therefore generates a cyclic subgroup of order s while as generates a subgroup of order r.
We can go a bit further in looking at subgroups of cyclic groups. Not only does a cyclic group have a subgroup of order r for every r that divides the order of the group but it has exactly one subgroup for each distinct divisor of n. To see this suppose that S is a subgroup of a cyclic group of order n and a is a generator. Suppose S has order r where rs = n. Then S is generated by one of its elements, ak for some k. This means that ak has order r which in turn means that k times r equals some multiple of n. Now since rs = n, s must divide k. Therefore ak is in the group generated by as which is of order r. However ak generates a group of order r. Thus r elements of the subgroup generated by ak are in the subgroup generated by as which has only r elements. The subgroups must be identical.
Finally let's use group theory to deduce a famous result of number theory. Consider the non-zero members of integers mod p where p is prime. If we let our binary operation be multiplication mod p then we get a group with p-1 elements (we've thrown out zero). [Is it really a group?]
This result is known as Fermat's Little Theorem.
Permutations
Back to the Index
© 1998 by Arfur Dogfrey