# 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 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?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.

## Comment viewing options

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

### 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.

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.

### 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/

### 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...

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

### 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.

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.

### 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 | aThis 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}= b^{2}= c^{2}= 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 >

(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

### 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 acacbcbabcabcabcababacacabcbaHere 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 24Curiously 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 = cbcbacabacbacbcbcacbacbMy 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!

### 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

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

## I used GAP to find the size o