Home »

Presentation for Rubik's cube

Submitted by jaap on Fri, 03/12/2010 - 03:32.
I just found a recent post by "secondmouse" on sci.math that deserves a wider audience. I'll quote it here in full. 
I found the following short presentation for the
miniature 2x2x2 Rubik's cube of order 3674160:

    < a,b,c | a^4 = b^4 = c^4 = 1,
                 ababa = babab,
                 bcbcb = cbcbc,
                 abcba = bcbac,
                 bcacb = cacba,
                 cabac = abacb,
                 (ac)^2 (ab)^3 (cb)^2 = 1 >

See the following link for more info as to why
3 generators makes sense in this case:

http://www.jaapsch.net/puzzles/cube2.htm

By adding three more generators a^2, b^2 and c^2
and six extra relators I found another presentation
describing it in terms of the half-turn metric
(the diameter of the Cayley graph on the nine
generators including inverses is known to be 11).

Would this approach (i.e. finding short edge-cycles
of adjacent generators) be fructiferous in tackling the
much harder 3x3x3 case presented on it's usual
generators {L, R, F, B, U, D}  - rather than using
semidirect or wreath products which has seemed
to be the case traditionally?

Someone must know more about this given it's
a 30-year old question of Singmaster.
I checked that the relations are indeed correct (using a=R, b=U, c=F for example). I know very little about presentations, so I'd like to know what would be the easiest way to check that this is indeed a presentation of the 2x2x2 cube group and not some supergroup of it?
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

I used GAP to find the size o

Submitted by Bruce Norskog on Mon, 03/15/2010 - 11:30.
I used GAP to find the size of the group that the presentation would produce and got 3674160, so I assume this means its a valid presentation of the 2x2x2. 
gap> G := FreeGroup ("a", "b", "c");

gap> H := G / [ G.1^4, G.2^4, G.3^4,
>  G.1*G.2*G.1*G.2*G.1*G.2^-1*G.1^-1*G.2^-1*G.1^-1*G.2^-1,
>  G.2*G.3*G.2*G.3*G.2*G.3^-1*G.2^-1*G.3^-1*G.2^-1*G.3^-1,
>  G.1*G.2*G.3*G.2*G.1*G.3^-1*G.1^-1*G.2^-1*G.3^-1*G.2^-1,
>  G.2*G.3*G.1*G.3*G.2*G.1^-1*G.2^-1*G.3^-1*G.1^-1*G.3^-1,
>  G.3*G.1*G.2*G.1*G.3*G.2^-1*G.3^-1*G.1^-1*G.2^-1*G.1^-1,
>  G.1*G.3*G.1*G.3*G.1*G.2*G.1*G.2*G.1*G.2*G.3*G.2*G.3*G.2 ];

gap> Size(H);
3674160
(I posted something similar earlier, but the post got lost.)
» login or register to post comments

Non trivial identities

Submitted by mdlazreg on Mon, 03/15/2010 - 08:40.
I think presentations are simply descriptions of a group using its non trivial identities. This relates to the following post :
Non trivial identities

The easiest way to check if the above presentation describes the 2x2x2 cube group or not is to write a program that generates all positions in a breath first manner while not counting any position that has already been seen based on the provided identities. If the final count is 3674160 then this presentation is indeed a 2x2x2 cube one.

For the 2x2x2 cube, this is easy since 3674160 is a small number. But for the 3x3x3 the task is quite difficult.

I will be very much interested in knowing how the above presentation was found especially the following non trivial identity:

(ac)^2 (ab)^3 (cb)^2 = 1


Please note that this non trivial identity has a length of 14 which is the diameter in the QTM... This answers a question that I had a long time ago if the length of non trivial identities can reach the diameter... Apparently the answer is yes.
» login or register to post comments

Bounds on identity length

Submitted by jaap on Sat, 03/20/2010 - 03:15.

"This answers a question that I had a long time ago if the length of non trivial identities can reach the diameter... Apparently the answer is yes."

I don't see why the diameter would be special with regards to the length of an identity. The longest an identity could be is if it were to reach an antipode, in which case it would be twice the diameter (start to antipode, plus antipode to start via a different route).

The 2x2x1 cuboid (e.g. the Morph Head puzzle, or equivalently the <R2,U2> group on the 2x2x2 cube) has a diameter of 6, and has the non trivial identity (R2U2)6, which is 12 moves.
Granted that is a trivial puzzle, but I see no reason to think that the diameter itself is a bound on identity length in a more complicated puzzle rather than twice the diameter.

Edited to add:
Another thing is that we don't know if that 14q identity on the 2x2x2 is non-trivial, in the sense that there may be one or more shorter identities which can be used in its place in the presentation.

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

» login or register to post comments

Hi Jaap, Actually I was wr

