# The entire cube is 2-gen!

#### Lucas Garron

##### Moderator
Staff member
By which we mean the cube group can be generated by 2 elements:

G = <g1, g2> = <U B L U L' U' B', R2 F L D' R'>

So, any position of the cube can be written as something like $$g1 g2^2 g1^{-1} g2^3$$, except longer.

Apparently this was known in 1980. Joyner cites this set by "F. Barnes" in a book by Bandelow (which I have yet to see).

I believe this, but I'd like to see a proof by generating each of {B, F, U, D, L, R} as an "alg" in <g1, g2>. (Or at least 5 of them.)

ksolve can't quite handle this. Since 4.3*10^19 is about 65 binary digits, we'd expect the length of an alg for a position (like the regular generators) to have a length of about 65, ~32 if we allow inverses.

Does anyone know a nice (algorithmic?) way to generate {B, F, U, D, L, R} using <g1, g2>, or come up with some other nice set of two generators for which we can do this?

#### Johannes91

##### Member
Since 4.3*10^19 is about 65 binary digits, we'd expect the length of an alg for a position (like the regular generators) to have a length of about 65, ~32 if we allow inverses.
Non sequitur? Can you show that almost all of the 2^65 algs produce different positions?

#### Stefan

##### Member
are you guys saying that and cube can be solved using 2 gen algs and cube rotations?
Cube rotations?!? Noob. No cube rotations. Just the two algs.

I'll try to find another discussion we had about it in the yahoo group...
I misremembered a bit, this is what I meant:

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13973?l=1

Begin at "Hmm, do you remember that the cube group can be generated by just two different algorithms?". It was my attempt to explain how to use two certain algs to generate all positions, embedded in a devil's algorithm thread. But they were different algs, not those that Lucas posted above.

Last edited:

#### Stefan

##### Member
Apparently this was known in 1980. Joyner cites this set by "F. Barnes" in a book by Bandelow (which I have yet to see).
I have Bandelow's book (in German). Does Joyner tell the page number or chapter or so?

Edit: Found it, will take a picture. Not sure how much it's explained, though (relies on previous stuff that I haven't checked yet).

Last edited:

#### Lucas Garron

##### Moderator
Staff member
I suppose I never thought about it. And realized it had never been discussed here.

