# The Ultimate Guide to Groups: Part III

Gavin Jared Bala

Some of us, when bored as a child, might have experienced the “pleasure” of putting a whole number into the calculator, pressing the “×” button, and then pressing the “=” button as fast as we possibly could. Of course, this either gets us nowhere (if we started with 0 or 1), or it quite quickly leads to exponential growth and an error message (if we started with anything else).

Let’s think about what happens when we do this in a finite group.

Suppose the element we are repeatedly multiplying is called a. Well, we will then get a*a = a2. And then a3. And then a4. And so on…ah, but we could not be generating new elements forever, could we? We only have a finite number of them, so eventually they have to repeat, and we have ak = al for some whole numbers k and l.

In fact, we can cancel off a bunch of a’s at the start, so we’d get (assuming k is smaller than l): al-k = 1.

Actually, we may as well rephrase this as am = 1 for some whole number m, since we only care about the difference anyway.

Now, there must be a first time we have this situation of returning to 1. So we’ll have an = 1 where n is the smallest possible natural number that allows that.

Everything before that must be different. For if ak = al for some natural numbers k < l < n, then al-k = 1 when l-k < n, but we said that n was the first time that happened.

This means we have elements 1, a, a2, …, up to an-1; and the exponents reset to 0 when they pass n. That’s exactly the cyclic group Cn in disguise!

This is our second encounter with the idea of a subgroup: a group contained in another group. We’ve seen that every element of a group defines a cyclic subgroup: the order of that cyclic subgroup will be called the order of that element.

Let’s look at C4 again:

We can see that and a3 have order 4, because it takes four times to get them back to 1: a4 = (a3)4 = 1. But a2 has order 2, since it only takes two times to get it back to 1: (a2)2 = 1. The identity element, of course, has order 1.

What we have done is single out an element of the group, and found the smallest possible group that still contains it. If we include a in our group, then because we have to have closure, we have to include all powers of a (including the identity, as a0 = 1), for the result to be a group. But we don’t have to include anything else. This is called the group generated by a, and symbolised <a>.

For example, sticking with C4 = {1, a, a2, a3}, the group generated by a is the whole group. But the group generated by a2 is just {1, a2}, as we would only get even powers this way. This forms a mini-C2 inside our C4, showing that C2 is a subgroup of C4: we write C2 ≤ C4.

This can be extended to having multiple generators. We’ve seen that a group generated by one element has to be cyclic, so we could not generate V4 = {1, a, b, c} by one element (see previous article for a discussion of where V4 comes from). But if we examine the tables in the previous article, we’d see that if we are given a and b as part of our group, they necessitate everything else to be included. So we can say that V4 is generated by a and b. Indeed, it’s also generated by a, b, and c, as no one said we had to be efficient about it (but it’s usually useful to do so).

As a special case, what happens if we ask for a group generated by no elements? Then we do not require anything to be included other than what is forced by being a group – which means the only element that expressly has to be included is the identity, and the group is C1.

Let’s now use the ideas of subgroups and orders to prove something important:

Lagrange’s Theorem: The order of an element in a group always evenly divides the order of the whole group.

Let’s call our group G and our element a; suppose that element’s order is n. The subgroup generated by a is H = <a> = {1, a, … , an-1}.

Now, suppose G = {1, g1, g2, g3, … , gk} (listing the elements of the group). Then the cosets

must between them include all the elements of the group.

Now, because all the elements 1, a, …, an-1 are distinct, so must be the elements gm, gma, … , gman-1: for if they were not, and gmax = gmay, then we could cancel the gm’s, and conclude that ax = ay, contradicting that the original elements were distinct. So each coset has the same number of elements as the original: n.

Furthermore, suppose two cosets share an element: say, glax = glay. In that case we have gl = gmay-x by cancelling ax on the right-hand side, and therefore actually glH = gmH; all we’ve done is rearrange the powers of a on the right. So two cosets either are completely separate, or they are the same.

Therefore, we have partitioned the group into a bunch of cosets, each with n elements. But for that to work, the number of elements in the whole group must be a multiple of n. Whew! That was a serious theorem. But it will now pay off handsomely by enabling us to classify larger groups.

Firstly, we can now dispose of all prime orders.

A prime number p has precisely two factors: 1 and itself. So the elements of a p-element group must either have order 1 or p. But the only order-1 element is the identity (as that’s what “order 1” means, if you think about it); so actually all the others are order-p elements. That means they generate the whole group, so the group is cyclic.

That tackles orders five and seven. What about order six?

Well, Lagrange’s theorem tells us that the orders of the elements in our order-six group must divide six: so they must be 1, 2, 3, or 6. (Notice how building up groups is so reminiscent of building up numbers from their prime factors!)

If there is an order-6 element, then it generates the whole group, and we have C6.

If there is no order-6 element, but there is an order-3 element a, then we have guaranteed elements 1, a, a2. There must be some other element outside this to make six, so we’ll call it b; this guarantees elements {1, a, a2, b, ab, a2b}. Let’s fill a Cayley table to this effect:

