Generators

Suppose you pick some complete symmetry group and choose some number of permutations from it. Then you construct the smallest subgroup that contains all of them. This is the subgroup generated by the initial set of permutations you chose.

Using again $S_3$ as our example, what is the subgroup generated by $\{ (1 2 3) \}$? Well, it has to contain $(1 2 3)$ itself, $(1 2 3)^2 = (1 3 2)$, $(1 2 3)^3 = (1)$ and nothing else since higher powers of $(1 2 3)$ start repeating: $(1 2 3)^4 = (1 2 3)^3(1 2 3) = (1)(1 2 3) = (1 2 3)$. In general, if $n>=3$, $(1 2 3)^n = (1 2 3)^{n-3}$. We know that $\{ (1),\ (1 2 3),\ (1 3 2) \}$ is a subgroup of $S_3$ so it is the subgroup generated by $(1 2 3)$.

Using Rubik's Cube as an example, if you've played with it, you know that there are billions (acutally, there are a lot more!) of permutations in the ``Rubik's Cube group'', but if we consider as a generator a 1/4-twist of the front (in other words, the $F$ move), you can see that if that is the only operation you're allowed to do, there are only four possible rearrangments of the cube you can achieve. So that particular generator will generate a subgroup of size 4.

If you have a cube handy, here's an exercise. Begin with a solved cube. You are only allowed to make two sorts of move: $F^2$ and $R^2$, in other words, only $180^\circ$ rotations about the front and right faces are allowed. These moves certainly are permutations of the cube's faces. Show that the order of the subgroup they generate is 6. In other words, show that you can only get the cube into 6 different patterns (including the ``solved'' pattern) if $F^2$ and $R^2$ are the only allowed moves.

If we have a finite group (and that's the only sort we consider in this paper), every element has some finite order. The proof is easy:

Let $P$ be some permutation, and consider $P^1, P^2, P^3, \ldots$. eventually, since there are only a finite number of elements in the group, there has to be some $i$ and $j$ such that $P^i = P^j$. Assume $j > i$. Then $P^{j-i}P^{i} = P^j = P^{i}$. Thus $P^{j-i} = e$, the identity.

We can also see that it's true since every permutation expressed in proper cycle form will have an order equal to the least common multiple of the lengths of its cycles as we stated previously. The advantage of the proof in the previous paragraph is that it applies to all finite groups--not just permutation groups.

On the other hand, it is sometimes quite difficult to guess what the order of an element of the permutation group might be. For example, consider the following permutation of Rubik's Cube: $FR$. Suppose that it is one indivisible move. it is obvious that both the $F$ and $R$ moves by themselves have order 4--4 such turns return the cube to the original condition. But if you consider the pair of turns to be a single move, what is the order of that? The answer turns out to be 105--not an obvious result!

My initial (and very painful) solution to the cube was based on the above concept. I knew that any operation, if repeated enough times, would return an initially solved cube back to the solved condition. But by experimentation, I found that if my operation required, say, 24 repeats to get from solved to solved, very often the condition after 12 or 8 moves (these are divisors of 24) would leave most of the cubies fixed.

It is pretty obvious why this works. Imagine a permutation with a cycle structure like this: $P = (1 2 3)(4 5 6 7)(8 9)$. We know that $P^{12} = e$, but what does $P^6$ or $P^4$ look like? Work it out: $P^6 = (46)(57)$, $P^4 = (1 2 3)$. Do you see what's going on?

Here is an interesting exercise. Show that if you have a subgroup of $S_n$ that contains $(1 2)$ and $(1 2 3 \cdots n)$, then the subgroup is the entire group $S_n$. In other words, any possible permutation of $n$ objects can be expressed as some product of a 2-cycle and an $n$-cycle. (Clearly it doesn't matter what particular 2-cycle or $n$-cycle you use.)