# UF and RBL generate the whole cube group

It's surprising to me that these two very simple generators suffice.

It's easy to see no shorter set of generators (expressed in face turns) suffice because you need at least five faces.

## Comment viewing options

### If you already had computed t

### Au contraire I'd be surprised

In your example above I think you must know that this behaviour can't continue indefinitely. Once the other relations have kicked in, e.g. Comm(a,b)^42 = [a,b]^42 = (a^-1*b^-1*a*b)^42 = 1, the count of positions will start to tail off and follow the normal behaviour of a Cayley graph.

BTW why are use using the notation F3 when you should be using F' (of length one)?

### Nice - thanks

{U,F,R} occur in a cycle and {D,B,L} occur in a cycle?

e.g. taking the first of these from your an example we would have

F^2R'L'FRL, R^2U'D'RUD and U^2F'B'UFB

These only generate an order 2592 group however.

Failing that what's the maximum order you can find using this

strategy? I found one of order 14696640

taking (U^2FU^2R^2)^5, (F^2RF^2U^2)^5 and (R^2UR^2F^2)^5.

Obviously I know that these 3 generators won't suffice as a

2x2x2 block remains untouched - was just using this as an example.

### Not surprising

In addition, I do think this is the first time anyone has listed generators of orders 2 and 4 for the cube group.

So I'm not sure I understand the "Au contraire".

I do know this doesn't continue indefinitely. I'm currently looking for other generators that push it a little further (I've gotten it out to level 41 with one pair).

I don't like using the F' notation in my programs because it's not shell friendly nor is it typographically friendly; I tend to always use [UFRDBL][123]. It's pretty clear what is meant. For formal publication I'll use the standard notation.

### Sorry if I came across as rud

Have you seen the posting by Jaap below in this thread dated 03-APR-2010? This example is extracted from Singmaster's notes from 1982 so no it's not the first time. I have to say I'm not very familiar with this particular bracket notation though so I can't say what Conder's g (or g') and h are expressed in terms of just R,L,F,B,U,R without the brackets.

It would be interesting to compare the Cayley graph of your generators of orders 2 and 4 versus those two of Conder's.

### I'm pretty sure the notation

I'm pretty sure the notation in that post is simply cycle notation, with edge pieces denoted by 2 letters, and corner pieces denoted by 3 letters.

### A Note in Proof

Challenged by your assertion, I've been playing around trying to see if I could derive the standard cube face turns from your two generators. My initial attempt to derive a U face turn directly from the generators with an IDA search failed after an all day run. I decided that deriving all the face turns directly would not be any fun and set out to build up the set of generators. After a few hours of CPU time I found:

Generators: a = R B L b = U F Symmetries: x, y, z E c = R B = b a' b' a b a' b' a' b' a b a' b'5 a3 b a b a b a b a3 b2 a' b' a b2 a

After adding this state to the generator set the face turn set was found in under a minute:

Generators: a = R B L b = U F c = R B Symmetries: x, y, z E R = b' a c' b c b' a' c b2 a'3 c a2 b' U = a' c2 b' a' c a' c b c' b' a c' a c'2 a b c' a F = a' c b' a' c a c' a c' b c b' a' c a' c b c'2 a b L = c' a D = b' c a' c b c' b c'2 a2 b c' b' a' c2 b'2 a c' b B = b a'2 c' a3 b'2 c' a b c' b' c a' b c

### Wow

I've managed to find "optimal" solutions in a and b to all the face turns (except I've chosen a=UF and b=RBL):

U=a'a'a'b'b'ab'a'a'a'bbaabba'b'a'bba'a'a'baaaaaaba'bab'ab'a'a'

F=aaba'ba'b'ab'a'a'a'a'a'a'b'aaab'b'abab'b'a'a'b'b'aaaba'bbaaaa

R=b'a'babba'b'a'b'a'a'ba'b'a'a'bab'abab'a'a'b'abbbbabababab

D=a'a'baaab'b'aba'a'bab'b'abbbab'a'b'aab'b'a'baaaab'b'aabb

