GAP: Rubik’s Cube Group – Thistlethwaite’s algorithm

algorithmsgapgroup-theoryrubiks-cube

In GAP let $G_0$ be the Rubik's Cube Group defined by the six moves

U := (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19);
L := (9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35);
F := (17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11);
R := (25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24);
B := (33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27);
D := (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40);
G0 := Group([U, L, F, R, B, D]);

Then define the subgroups, see Thistlethwaite's Algorithm

G1 := Subgroup(G0, [L,   R,   F,   B,   U^2, D^2]); 
G2 := Subgroup(G0, [L,   R,   F^2, B^2, U^2, D^2]);
G3 := Subgroup(G0, [L^2, R^2, F^2, B^2, U^2, D^2]);

I try to define quotient groups with GAP, but unfortunately I get the following error:

FactorGroup(G2, G3);
Error, <N> must be a normal subgroup of <G> at /proc/cygdrive/C/gap-4.11.0/lib/grp.gi:2569 called from
<function "FactorGroup">( <arguments> )
 called from read-eval loop at *stdin*:13
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

I do not understand this error since

IsNormal(G3, G2);
true

tells me that $G_3$ is indeed normal in $G_2$. What is wrong with my code?

Best Answer

Thistlethwaite's algorithm uses coset spaces, not factor groups. The groups aren't normal. The function is IsNormal(G, H), i.e. the bigger group goes first, but you're plugging in the smaller group first. As GroupProps notes, "Note that if the order of the group and the subgroup are interchanged, GAP will not detect an error and will return true, because any subgroup of a group normalizes the whole group."

Related Solutions

Group Theory – Creating a Rubik’s Cube Algorithm

I assume you are referring to human methods and not using Rubik's cube solvers such as Cube Explorer to create algorithms for you.

In addition, I assume that you are wondering about how to create a set of algorithms which collectively solve a certain phase of a step-by-step process. Maybe you want to find an algorithm set which solves the last 3 corners? An algorithm which flips the last 4 edges?

First off, if you want to create an algorithm which affects a certain amount of pieces on a cube in a certain fashion (or at least a definable portion of a cube), it's only practical to be able to experiment with a solved cube. That is, use some computer animated Rubik's cube for which you can click the reset (solve) button to start off with a solved cube again whenever you try to do some moves but accidentally scramble the cube.

After a while of experimenting, if you write down short sequences you find which affect a few pieces at a time and learn about commutators and conjugates, then eventually you will have a small "library" of sequences which you use to build longer and more complicated algorithms from than you ever imagined.

An interesting technique I taught myself is that you can literally cyclically shift the moves of one algorithm to create another algorithm. For example, maybe you know of the Niklas commutator, R U' L' U R' U' L U. If we shift (conjugate it with the inverse of the first move) this algorithm once, we get an alternate 3 corner cycle algorithm U' L' U R' U' L U R.

In addition, we can invert turns in some existing algorithms to get other useful algorithms. Using the Niklas again, how about we invert all U face turns to get R U L' U' R' U L U'. How about convert some turns to half turns? R U L2 U' R' U L2 U'

This leads me into another strategy. I recall many times when I studied existing algorithms to see (or guess) how they work, and in that process of struggling, I perhaps not only understood how an existing algorithm worked, I created a new one based off of the "idea" of my interpretation of how that algorithm worked. In addition, some existing algorithms can be broken into several understandable steps, and so perhaps you can use a portion of an existing algorithm to create a new algorithm.

In addition, a simple technique (although algorithms found this way will be quite lengthy) is to repeat a short random sequence you find to create a base algorithm (instead of using commutators). For example, if you have the algorithm R U R' U' R (which appears to be random moves), you can repeat it three times to create an algorithm which swaps two edges: (R U R' U' R)3. It of course also cycles 4 corners, but maybe we can use it to do something we are familiar with. Let's give it a shot!

If we:

