From: hoey@aic.nrl.navy.mil (Dan Hoey) Newsgroups: sci.math Subject: Re: Math involved with Rubik's Cube Date: 10 Jul 1995 21:33:19 GMT dmorton@undergrad.math.uwaterloo.ca (David Morton) writes: > ... does anybody have information on > mathematical analysis of the Rubik's cube? I heard that it was > proven that the best solution for a given cube would be less then > ~50 twists (a twist being 90 degree turn of a side).... I think the best upper bound now known is michael reid's. In January 1995, he showed that 42 moves suffice (or 29 moves if you also allow 180-degree turns). You can see his report of it on http://www.math.rwth-aachen.de:8000/~mschoene /Cube-Lovers/michael_reid__new_upper_bounds.html also available in ftp://ftp.ai.mit.edu/pub/cube-lovers/cube-mail-14.gz If you want to join the mailing list where we discuss this and other aspects of cube analysis, send email to Alan Bawden at Cube-Lovers-Request@AI.MIT.Edu and he'll put you on the list. Dan Hoey Hoey@AIC.NRL.Navy.Mil ============================================================================== [I received some corrections to a file previously in this place from David Joyner . I believe they are correct. In what follows, lines beginning with ">" are from the original poster (parendt), lines beginning with "###" are from wdj, and unmarked lines are from me -- djr] ============================================================================== ###Date: Mon, 27 Jan 1997 11:47:52 -0800 ###From: David Joyner ###To: rusin@math.niu.edu ###Subject: Rubik's cube Date: Wed, 29 Nov 95 13:38:26 CST From: rusin (Dave Rusin) To: parendt@nmt.edu Subject: Re: Rubik's Cube Newsgroups: sci.math In article <49dhqm$93e@newshost.nmt.edu> you write: >While people are on the subject, a related question: >Has anyone looked at the cube via group-graph methods? In particular: >1. How many independent generators are there? Six generators (1/4 >turns about each face) will generate the whole group, but can one of >these be expressed as a multiplication of the others? In other words, >can we effect a turn about one face by only turning the other 5? Note >that I'm counting rotations of the face centers as indistinguishable. >(I've a hunch 5 is the answer to this.) You are asking about whether G_S=< g_i | i in S > generates the whole group when S is a proper subset of {1, 2, 3, 4, 5, 6}. I have the same hunch as you. It would be easy to demonstrate as follows: for each of the fifteen subsets S of cardinality 4, show that the above group G_S is a proper subgroup of the group Rubik. This in turn you can show by showing that for some homomorphism f on Rubik you have f(G_S) < f(Rubik). Almost certainly you can use f: Rubik --> S_8, the function which assigns to each rubik motion the corresponding permutation of the 8 corners. The image of f is the alternating group. I'm not ### I don't think f(Rubik)=A_8 is correct. f "forgets" the edge permutations. ###There are moves which are 2-cycles on corners and 2-cycles on edges. ###For example, g=(ufr,ufl)(ur,ul) is a move in Rubik and f(g) is a 2-cycle. ###Any 2-cycle can be obtained this way, so f(Rubik) is S_8. inclined to do so myself but you could fire up GAP/Magma/Caylet/etc. and ask for the computation of the subgroup of S_8 generated by the f(g_i) for i in S. (Actually there are among the 15 subgroups here only 2 equivalence classes of subgroups under the action of the automorphism group: you need only consider the effect of leaving out two of the g_i corresponding to opposite faces, and that of leaving out two adjacent g_i). ###The "2-faces group" is isomorphic to S_7xPGL_2(F_5) according to ###D Singmaster. I don't know the result for 3- or 4-faces, though it ###may be known. >2. How many relations between the generators suffice to determine the >whole group? For those who require an explanation: a relation is an >expression of the form > g g g ... g = e (the identity) > a1 a2 a3 aN >where the g's are group generators. For example, taking the 6 generators >in #1 above, we have: > 4 > (g) = e for any face turn, and > 2 2 4 > [(g ) (g ) ] = e for adjacent faces a and b. > a b > ### I think that (R^2U^2)^6=1, but (R^2U^2)^4 <> 1. >I've no hunches about this one! More relations are certainly necessary. Take the free group on 6 letters g_a and mod out by the relations shown. You are asking if this is the Rubik group. Well, in the group you just created there is the subgroup generated by the g_a^2 for two opposite sides and a side between them. This subgroup is isomorphic to the group , a Coxeter group known as 4 4 * --------- * ---------- * which is infinite. ### One should replace the 4's by 6's I think. The group is still infinite ###I think (see Humphrey's book on Coxeter groups, sections 6.4, 6.7). Indeed, your question may be recast in this language: You are fixing a homomorphism f: Free(6) --> Rubik and you are looking at the kernel N. You want to know the smallest free group K < N such that its normal closure in Free(6) is N. This sort of thing is done in group theory by looking at the quotient of the whole thing modulo [Free(6), N], turning the free abelian group N/[N,N] into a Z[Rubik]-module; you are asking for the number of generators of this module (I suppose you wouldn't mind having the generators spelled out, either). I don't know the answer, but this sort of thing is doable by those who do this sort of thing :-). [Consult books on group cohomology and group rings for this discussion.] ==============================================================================