B=b'a'ba'a'a'a'bab'a'a'b'b'a'b'aaba'a'bba'bbaaaaba'ba'bba'b'

L=b'a'a'b'aba'a'b'b'b'a'b'a'b'a'b'a'b'b'b'aaaaaba'b'ababa'b'aba'b

These are shortest solutions. The lengths are 40, 41, 40, 40,

38, and 39 respectively.

### Generator Sets

How did I know that adding R B would give short solutions? The answer to that was that I didn't. I first set out to develop a set of generators with some symmetry which could be used to multiply the effectiveness of the pruning table. I arrived at the set:

Initializing Solver Generators: a = R B L b = L B R c = U F D d = D F U Symmetries: x, y, z E -x,-y, z C2_4 y, x,-z C2 -y,-x,-z C2 y,-x,-z S4 -y, x,-z S4 x,-y, z Sigma_h -x, y, z Sigma_h

With D_{2d} symmetry to work with I then was able to find routes to the U and F face turns which with the above symmetry gives the complete set. Still playing around, I added back the original U F generator which distroyed the symmetry but gave more accessible solutions. I worked back from there to arrive at the three generator set.

I am impressed that you were able find routes to the face turns directly from the two generators. A day of CPU time only gets me out to depth 39. To find a depth 41 solution would take me well over a week.

### 8GB

I may try some additional generator pairs. In particular, if one of the generators is order 2, the distance for random positions has got to be insanely long.

### I can confirm your depth 38

I can confirm your depth 38 solution for the B turn( it only took 6hr 17min + 3 min to generate the pruning table).

If one of the generators is self inverse you're down to three generators counting the inverses. Assuming there are no more simple identities this give a branching factor of two. From this one may estimate:

log( 4.325 x 10^{19} ) / log(2) = 65.2

So one would have to approach depth 65 before a significant fraction of the total number of states are examined. The maximum for the distribution would then be a depth or two beyond this.

### More "nice" unusual generators

I notice for example that g = U^2D^2 and h = URFUBR^2

also generate the whole cube group.

Question: Can this be improved upon?

i.e. Are there g and h which generate the whole cube group

with |g| = 2 and |h| < 8?

I would think the answer is probably yes. It would be to have an example. Could |h| be equal to 3 for example? I don't think it could be generated by two involutions though haven't done the analysis.

### Challenge

I wasn't able to but I would strongly wager that it is possible to do so.

### Three more

Two of these commute, so this should also generate the Fibonacci sequence in counts of positions at a given distance.

u2

d2

f*u*r2*u3*d3*r*l2*d*u

### Face turns for (2,6) generators

b=F1U2R2U1F1

a=R1U2D2R1L2

U=bab'ab'abab'abbbabababab'b'ab'ababbabab'abab'b'abbababbab'b'ababab'b'ababab'ab'b'ab'b'ab'abb (73*)

F=b'b'ababbabbababbabbabbbab'b'abab'ab'abbbab'ab'b'ab'b'abab'ab'ab'ababab'ab'b'abababab'ab'b' (71*)

R=babbbab'abab'b'abbbab'ab'b'abbabbabbab'ab'ab'abbbab'b'ababbbabab'b'ababab'b'ab'ab'ab'b'ab'ab (72*)

D=bab'ab'ab'b'abbab'abbabbab'b'ab'ababbab'abab'ababbbabbab'ab'ab'ababbbab'b'abbbab'b'ab'ab'a (71*)

B=abab'abbab'ab'ab'ab'b'ab'b'abbbab'b'ab'abbabbabab'abbab'b'ab'ab'ab'b'abbabab'ab'b'abab'abbab'ab (72*)

L=bbbabababbab'b'ab'abbabbab'b'ab'abab'ab'ab'ab'abbbab'ab'ab'b'ab'b'ababbab'ababbababbab'b'a (71*)

### Longer solutions

the face turns (pretty obvious with an order-2 generator).

This is what I get.

h=U1R1F1U1B1R2

g=U2D2

