• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

The entire cube is 2-gen!

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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
Joined
Mar 28, 2006
Messages
1,341
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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).)
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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"
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
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
Joined
Oct 31, 2008
Messages
301
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
Joined
Oct 31, 2008
Messages
301
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?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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
Joined
Oct 31, 2008
Messages
301
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.)
 
Top