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.]
==============================================================================