Home »

UF and RBL generate the whole cube group

Submitted by rokicki on Sat, 03/20/2010 - 13:43.
The two simple generators UF and RBL (without any rotations) generate the whole cube group.

It's surprising to me that these two very simple generators suffice.

It's easy to see no shorter set of generators (expressed in face turns) suffice because you need at least five faces.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Orders 2 and 4

Submitted by rokicki on Tue, 04/13/2010 - 11:03.
I've found a pair of generators of order 2 and 4 that generate the whole cube.

a=U2F1B1D2F3B3D1
b=F1B2R1L1U2F1

These are the smallest orders possible that generate the whole cube.

The count of positions at levels 1, 2, ... goes 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711 ... which I suspect many of you will recognize as the Fibonacci sequence.
» login or register to post comments

If you already had computed t

Submitted by secondmouse on Sun, 04/18/2010 - 09:02.
If you already had computed the values of R,L,F,B,U,D w.r.t. these values of a and b I'd be grateful if you could post here. I juts wanted to get an idea of how long these might be (about 80 or 90?).
» login or register to post comments

Au contraire I'd be surprised

Submitted by secondmouse on Fri, 04/16/2010 - 08:44.
Au contraire I'd be surprised if this behaviour did not happen. The group with two generators (one of order 2 and the other of order 4) without any additional relations specified is automatic and infinite. I'm sure a combinatorics expert would be able to confirm that the number of reduced words of a particular length does indeed follow the Fibonacci sequence.

In your example above I think you must know that this behaviour can't continue indefinitely. Once the other relations have kicked in, e.g. Comm(a,b)^42 = [a,b]^42 = (a^-1*b^-1*a*b)^42 = 1, the count of positions will start to tail off and follow the normal behaviour of a Cayley graph.

BTW why are use using the notation F3 when you should be using F' (of length one)?
» login or register to post comments

Set of 3, order-2 generators

Submitted by rokicki on Fri, 04/16/2010 - 23:29.
Here's a set of 3 order-2 generators:

f2r3l3f1r1l1 u1f2b2u1d2 r3f2b2r1
» login or register to post comments

Nice - thanks

Submitted by secondmouse on Sat, 04/17/2010 - 14:25.
How about 3 involutory (i.e. order 2) generators such that
{U,F,R} occur in a cycle and {D,B,L} occur in a cycle?
e.g. taking the first of these from your an example we would have
F^2R'L'FRL, R^2U'D'RUD and U^2F'B'UFB
These only generate an order 2592 group however.

Failing that what's the maximum order you can find using this
strategy? I found one of order 14696640
taking (U^2FU^2R^2)^5, (F^2RF^2U^2)^5 and (R^2UR^2F^2)^5.
Obviously I know that these 3 generators won't suffice as a
2x2x2 block remains untouched - was just using this as an example.
» login or register to post comments

Not surprising

Submitted by rokicki on Fri, 04/16/2010 - 21:52.
I didn't say it was surprising; I just think it's cute. Sure, it's obvious to anyone who has done the math, but then so is any provable theorem. No need to be a combinatorics export; it's pretty simple group theory.

In addition, I do think this is the first time anyone has listed generators of orders 2 and 4 for the cube group.

So I'm not sure I understand the "Au contraire".

I do know this doesn't continue indefinitely. I'm currently looking for other generators that push it a little further (I've gotten it out to level 41 with one pair).

I don't like using the F' notation in my programs because it's not shell friendly nor is it typographically friendly; I tend to always use [UFRDBL][123]. It's pretty clear what is meant. For formal publication I'll use the standard notation.
» login or register to post comments

Sorry if I came across as rud

Submitted by secondmouse on Sat, 04/17/2010 - 10:40.
Sorry if I came across as rude - that was not my intention.
Have you seen the posting by Jaap below in this thread dated 03-APR-2010? This example is extracted from Singmaster's notes from 1982 so no it's not the first time. I have to say I'm not very familiar with this particular bracket notation though so I can't say what Conder's g (or g') and h are expressed in terms of just R,L,F,B,U,R without the brackets.

It would be interesting to compare the Cayley graph of your generators of orders 2 and 4 versus those two of Conder's.
» login or register to post comments

I'm pretty sure the notation