Expand it, R U R' U' R R U R' U' R R U R' U' R
Shift the first three moves U' R R U R' U' R R U R' U' R R U R'
Conjugate it with one move, B' U' R R U R' U' R R U R' U' R R U R' B

= B' U' R2 U R' U' R2 U R' U' R2 U R' B, then we have an algorithm which can be used to place an edge in the middle layer (where we assume we have solved the bottom layer and have not solved the top layer), for example.

All in all, it really depends what you want to accomplish with the algorithms you find for anyone to more accurately describe to you the methods humans use to do what you want to do in particular, as there are literally an unlimited number of algorithms you can find, and there are many sub-step methods (one of them being the beginner's layer by layer 3x3x3 solving method), some which are speedsolving methods, others are fewest move methods, others blind-solving methods, and so forth.

Personally, I have created hundreds of very short and complicated 4x4x4 parity algorithms from 2009-2013 which I eventually put on this page, and thus I probably do not look at parity algorithms the way anyone else does. The way I created so many algorithms is because when I found one algorithm, I remembered how I found it--the different pieces which make it up--and I later reused either those moves or simply the concept to construct a new parity algorithm. That is, the human mind has the memory capacity to be able to relate two unrelated algorithms (which can affect a cube differently) and form a third algorithm which you can think of as a "hybrid" of the two ideas from both algorithms. In addition, I started a thread about the methods I created and used to find several parity algorithms, if you're also interested in the 4x4x4.

I could continue on and on, but hopefully this post has given you a small idea of how humans can find algorithms without using solvers. However programs can be used to find all possible short sequences to do a specific task for you, for example, and you can then experiment with those short sequences and build algorithms from them: no one ever ruled out computer and human interaction.

[Math] Determine the highest order of an element of a Rubik’s Cube group

The maximum orders for a $n\times n\times n$ Rubik's cube group: \begin{align*}n=2: &\quad 3^2\cdot 5 = 45\\ n=3: &\quad 2^2\cdot 3^2\cdot 5\cdot 7 = 1260\\ n=4: &\quad 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17 = 765765\\ n=5: &\quad 2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 23 = 281801520\\ n\ge 6: &\quad 2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 5354228880\end{align*}

In general, there are five types of piece to consider:

For odd $n$, each face has a center. By convention, we treat these as fixed. If we don't, they can be rotated like a solid cube, for a copy of $S_4$. Highest order $4$, least common multiple $2^2\cdot 3=12$. As the largest possible order is divisible by $12$ for all odd $n\ge 3$, whether we include these doesn't affect the answer.
For any $n\ge 2$, there are $8$ corner pieces which can be permuted and rotated, a semidirect product of $S_8$ and $(\mathbb{Z}/3)^8$ - except that that the "sum" of those rotations is zero, dropping one factor of $3$ from the latter part. The order of an element is at worst $3$ times the order of an element of $S_8$. Highest possible order $15\cdot 3=45$, least common multiple $2^3\cdot 3^2\cdot 5\cdot 7$.
For any odd $n\ge 3$, there are $12$ centers of edges, which can be permuted and reflected. The number of reflections must also be even, for a semidirect product of $S_{12}$ and $(\mathbb{Z}/2)^{11}$. Highest possible order $60\cdot 2=120$, least common multiple $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11$.
For any $n\ge 4$, there are $\left\lfloor\frac{n}{2}\right\rfloor-1$ orbits of 24 off-center edges, which can't change how far from the center of their edge they are. The pair of edges on each side are distinguishable due to being reflections of each other, and the group for each set of these pieces is a copy of $S_{24}$. Highest possible order $8\cdot 7\cdot 5\cdot 3 = 840$, least common multiple $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$.
For any $n\ge 4$, there are $\left\lfloor\frac{(n-2)^2}{4}\right\rfloor$ orbits of 24 off-center face pieces each. These can be rotated in their face, but not reflected; mirror images across a symmetry line within a face (in size $\ge 6$) are separate orbits. Each piece of the same color in one of these sets is indistinguishable, so that gets us an action of $S_{24}$, with $\frac{24!}{24^6}$ possible states. The possible orders are the same as in the previous case. In terms of what we need to solve the cube, there are three variants based on whether they lie on a symmetry line of a face - but they're all the same for the count we care about here.

So then, the highest possible order in any Rubik group is the least common multiple of all of these, namely $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$. This is achieved for all $n\ge 6$; we have at least six of the size-24 orbits, which we can use to produce orders of $16\cdot 5$, $9\cdot 11$, $7\cdot 13$, $17$, $19$, and $23$.

Now, all of this assumes that we can modify the pieces in each orbit independently. That isn't quite true - several combinations must be even permutations. First, for odd $n$, the combined permutation of corners and edge centers is even; they're modified by face rotations, each of which is a 4-cycle of edges and a 4-cycle of corners. Second, for $n\ge 4$, the combined permutation of the corners and an orbit of pieces on face diagonals is even. Next, for $n\ge 6$, each mirrored pair of orbits of off-center face pieces must have a combined even permutation; each face rotation and each relevant slice rotation is a 4-cycle in each of the orbits. Finally, for odd $n\ge 5$, the combined permutation of off-center edge pieces, pieces on face diagonals, and pieces on face midlines at a fixed distance from the center is even. These parity restrictions are the only additional restriction; other than that, the orbits can be manipulated independently.
How does this change things? For the $n\ge 6$ case, all we have to do is implement the order $16\cdot 5$ piece as the product of a $16$-cycle, a $2$-cycle, and a $5$-cycle. Then all of the permutations we're working with are even, so there aren't any problems. In the smaller cases, we'll have to check.

For $n=2$, only the corners matter, and the highest order is $45$.
For $n=3$, we have corners and edge centers. With $17$ possible orders for the first and $31$ for the second, we can just scan all of the possible combinations. The highest LCM is $2520$, from order $45$ (3-cycle, 5-cycle, rotations in the 3-cycle don't add to zero) in the corners and order $56$ (4-cycle, 7-cycle, reflections in the 4-cycle don't add to zero) in the edges. This, however, doesn't pass the parity check; the combined permutation is odd, and there's no wiggle room to change that. That leaves us dropping down to the second-highest possibility of $1260$, possible in several ways ($45$ and $28$, $45$ and $84$, $35$ and $36$, $70$ and $36$). Three of those fail the parity check, leaving only the pair of order $45$ in the corners and order $28$ (Two 2-cycles, a 7-cycle, reflections in at least one 2-cycle don't add to zero) in the edges. Highest order $1260$, as previously noted.
For $n=4$, we have the corners, one orbit of off-center edges, and one orbit of off-center face pieces. With over a hundred possible orders in $S_{24}$, finding the least common multiple isn't the easiest search. Pruning everything with an order that divides another gets that down to a manageable total of $27$, and $5$ for the corners. Running it in the spreadsheet I've been using, the LCM is $765765=3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$; $45$ in the corners, $11\cdot 13$ in the edges, and $7\cdot 17$ in the faces. Checking parity... all the pieces are odd permutations, so we'll actually have something of that order.
For $n=5$, we have corners, edge centers, three size-24 orbits, and two parity restrictions that cross orbits. The best I've got here is $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 23 = 281801520$; it could use an independent check, but I'm pretty sure it's right. The three size-24 orbits get us orders of $23$, $7\cdot 17$, and $11\cdot 13$ while the corners give us order $45$ and the edges give order $16$ (an 8-cycle and a 2-cycle, with an odd number of reflections in the 8-cycle). They're all odd permutations, so the parity checks pass.
For $n\ge 6$, as previously noted, we reach the maximum possible order $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 5354228880$.

Best Answer

Related Solutions

Group Theory – Creating a Rubik’s Cube Algorithm

[Math] Determine the highest order of an element of a Rubik’s Cube group

Related Question