Submitted by mdlazreg on Fri, 04/02/2010 - 05:20.
Hi Jaap,

Actually I was wrong in the sense that that does not answer my question because the 14q identity is not twice the diameter. I was confused by the number 14 appearing as the diameter and as the length of the identity and jumped to my conclusion...

However your example of the Morph Head puzzle does answer my question that they are puzzles for which the longest non trivial identity is twice the diameter.


We should be able to verify if the 14q identity on the 2x2x2 is non-trivial or not. All is needed is a program that generates positions in a breath-first manner and eliminate duplicates using the supplied identities, if the distribution table found this way matches the known optimal distribution of 2x2x2 then the identity is non-trivial otherwise there is a lower identity which should be easy to spot by looking at when the numbers start to diverge...

The 2x2x2 puzzle is so small and simple that such program is possible I think and would not take much time to complete. I will write one if I have time.

I doubt however that such techniques will shed any lights on the 3x3x3 non trivial identities...
» login or register to post comments

Another presentation on 3 involutions!

Submitted by secondmouse on Tue, 03/30/2010 - 15:22.
The length 14 one I think cannot be made shorter.
It is difficult to be certain but I think this presentation on the usual generators is quite optimal.
However note that b^4 = 1 & c^4 = 1 are actually redundant.

Unravelling the symmetry a little more it can be seen that the miniature Rubik's cube group can also actually be generated by 3 involutory elements.