Since 4.3*10^19 is about 65 binary digits, we'd expect the length of an alg for a position (like the regular generators) to have a length of about 65, ~32 if we allow inverses.
Non sequitur? Can you show that almost all of the 2^65 algs produce different positions?
I was just stating a lightly informed estimate of the depth of a needed search (e.g. why I wasn't expecting ksolve to get it). And no, I can't. But that would only make things a bit worse.

(However, note that the God's number for 3x3x3 is on the order of the log(18, 4.3*10^19).)

#### Lucas Garron

##### Moderator
Staff member
Hmm, how hard would it be to find optimal <g1, g2> solutions to the 6 face turns?

#### Stefan

##### Member
But they were different algs, not those that Lucas posted above.
Not much off, though. The R2 F L D' R' alg Lucas posted is indeed an 11-cycle of edges and a 7-cycle of corners. But the U B L U L' U' B' has a bigger effect than just swapping two edges and two corners.

Apparently from Singmaster, quoted here:

"Frank Barnes observes that the group of the cube is generated by two
moves:
alpha = L2BRD-1L-1
beta = UFRUR-1U-1F-1
Observe that alpha^7 is an 11-cycle of edges and alpha^11 is a 7-cycle
of corners"

#### Stefan

##### Member
I suppose I never thought about it. And realized it had never been discussed here.
Not sure you saw it (cause you didn't comment on it): That post tells how to generate each of {B, F, U, D, L, R}.

Last edited:

#### Lucas Garron

##### Moderator
Staff member
I suppose I never thought about it. And realized it had never been discussed here.
Not sure you saw it (cause you didn't comment on it): That post tells how to generate each of {B, F, U, D, L, R}.
Oh, I did see it, thank you very much.

#### cuBerBruce

##### Member
I note that Joyner's book also mentions this Cube Lovers post where it is mentioned that if you pick two elements of the group at random, you seem to have a roughly 50% chance that they will generate the whole group. So such pairs are actually very common.

#### meichenl

##### Member
I had been wondering about the minimum number of generators. Thanks for the discussion.

The claim that roughly half of pairs of algorithms generate the cube is intriguing. Is there an easy way to tell whether two elements of the cube group will generate the cube?

#### rokicki

##### Member
Random generators

I'm also keenly interested in this.

Clearly both generators can't be even. So that accounts for 25% of the 50%.

Is there something equally obvious for the other 25%?

Or is the 50% only an approximate answer, and the real answer might be something like 53.1% or some such?

Another unanswered question that has been posed is, what is the shortest pair of generators that generate the cube? (Use HTM).

#### rokicki

##### Member
Wow. If my analysis is correct, then (for instance) just UF and RBL are sufficient to generate the entire group.

Indeed, just restricting yourself to the six generators UFRDBL, there are 720 different ways to select two generators for the first and three for the second such that all five selected are unique (this is an obvious requirement). Of those 720 ways, 96 generate the full cube group.

Can anyone confirm this?

#### Lucas Garron

##### Moderator
Staff member
Wow. If my analysis is correct, then (for instance) just UF and RBL are sufficient to generate the entire group.
Wow.
Any way you can extend your code to "prove" its results by generating {B, F, U, D, L, R}? That would be enough to confirm.

#### cuBerBruce

##### Member
Wow. If my analysis is correct, then (for instance) just UF and RBL are sufficient to generate the entire group.

Indeed, just restricting yourself to the six generators UFRDBL, there are 720 different ways to select two generators for the first and three for the second such that all five selected are unique (this is an obvious requirement). Of those 720 ways, 96 generate the full cube group.

Can anyone confirm this?
I confirm.

I note that it is easy to test if a set of generators generates the whole cube group with GAP.

Code:
gap> U := ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19);
(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)
gap> L := ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35);
(1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12)
gap> F := (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11);
(6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20)
gap> R := (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24);
(3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28)
gap> B := (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27);
(1,14,48,27)(2,12,47,29)(3,9,46,32)(33,35,40,38)(34,37,39,36)
gap> D := (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40);
(14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44)
gap> G := Group (U,D,L,R,B,F);
<permutation group with 6 generators>
gap> gens := [ U, D, L, R, F, B ];
[ (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19),
(14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44),
(1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12),
(3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28),
(6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20),
(1,14,48,27)(2,12,47,29)(3,9,46,32)(33,35,40,38)(34,37,39,36) ]
gap>
gap> PermNUnpackA := function (n, idx)
>   local i, j, nn, lst;
>   nn := n;
>   i := 1;
>   lst := [ ];
>   while i <= n do;
>     lst[i] := 0;
>     i := i + 1;
>   od;
>   i := nn - 1;
>   while i >= 0 do;
>     lst[i + 1] := idx mod (nn - i);
>     idx := (idx - lst[i + 1]) / (nn - i);
>     j := i + 1;
>     while j < nn do;
>       if lst[j + 1] >= lst[i + 1] then
>         lst[j + 1] := lst[j + 1] + 1;
>       fi;
>       j := j + 1;
>     od;
>     i := i - 1;
>   od;
>   return lst;
> end;
function( n, idx ) ... end
gap>
gap> TryAll720 := function (Lm)
>   local i, z, H, g1, g2, count, Lx;
>   count := 0;
>   i := 0;
>   while i < 720 do
>     Lx := PermNUnpackA (6, i);
>     g1 := Lm[Lx[1]+1]*Lm[Lx[2]+1];
>     g2 := Lm[Lx[3]+1]*Lm[Lx[4]+1]*Lm[Lx[5]+1];
>     H := Group (g1, g2);
>     if H = G then
>       count := count + 1;
>     fi;
>     i := i + 1;
>   od;
>   return count;
> end;
function( Lm ) ... end
gap>
gap> TryAll720 (gens);
96

#### rokicki

##### Member
Thanks for the confirmation! (I also used GAP but feared I might
have made a typo or error.)

The sequences U, R2D2BL also work, as do the sequences U, D'LRF.
(You need at least one half turn or counter clockwise turn if you want
to use sequences of length 1 and 4 in the QTM.)