• 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!

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Here's another interesting (2,4) generator pair. This one extends the Fibonacci sequence out to level 41.

U2R3L3D2R1L1D1
R1L2F3B3U2R1

0 1
1 3
2 5
3 8
4 13
5 21
6 34
7 55
8 89
9 144
10 233
11 377
12 610
13 987
14 1597
15 2584
16 4181
17 6765
18 10946
19 17711
20 28657
21 46368
22 75025
23 121393
24 196418
25 317811
26 514229
27 832040
28 1346269
29 2178309
30 3524578
31 5702887
32 9227465
33 14930352
34 24157817
35 39088169
36 63245986
37 102334155
38 165580141
39 267914296
40 433494437
41 701408733
 

jaap

Member
Joined
Sep 22, 2009
Messages
32
Location
Netherlands
WCA
2003SCHE01
YouTube
Visit Channel
The six face turns answer???? That's trivial.

If it's oh so trivial, then why did you ask in the first place?

I wanted to know if something better is possible (fewer generators). Duh!

Per

What Tim said is a proof that fewer than 6 generators is not possible for the supergroup.

Let me explain it slightly more than Tim did. Consider the effect of your generators on just the face centres. In other words, take the cube apart, and only use the spider. Your generators generate the supergroup, and so must also generate all 4^6 possible positions of the centres alone. Each generator has at most order 4 when considered as acting only on the centres. The order you apply them also doesn't matter (they form an Abelian group). Therefore you can get at most 4^g positions with g generators, and so you need at least 6. This is why {U,D,R,L,F,B} is minimal.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Also, Tim even explicitly said "You need at least six generators" and "{U,D,F,B,R,L} is a minimal set" (*). I don't understand how that was not clear. And then Tom and Lucas even went through it again. Btw, I didn't see the solution myself and didn't think much about it, then I saw Tim's answer and thought "darn, of course!".

(*) ikmcmtnstwbidthpuiptnalswc
 
Last edited:

Tim Reynolds

Premium Member
Joined
Jun 28, 2006
Messages
995
Location
Boston, MA
WCA
2005REYN01
YouTube
Visit Channel
Hmm, I said there were only 4^6/2 center positions (that is, that's how many center positions there are for any given (non-super)cube position). I realize now that that /2 doesn't matter. But undercounting in that direction doesn't mess anything up--my proof still effectively works.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Generators of order 2 and 3?

Until Jaap posted his explanation, I don't think there was a clear proof of
exactly why six generators were minimal. The key is the effect on the
face centers is Abelian. It may have been clear to some of us, but I bet
not to all.

In any case, moving on to more interesting things---can anyone shed
light on why there is no pair of generators of orders 2 and 3 that
generate the cube? I've been puzzling over this, and not figured it out,
but perhaps it is pretty obvious to someone else out there.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I don't know, but I can prove something about any such generators (if they exist, which I guess they don't) by considering corner permutation. A generator of order 3 must either be one 3-cycle or two 3-cycles; a generator of order 2 must be some number of 2-cycles. The goal is to generate all possible corner permutations. We can't do this if the order-3 generator has just one corner 3-cycle because then the orbit of a piece in that cycle can be at most 6 corners (and it should be 8). So the order-3 generator would have to be two corner 3-cycles (ignoring orientation).

Maybe this will lead to a direct proof by contradiction?
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
orders 2 and 3 cannot generate S_8

I think you're right. I've found a paper by Miller from 1901 that says
generators of orders 2 and 3 cannot generate S_8 so I think that
covers it. I haven't read the Miller paper close enough to finish
it off, but I think you're on the right track.

The 3-generator clearly has to be a pair of three cycles, so we
can call it (1,2,3)(4,5,6) without loss of generalization. The
2-generator must be odd (if it were even, we could only generate
even perms). If the 2-generator was only (a,b), then at least
one piece could not have a full orbit. It can't be (a,b)(c,d)(7,8)
because then the 7 wouldn't have a full orbit. So it must be
(a,b)(c,7)(e,8). The a must be from 1..3 and the c must be
from 4..6, else you couldn't move pieces between these orbits,
so call it (1,4)(c,7)(e,8). There's only a few possibilities left. Who
can finish this off without enumerating them explicitly?
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
So it must be
(a,b)(c,7)(e,8). The a must be from 1..3 and the b must be
from 4..6, else you couldn't move pieces between these orbits,
so call it (1,4)(c,7)(e,8). There's only a few possibilities left. Who
can finish this off without enumerating them explicitly?

Hm, well, c and e cannot be 1, 4, 7, 8, so they are in {2, 3, 5, 6}; and since the positions of 7 and 8 can be swapped WLOG we can assume that c < e. So that leaves just 6 possibilities.

Considering that our other cycle is (1,2,3)(4,5,6) we notice that if (c,e) = (2,5) or (3,6) then the pair (1,4) remains "across" from each other no matter what. We can exchange their positions and/or place them into (7,8) but it is not possible to place them in the same 3-cycle.

I'm not sure about proving the other four cases, but I'm sure GAP will happily tell you that the order of the generated group is less than 8!.
 

mrCage

Member
Joined
Jun 17, 2006
Messages
655
The six face turns answer???? That's trivial.

If it's oh so trivial, then why did you ask in the first place?

I wanted to know if something better is possible (fewer generators). Duh!

Per

What Tim said is a proof that fewer than 6 generators is not possible for the supergroup.

Let me explain it slightly more than Tim did. Consider the effect of your generators on just the face centres. In other words, take the cube apart, and only use the spider. Your generators generate the supergroup, and so must also generate all 4^6 possible positions of the centres alone. Each generator has at most order 4 when considered as acting only on the centres. The order you apply them also doesn't matter (they form an Abelian group). Therefore you can get at most 4^g positions with g generators, and so you need at least 6. This is why {U,D,R,L,F,B} is minimal.

That's more clear. Now it seems obvious. A bit sad though that we really need so many "proper" generators for the cube supergroup:rolleyes:

Per
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Earlier in this thread, I mentioned a generator pair that generates the group consisting of all supercube positions in all 24 orientations of the cube. This pair I believed to minimal if you only use single-layer and double-layer turns to compose the generators. This pair was <Uw, LUwRw>.

If you allow the use of whole cube rotations, then the above pair is not minimal. I have found that <x, Uz> is sufficient to generate this group.

It is easy to see that this indeed generates the whole group. It suffices to find sequences in <x, Uz> that are equivalent to U, x, and y. This is straightforward.

x = x
y = (Uz) x (Uz)'
U = (Uz) z' = (Uz) yxy' = (Uz)2 x (Uz)' x (Uz) x' (Uz)'
 
Top