From:

~~~ Subject:

dan hoey writes:

On 14 Jan 1992, Allan C. Wechsler postedRegarding the meta-approach of descending through a series of subgroups,

how much leverage does properly selecting the chain give you? It seems

like the jump from <F2,B2,...> to <F2,B2,L2,R2,...> is pretty large.

There are probably other paths through the subgroup lattice.

Does anyone have a table of subgroups?

well, i don't know ALL the subgroups, but i did some investigation

before devising my three stage algorithm. one of the great advantages

of thistlethwaite's four stage method is that since each subgroup

restricts the motion of various faces, it is routine to exhaustively

search the cosets spaces at each stage, since we only make twists that

leave us in the given space. so i looked at all possible ways of

restricting various faces, up to symmetry. there are three possible

restrictions for a face: no restriction, half turns only, no turns.

our problem is then coloring the faces of the cube with 3 colors, up

to symmetry (rigid and non-rigid). the polya polynomial for the faces

of the cube under this group of symmetries is:

( x^6 + 3 x^5 + 9 x^4 + 13 x^3 + 14 x^2 + 8 x ) / 48

so there are 56 different ways to three-color the faces. i spent the

better part of an evening and most of the night calculating (by hand)

the orders of these subgroups. shortly thereafter, i saw an announcement

for the group theory package GAP, which specifically mentions calculating

the order of the rubik's cube group. so i used the package to verify my

answers. here's the list (i don't see a canonical way of ordering them):

1. |<>| = 1 2. |<U2>| = 2 = 2 3. |<U>| = 2^2 = 4 4. |<U2, D2>| = 2^2 = 4 5. |<U, D2>| = 2^3 = 8 6. |<U, D>| = 2^4 = 16 7. |<U2, R2>| = 2 3 = 12 8. |<U, R2>| = 2^6 3^2 5^2 = 14400 9. |<U, R>| = 2^6 3^8 5^2 7 = 73483200 10. |<U2, R2, L2>| = 2^5 3 = 96 11. |<U, R2, L2>| = 2^12 3^4 5^2 7 = 58060800 12. |<U2, R, L2>| = 2^12 3^4 5^2 7 = 58060800 13. |<U2, R, L>| = 2^14 3^4 5^2 7^2 = 1625702400 14. |<U, R, L2>| = 2^14 3^11 5^2 7^2 = 3555411148800 15. |<U, R, L>| = 2^14 3^13 5^3 7^2 = 159993501696000 16. |<U2, R2, F2>| = 2^5 3^4 = 2592 17. |<U, R2, F2>| = 2^8 3^5 5^2 7 = 10886400 18. |<U, R, F2>| = 2^10 3^12 5^2 7^2 = 666639590400 19. |<U, R, F>| = 2^18 3^12 5^2 7^2 = 170659735142400 20. |<U2, R2, L2, D2>| = 2^6 3 = 192 21. |<U, R2, L2, D2>| = 2^13 3^4 5^2 7 = 116121600 22. |<U, R2, L2, D>| = 2^15 3^4 5^2 7^2 = 3251404800 23. |<U, R, L2, D2>| = 2^15 3^11 5^2 7^2 = 7110822297600 24. |<U, R, L, D2>| = 2^15 3^13 5^3 7^2 = 319987003392000 25. |<U, R, L, D>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 26. |<U2, R2, L2, F2>| = 2^11 3^4 = 165888 27. |<U, R2, L2, F2>| = 2^13 3^5 5^2 7^2 = 2438553600 28. |<U2, R, L2, F2>| = 2^14 3^5 5^2 7^2 = 4877107200 29. |<U2, R, L, F2>| = 2^14 3^5 5^2 7^2 = 4877107200 30. |<U, R2, L2, F>| = 2^14 3^13 5^3 7^2 11 = 1759928518656000 31. |<U2, R2, L, F>| = 2^14 3^13 5^3 7^2 11 = 1759928518656000 32. |<U2, R, L, F>| = 2^14 3^13 5^3 7^2 11 = 1759928518656000 33. |<U, R, L2, F>| = 2^24 3^13 5^3 7^2 11 = 1802166803103744000 34. |<U, R, L, F>| = 2^24 3^13 5^3 7^2 11 = 1802166803103744000 35. |<U2, F2, R2, L2, B2>| = 2^13 3^4 = 663552 36. |<U, F2, R2, L2, B2>| = 2^16 3^5 5^2 7^2 = 19508428800 37. |<U2, F, R2, L2, B2>| = 2^16 3^5 5^2 7^2 = 19508428800 38. |<U2, F2, R, L, B2>| = 2^16 3^5 5^2 7^2 = 19508428800 39. |<U2, F, R, L2, B2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 40. |<U, F, R2, L2, B2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 41. |<U2, F, R, L, B2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 42. |<U, F2, R, L, B2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 43. |<U, F, R, L2, B2>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 44. |<U2, F, R, L, B>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 45. |<U, F2, R, L, B>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 46. |<U, F, R, L, B>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 47. |<U2, F2, R2, L2, B2, D2>| = 2^13 3^4 = 663552 48. |<U, F2, R2, L2, B2, D2>| = 2^16 3^5 5^2 7^2 = 19508428800 49. |<U, F2, R2, L2, B2, D>| = 2^16 3^5 5^2 7^2 = 19508428800 50. |<U, F, R2, L2, B2, D2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 51. |<U, F, R2, L2, B, D2>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 52. |<U, F, R, L2, B2, D2>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 53. |<U, F, R2, L2, B, D>| = 2^16 3^14 5^3 7^2 11 = 21119142223872000 54. |<U, F, R, L, B2, D2>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 55. |<U, F, R, L, B, D2>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000 56. |<U, F, R, L, B, D>| = 2^27 3^14 5^3 7^2 11 = 43252003274489856000

