# UF and RBL generate the whole cube group

The two simple generators UF and RBL (without any rotations) 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

### Orders 2 and 4

I've found a pair of generators of order 2 and 4 that generate the whole cube.

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.

If you already had computed the values of R,L,F,B,U,D w.r.t. these values of a and b I'd be grateful if you could post here. I juts wanted to get an idea of how long these might be (about 80 or 90?).

### Au contraire I'd be surprised

Au contraire I'd be surprised if this behaviour did not happen. The group with two generators (one of order 2 and the other of order 4) without any additional relations specified is automatic and infinite. I'm sure a combinatorics expert would be able to confirm that the number of reduced words of a particular length does indeed follow the Fibonacci sequence.

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)?

### Set of 3, order-2 generators

Here's a set of 3 order-2 generators:

f2r3l3f1r1l1 u1f2b2u1d2 r3f2b2r1

### Nice - thanks

How about 3 involutory (i.e. order 2) generators such that
{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

I didn't say it was surprising; I just think it's cute. Sure, it's obvious to anyone who has done the math, but then so is any provable theorem. No need to be a combinatorics export; it's pretty simple group theory.

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]. It's pretty clear what is meant. For formal publication I'll use the standard notation.

### Sorry if I came across as rud

Sorry if I came across as rude - that was not my intention.
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

Pretty impressive; how did you know adding "c" would end up giving you such short solutions?

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

Heh, I "cheated". I used an 8GB pruning table (that took 5 hours to generate). With this, the six solutions popped out of the program in about an hour (and of course I can now optimally solve any position with these generators).

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 1019 ) / 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.

### More generators of small orders

I found the following pairs of generators that generate the whole cube group, and have short orders:

a=RU2D2RL2 |a|=2
b=UFR2F2U |b|=6

c=UF3B3DRL |c|=3
d=ULUD2L3L3 |d|=4

### Challenge

Are you able to find six generators all of order 2 which generate the whole 3x3x3 group expressed as combinations of {R, L, F, B, U, D}?
I wasn't able to but I would strongly wager that it is possible to do so.

### Three more

Here are three more generators of order 2 that generate the cube.

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

### I can do it in 4

Here are the four:

d*r*l*d2*r3*l3
f2*b2*r2*l2
f2*r3*l3*f*r*l
l*d2*r3*l3*d*r

I would think this could be reduced to 3.

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

This is a different set of (2,6) generators than I gave before.

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

Wow, these two generators require much longer solutions for
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

In Singmaster's "Notes on Rubik's Magic Cube", 5th Edition, p49, he says:
"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

Certainly this example of a 2-generator set is a lot more straightforward than the one cited in David Joyner's book!

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

you mean his book adventures in group theory ?
what example does he cite there ?
how are these actually computed(I'm curious)

thanks

### Yes, I'm sure Adeventures in

Yes, I'm sure 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.