Introduction
Groups are one of the most fundamental objects in mathematics. They arise everywhere, from snowflakes to particle physics. Most guides to groups start by considering them as a very abstract theoretical idea. This guide is different — we will start with a very concrete example, and consider being more abstract later.
This guide is also designed for people interested in computing with groups — we are going to introduce code early, and by the end you will know how to implement state-of-the-art algorithms for some important problems on groups. Our overall target is an efficient algorithm for intersecting two permutation groups, a problem which has no easy answer, and which will take us through stabiliser chains, graph isomorphism, and backtrack search on the way.
Many of the examples we use are going to be based on games and puzzles. Let’s begin with our first one.
This puzzle consists of six balls placed in two circles. The two circles can spin independently. Here is a simple interactive version.
Here is a concrete question to motivate us. Starting from the position above, can we rearrange the balls so the top row reads 4 5 6 and the bottom row reads 1 2 3? Yes — try it! If you don’t believe us, one way to get there is L L R R R L R L R R R, writing L for Rotate Left and R for Rotate Right. It can in fact be done in 9 moves, though finding the shortest solution to a puzzle like this is itself a harder problem, which we won’t tackle here. On the other hand, can we just swap balls 3 and 6, ending with 1 2 6 on top and 4 5 3 on the bottom? No — that arrangement is unreachable.
How do we know which arrangements are reachable and which aren’t? We could enumerate every arrangement the puzzle can produce: it turns out there are 120 of them, out of the \(6! = 720\) ways of arranging six balls. Except, enumeration like this won’t scale — a larger puzzle has far too many states to list. Group theory lets us answer questions like this much faster, and much more effectively, than brute-force enumeration.
Consider all the lists of moves we can perform in this game — we will show these are a group, and explain what a group is. A collection of moves is a group if it satisfies three conditions. There are a few different, equivalent, ways of writing what a group is; we give one here, and discuss others later.
Binary operation. A group has a binary operation: given two moves \(a\) and \(b\), we can make a new move \(a.b\) by doing \(a\) then \(b\). For example, we can make a move by doing Rotate Left followed by Rotate Right. Any series of moves must itself be a move.
Inverse element. For every move, there must be an inverse move which gets us back to where we started. For example, the inverse of Rotate Left is Rotate Left three times.
Identity element. Paired with the inverse, there must be a ‘move’ — the identity — which does nothing.
The puzzle above is a group: any sequence of rotations is itself a rotation sequence, each rotation can be undone by rotating the other way three more times, and doing no rotations is the identity.
Not everything is a group. For example, imagine we broke the puzzle open and threw some of the balls out of the window. Now the puzzle isn’t reversible. In that case, we have a semigroup, a whole different (but closely related) mathematical object. The theory of semigroups is very different from the theory of groups, and we won’t discuss it here. If you want to play with semigroups, there is an excellent Semigroups package in GAP.
In the next chapter we will meet GAP and start computing with groups like this one.