subgroups with the same order are equal (possibly after necessary rotation

of the cube) with the following exceptions: (3, 4), (11, 12), (30, 31) and

(30, 32). equality of various pairs of subgroups can be obtained from the

three maneuvers:

R L F2 R2 F B L F2 B2 R2 F2 B2 L F B3 R3 L3 ~ U2 , so that <L, F, R, B> = <L, F, R, B, U2>, F2 U2 L2 F2 R2 U2 F2 R F2 U2 R2 F2 L2 U2 F2 ~ L , so that <U2, F2, R, L2> = <U2, F2, R, L> and R2 F2 B2 L2 U2 L2 F2 B2 R2 ~ D2 , so that <U2, F2, R2, L2, B2> = <U2, F2, R2, L2, B2, D2>.

thistlethwaite's filtration is 56 --> 53 --> 49 --> 47 --> 1.

kloosterman replaced 47 by a subgroup not on this list (one not obtained

by restricting face turns). call this 56 --> 53 --> 49 --> kl --> 1.

(in his final stage, kloosterman allows all twists available in the

subgroup 49.) my filtration is 56 --> 19 --> 17 --> 1 , which was

chosen precisely because it had the smallest size of the largest coset

space amongst all three stage filtrations with subgroups from the above.

winter's filtration is 56 --> 49 --> kl --> 1. it may be the case that

this can be improved by replacing kl with 17 , and allowing all face

turns available in the subgroup 49. i haven't had the time to look into

this yet.

using subgroups on the list above, we see that the only reasonable two

stage filtrations are:

56 --> 29 --> 1 with coset sizes 8868372480 and 4877107200 56 --> 22 --> 1 with coset sizes 13302558720 and 3251404800 56 --> 27 --> 1 with coset sizes 17736744960 and 2438553600 56 --> 49 --> 1 with coset sizes 2217093120 and 19508428800 56 --> 13 --> 1 with coset sizes 26605117440 and 1625702400

of these, the best seems to be 56 --> 49 --> 1 , since it has the most

symmetries (16). the number of symmetries the others have is 4 (for 29),

8 (for 22), 2 (for 27) and 2 (for 13). furthermore, aside from subgroup

49, the other intermediate groups seem to have too much restriction to

be efficient. also, of course, dik winter has already calculated that

the stage 56 --> 49 can always be accomplished in 12 face turns.

On 29 Jan 1992, wft@math.canterbury.ac.nz (Bill Taylor) posted

There hasn't been any response to this, seemingly, which is a pity.For some reason, I never saw Bill's message. I just noticed it when

comparing my files against the archives. [ Archives seekers note: the

archives have moved to FTP.LCS.MIT.EDU (18.26.0.36), still in

directory /pub/cube-lovers. ]

i also seem to have missed both allen's post as well as bill's reply.

perhaps 'twas the twilight zone between the start of my subscription to

cube-lovers and the time it takes recent messages to reach the archives.

however, i don't find the archives on ftp.lcs , but rather on

ftp.ai.mit.edu. also i see we've spawned cube-mail-8.Z.

In any event, I would like to know of any other well-known subgroups.

There are the slice group; double-slice group; U group; square group;

anti-slice group. How many others are there not mentioned here, that

people know of ?

in addition to those listed above there are subgroups generated by

combinations of face turns and slice turns, e.g. <U, M_R>, <U2, M_R>,

<U, R, M_R>, etc. i haven't looked at these at all. there's a lot of

work to be done here.

mike