U=hhgh'gh'h'h'gh'gh'gh'h'h'ghgh'h'gh'gh'ghhhghghgh'h'gh'h'h'gh'h'h'gh'h'ghgh'ghhgh'gh'ghgh'gh'ghghhg (70*)

F=gh'h'gh'gh'h'ghgh'gh'ghghgh'h'gh'ghghghghghhghhhhgh'ghhhgh'h'gh'gh'gh'gh'ghhhgh'h'gh'g (66*)

R=h'h'gh'h'ghghgh'gh'ghgh'gh'ghghghhghghhgh'h'gh'ghhghhhgh'h'gh'ghhghhhhghhhhghghg (66*)

D=h'h'h'ghhhgh'gh'ghghghghhhhghhghhhghghhghhhghhhghhgh'h'h'gh'gh'ghhgh'h'ghhghgh'gh (68*)

B=ghhhhghghhhhgh'h'gh'h'ghhhghghhhghhhghhgh'h'h'ghgh'h'ghghhhgh'ghgh'h'h'ghhghgh'gh (67*)

L=ghhhgh'ghhhgh'h'ghgh'h'ghhhhgh'gh'ghghgh'h'gh'ghhhgh'gh'h'gh'gh'gh'h'ghhhhghhghghghgh' (68*)

### From Singmaster's Notes

"Frank Barnes has shown that the group of the cube is generated by just two elements. Marston D. E. Conder has shown that it can be generated by two elements, g, h, of orders 2 and 4 and that orders 2 and 3 will not suffice. It is well known that two elements of order 2 can only generate the symmetries of an n-gon, where n is the order of gh. (When n = 1 or 2 the n-gon is a bit degenerate.) Elements of order 3 and 3 can only generate even permutations on corners and on edges, hence cannot generate the whole group. It is not clear if Conder's generators also generate the supergroup."

"Explicitly, Condor shows that the following serve:

g = (UR,RB)(DR,UB)(FR,FL)(UL,LB) (RFU,RUB)(DFR,DBL)(UFL,BUL)

h = (UR,BR,DR,FR)(UF,UB,DF,DB)(UL,FL,DL,BL) (RFU,DFR,LFD,UFL)(RUB,BDR)(DBL,ULB)"

"In a revised version of his note, he uses

g' = (FL,LB)(BR,FR)(DL,UB)(DR,UF)(DF,DB) (RFU,RUB)(DFR,DBL)(UFL,BUL)

and he shows that g'h has the maximal order of 1260."

Jaap

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

### Depends on your definition of simplicity

However I wouldn't have said these two generators are "simple". The orders of UF and RBL are 105 and 90 respectively. A more compact example (wrt to the face metric) is U^2F and DRB^2 for example (of orders 30 and 9)

Regarding 2 generators using the QTM - why not take UD and RBL instead?

### you mean his book adventures

what example does he cite there ?

how are these actually computed(I'm curious)

thanks

### Yes, I'm sure Adeventures in

*Adeventures in Group Theory*is what he is referring to. In the copy of the book I have, it's on page 167 (Section 10.3, Presentations and Plutonian robots). He attributes the generators to someone named F. Barnes. They are U B L U L' U' B' and R2 F L D' R'.

Basically, to prove a set of generators generate the whole group, it is sufficient to show that they can be used to generate each one of some other set of generators, such as { U, D, L, R, F }. Or you can simply use GAP to find out if a set of generators generate the whole cube group.

For example, (U B L U L' U' B')^6 flips two edges. Then you can find sequences (of these two generators) to move two other edges to these positions to come up with a conjugation that flips two different edges. Then you could find enough such two-flips to show that you can solve any edge orientation situation. Apply the same idea to corner orientation and to permuting the pieces and you should eventually be able find suitable sequences for { U, D, L, R, F } or whatever known set of cube generators you're trying to find sequences for. Generally GAP can also be used to find such sequences.

## Orders 2 and 4

a=U2F1B1D2F3B3D1

b=F1B2R1L1U2F1

These are the smallest orders possible that generate the whole cube.

The count of positions at levels 1, 2, ... goes 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711 ... which I suspect many of you will recognize as the Fibonacci sequence.