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!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. Lucas Garron

    Lucas Garron Super-Duper 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?
     
  2. Stefan

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
  3. Johannes91

    Johannes91 Member

    1,341
    3
    Mar 28, 2006
    Non sequitur? Can you show that almost all of the 2^65 algs produce different positions?
     
  4. vcuber13

    vcuber13 Member

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

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    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. Stefan

    Stefan Member

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

    Lucas Garron Super-Duper Moderator Staff 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 Garron

    Lucas Garron Super-Duper Moderator Staff Member

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

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    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. Stefan

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
  11. Stefan

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    Last edited: Mar 10, 2010
  12. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    Oh, I did see it, thank you very much. :)
     
  13. cuBerBruce

    cuBerBruce Member

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

    meichenl Member

    32
    0
    Aug 27, 2009
    WCA:
    2009EICH01
    YouTube:
    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. rokicki

    rokicki Member

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

    rokicki Member

    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 Garron

    Lucas Garron Super-Duper Moderator Staff 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. cuBerBruce

    cuBerBruce Member

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

    rokicki Member

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

    Cielo Member

    35
    0
    Mar 22, 2009
    Beijing, China
    WCA:
    2008LUYU01
    Interesting! I've never thought about this before.
     

Share This Page