Submitted by Bruce Norskog on Sat, 04/17/2010 - 22:37.

I'm pretty sure the notation in that post is simply cycle notation, with edge pieces denoted by 2 letters, and corner pieces denoted by 3 letters.

» login or register to post comments

A Note in Proof

Submitted by B MacKenzie on Tue, 03/30/2010 - 12:40.

Challenged by your assertion, I've been playing around trying to see if I could derive the standard cube face turns from your two generators. My initial attempt to derive a U face turn directly from the generators with an IDA search failed after an all day run. I decided that deriving all the face turns directly would not be any fun and set out to build up the set of generators. After a few hours of CPU time I found: 

 Generators:
	a = R B L
	b = U F
 Symmetries:
	 x, y, z  E

	c = R B	  = b a' b' a b a' b' a' b' a b a' b'5 a3 b a b a b a b a3 b2 a' b' a b2 a

After adding this state to the generator set the face turn set was found in under a minute: 

 Generators:
	a = R B L
	b = U F
	c = R B
 Symmetries:
	 x, y, z  E

	R = b' a c' b c b' a' c b2 a'3 c a2 b'
	U = a' c2 b' a' c a' c b c' b' a c' a c'2 a b c' a
	F = a' c b' a' c a c' a c' b c b' a' c a' c b c'2 a b
	L = c' a
	D = b' c a' c b c' b c'2 a2 b c' b' a' c2 b'2 a c' b
	B = b a'2 c' a3 b'2 c' a b c' b' c a' b c
» login or register to post comments

Wow

Submitted by rokicki on Sat, 04/10/2010 - 20:41.
Pretty impressive; how did you know adding "c" would end up giving you such short solutions?

I've managed to find "optimal" solutions in a and b to all the face turns (except I've chosen a=UF and b=RBL):

U=a'a'a'b'b'ab'a'a'a'bbaabba'b'a'bba'a'a'baaaaaaba'bab'ab'a'a'
F=aaba'ba'b'ab'a'a'a'a'a'a'b'aaab'b'abab'b'a'a'b'b'aaaba'bbaaaa
R=b'a'babba'b'a'b'a'a'ba'b'a'a'bab'abab'a'a'b'abbbbabababab
D=a'a'baaab'b'aba'a'bab'b'abbbab'a'b'aab'b'a'baaaab'b'aabb
B=b'a'ba'a'a'a'bab'a'a'b'b'a'b'aaba'a'bba'bbaaaaba'ba'bba'b'
L=b'a'a'b'aba'a'b'b'b'a'b'a'b'a'b'a'b'b'b'aaaaaba'b'ababa'b'aba'b

These are shortest solutions. The lengths are 40, 41, 40, 40,
38, and 39 respectively.
» login or register to post comments

Generator Sets

Submitted by B MacKenzie on Sun, 04/11/2010 - 08:42.

How did I know that adding R B would give short solutions? The answer to that was that I didn't. I first set out to develop a set of generators with some symmetry which could be used to multiply the effectiveness of the pruning table. I arrived at the set: 

Initializing Solver
 Generators:
	a = R B L
	b = L B R
	c = U F D
	d = D F U
 Symmetries:
	 x, y, z  E
	-x,-y, z  C2_4
	 y, x,-z  C2
	-y,-x,-z  C2
	 y,-x,-z  S4
	-y, x,-z  S4
	 x,-y, z  Sigma_h
	-x, y, z  Sigma_h

With D2d symmetry to work with I then was able to find routes to the U and F face turns which with the above symmetry gives the complete set. Still playing around, I added back the original U F generator which distroyed the symmetry but gave more accessible solutions. I worked back from there to arrive at the three generator set.

I am impressed that you were able find routes to the face turns directly from the two generators. A day of CPU time only gets me out to depth 39. To find a depth 41 solution would take me well over a week.

» login or register to post comments

8GB

Submitted by rokicki on Sun, 04/11/2010 - 10:27.
Heh, I "cheated". I used an 8GB pruning table (that took 5 hours to generate). With this, the six solutions popped out of the program in about an hour (and of course I can now optimally solve any position with these generators).

I may try some additional generator pairs. In particular, if one of the generators is order 2, the distance for random positions has got to be insanely long.
» login or register to post comments

I can confirm your depth 38