Here is the presentation expressed as compactly as I could find (the # just denotes a comment):

< a,b,c | a^2 = b^2 = c^2 = 1,
(ab)^6 = 1, # all 9 edge-pairs get moved in a 3x3 cycle - nice!
(bc)^6 = 1, # ditto
(ca)^6 = 1, # redundant
abcabacba = bacbabcab, # 2+2+4+10
abacbabcbabcaba = bacabacacabacab, # 4+4+4+6
cbabcabcbcbacbabc = acababcacacbabaca, # 4+12
bcacbcabcbcbacbcacb = acabacabababacabaca # 3+3+4+8 >

Here we can set for example:

a = U^2 F U^2 R^2,
b = F^2 R F^2 U^2,
c = R^2 U R^2 F^2

where {U,F,R} are per the Rubik's cube example
in GAP with the edges taken out, i.e.

U := ( 1, 3, 8, 6)( 9,33,25,17)(11,35,27,19);
F := (17,19,24,22)( 6,25,43,16)( 8,30,41,11);
R := (25,27,32,30)( 3,38,43,19)( 8,33,48,24);

Each generator moves 18 of the 21 corner elements - one of the seven corners stays fixed by each generator.

Re-define the values of U, F and R to verify the assertions to the right of the #'s.

The group generated by U, F and R below is the "edge" group of the 2x2x2 - i.e. with corner moves taken out.

U := ( 2, 5, 7, 4)(10,34,26,18);
F := (18,21,23,20)( 7,28,42,13);
R := (26,29,31,28)( 5,36,45,21);

I'd be very interested if the above presentation of total length 150 (without the redundant one) could be improved upon. This is terms of number of relations and relations that move ALL the edges in the larger 3x3x3.

BTW I used the following open-source code (kbprog) to verify the presentation as it proved significantly faster than GAP. This involves casting the presentation as a potentially confluent rewriting system (RWS) - see the examples/rubik folder
for the syntax.

http://sourceforge.net/projects/maffsa/

I haven't tried to establish the diameter w.r.t. this generating set yet though it seems probable it will be in excess of 50.

EDITED on 1/4/2010 - shows how one should not speculate! - indications are from a sample of 100 randomly generated reduced words that the diameter of the Cayley graph should be not nearly that big.

P.S. I made a few corrections also to the comments of the behaviour of the edge patterns in the presentation. I'm very sorry if this confused anyone - I only noticed the egregrious errors in the comments today - I think I must have left out a squared entry in the U^2 F U^2 R^2 etc. generators (curiously of length 7 in the QTM!) when I was typing them in by hand to work out the edges permutations. I also replaced two length 34 relations with one single third one also of length 34 but apart from the I wasn't able to simplify it any further.

Paul T.
» login or register to post comments

Revision - Much clearer presentation

Submitted by secondmouse on Fri, 04/16/2010 - 09:59.
In the presentation above I have been over-complicating things. Here is the revised presentation for the miniature 2x2x2 Rubik's cube group on 3 involutory generators: 
< a,b,c | a2 = b2 = c2 = 1, 
  (ab)6 = 1, # all 9 edge-pairs get moved in a 3x3 cycle
  (bc)6 = 1, # ditto
  (ca)6 = 1, # redundant
  abcabacba = bacbabcab, # 2+2+4+10
  bcabcbacb = cbacbcabc, # ditto
  cabcacbac = acbacabca, # redundant (not in the order 4 analogue!)
  abacacabcabacbacacaba = cacbcababacababacbcac # 2+2+2+4+4+4 >
This is of total length 108 with the redundant ones taken out - a saving of 42 versus the previous one! Note the Cayley graph and the antipodes supplied remain valid as the same permutation representations are being used to search for a more compact/sensible set of relations. Note the appearance of a new length 42 relation which supersedes the other ones. This is analogous to the length 14 relation in the presentation on the quarter-turn generators earlier in the thread. This is of order 4 in the larger 3x3x3. Squaring this up we have a mini-superflip of six edge pairs: 
(2,34)(7,18)(13,20)(21,28)(23,42)(29,36)
as opposed to (UR)2 (UF)3 (RF)2 squared in the larger 3x3x3 which yields 
(2,34)(4,10)(5,26)(13,20)(21,28)(23,42)(29,36)(31,45)
Both of these mini-superflips can be seen to be symmetric diagonally about the fixed 2x2x2 block of the unmoved D,B and L faces.

Paul Timmons

» login or register to post comments

For anyone interested

Submitted by secondmouse on Mon, 04/05/2010 - 16:41.
Using the "autgroup" function in Alun Williams Monoid Automata Factory (MAF) par-excellence re-engineered suite of programs (originally provided by Derek Holt et al as the KBMAG package) - I've now worked out the diameter of the Cayley graph as 29. Here are the 24 antipodes w.r.t. the "shortlex" ordering 
  abababcabcababcacabcabcbabacb
  abababcabcbcbacbacbabacacabac
  abababcacbabacbacbacbacababca
  abababcbacacabcabcababcbcbabc
  ababacababacbcabcabcbcbacabac
  ababacabcababcacabcabcbabacbc
  ababacabcababcbacbcacacbabaca
  ababacacbcbacacabacbabcbcabca
  ababacbacacabcabcababcbcbabca
  ababacbacacabcabcababcbcbabcb
  ababacbacbabacabcacbcbcababcb
  ababacbcacabcbcbabcabacacbacb
  ababcabcabacabcbacbabcbacabca
  ababcabcabcabababcacacbcbcaba
  ababcbcababacabcacbcbacbacbcb
  ababcbcacbacbacbacacababacbca
  ababcbcbcabcababacabcabcbabca
  abacabacababcbcacabcbcacbabca
  abacacbababcbacbcacabcabcacac
  abacbacacacbacbababcbacbacabc
  acabacacababcabcabcbcbacbabab
  acabcabababcabcacacbcabcabacb
  acabcbacbacababacbabcbcbcacba
  acacbcbabcabcabcababacacabcba
Here is a table with length vs. count of reduced words of that length as Jaap has already provided for the 2x2x2 cube on the order 4 generators e.g. {U,F,R} now on Wikipedia. 
Length Number
0      1
1      3
2      6
3      12
4      24
5      48
6      93
7      180
8      351
9      657
10     1224
11     2243
12     4098
13     7446
14     13416
15     23976
16     42516
17     74844
18     129419
19     217756
20     351336
21     526456
22     693365
23     731177
24     546662
25     247745
26     54345
27     4513
28     224
29     24
Curiously the values of U, F and R expressed in terms of a, b and c are of length 23, the "densest" (is this the correct term?) length. 
U = acacbabcbacbacacabacbac
F = babacbcacbacbababcbacba
R = cbcbacabacbacbcbcacbacb
My motivation in posting this is that it is far easier for the computer to work with the presentation on the involutory generators rather than each generator being of order 4. Though perhaps not for humans!
» login or register to post comments

The cube

Submitted by gaetanguimond on Wed, 03/17/2010 - 06:58.
The heart of the cube is the 8 corners because it's number can not change. 2x2x2
Pure system http://pages.videotron.com/toulou/gaetan/

The cube popularity took a dive after hungary budapest championship of the world in 1982. The return in competition after 21 years was the world championship in toronto canada in 2003. Exactly had the same place at the science fair my web page photo that I placed on my web site that I took on the national championship of 1982.

The name of my domain rubikscuberecord.com and I'm the only one to have solved the cube blindfolded. If you don't believe in the one that has brought back the cube you will have to answer to the irreversables evidence. Contrary to it's return in 2003 in the store where the cube sales were influenced by the championship wich was not the case in 1982.

The cube is'nt musical (method & math) partition exchange only but it's has competitive.

The cube is a puzzle where the genius of the teenager's suffice to reach world records. I never said that it was not for children or adults because human curiosity has no age.

The emails that I kept in my reception box before 2003 from hotmail speak for themselves. Journalists outside the province of quebec never heard from me because the cuber's of my generation present on the web before 2003 never told my name with my story. People are sold by popular culture.

http://www.youtube.com/watch?v=iE1RH2S1fWQ
» login or register to post comments