# The entire cube is 2-gen!

Discussion in 'Puzzle Theory' started by Lucas Garron, Mar 10, 2010.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

1. ### Lucas GarronSuper-Duper ModeratorStaff 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?

2. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
3. ### Johannes91Member

Mar 28, 2006
Non sequitur? Can you show that almost all of the 2^65 algs produce different positions?

4. ### vcuber13Member

Oct 14, 2009
Near Toronto
WCA:
2009METH01
simpsons36109
are you guys saying that and cube can be solved using 2 gen algs and cube rotations?

5. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
Cube rotations?!? Noob. No cube rotations. Just the two algs.

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: Mar 10, 2010
6. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
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: Mar 10, 2010
7. ### Lucas GarronSuper-Duper ModeratorStaff Member

I suppose I never thought about it. And realized it had never been discussed here.

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

8. ### Lucas GarronSuper-Duper ModeratorStaff Member

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

9. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
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"

10. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
11. ### StefanMember

7,287
12
May 7, 2006
WCA:
2003POCH01
StefanPochmann
Last edited: Mar 10, 2010
12. ### Lucas GarronSuper-Duper ModeratorStaff Member

Oh, I did see it, thank you very much.

13. ### cuBerBruceMember

912
4
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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.

14. ### meichenlMember

32
0
Aug 27, 2009
WCA:
2009EICH01
meichenl
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?

15. ### rokickiMember

254
3
Oct 31, 2008
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).

16. ### rokickiMember

254
3
Oct 31, 2008
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?

17. ### Lucas GarronSuper-Duper ModeratorStaff Member

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.

18. ### cuBerBruceMember

912
4
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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 := 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

19. ### rokickiMember

254
3
Oct 31, 2008
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.)

20. ### CieloMember

35
0
Mar 22, 2009
Beijing, China
WCA:
2008LUYU01