Submitted by B MacKenzie on Sun, 04/11/2010 - 17:00.

I can confirm your depth 38 solution for the B turn( it only took 6hr 17min + 3 min to generate the pruning table).

If one of the generators is self inverse you're down to three generators counting the inverses. Assuming there are no more simple identities this give a branching factor of two. From this one may estimate:

log( 4.325 x 1019 ) / log(2) = 65.2

So one would have to approach depth 65 before a significant fraction of the total number of states are examined. The maximum for the distribution would then be a depth or two beyond this.

» login or register to post comments

More "nice" unusual generators

Submitted by secondmouse on Mon, 03/22/2010 - 13:27.
Further to yesterday's comments:

I notice for example that g = U^2D^2 and h = URFUBR^2
also generate the whole cube group.

Question: Can this be improved upon?

i.e. Are there g and h which generate the whole cube group
with |g| = 2 and |h| < 8?
I would think the answer is probably yes. It would be to have an example. Could |h| be equal to 3 for example? I don't think it could be generated by two involutions though haven't done the analysis.
» login or register to post comments

More generators of small orders

Submitted by rokicki on Mon, 04/12/2010 - 21:39.
I found the following pairs of generators that generate the whole cube group, and have short orders:

a=RU2D2RL2 |a|=2
b=UFR2F2U |b|=6

c=UF3B3DRL |c|=3
d=ULUD2L3L3 |d|=4
» login or register to post comments

Challenge

Submitted by secondmouse on Fri, 04/16/2010 - 14:31.
Are you able to find six generators all of order 2 which generate the whole 3x3x3 group expressed as combinations of {R, L, F, B, U, D}?
I wasn't able to but I would strongly wager that it is possible to do so.
» login or register to post comments

Three more

Submitted by rokicki on Sat, 04/17/2010 - 12:05.
Here are three more generators of order 2 that generate the cube.

Two of these commute, so this should also generate the Fibonacci sequence in counts of positions at a given distance.

u2
d2
f*u*r2*u3*d3*r*l2*d*u
» login or register to post comments

I can do it in 4

Submitted by rokicki on Fri, 04/16/2010 - 22:10.
Here are the four:

d*r*l*d2*r3*l3
f2*b2*r2*l2
f2*r3*l3*f*r*l
l*d2*r3*l3*d*r

I would think this could be reduced to 3.
» login or register to post comments

Face turns for (2,6) generators

Submitted by rokicki on Mon, 04/12/2010 - 23:36.
This is a different set of (2,6) generators than I gave before.

b=F1U2R2U1F1
a=R1U2D2R1L2

U=bab'ab'abab'abbbabababab'b'ab'ababbabab'abab'b'abbababbab'b'ababab'b'ababab'ab'b'ab'b'ab'abb (73*)
F=b'b'ababbabbababbabbabbbab'b'abab'ab'abbbab'ab'b'ab'b'abab'ab'ab'ababab'ab'b'abababab'ab'b' (71*)
R=babbbab'abab'b'abbbab'ab'b'abbabbabbab'ab'ab'abbbab'b'ababbbabab'b'ababab'b'ab'ab'ab'b'ab'ab (72*)
D=bab'ab'ab'b'abbab'abbabbab'b'ab'ababbab'abab'ababbbabbab'ab'ab'ababbbab'b'abbbab'b'ab'ab'a (71*)
B=abab'abbab'ab'ab'ab'b'ab'b'abbbab'b'ab'abbabbabab'abbab'b'ab'ab'ab'b'abbabab'ab'b'abab'abbab'ab (72*)
L=bbbabababbab'b'ab'abbabbab'b'ab'abab'ab'ab'ab'abbbab'ab'ab'b'ab'b'ababbab'ababbababbab'b'a (71*)
» login or register to post comments

Longer solutions

Submitted by rokicki on Mon, 04/12/2010 - 21:26.
Wow, these two generators require much longer solutions for
the face turns (pretty obvious with an order-2 generator).

This is what I get.

h=U1R1F1U1B1R2
g=U2D2

