From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Generating Rubik's Cube
Date: 29 Nov 1995 20:58:21 GMT
Just a couple of high-end leads for those who want to pursue more of the
math behind the cube. First of all we have:
In article <9511291210.Hoey@aic.nrl.navy.mil>,
Dan Hoey wrote:
>About the minimal presentation of the cube group on the usual generators,
>frb6006@cs.rit.edu (Frank R Bernhart) writes:
>
>> The answers may be in SINGMASTER, et.al.
>> "Handbook of Cubic Math" or BANDEMEISTER (sp?) "Beyond R. Cube"
>
>I recall Singmaster wanted to know if anyone found a reasonably-sized
>presentation; I don't know if any have been found in the intervening
>fifteen years. The best I know of is a few thousand relations, some
>of them several thousand letters long.
Whew! I didn't know that. It is true that the question has a clearer
statement than "what's the shortest way you've found to present the group".
For the record it goes like this:
You have a group Rubik generated by the 6 90-degree rotations g_i.
Let F be the free group on 6 generators x_i and f: F --> Rubik the
obvious homomorphism. There is a big kernel N of f. (It is actually a
free group: subgroups of free groups are free). You wish to find the
smallest (free) subgroup K of N such that N is the normal closure
of K in F. (When you give a presentation of Rubik in the form
Rubik = ,
you are implicitly describing K as the subgroup of F generated by the
corresponding words in the x_i.)
To give this process at least a chance of success, you abelianize it:
Let N_ab be the free abelian group N/[N,N], so that there is a natural
map from N into N_ab. Since N is normal in F and [N,N] is
characteristic in N, the action of F by conjugation on N lifts to an
action of F on N_ab; even better, the subgroup N < F acts trivially on
N_ab, so that F/N (i.e., the Rubik group itself) acts on N_ab.
We think of N_ab as a Rubik-module (or better, as a Z[Rubik]-module).
The subgroup K < N also maps to a subgroup K[N,N]/[N,N] of N_ab;
significantly, N is the F-closure of K iff N=[K,F]K so that N_ab
is generated as a Z[Rubik]-module by F.
Thus, the question of what constitutes a minimal set of
relations is the same as asking for the number of generators needed for
a certain Rubik-module. (Of course, while you're at it, you might as well
ask for a whole presentation or resolution of the Rubik-module. Inevitably,
you will be led to questions of group cohomology.)
===========================================================
Separately, I should point out that these computations can be automated to
an extent. I enclose a portion of the readme file from the (free!) GAP
computer algebra system, which Martin Sch"onert was perhaps too modest to
post.
dave
Analyzing Rubik's Cube with GAP
===============================
Ideal Toy Company stated on the package of
the original Rubik cube that there were more than
three billion possible states the cube could attain.
It's analogous to Mac Donald's proudly announcing
that they've sold more than 120 hamburgers.
(J. A. Paulos, Innumeracy)
To show you what GAP can do a short example is probably best. If you are
not interested in this example skip to the section "An Overview of GAP".
For the example we consider the group of transformations of Rubik's magic
cube. If we number the faces of this cube as follows
+--------------+
| 1 2 3 |
| 4 top 5 |
| 6 7 8 |
+--------------+--------------+--------------+--------------+
| 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 |
| 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 |
| 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 |
+--------------+--------------+--------------+--------------+
| 41 42 43 |
| 44 bottom 45 |
| 46 47 48 |
+--------------+
then the group is generated by the following generators, corresponding
to the six faces of the cube (the two semicolons tell GAP not to print
the result, which is identical to the input here).
gap> cube := Group(
> ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),
> ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),
> (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),
> (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),
> (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),
> (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)
> );;
First we want to know the size of this group.
gap> Size( cube );
43252003274489856000
Since this is a little bit unhandy, let us factorize this number.
gap> Collected( Factors( last ) );
[ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ]
(The result tells us that the size is 2^27 3^14 5^3 7^2 11.)
Next let us investigate the operation of the group on the 48 points.
gap> orbits := Orbits( cube, [1..48] );
[ [ 1, 3, 17, 14, 8, 38, 9, 41, 19, 48, 22, 6, 30, 33, 43, 11, 46,
40, 24, 27, 25, 35, 16, 32 ],
[ 2, 5, 12, 7, 36, 10, 47, 4, 28, 45, 34, 13, 29, 44, 20, 42,
26, 21, 37, 15, 31, 18, 23, 39 ] ]
The first orbit contains the points at the corners, the second those at
the edges; clearly the group cannot move a point at a corner onto a point
at an edge.
So to investigate the cube group we first investigate the operation on
the corner points. Note that the constructed group that describes this
operation will operate on the set [1..24], not on the original set
[1,3,17,14,8,38,9,41,19,48,22,6,30,33,43,11,46,40,24,27,25,35,16,32].
gap> cube1 := Operation( cube, orbits[1] );
Group( ( 1, 2, 5,12)( 3, 7,14,21)( 9,16,22,20),
( 1, 3, 8,18)( 4, 7,16,23)(11,17,22,12),
( 3, 9,19,11)( 5,13, 8,16)(12,21,15,23),
( 2, 6,15, 9)( 5,14,10,19)(13,21,20,24),
( 1, 4,10,20)( 2, 7,17,24)( 6,14,22,18),
( 4,11,13, 6)( 8,15,10,17)(18,23,19,24) )
gap> Size( cube1 );
88179840
Now this group obviously operates transitively, but let us test whether
it is also primitive.
gap> corners := Blocks( cube1, [1..24] );
[ [ 1, 7, 22 ], [ 2, 14, 20 ], [ 3, 12, 16 ], [ 4, 17, 18 ],
[ 5, 9, 21 ], [ 6, 10, 24 ], [ 8, 11, 23 ], [ 13, 15, 19 ] ]
Those eight blocks correspond to the eight corners of the cube; on the
one hand the group permutes those and on the other hand it permutes the
three points at each corner cyclically.
So the obvious thing to do is to investigate the operation of the group
on the eight corners.
gap> cube1b := Operation( cube1, corners, OnSets );
Group( (1,2,5,3), (1,3,7,4), (3,5,8,7),
(2,6,8,5), (1,4,6,2), (4,7,8,6) )
gap> Size( cube1b );
40320
Now a permutation group of degree 8 that has order 40320 must be the full
symmetric group S(8) on eight points.
The next thing then is to investigate the kernel of this operation on
blocks, i.e., the subgroup of 'cube1' of those elements that fix the
blocks setwise.
gap> blockhom1 := OperationHomomorphism( cube1, cube1b );;
gap> Factors( Size( Kernel( blockhom1 ) ) );
[ 3, 3, 3, 3, 3, 3, 3 ]
gap> IsElementaryAbelian( Kernel( blockhom1 ) );
true
We can show that the product of this elementary abelian group 3^7 with
the S(8) is semidirect by finding a complement, i.e., a subgroup that has
trivial intersection with the kernel and that generates 'cube1' together
with the kernel.
gap> cmpl1 := Stabilizer( cube1, [1,2,3,4,5,6,8,13], OnSets );;
gap> Size( cmpl1 );
40320
gap> Size( Intersection( cmpl1, Kernel( blockhom1 ) ) );
1
gap> Closure( cmpl1, Kernel( blockhom1 ) ) = cube1;
true
There is even a more elegant way to show that 'cmpl1' is a complement.
gap> IsIsomorphism( OperationHomomorphism( cmpl1, cube1b ) );
true
Of course, theoretically it is clear that 'cmpl1' must indeed be a
complement.
In fact we know that 'cube1' is a subgroup of index 3 in the wreath
product of a cyclic 3 with S(8). This missing index 3 tells us that we
do not have total freedom in turning the corners. The following tests
show that whenever we turn one corner clockwise we must turn another
corner counterclockwise.
gap> (1,7,22) in cube1;
false
gap> (1,7,22)(2,20,14) in cube1;
true
More or less the same things happen when we consider the operation of the
cube group on the edges.
gap> cube2 := Operation( cube, orbits[2] );;
gap> Size( cube2 );
980995276800
gap> edges := Blocks( cube2, [1..24] );
[ [ 1, 11 ], [ 2, 17 ], [ 3, 19 ], [ 4, 22 ], [ 5, 13 ], [ 6, 8 ],
[ 7, 24 ], [ 9, 18 ], [ 10, 21 ], [ 12, 15 ], [ 14, 20 ], [ 16, 23 ] ]
gap> cube2b := Operation( cube2, edges, OnSets );;
gap> Size( cube2b );
479001600
gap> blockhom2 := OperationHomomorphism( cube2, cube2b );;
gap> Factors( Size( Kernel( blockhom2 ) ) );
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> IsElementaryAbelian( Kernel( blockhom2 ) );
true
gap> cmpl2 := Stabilizer(cube2,[1,2,3,4,5,6,7,9,10,12,14,16],OnSets);;
gap> IsIsomorphism( OperationHomomorphism( cmpl2, cube2b ) );
true
This time we get a semidirect product of a 2^11 with an S(12), namely a
subgroup of index 2 of the wreath product of a cyclic 2 with S(12). Here
the missing index 2 tells us again that we do not have total freedom in
turning the edges. The following tests show that whenever we flip one
edge we must also flip another edge.
gap> (1,11) in cube2;
false
gap> (1,11)(2,17) in cube2;
true
Since 'cube1' and 'cube2' are the groups describing the actions on the
two orbits of 'cube', it is clear that 'cube' is a subdirect product of
those groups, i.e., a subgroup of the direct product. Comparing the
sizes of 'cube1', 'cube2', and 'cube' we see that 'cube' must be a
subgroup of index 2 in the direct product of those two groups.
gap> Size( cube );
43252003274489856000
gap> Size( cube1 ) * Size( cube2 );
86504006548979712000
This final missing index 2 tells us that we cannot operate on corners and
edges totally independently. The following tests show that whenever we
exchange a pair of corners we must also exchange a pair of edges (and
vice versa).
gap> (17,19)(11,8)(6,25) in cube;
false
gap> (7,28)(18,21) in cube;
false
gap> (17,19)(11,8)(6,25)(7,28)(18,21) in cube;
true
Finally let us compute the centre of the cube group, i.e., the subgroup
of those operations that can be performed either before or after any
other operation with the same result.
gap> Centre( cube );
Subgroup( cube, [ ( 2,34)( 4,10)( 5,26)( 7,18)(12,37)(13,20)
(15,44)(21,28)(23,42)(29,36)(31,45)(39,47) ] )
We see that the centre contains one nontrivial element, namely the
operation that flips all 12 edges simultaneously.
This concludes our example. Of course, GAP can do much more, and the
next section gives an overview of its capabilities, but demonstrating
them all would take too much room.
==============================================================================
From: Paul Arendt
Date: Fri, 1 Dec 1995 15:38:49 -0700
To: rusin@math.niu.edu
Subject: Rubik
Hi there,
Thanks for your mail about my cube questions. Another respondent has written
saying that 5 of the 1/4 turn generators are sufficient; explicit sequences
were found by many. There was a post by someone that 2 generators actually
suffice; I'm assuming that the generators are a longer sequence of turns whose
commutator generates more generators, or something like that.
A question: you mentioned the group generated by the 2 simple relations I gave
as being isomorphic to something called a Coxeter group, and gave some
diagram (kinda Dynkin-looking) which classified it. I haven't heard of these;
is there a reference you could give me? (Sorry; that should be "a subgroup of
the group generated by the 2 relations I gave".)
Thanks also for the GAP documentation; I hadn't heard of such a package! The
examples it gave on the cube were truly impressive.
Many thanks,
- Paul Arendt
(parendt@aoc.nrao.edu)
==============================================================================
Date: Fri, 1 Dec 95 17:12:08 CST
From: rusin (Dave Rusin)
To: parendt@mailhost.nmt.edu
Subject: Re: Rubik
Yes, the Coxeter groups are related to Dynkin diagrams. The DD's are supposed
to illustrate roots systems of Lie algebras or Lie groups; the group of
automorphisms of these algebras is the Weyl group, which is an example of
the Coxeter groups. In general though you can use this shorthand for a
wider family of groups. Each dot corrresponds to a generator of order 2.
Each edge gives a relation (gh)^n=1 [n=label on the edge, 3 if unlabelled,
and (gh)^2=1, i.e. g and h commute, if there is no edge] There are to
be no other generators or relations implied.
I suppose a reference is Coxeter and Moser, "Generators and RElations for
Discrete Groups", but I don't remember exactly what's in there. Bourbaki
has a volume on Lie Groups and Algebras. There's a book by Hller on
Geometry of Coxeter Groups. (That's Hiller, sorry). One gets into
geometric questions by asking if these abstract groups act on spaces
with the generators being reflections; constraints on the labels make the
groups act on a sphere, a plane, or hyperbolic space. It's quite fun,
actually.
dave
==============================================================================
From: Paul Arendt
Date: Fri, 1 Dec 1995 16:21:08 -0700
To: rusin@math.niu.edu
Subject: Re: Rubik
Thanks for the references. The diagram had me confused; I've only seen these
for continuous groups before, never infinite discrete groups. I've seen
the Bourbaki Lie group book before; it would take me quite some time to work
all the way through!
- Paul Arendt
==============================================================================
Date: Sun, 17 Dec 95 02:41:02 EST
From: hoey@AIC.NRL.Navy.Mil
To: Cube-Lovers@life.ai.mit.edu, rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Presenting Rubik's Cube
A few weeks ago I mentioned the old problem of finding a presentation
of the Rubik's cube group in terms of the usual generators. This was
posed by Singmaster over 15 years ago, and as far as I know has never
been addressed. I've made some progress.
I work using a specially selected set of generators, rather than the
usual generators given for the cube. First I give presentations
separately for the permutation groups of the corners and edges, and
the orientation groups of the corners and edges. Then I join the
permutation groups with their respective orientation groups to form
the wreath groups, which describe the possible motions of the
respective piece types. I join the two wreath groups in such a way
that the permutation parity of the two is equal. Finally, I discuss a
method of converting to the usual generators.
In Coxeter and Moser's _Generators and Relations for Discrete Groups,
2nd ed_ I found Coxeter's presentation 6.271 for the symmetric group
on {1,2,...,n}, n even. With a modest change of variables, his
presentation is on generators
v=(1 2) and s=(2 3 ... n) ((1))
and relators
v^2,
v s^(n-2) (v s^-1)^(n-1),
(s^-1 v s v)^3, and
((s^-1 v)^i (s v)^i)^2, i=2,...,n/2-1. ((2))
Here n will be 8 or 12 to present the group of the permutations of
corners or edges, respectively.
The orientation group of the corners (or edges) is the direct product
of n-1 cyclic groups, which can be presented with generators
r_0=(1)+(2)-
r_1=(1)+(3)-, ...,
r_(n-2)=(1)+(n)-, ((3))
where (k)+ indicates a reorientation of piece k in place and (k)-
indicates the inverse reorientation. The relators here are
r_i^d, (d=3 (corners) or 2 (edges)), and
r_i r_j r_i^-1 r_j^-1, 0 <= i < j <= n-2. ((4))
I generate the wreath group with the union of the generators ((1,3)).
The added relators
v r_0 v r_0
v r_i v r_0 r_i i=1,...,n-2,
s^-1 r_i s^i r_(i+1)^-1 i=0,...,n-3, and
s^-1 r_(n-2) s^i r_0^-1 ((5))
will permit moving the r_i to the end of a word, after which the
previous relators ((2)) and ((4)) may be used to manipulate the parts
separately, just as a Rubik's cube solvers can perform any needed
permutations before reorientations.
In the wreath group, the r_i are conjugate to each other. The third
line of ((5)) may be used to define r_k = s^-k r_0 s^k, so I eliminate
r_1,...,r_(n-1) and write r_0 as r. The last line of ((5)) is then a
consequence of s^(n-1)=e, which is implied by ((2)), according to
Coxeter. The conjugacy also lets me rewrite ((4)) as
r^d, (d=3 (corners) or 2 (edges)), and
s^-j r s^j r' s^-j r' s^j r, j=1,...,(n-2)/2. ((6))
As the discussion turns to working with corners and edges together, I
write cs,cr and es,er for the respective generators. I use a single
generator v that acts on both corners and edges, to ensure that the
corner permutation has the same parity as the edge permutation. Since
any identity in {v,cs,cr} must use an even number of v's, the identity
will hold in the when the v operates on edges as well; similarly for
{v,es,er} operating on the corners.
To present the whole cube group, I use all five generators, relators
((2,5,6)) for both corners and edges, and new relators
es cs es' cs', er cs er cs', es cr es' cr', er cr er cr'
to make the two kinds of generators commute, so they may be separated
in a word. According to GAP, the complete set of relators is
er^2,
v^2,
cr^3,
er cr er cr^-1,
er cs er cs^-1,
es cr es^-1 cr^-1,
es cs es^-1 cs^-1,
(v cr)^2,
(v er)^2,
cr cs cr cs^-1 cr^-1 cs cr^-1 cs^-1,
(er es er es^-1)^2,
cs cr^-1 cs^-1 v cs cr cs^-1 v cr,
cs^-1 cr^-1 cs v cs^-1 cr cs v cr,
(es er es^-1 v)^2 er,
(es^-1 er es v)^2 er,
cr cs^2 cr cs^-2 cr^-1 cs^2 cr^-1 cs^-2,
(cs^-1 v cs v)^3,
(er es^2 er es^-2)^2,
(es^-1 v es v)^3,
cr^-1 cs^-2 v cs^2 cr cs^-2 v cr cs^2,
cr^-1 cs^2 v cs^-2 cr cs^2 v cr cs^-2,
er es^-2 v es^2 er es^-2 v er es^2,
er es^2 v es^-2 er es^2 v er es^-2,
cr cs^3 cr cs^-3 cr^-1 cs^3 cr^-1 cs^-3,
((cs^-1 v)^2 (cs v)^2)^2,
(er es^3 er es^-3)^2,
((es^-1 v)^2 (es v)^2)^2,
cs^-3 v cs^3 cr cs^-3 v cr cs^3 cr^-1,
cs^3 v cs^-3 cr cs^3 v cr cs^-3 cr^-1,
(es^3 er es^-3 v)^2 er,
(es^-3 er es^3 v)^2 er,
(cs^-2 v cs^-1 v cs v cs^2 v)^2,
(es^-2 v es^-1 v es v es^2 v)^2,
(er es^4 er es^-4)^2,
(es^-4 er es^4 v)^2 er,
(es^4 er es^-4 v)^2 er,
v cs^6 (v cs^-1)^7,
(es^-3 v es^-1 v es v es^3 v)^2,
(er es^5 er es^-5)^2,
(es^5 er es^-5 v)^2 er,
(es^-5 er es^5 v)^2 er,
(es^4 v es^-4 v es^-1 v es v)^2,
v es^10 (v es^-1)^11, ((7))
which has 43 relators of total length 597. It is apparently beyond
GAP's ability to verify that these relators present the cube group,
though I have verified some smaller wreath groups.
This presentation is of course in terms of generators {v,es,er,cs,cr},
not the generators {F,B,L,R,T,D} natural to the cube. But they can be
translated as follows. Each quarter-turn Q can be expressed as a word
w(Q) over {v,es,er,cs,cr}, and adding the relators
F' w(F), B' w(B), L' w(L), R' w(R), T' w(T), D' w(D) ((8))
will create a presentation on eleven generators
{v,es,er,cs,cr,F,B,L,R,T,D}. I estimate that the added relators will
be under 70 letters each, and probably less. If it is desired to
completely eliminate {v,es,er,cs,cr}, that may be done by replacing
each of {v,es,er,cs,cr} with processes in terms of F,B,L,R,T,D,
throughout ((7,8)). My understanding of the current state of the
software is that the processes will probably be less than 30
quarter-turns each. This would yield a presentation of 49 relators
and perhaps 2000 letters. It should be possible to improve this quite
a bit. I would suggest:
1. Choosing the corner and edge numbering to reduce the
rewriting blowup,
2. Allowing w(Q) to use previously-related Q's as well as
{v,es,er,cs,cr}.
3. Adding new relators to abbreviate higher powers, especially
of es and cs, in the presentation.
4. Introducing short relators such as F^4=FBF'B'=e to cut down on
the general verbosity of the relators.
But improvement to the level of actual comprehensibility may require
new ideas. Perhaps Dave Rusin's "clearer statement" of the question
may help, if I can figure out what it means.
Dan posted and e-mailed
Hoey@AIC.NRL.Navy.Mil
==============================================================================
Date: Sun, 17 Dec 95 21:09:25 EST
From: hoey@AIC.NRL.Navy.Mil
To: Cube-Lovers@AIC.NRL.Navy.Mil, Frank R Bernhart ,
rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Presenting Rubik's Cube
In my article on a presentation of the Rubik's cube group last night,
I omitted a relator from list ((7)):
v es v cs v es^-1 v cs^-1.
This brings the number of relators to 44, with a total length of 605.
Experiments with GAP on some smaller cube-like groups indicate that
with this addition, the presentation is correct.
My apologies for the error.
Dan Hoey Posted and e-mailed.
Hoey@AIC.NRL.Navy.Mil