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 = a². And then a³. And then a⁴. 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 a^k = a^l 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): a^l-k = 1.

Actually, we may as well rephrase this as a^m = 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 aⁿ = 1 where n is the smallest possible natural number that allows that.

Everything before that must be different. For if a^k = a^l for some natural numbers k < l < n, then a^l-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 a^n-1; and the exponents reset to 0 when they pass n. That’s exactly the cyclic group C_n 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 C₄ again:

We can see that a and a³ have order 4, because it takes four times to get them back to 1: a⁴ = (a³)⁴ = 1. But a² has order 2, since it only takes two times to get it back to 1: (a²)² = 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 a⁰ = 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 C₄ = {1, a, a², a³}, the group generated by a is the whole group. But the group generated by a² is just {1, a²}, as we would only get even powers this way. This forms a mini-C₂ inside our C₄, showing that C₂ is a subgroup of C₄: 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 V₄ = {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 V₄ 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 C₁.

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, … , a^n-1}.

Now, suppose G = {1, g₁, g₂, g₃, … , g_k} (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, …, a^n-1 are distinct, so must be the elements g_m, g_ma, … , g_ma^n-1: for if they were not, and g_ma^x = g_ma^y, then we could cancel the g_m’s, and conclude that a^x = a^y, 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, g_la^x = g_la^y. In that case we have g_l = g_ma^y-x by cancelling a^x on the right-hand side, and therefore actually g_lH = g_mH; 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 C₆.

If there is no order-6 element, but there is an order-3 element a, then we have guaranteed elements 1, a, a². There must be some other element outside this to make six, so we’ll call it b; this guarantees elements {1, a, a², b, ab, a²b}. 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 b²?

The Latin-square property says that it can only be a, a², or 1. But if we accept one of the first two possibilities, then b³ is either ab or a²b, 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 b² = 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 = a²b.)

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

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

We’ve actually seen a structure like this before: you can check that V₄ = C₂ x C₂. (The two non-interacting C₂’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 C₃ x C₂ is the same group as C₆. 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 = a²b 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 C₃ and C₂, which is symbolised C₃ ⋊ C₂. Remember that the only non-trivial automorphism of C₃ = {1, a, a²} was swapping a and a². And that is exactly what moving an element past b does here: ba = a²b and ba² = ab.

In this specific case, the group we have made is known. It is our old friend the dihedral group D₆ 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 2ⁿ. (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 C₈.

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

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

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

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

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

By the Latin-square property, ba could only be one of ab, a²b, a³b. But actually, the middle one doesn’t work: ba = a²b ⇒ a = b^-1a²b ⇒ a² = b^-1a²bb^-1a²b = b^-1a⁴b = b^-1b = 1, but we said that a had order four. (This is connected to how the only nontrivial automorphism of C₄ swaps a and a³, but has to leave a² alone.)

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

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

Whereas the choice ba = a³b leads to a semi-direct product C₄ ⋊ C₂, more commonly known as the dihedral group of order 8: D₈.

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

But finally we must investigate the case b² = a². Here we end up with:

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

But the choice ba = a³b leads to something new:

This is called the quaternion group Q₈. It comes about most naturally from the quaternions, a kind of extended complex number with three imaginary axes satisfying i² = j² = k² = 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.