U=hhgh'gh'h'h'gh'gh'gh'h'h'ghgh'h'gh'gh'ghhhghghgh'h'gh'h'h'gh'h'h'gh'h'ghgh'ghhgh'gh'ghgh'gh'ghghhg (70*)
F=gh'h'gh'gh'h'ghgh'gh'ghghgh'h'gh'ghghghghghhghhhhgh'ghhhgh'h'gh'gh'gh'gh'ghhhgh'h'gh'g (66*)
R=h'h'gh'h'ghghgh'gh'ghgh'gh'ghghghhghghhgh'h'gh'ghhghhhgh'h'gh'ghhghhhhghhhhghghg (66*)
D=h'h'h'ghhhgh'gh'ghghghghhhhghhghhhghghhghhhghhhghhgh'h'h'gh'gh'ghhgh'h'ghhghgh'gh (68*)
B=ghhhhghghhhhgh'h'gh'h'ghhhghghhhghhhghhgh'h'h'ghgh'h'ghghhhgh'ghgh'h'h'ghhghgh'gh (67*)
L=ghhhgh'ghhhgh'h'ghgh'h'ghhhhgh'gh'ghghgh'h'gh'ghhhgh'gh'h'gh'gh'gh'h'ghhhhghhghghghgh' (68*)
» login or register to post comments

From Singmaster's Notes

Submitted by jaap on Sat, 04/03/2010 - 01:44.
In Singmaster's "Notes on Rubik's Magic Cube", 5th Edition, p49, he says:
"Frank Barnes has shown that the group of the cube is generated by just two elements. Marston D. E. Conder has shown that it can be generated by two elements, g, h, of orders 2 and 4 and that orders 2 and 3 will not suffice. It is well known that two elements of order 2 can only generate the symmetries of an n-gon, where n is the order of gh. (When n = 1 or 2 the n-gon is a bit degenerate.) Elements of order 3 and 3 can only generate even permutations on corners and on edges, hence cannot generate the whole group. It is not clear if Conder's generators also generate the supergroup."

"Explicitly, Condor shows that the following serve:
g = (UR,RB)(DR,UB)(FR,FL)(UL,LB) (RFU,RUB)(DFR,DBL)(UFL,BUL)
h = (UR,BR,DR,FR)(UF,UB,DF,DB)(UL,FL,DL,BL) (RFU,DFR,LFD,UFL)(RUB,BDR)(DBL,ULB)"

"In a revised version of his note, he uses
g' = (FL,LB)(BR,FR)(DL,UB)(DR,UF)(DF,DB) (RFU,RUB)(DFR,DBL)(UFL,BUL)
and he shows that g'h has the maximal order of 1260."

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

» login or register to post comments

Depends on your definition of simplicity

Submitted by secondmouse on Sun, 03/21/2010 - 18:14.
Certainly this example of a 2-generator set is a lot more straightforward than the one cited in David Joyner's book!

However I wouldn't have said these two generators are "simple". The orders of UF and RBL are 105 and 90 respectively. A more compact example (wrt to the face metric) is U^2F and DRB^2 for example (of orders 30 and 9)

Regarding 2 generators using the QTM - why not take UD and RBL instead?
» login or register to post comments

you mean his book adventures

Submitted by nooneimportant on Sat, 03/27/2010 - 17:23.
you mean his book adventures in group theory ?
what example does he cite there ?
how are these actually computed(I'm curious)

thanks
» login or register to post comments

Yes, I'm sure Adeventures in

Submitted by Bruce Norskog on Sun, 03/28/2010 - 12:54.
Yes, I'm sure Adeventures in Group Theory is what he is referring to. In the copy of the book I have, it's on page 167 (Section 10.3, Presentations and Plutonian robots). He attributes the generators to someone named F. Barnes. They are U B L U L' U' B' and R2 F L D' R'.

Basically, to prove a set of generators generate the whole group, it is sufficient to show that they can be used to generate each one of some other set of generators, such as { U, D, L, R, F }. Or you can simply use GAP to find out if a set of generators generate the whole cube group.

For example, (U B L U L' U' B')^6 flips two edges. Then you can find sequences (of these two generators) to move two other edges to these positions to come up with a conjugation that flips two different edges. Then you could find enough such two-flips to show that you can solve any edge orientation situation. Apply the same idea to corner orientation and to permuting the pieces and you should eventually be able find suitable sequences for { U, D, L, R, F } or whatever known set of cube generators you're trying to find sequences for. Generally GAP can also be used to find such sequences.
» login or register to post comments