In some sense, every group is a permutation group. The action of x ∈ G moves all the elements of G to other elements of G, in a manner that can be reversed. In other words, the action of x permutes the elements of G. This holds for every x, and G becomes a permutation group. However, the term permutation group usually means something a bit more restrictive.
For starters, a permutation group G is finite, and G can be represented by permutations on a small set of letters, relative to the size of G. The latter constraint is a somewhat subjective attempt to avoid the useless conclusion that every finite group is a permutation group. If |G| is several million, yet G can be represented as permutations on 10 letters, then G is indeed a permutation group. In fact there is such a group, namely S10, the symmetric group on 10 letters. But there are other large groups, such as the cyclic group of order 33911, that cannot be embedded in Sn for modest values of n. In fact, since 33911 is prime, G is forced to permute at least 33911 letters. By our criteria, G is not a permutation group.
Permutation groups often appear in the form of puzzles. The Rubix cube is a classic example, and I will refer to it from time to time throughout this chapter. Try to get your hands on one, and other Rubix puzzles, if you can.
I know, it's Rubik's cube, and no offense to Mr. Rubik, the inventor of said cube, but Rubix has become its own adjective, e.G. the Rubix Snake, which Mr. Rubik had nothing to do with. The word Rubix now implies any physical puzzle that realizes a permutation group, and that's what we're interested in. So I'm going to call it the Rubix cube, even though that is not historically accurate.
Note to puzzle aficionados - you should search for both Rubix and Rubik, as each keyword seems to bring up a separate collection of websites.
The standard Rubix cube consists of subcubes in a 3 by 3 by 3 arrangement. There are therefore 6×3×3 or 54 squares on the outside. The six center squares spin, but do not move, hence there are 48 movable squares. As each face turns, the squares move through a permutation. There are 6 faces, hence there are 6 generators for the permutation group. Can we answer questions about the group simply by looking at its generators? How large is the group? Is it abelian? Is it solvable? What is its composition series? That's what this chapter is all about.
Let's answer one of the questions straight away. Determining whether G is abelian is easy. G is abelian iff its generators commute. For each pair of generators x and y, ask whether xy = yx. The Rubix cube is not abelian. Turn the front face, then the right face; this is not the same as turning the right face and then the front face.
Let G be a permutation group on n letters. Thus G embeds in Sn. In other words, G is a subgroup of Sn. If the generators of G are all even, then G embeds in An. In other words, all the permutations of G are even. One might call such a group even, while the presence of one odd generator makes G odd.
This is reasonable, but there is another way to look at it. Let G be even if all its generators are even, and odd if all its generators are all odd, and undefined otherwise. We may apply this definition to G, or to a quotient group H of G.
Look again at the Rubix cube. Consider only the corner pieces, as they move about in their own cycles. Don't worry about their orientations (spin), just ask whether they are in the correct locations. This is (technically) a factor group of G. Eight corner pieces move about in 8 locations, giving a permutation group on 8 elements. A 90 degree turn of the front face implements a 4-cycle, which is an odd permutation within H. Every quarter turn of every face is an odd permutation. The generators (moves) are all odd, and H is odd. If you are given a scrambled cube, and asked how many moves are required to solve the cube, i.e. how many moves back to start, you can tell at a glance whether the answer is even or odd. If the "corner location" permutation is odd, then you must apply an odd number of moves to get back to start. If the permutation is even then you must apply an even number of moves to get back to start.
The same analysis applies to the 12 side pieces (disregarding flips), as they move about in their locations. The parity of the "side location" permutation determines the parity of the path back to start.
If you have a friend who has mastered the cube, and you enjoy practical jokes, try the following. Physically take apart his cube. Twist one face 45 degrees and gently pry a side piece out with a spoon. Swap two corners and put the side piece back in. Then mix it up, and casually inquire, "So … you can really solve this thing, eh?" The corners mandate an odd path back to start, while the sides force an even path back to start, or vice versa. In other words, the cube is unsolvable. I played this trick on a friend in college, who then spent several frustrating days trying to solve the cube that he thought he had mastered.
The definition of a move is somewhat arbitrary. Some people consider a 180 degree turn to be a single move, rather than a double move, and in that case the even odd analysis is not valid. Turn the front face 90 degrees, then 90 degrees, then 180 degrees, and find a path of length 3 from start back to start. We would not be able to tell, in this case, whether a scrambled cube has an even or odd path back to start. For this and other reasons, I usually consider quarter turns to be moves, and similarly for other Rubix puzzles.
Let an initial set of generators, e.G. the moves of a puzzle, span a group G. Use these generators to build a new set of generators, which are more convenient. These are called strong generators. They aren't really any stronger, in that they span the same group G, but it's too awkward to call them "convenient generators", so we call them strong generators.
Some applications build a path back to start for each strong generator; other applications don't care. If x is a strong generator, and p(x) is the path back to start, then p(x) is the proof that x does indeed belong to G. Reverse the moves in p(x) to create the strong generator x from the start state. If, after some analysis, the puzzle is in configuration xyz, where x y and z are strong generators, then the path back to start is p(z)p(y)p(x). It may not be the shortest path back to start, but it is a solution, and if you don't make any mistakes, you will have a pristine cube at the end.
Strong generators exist at levels 0 1 2 3 etc, corresponding to a descending chain of subgroups G0 G1 G2 G3 etc, where G0 = G. In other words, the strong generators at level 0 belong to G0, and the strong generators at level 1 belong to G1, and the strong generators at level 2 belong to G2, and so on. Let's build the chain of subgroups first, and then describe the generators at each level.
As mentioned earlier, G0 = G.
Assign numbers to the elements that are permuted by G. In theory this enumeration is arbitrary, though in practice you get much shorter paths back to start if you number the items properly. In any case, assume they have been numbered 1 to n. Let G1 be the subgroup of G that fixes 1. (This is also called a stabilizer.) Let G2 be the subgroup of G1 that fixes 1 and 2. Let G3 be the subgroup of G2 that fixes 1 2 and 3. Continue down to Gn, which is trivial.
Realize that inclusion need not be strict. That is, Gi could equal Gi+1. I'll illustrate with the Rubix cube. Start with the corner piece at the front top left. This piece has three faces; number them 1 2 and 3. Clearly the faces move together, carried along by the corner piece. If a permutation, or a series of moves, returns face #1 to its original location, then face #2 and face #3 are also where they belong. Therefore G1 = G2 = G3.
There is one strong generator at level 0 for each coset of G1 in G0. Strong generator is just another word for cosrep. There is no particular advantage to left cosets versus right cosets, but you have to pick your chirality and stick with it. After all, G1 is probably not normal in G0. I'm going to use left cosets, because it fits well with right translation. Let x be a strong generator at level 0 that moves #1 into position 7. Then G1x is the complete set of permutations that moves #1 into position 7. The strong generator x represents the left coset of G1 that moves #1 over to 7. Build such a generator for each coset of G1 in G0. Note that the identity permutation becomes the strong generator for the trivial coset G1 in G0.
And how many such cosets are there? There is one for each location that 1 can reach. In other words, the strong generators at level 0 establish the orbit of 1 within G.
Moving to level 1, find a strong generator for each point in the orbit of 2 within the group G1. These are permutations that move 2 about, while keeping 1 fixed. Continue building strong generators at each level, representing left cosets of Gi+1 in Gi. The procedure for transforming initial generators into strong generators will be described below.
Assume strong generators have been found. The size of G is then the size of G1 times the index of G1 in G. The latter is the number of strong generators at level 0. By induction, |G| is the product, over all levels, of the number of strong generators at each level.
Given a scrambled cube, how can it be solved? How can you find a path back to start? A set of strong generators makes it easy.
Find the location of the first square on the surface of the cube, i.e. the square that we arbitrarily labeled as #1. If it is already in position 1, let x1 be trivial. Otherwise let x1 be the inverse of the strong generator that moves square #1 into its current (scrambled) position. When x1 is applied, 1 is back home, and the resulting configuration is a permutation within the subgroup G1.
You can probably see what to do next. Find the location of square #2 and let x2 be the inverse of the strong generator that moves 2 into its present location. Applying x2 brings square #2 back home, leaving a permutation that belongs to G2. Continue this process all the way down to xn. The result is a word of length at most n, using strong generators, that establishes a path back to start. Of course each xi must be expanded into a sequence of moves that produces that particular strong generator. In other words, the computer has to do some bookkeeping along the way, and remember which moves led to each xi. This is not necessary if you only care about the size of the group, or the structure of the group, but if you want to take a scrambled cube back to start using the actual moves of the puzzle, you have to map strong generators back to initial generators.
Unless you are lucky, or careful, the map back to initial generators can grow quite long. In other words, it can take a lot of moves to get back to start. Left to its own devices, and without any tricks, my software solves the cube in about 4200 moves - which is far too long.
The first trick is to hand-select the order of the squares. Your first guess, a simple raster pattern on each face, is far from ideal. Choose an order that solves the cube starting at one corner, spreading out along the sides, and across the top layer, then the middle layer, and finally the bottom layer, much as a human would do. With this reordering, the average path back to start drops to 277.
Next, hand-pick the strong generators. Don't let the computer build them, (using the algorithm described below). A human can find better, shorter transformations that move a couple of pieces about while leaving the majority of the cube undisturbed. These transformations become the strong generators that are employed near the end. With this accomplished, my program solves the cube in 113 moves (average), and 213 moves (worst case).
Finally, the average is cut in half by considering all possible rotations and reflections. Spin the cube about and run the program again, and see if the path is shorter. One perspective may be superior to another. My program literally runs itself 48 times, for all possible rotations and reflections of the cube, and remembers the shortest path. This is usually about 60 moves.
Another optimization, which I have not implemented, would consider a dozen different sets of strong generators, all hand crafted. Each might bring the squares home in a slightly different order, and each would employ its own transformations. Having built one set of strong generators from scratch, I haven't found the time to do it again and again, but I suspect it would reduce the length down to 45 or so.
Another enhancement would search for near solutions using brute force and a smattering of AI techniques. This would probably find paths of length 12 or less, and would avoid the embarrassment of making 6 moves on the cube, and having the software crank out a 53 move solution.
You can obtain my software, solve your scrambled cube, and build pretty patterns from my Rubix recreational page.
God's algorithm would solve the cube along a shortest path, i.e. the best solution. Research continues in this area, with tremendous progress. In particular, the cube can always be solved in 20 moves or less, assuming a move is any twist of any face, including 180 degree turns.
Is there a general purpose program that finds the best path back to start for any puzzle? The answer seems to be no. Even for abelian groups, even for cyclic groups, the problem is np complete. Discussions of this sort belong to complexity theory, which I may address later in this book. For now, judicious use of strong generators, possibly hand crafted, provides a reasonable solution to most permutation puzzles.
Let G be generated by a1 a2 a3 etc. These are the initial generators, the moves of the puzzle.
Let F be the free group on the symbols a1 a2 a3 etc. A natural map carries F onto G. Replace the symbols with their permutations and apply them in sequence. By correspondence, G1 has a preimage F1 in F, G2 has a preimage F2 in F1, and so on. The words in F2, for instance, are all the paths that put 1 and 2 back where they started.
Since left cosets correspond, a strong generator for Fi maps onto a strong generator for Gi. It is enough to find strong generators for F0 through Fn. Of course Fn is not the trivial group any more; it is the group of words that return the puzzle to its start state. It is also the kernel of the homomorphism from F onto G.
The problem has been pulled back to free groups, so we can take advantage of Schreier Nielsen rewriting. Given the generators of F, and the cosets of F1 in F, a fixed procedure cranks out a set of generators for F1. Find the cosets of F2 in F1, build more generators, and so on. Let's see how this works in practice.
Apply the initial generators a1 a2 a3 etc, again and again, and keep track of the location of square #1. For each new location, record the permutation, and the sequence of moves that got you there. The permutation becomes the cosrep of F1 in F. Continue this process until square #1 does not move to any new locations. You have established the orbit of element #1, and the strong generators at level 0.
Using Schreier Nielsen rewriting, cross the strong generators at level 0 with the group generators of F0 to give a set of generators for F1. Each generator is a permutation and a sequence of moves that got you there.
Now start the process over again. Apply the generators of F1 and mark the location of element #2 as it moves about in its orbit. These become the strong generators at level 1. Cross these with the generators of F1 to find generators for F2. Continue this process down to Fn, building strong generators at each level.
You also have something else, something you don't really want or need, namely a set of generators for Fn. Unfortunately the rank of Fn can be as large as G itself. Thus the aforementioned algorithm is impractical. It creates large numbers of generators at each step, while all you really need are the strong generators. Let's take a different approach.
Bring in each generator ai one at a time, and chase down all the strong generators that arise as a result of the new generator and the previous strong generators. The method used to produce these strong generators is essentially the same as that described above, so we know we're going to get them all.
The inductive assumptions, prior to the introduction of each generator, are listed below. These hold for the trivial groups F and G, having no generators.
F is generated by the previous symbols, prior to ai. Note that F will get larger when ai is introduced.
G is generated by the previous permutations, prior to ai. Note that G may get larger when ai is introduced.
Strong generators exist for G, from level 0 down to level n. In what follows, these will be treated as the generators for G, rather than a1 through ai-1. Careful bookkeeping along the way builds each of these generators as a sequence of original moves.
For notational convenience, let p be the permutation defined by ai. This is a new generator, and by Schreier Nielsen rewriting, p must be crossed with every cosrep at level 0 to create new generators for F1. Assume there are already k cosreps, k strong generators at level 0. Draw a line at this point, to separate the k existing cosreps from any new cosreps that might be created by p.
Find any additional cosets of F1 in F, thanks to the introduction of p. In my first implementation, I applied p to the previous k cosreps, again and again, until element #1 didn't reach any new locations - but this is not sufficient. The cosreps at level 0 are not the entire group G. Suppose p and the preexisting k strong generators at level 0 conspire to move #1 to a new location 7, but 9 remains out of reach. However, down at level 4, a strong generator carries 7 to 9. When all of G is considered, 9 is in the orbit of #1. For example, let a1 turn the top of the rubix cube, let a2 turn the bottom, and let a3 turn the front. Fold in a3, and element #1 can move to new places in the front, like the front bottom, wherein other generators from below will move this piece around to the back.
Apply p to all previous strong generators at and below the current level, looking for new left cosets. These are added to the list at level 0, after the line that separates new from old.
Combine p with each cosrep at level 0, old and new, to create new generators for F1. Let q be one of these constructed generators. Now for the magic. Call the routine recursively at level 1, adding q to G1.
Once this is done, loop over the new cosreps at level 0. Each must be crossed with every generator of G, i.e. the strong generators at and below level 0. If r is the result of one of these crossings, call the routine at level 1, folding r into the next group down. The routine will call itself as necessary, filling out the strong generators all the way down to level n.
Assume the set of initial generators is linear in n, where n is the number of elements in the permutation group. This is typical of physical puzzles. The number of possible moves does not grow faster than the number of pieces being moved about.
In the worst case, there are n levels, and n, n-1, n-2 … cosreps at each level. Whenever a new cosrep is introduced, it is crossed with all cosreps at and below its level. There are n2 such cosreps, and this happens n2 times, thus cranking out n4 generators.
Each new generator is crossed with n2 cosreps at and below itself, to make new generators, and to find new cosreps. We saw above that n4 generators are produced, so this takes us up to n6.
Finally, each crossing operation is linear in n. This takes us to n7. This is a rather sloppy analysis, but in any case, strong generators are produced in polynomial time.
If some elements are not moved by G, such as the center squares on the Rubix cube, they can be removed, and the remaining elements renumbered, to give a smaller representation of G. This allows me to number the Rubix squares in a simple raster pattern, which is easy for a human to follow, giving 54 elements. The software trims this down to 48.
As we search for a normal subgroup H of a permutation group G, there may be some low hanging fruit, especially if G is derived from a physical puzzle. Consider again the Rubix cube. The corner pieces move about in their orbit, and the side pieces move about in a separate orbit. In other words, G is not transitive. A square cannot start on a corner and wind up on a side.
Let O be the orbit of element #1, and let P be the remaining locations. Now every permutation in G keeps O within O, and P within P. Let H be the subgroup that fixes O, and verify that H is normal in G.
For convenience, renumber the elements so that the first k lie inside O, and the rest lie inside P. Build strong generators as usual, and note that H = Gk. We get, for free, strong generators for the subgroup H. Thus H is written as a permutation group, and it can be analyzed by the same software. Then, restrict the generators of G to O, i.e. the first k elements. This is the factor group G/H, written as a permutation group, whence it too can be analyzed. This procedure splits the Rubix cube into its corner moves, and the permutations that move the sides about and keep the corners fixed.
Since either O or P can establish a normal subgroup, you might think G is the direct product of the two, but this need not be the case. Let G be generated by one permutation having two disjoint cycles of length 5. Thus G = Z/5. The subgroups determined by O, and P, are both trivial. Focus on either one, and the factor group is Z/5, which is all of G.
Even the Rubix cube exhibits some overlap. Both the corners and the sides include even and odd permutations, but you cannot move the corners through an even permutation and the sides through an odd permutation. Thus G is not the direct product of the two normal subgroups determined by O and P.
Assume the group has been separated by orbits, so that G is transitive. Perhaps G is the corners of the Rubix cube. There is still a factor group that is easily spotted by a human. Ignore orientations, and focus on the locations of the 8 corner subcubes. This is a map from 24 squares onto 8 physical pieces. Let's try to formalize this.
Assume the elements can be partitioned into blocks of equal sizes, such that G carries blocks to blocks. Given such a block partition, collapse blocks into single elements to produce the factor group. Prepend these elements to the existing permutations, and for each generator, let these elements mirror the block permutations. This is an isomorphic representation of G that is not transitive, hence the previous procedure can be invoked. Let O be the new elements, placed in front, and let P be the original elements. Analyze H, the subgroup that fixes O, then analyze the restriction to O, which is the factor group.
The same procedure takes the sides of the Rubix cube and decomposes them into their 12 locations in space, and their flip orientations.
How do we partition elements into blocks? Build a remapping array r, that will (eventually) link each element to the least element in its block. At the start, let ri = i.
Let x loop over every position from 2 to n. Assume that 1 and x are in the same block. In other words, set rx = 1. Let's see where this leads.
If a generator moves two elements of the same block to two new positions, then these positions must also live in a common block. Suppose they map to different blocks u and v, where u < v. These blocks must merge. Everything that was in block v is now in block u. Run through the array and replace v with u. Continue modifying the remapping array in this fashion until the generators introduce no new changes. If all the elements are in block 1 then we have no partition. Try again with the next value of x. Otherwise, group the elements together by blocks and apply the above procedure.
If you use the -q option, my software searches for these easy subgroups. This is sufficient to decompose most real-world puzzles. The Rubix cube, for instance, has the following composition series.
S8 (Z/3)7 A12 (Z/2)11
The 8 corners can be permuted in any way, then 7 of the 8 can be spun (reoriented) in any way, whence the orientation of the 8th corner is determined. With the parity of the corner pieces set, The locations of the sides are restricted in parity, hence the alternating group A12. Finally 11 of the 12 sides can be flipped in any way, whence the orientation of the 12th side is determined.
To be technically correct, I should write S8 as Z/2 A8, but I think S8 is a bit clearer in this context. Of course the following decomposition series, starting with the sides, is equally valid.
S12 (Z/2)11 A7 (Z/3)7
How many Rubix cube configurations are there? Multiply the sizes of these groups together to get:
12! × 8!/2 × 37 × 211 = 43,252,003,274,489,856,000
Let's look for a subgroup H of G that is not found by separating the elements of G into blocks. As before, G has descending subgroups G1, G2, G3, … Gn, and strong generators at every level. Let Hi be the intersection of H and Gi.
For notational convenience, assume 5 is the first level where Hi ≠ Gi. Thus H6 and G6 are the same. The strong generators at level 5 determine the left cosets of G6 in G5. Some of these cosets belong to H5; some do not.
Multiply each cosrep at level 5 on the right by each generator in G6, and see where element #6 winds up. If x is the cosrep that moves #6 to location 7, and a strong generator at level 6 moves 7 to 9, and y is the cosrep that moves #6 to 9, then x implies y. Conversely, G6 includes the inverse of the aforementioned strong generator at level 6. Thus y implies x.
If something in G6 forces x → y, and something else in G6 forces y → z, then the composition of those two elements forces x → z. We have an equivalence relation. The presence of G6 partitions the strong generators at level 5 into equivalence classes, or blocks. Each block is part of H5, or it is not.
These blocks need not be the same size. In fact the first block, consisting of the trivial cosrep, has size 1. Select this block alone if you want H5 to equal G6. Remember that it has to be at least G6, because H6 = G6.
Assume a block contains x y and z. If this is folded into H5, we also need xx, zyz, etc. This may bring in other blocks. Build a digraph of blocks that imply other blocks.
Now select a subset of these blocks that is directionally closed. If block A implies block B, and you want A, you have to bring in B. If A and B stand alone, and you want them both in H5, the composition of their strong generators might imply block C, which must also be part of H5.
Build a collection of strong generators at level 5 that combines with G6 to create a closed subgroup of G5, which becomes H5.
With H5 set, move up and define H4. The process is the same. Use H5 (not G5) to clump the strong generators at level 4 into blocks, build a digraph among these blocks, and select a consistent set of these blocks to build H4. Repeat this process all the way up to H0, which becomes H.
Having built a subgroup H, it is easy to test for normality. Conjugate each generator of H by each generator of G, and ask whether the resulting word w is in H. Since we have strong generators for H, one can quickly determine whether w belongs to H.
You don't have to wait until the end to test for normality. At the bottom, when we built H5, conjugate those generators by every generator in G and ask if the resulting word is in G5, but not in H5. If this happens, you need to select a different H5. If you get up to level 3, and there is no way to make H3 normal, use a stack to backtrack. Try a different H4, or a different H5 etc.
Now we have strong generators for the normal subgroup H, but what about the factor group G/H? When the index is prime, there is nothing to analyze; the factor group is cyclic. Still, this gives us a clue. At some level, say level 5, H5 has a certain index in G5. The generators of H5 builda block, and all the elements of G move this block onto other blocks. If these blocks are reduced to points, then G acts on these points. This is true in general. At every level, the strong generators that belong to H can be folded into a block, and G maps this block to other blocks at the same level. Do this across all levels, and G/H becomes a permutation group, which can be analyzed. This is the factor group G/H.
My software looks for the easy subgroups, based on orbits, as described in the previous section; it does not employ the algorithms described here. As mentioned above, most of the physical puzzles decompose into symmetric and cyclic groups by orbits alone.