(The left factor is given by the column, and the right factor by the row. Remember, nothing in the group axioms said ab had to equal ba!)

We now need to answer two questions. The first question is: what is b2?

The Latin-square property says that it can only be a, a2, or 1. But if we accept one of the first two possibilities, then b3 is either ab or a2b, and these are not 1. So b has order greater than 3, so it must have order 6, and we just said there is no such element. Therefore b2 = 1, and we can fill:

We now have an order-3 element a and an order-2 element b acting independently. So our second and last question will be how they interact when passing each other. Is ba = ab, or are they different? (In that case, the Latin-square property implies that ba = a2b.)

If they are the same, then we can fill the table as:

Everything works out. This situation, where we have a C3 and a C2 that do not interact, is called the direct product of the two groups. It’s written C3 x C2.

We’ve actually seen a structure like this before: you can check that V4 = C2 x C2. (The two non-interacting C2’s are generated by a and b in the notation we used before.)

However, in this case, we do not get anything new. The element ab turns out to have order six, so actually C3 x C2 is the same group as C6. This “simplification of products” when the cyclic groups don’t share factors is a special case of something called the Chinese remainder theorem.

The other choice lets them interact!

The Latin-square property implies that ba = a2b in this case. But how can we understand what this is telling us?

This is a special case of something called a semi-direct product. Here we have a semi-direct product of C3 and C2, which is symbolised C3 C2. Remember that the only non-trivial automorphism of C3 = {1, a, a2} was swapping a and a2. And that is exactly what moving an element past b does here: ba = a2b and ba2 = ab.

In this specific case, the group we have made is known. It is our old friend the dihedral group D6 in disguise. Think of a as a 120° rotation and b as one of the reflections.

We just have to polish off one more case, which is why we can’t have all the elements having order 2.

Here is where understanding generators come in handy. Well, some finite number of them will generate the group, and there’s a least sufficient number of them such that n order-2 elements of the group will generate it and n-1 won’t.

Suppose aa = bb =1. We also know ba is an element in the group, so it also squares to 1: baba = 1. Multiplying by ab on the right gives babaab = babb = ba on the left and ab on the right, so ba = ab. The order then doesn’t matter, so we can move all the letters in any random element so that all letters of the same type are together, and then cancel out doubles: aababbabaa = a*aa*aa*bb*bb = a.

Therefore, all that matters is whether each generator shows up or not. For each generator, this is a binary choice, so the total number of elements is 2n. (You get one factor of two for each generator.) Since 6 is not a power of two, this can’t happen.

Let’s go for one more order: order eight. This will be something of a marathon, but it’s nothing we haven’t previously encountered. The factors of eight are one, two, four, and eight: but only the identity can have order 1.

If there is an order-8 element, then it generates the whole group, which is thus cyclic C8.

As we showed above, if all nontrivial elements have order 2, then this is a group generated by three noninteracting order-2 elements, called C2 x C2 x C2:

So the only remaining case is if we have an order-4 element: call it a. So we have guaranteed elements 1, a, a2, a3. There must be some other element outside this to make eight, so we’ll call it b; this guarantees elements {1, a, a2, a3, b, ab, a2b, a3b}. Let’s fill a Cayley table to this effect:

So, just like in the order-six case, we need to figure out what b2 and ba are.

As before, the Latin-square property means that b2 could only be one of 1, a, a2, a3. But actually it could not be a or a3, as then b would have order eight.

First, we’ll investigate the case b2 = 1. This turns out quite analogous to the order-six case.

By the Latin-square property, ba could only be one of ab, a2b, a3b. But actually, the middle one doesn’t work: ba = a2b ⇒ a = b-1a2b ⇒ a2 = b-1a2bb-1a2b = b-1a4b = b-1b = 1, but we said that had order four. (This is connected to how the only nontrivial automorphism of C4 swaps a and a3, but has to leave a2 alone.)

The choice ba = ab leads to a group C4 x C2 where the order-four and the order-two element “don’t interact”:

It’s not the same as C8, as there is no order-eight element here.

Whereas the choice ba = a3b leads to a semi-direct product C4 C2, more commonly known as the dihedral group of order 8: D8.

This is the symmetry group of a square: consider as rotating a right angle clockwise, and b as reflecting in a diagonal.

But finally we must investigate the case b2 = a2. Here we end up with:

Once again, ba can only be ab or a3b. If it is ab, then we can check that we actually get C4 x C2 again: to see why, replace ab in the earlier table by b. You’ll indeed get:

But the choice ba = a3b leads to something new:

This is called the quaternion group Q8. It comes about most naturally from the quaternions, a kind of extended complex number with three imaginary axes satisfying i2 = j2 = k2 = ijk = -1.

You can check that according to these rules, multiplication on the set {1, i, j, k, -1, -i, -j, -k} works exactly like the quaternion group.

In the next article, we’ll go for a grand finale. We’ll use what we’ve learned about how to build up groups, to construct as many low-order groups as we possibly can.