cube files
Indexed Cube Lovers Archive
A Little More on Odd and Even Permutations
Submitted by Jerry Bryan on Thu, 01/11/2007 - 12:50.
One of the basic tenents of cube theory (a highly specialized branch of group theory - grin!) is that odd permutations of the corners can only occur with odd permutations of the edges, and that even permutations of the corners can only occur with even permutations of the edges. This fact is one of the three factors that causes the order of the cube group to be smaller than the order of what is sometimes the illegal cube group.
If you take a cube apart and put it back together, you can put it back together in twelve times as many ways as there are positions in the cube group. Twelve is because 3 * 2 * 2 = 12. Three of the ways are because the twist of the last corner cubie you put back together can be set in one of three different ways, only one of which is legal. Two of the ways are because the flip of the last edge cubie you put back together can be set in one of two different ways, only one of which is legal. The last two of the ways are because the corners and edges can by put back together either with the same odd/even parity (legal) or with the opposite odd/even parity (illegal).
However, in one of my original cube programs nearly 20 years ago, I noticed that all edge permutations seemed to be even. So even edge permutations were occurring with odd corner permutations. Not only that, my program was producing correct results. How could this be?
What I didn't really realize at the time is that the odd and even properties of permutations are not necessarily preserved by an isomorphism. I was surprised, but I really shouldn't have been. There is nothing in the four basic group properties of closure, associativity, identity, and inverse that implies anything about odd and even permutations. And an isomorphism depends only upon the four basic group properties.
Here's a trivial example. Consider first the group S2 operating on the set {0,1}. S2 contains two elements, namely the identity () and the transposition (0,1). The identity () is even, consisting of zero transpositions. The transposition (0,1) is odd, consisting of one transposition. Consider second the group H operating on the set {0,1,2,3}, consisting of the identity () and the element (0,1)(2,3). The identity () is even as before, and the element (0,1)(2,3) is also even, consisting as it does of two transpositions. S2 and H are clearly isomorphic, even though S2 contains one even and one odd permutation, and H contains two even and zero odd permutations.
The reason my program was treating every permutation of the edges as even was that it was using an S24 representation for the edges. If you think of an odd permutation on the edge cubies, in an S24 representation there will be an odd number of transpostions considering one facelet from each cubie. But there will also be an odd number of transpositions considering the second facelet from each respective cubie. Odd plus odd is even, so the overall parity is even.
I still use primarily an S24 representation for the edges in my programs. However, in order to think properly about odd and even permutations on the cube, you are probably better served thinking of a wreath product representation for the edges such as S12 wr C2. Within the S12 part of the wreath product, the twelve edge cubies will be represented by either odd or even permutations as expected. The C2 part of the wreath products then represents the flips.
If you take a cube apart and put it back together, you can put it back together in twelve times as many ways as there are positions in the cube group. Twelve is because 3 * 2 * 2 = 12. Three of the ways are because the twist of the last corner cubie you put back together can be set in one of three different ways, only one of which is legal. Two of the ways are because the flip of the last edge cubie you put back together can be set in one of two different ways, only one of which is legal. The last two of the ways are because the corners and edges can by put back together either with the same odd/even parity (legal) or with the opposite odd/even parity (illegal).
However, in one of my original cube programs nearly 20 years ago, I noticed that all edge permutations seemed to be even. So even edge permutations were occurring with odd corner permutations. Not only that, my program was producing correct results. How could this be?
What I didn't really realize at the time is that the odd and even properties of permutations are not necessarily preserved by an isomorphism. I was surprised, but I really shouldn't have been. There is nothing in the four basic group properties of closure, associativity, identity, and inverse that implies anything about odd and even permutations. And an isomorphism depends only upon the four basic group properties.
Here's a trivial example. Consider first the group S2 operating on the set {0,1}. S2 contains two elements, namely the identity () and the transposition (0,1). The identity () is even, consisting of zero transpositions. The transposition (0,1) is odd, consisting of one transposition. Consider second the group H operating on the set {0,1,2,3}, consisting of the identity () and the element (0,1)(2,3). The identity () is even as before, and the element (0,1)(2,3) is also even, consisting as it does of two transpositions. S2 and H are clearly isomorphic, even though S2 contains one even and one odd permutation, and H contains two even and zero odd permutations.
The reason my program was treating every permutation of the edges as even was that it was using an S24 representation for the edges. If you think of an odd permutation on the edge cubies, in an S24 representation there will be an odd number of transpostions considering one facelet from each cubie. But there will also be an odd number of transpositions considering the second facelet from each respective cubie. Odd plus odd is even, so the overall parity is even.
I still use primarily an S24 representation for the edges in my programs. However, in order to think properly about odd and even permutations on the cube, you are probably better served thinking of a wreath product representation for the edges such as S12 wr C2. Within the S12 part of the wreath product, the twelve edge cubies will be represented by either odd or even permutations as expected. The C2 part of the wreath products then represents the flips.
