# Things that are 'n-gen'?



## StachuK1992 (Aug 8, 2011)

WE NEED TO CLEAR UP THIS DEFINITION.

This is how I see it:

By default, many assume the term 2-gen to default as <R,U> solving or scrambling, meaning doing either by only turning the R and U faces.

2-gen can refer to any two faces/slices being turned, so <M,U> or <R,D> are both 2-gen, while <R,U,D> is 3-gen.

2-gen can, being as correct as I know, refer also to algs solved/scrambled with <R U R', D> meaning you're allowed to apply the short sequence "R U R'", its inverse, D, or its inverse.

For this reason, the following algs should be considered 2-gen:
I'll just use | as a random separator
M U M' | <M,U>
R U R' | <R,U>
R U R' D R U' R' D' | <R U R', D>

while this is 3gen
r (R U R' U') r' U2 (R U R U' R2) <R,r,U>


I'd just like to clear up some confusion concerning the n-gen term -
it seems as though people overlook some applications of it.




Just as a note, any 3x3 cube solution should be 3-gen at max:


Spoiler



<R,x,y>



Discuss.


----------



## 5BLD (Aug 8, 2011)

Well, theres some common sense involved I guess.
Technically, <R U F2 U' B S2, D> is also 2-gen. Therefore, maybe a solution given to a scrambled cube could be 1-gen, i.e. <solution to the cube>
However, for our uses this isn't exactly practical right?

By the way, I'm just pondering...


----------



## StachuK1992 (Aug 8, 2011)

Clarification:
ALL 3x3 scrambled positions can be solved with the *same* 3-gen restrictions.
I think that's better?


----------



## Escher (Aug 8, 2011)

<R U R' U R U2 R', R U R' F' R U R' U' R' F R2 U' R'>

You make it sound as though <R U R', D> is something special...


----------



## StachuK1992 (Aug 8, 2011)

Of course it's nothing special. I just like my <R,U,D> algs and that's the first generator combination that came to mind.


----------



## Escher (Aug 8, 2011)

StachuK1992 said:


> Of course it's nothing special. I just like my <R,U,D> algs and that's the first generator combination that came to mind.


 
Sure, I was just trying to point out it didn't sound like an analogy/example of something bigger.


----------



## Sa967St (Aug 8, 2011)

Is there another term that can be used to describe a sequence of turns that involve N faces? 

e.g. 
Person A: "R U R' D R U' R' D' is 3-gen because it uses 3 different faces." 
Person B: "No it's not 3-gen because it can be notated as <R U R', D>, you mean it's 3-______."


----------



## 5BLD (Aug 8, 2011)

StachuK1992 said:


> Clarification:
> ALL 3x3 scrambled positions can be solved with the *same* 3-gen restrictions.
> I think that's better?


 
Yah.
But still, with your definition... ANY alg could be 2gen.

As I said there's common sense involved...
My point is that ANY sequence of moves can be 2gen by definition.
Also, if RUL is 2-gen, it means on two axes then, not just two layers?
The definition is a bit vague in my opinion.


----------



## Escher (Aug 8, 2011)

5BLD said:


> Yah.
> But still, with your definition... ANY alg could be 2gen.
> 
> As I said there's common sense involved...
> ...



How is it vague?

Don't use Stachu's post as a perfect definition of '2-gen'. It doesn't really tell you what a generator is. 

<R, U, L> is not '2-gen', for example, but that moveset can be used to write a 2-generator sequence, such as L U' R' U L' R.

The first 'generator' in that instance is the sequence L U'. It cannot be re-written as L U or L' U'. Not 'any' alg can be 2-gen.


Correct me if I'm wrong, I've never studied mathematics beyond the age of 16 and my knowledge comes from a few people on this forum.


----------



## JustinJ (Aug 8, 2011)

StachuK1992 said:


> while this is 3gen
> r (R U R' U') r' U2 (R U R U' R2) <R,r,U>


 
No, it's 1-gen.

<r R U R' U' r' U2 R U R U' R2>


----------



## 5BLD (Aug 8, 2011)

Escher said:


> How is it vague?
> 
> Don't use Stachu's post as a perfect definition of '2-gen'. It doesn't really tell you what a generator is.
> 
> ...


 
Hm. I guess. But my point is that RUL is sometimes referred to as 2gen because it's on two axes...
And I'm not sure of Justin was joking, but yes, his statement DOES fit the definition. Therefore, in this way, ANY alg can be 2gen.
Furthermore, we could even call it 2gen due to it being on two axes...
That's what I mean by vague...

Please do argue against my points if necessary as that's the point of this thread. To discuss.


----------



## aronpm (Aug 8, 2011)

5BLD said:


> Hm. I guess. But my point is that RUL is sometimes referred to as 2gen because it's on two axes...


 
???


----------



## StachuK1992 (Aug 8, 2011)

A single alg can always be 1-gen.

An alg set can always be 3-gen (<R,x,y>).

I favorite alg sets usually fall under <R,U,D>.

I think this could be a more clear way to state this?


----------



## whauk (Aug 8, 2011)

what is an "alg set"?


----------



## StachuK1992 (Aug 8, 2011)

PLL.


----------



## DaKrazedKyubizt (Aug 8, 2011)

StachuK1992 said:


> A single alg can always be 1-gen.
> 
> An alg set can always be 3-gen (<R,x,y>).
> 
> ...


 
Here's a pretty straightforward way to state it: You're saying that the alg set, or whatever it's called (<A, B, C, etc.>) must be defined before defining an algorithm as "?-gen". It cannot be done the other way around. 

For example, R2 B2 R F R' B2 R F' R is ?-gen (or I guess you could call it "an undefined algorithm set"), but R2 B2 R F R' B2 R F' R given the generator <R, B, F> is 3-gen, or if you're given the generator <R2, B2 R, F R'> is also 3-gen, and if you're given <R2 B2 R F, R' B2 R F' R>, it becomes 2-gen. 

It's similar to saying that you can't have a blob of human skin keep its shape without a skeleton to hold it up.

It's not vague at all.


----------



## Stefan (Aug 8, 2011)

StachuK1992 said:


> An alg set can always be 3-gen (<R,x,y>).


 
I'd say an algorithm like y y y R y isn't the algorithm F, so F isn't in <R,x,y>. Talk about "cube group elements" or maybe "cases" instead of "algorithms", and I'd agree.


----------



## 5BLD (Aug 8, 2011)

This is what I mean. There are many interpretations...
I agree with the crazed cubist... There's no set way to tell is there?
But we use our discretion to tell...


----------



## cuBerBruce (Aug 8, 2011)

Mathematically speaking, <RUR', D> *is* a two-generator group. If I write "<RUR', D>", then by *definition* I am considering RUR' and D to be generators of a group.

Historically, mathematicians have used {U, D, L, R, F, B} as a set of generators for what is generally called the "Rubik's Cube group." It is obvious from these 6 "moves" we can create any legal cube position by combining them in some way. RUR', for example, can be generated by RURRR. The "Rubik's Cube group" was defined as <U, D, L, R, F, B>. (The order of the generators is unimportant). Of course, there are many other ways the same group can be defined in terms of some generators.

Any group using only two of the above generators, such as <U, R>, then logically became to be called two-generator as only two of the six standard generators were being used.

A problem arises in the speedsolving community, because we often use moves that don't keep the centers in a fixed location. (In other words U may not always turn the layer with the same color center piece). We are now dealing with a mathematical group that is 24 times larger than the group that is usually termed "the Rubik's Cube group." Within this larger group, we have other moves that are "basic" enough to think of as "standard generators": M, x, r or Rw, etc. There is really no "standard" set of generators for this group. We could write <U, D, L, R, F, B, x, y, z> or <U, D, L, R, F, B, M, E, S> or <U, x, y>. Logically it tends to make sense to think of any move that can be performed as a single simple action like M, x, or R as a "standard generator" and then calling any combination of the original six generators and this extended set of standard generators as "2-gen". This does not change the fact, of course, that it is always possible (mathemtically speaking, anyway) to use as generators, elements that are combinations of the "standard" generators like RUR' or MUM'.

In any case, <R, U, L> is definitely *three*-gen. I suppose there exist two elements within this group that will generate the whole group, but simply writing it as <R, U, L> means we are treating this group as a group generated by 3 elements, and thus, we can *not* say it is two-generator even though only two axes are turned. Anybody who does not understand this simply doesn't understand the concept of n-generator groups.


----------



## 5BLD (Aug 8, 2011)

Yay. A detailed explanation. Makes sense now.


----------



## Kirjava (Aug 8, 2011)

Sa967St said:


> Is there another term that can be used to describe a sequence of turns that involve N faces?


 
This is what we're missing. 

I don't think it's /that/ vital though - there are plenty of other terms with multiple meanings that usually require minimal clarification.


----------



## Cool Frog (Aug 8, 2011)

Comms are 2 gen. :O


----------



## Jorghi (Aug 8, 2011)

cuBerBruce said:


> Mathematically speaking, <RUR', D> *is* a two-generator group. If I write "<RUR', D>", then by *definition* I am considering RUR' and D to be generators of a group.
> 
> Historically, mathematicians have used {U, D, L, R, F, B} as a set of generators for what is generally called the "Rubik's Cube group." It is obvious from these 6 "moves" we can create any legal cube position by combining them in some way. RUR', for example, can be generated by RURRR. The "Rubik's Cube group" was defined as <U, D, L, R, F, B>. (The order of the generators is unimportant). Of course, there are many other ways the same group can be defined in terms of some generators.
> 
> ...



This guy just demolished everyone lol. Thanks for the explanation. Time to create 2-5 gen f2l scrambles and find thing cool things.


----------



## JonnyWhoopes (Aug 8, 2011)

Jorghi said:


> This guy just demolished everyone *and the OP* lol. Thanks for the explanation. Time to create 2-5 gen f2l scrambles and find thing cool things.


 
You see, it's funny, 'cause nothing Stachu said disagreed with what Bruce said.

::EDIT:: Editing to clarify why I said what I did. Bolded in the quote. This is what the quote looked like before it was ninja-edited. You're fast Jorghi 0_0.


----------



## StachuK1992 (Aug 8, 2011)

Did you know:

<M,U,R,D,E,r> can solve everything?
U D' E' = y
R y2 r' y2 = x
R = R.


----------



## Jorghi (Aug 8, 2011)

JonnyWhoopes said:


> Explain please? Either I lack understanding or that's a mistake (probably the former).


I don't think R r= x he made a mistake maybe.



JonnyWhoopes said:


> You see, it's funny, 'cause nothing Stachu said disagreed with what Bruce said.
> ::EDIT:: Editing to clarify why I said what I did. Bolded in the quote. This is what the quote looked like before it was ninja-edited. You're fast Jorghi 0_0.


 
Nope... I checked to see what Stachu said in case he was right. Thats why my post with edit was made before yours  And why it doesn't say last edited on it either.


----------



## cubernya (Aug 8, 2011)

Lol stachu...just remove the posts

By the way, isn't the E slice notation viewed from above?


----------



## JonnyWhoopes (Aug 8, 2011)

theZcuber said:


> By the way, isn't the E slice notation viewed from above?


 
Nope. Never understood why, it seems kinda non sequitur to me.


----------



## vcuber13 (Aug 8, 2011)

idk why m is the same as L either


----------



## cubernya (Aug 8, 2011)

I thought the slices were as follows:

M - same as L
E - same as U
S - same as F

Correct me if I'm wrong


----------



## StachuK1992 (Aug 8, 2011)

http://www.speedsolving.com/wiki/index.php/Puzzle_Notation


----------



## cubernya (Aug 8, 2011)

I could've sworn E was same as U

Edit: WCA regulations say E is same direction as D. Guess I'm going to have to get used to that


----------



## Julian (Aug 8, 2011)

M = top to bottom
E = left to right
S = clockwise


----------



## blah (Aug 8, 2011)

Didn't Lucas once prove that the entire cube group can be generated by a subgroup of order 2? Can't find the link though.

Edit: I refuse to use the term 2-gen in the middle of this noob confusion/ignorance.
Edit: Okay so he didn't prove it


----------



## Sa967St (Aug 8, 2011)

blah said:


> Didn't Lucas once prove that the entire cube group was 2-gen? Can't find the link though.


 
http://www.speedsolving.com/forum/showthread.php?19751-The-entire-cube-is-2-gen!


----------



## blah (Aug 8, 2011)

Not quite on-topic, but does anyone have a proof that the cube group is not cyclic? Does it involve permutation parities?


----------



## qqwref (Aug 8, 2011)

Keep this in mind: in a mathematical context, generators are in terms of positions (piece permutations). A generator like <RUR', D> is valid and useful in a mathematical context because RUR' actually represents a single piece permutation. That generator contains every permutation that can be generated by those two permutations. In the cubing context, though, it's very imporatnt to think in terms of moves themselves, rather than cube positions, because otherwise we can't distinguish betwen R2URUR'U'R'U'R'UR' and F2UR'LF2RL'UF2. So in that spirit we should be thinking of generators in terms of individual moves. Allowing generators of multiple moves just dilutes the definition to the point where there is no meaningful distinction between 2-gen and not. From both a conceptual and a practical viewpoint, it makes more sense to be strict and allow N-gen to only contain individual moves.

tl;dr: We shouldn't consider things like <RUR', D> to be 2-gen.


----------



## qqwref (Aug 8, 2011)

blah said:


> Not quite on-topic, but does anyone have a proof that the cube group is not cyclic? Does it involve permutation parities?


"The fundamental theorem of cyclic groups states that if G is a cyclic group of order n then every subgroup of G is cyclic."

EPLL (all 4!/2 cases) is a subgroup of G, and it is easy to see it is not cyclic (every element has order <12). QED.


----------



## Kirjava (Aug 8, 2011)

qqwref said:


> in that spirit we should be thinking of generators in terms of individual moves. Allowing generators of multiple moves just dilutes the definition to the point where there is no meaningful distinction between 2-gen and not. From both a conceptual and a practical viewpoint, it makes more sense to be strict and allow N-gen to only contain individual moves.


 
Unless useful to do otherwise of course, in which case the meaning can be specified.

I like it when other people post what I'm thinking.


----------



## JonnyWhoopes (Aug 8, 2011)

qqwref said:


> Keep this in mind: in a mathematical context, generators are in terms of positions (piece permutations). A generator like <RUR', D> is valid and useful in a mathematical context because RUR' actually represents a single piece permutation. That generator contains every permutation that can be generated by those two permutations. In the cubing context, though, it's very imporatnt to think in terms of moves themselves, rather than cube positions, because otherwise we can't distinguish betwen R2URUR'U'R'U'R'UR' and F2UR'LF2RL'UF2. So in that spirit we should be thinking of generators in terms of individual moves. Allowing generators of multiple moves just dilutes the definition to the point where there is no meaningful distinction between 2-gen and not. From both a conceptual and a practical viewpoint, it makes more sense to be strict and allow N-gen to only contain individual moves.
> 
> tl;dr: We shouldn't consider things like <RUR', D> to be 2-gen.


 
I am very okay with this.


----------



## blah (Aug 8, 2011)

qqwref said:


> "The fundamental theorem of cyclic groups states that if G is a cyclic group of order n then every subgroup of G is cyclic."
> 
> EPLL (all 4!/2 cases) is a subgroup of G, and it is easy to see it is not cyclic (every element has order <12). QED.


o i c wat u did thar

elegant proof is elegant 

are they really calling it the fundamental theorem of cyclic groups these days?


----------



## tx789 (Aug 8, 2011)

For last layer all you need is <R,U,M> <R,U> for corners and <M,U> for edges. So it's sort of 2 gen


----------



## RyanReese09 (Aug 8, 2011)

tx789 said:


> For last layer all you need is <R,U,M> <R,U> for corners and <M,U> for edges. So it's sort of 2 gen


 
Do Aperm on a solved cube.

Using <R, U> How can you solve this? You can't. Your example only works if CP is correct.


----------



## Jorghi (Aug 8, 2011)

RyanReese09 said:


> Do Aperm on a solved cube.
> 
> Using <R, U> How can you solve this? You can't. Your example only works if CP is correct.


 
I think you are thinking about 2gll.


----------



## macky (Aug 8, 2011)

qqwref said:


> Keep this in mind: in a mathematical context, generators are in terms of positions (piece permutations). A generator like <RUR', D> is valid and useful in a mathematical context because RUR' actually represents a single piece permutation. That generator contains every permutation that can be generated by those two permutations. In the cubing context, though, it's very imporatnt to think in terms of moves themselves, rather than cube positions, because otherwise we can't distinguish betwen R2URUR'U'R'U'R'UR' and F2UR'LF2RL'UF2. So in that spirit we should be thinking of generators in terms of individual moves. Allowing generators of multiple moves just dilutes the definition to the point where there is no meaningful distinction between 2-gen and not. From both a conceptual and a practical viewpoint, it makes more sense to be strict and allow N-gen to only contain individual moves.
> 
> tl;dr: We shouldn't consider things like <RUR', D> to be 2-gen.



Yeah, this needs to be understood before even talking about what Bruce wrote.



qqwref said:


> "The fundamental theorem of cyclic groups states that if G is a cyclic group of order n then every subgroup of G is cyclic."



The refinement is that there's a unique subgroup of order d for every divisor d of n, and that these are all the subgroups of G. So here's an even shorter proof that the cube group is not cyclic: <R> and <U> are distinct subgroups of the same order.



blah said:


> are they really calling it the fundamental theorem of cyclic groups these days?



I wouldn't call it anything since it's "common knowledge."


----------



## Meep (Aug 8, 2011)

Sa967St said:


> Is there another term that can be used to describe a sequence of turns that involve N faces?
> 
> e.g.
> Person A: "R U R' D R U' R' D' is 3-gen because it uses 3 different faces."
> Person B: "No it's not 3-gen because it can be notated as <R U R', D>, you mean it's 3-______."


 
I think it'd be easier to just say what faces the alg uses, like "R U R' D R U' R' D' is an RUD alg." It may seem silly, but I personally think it's more easily and readily understood than a more technical term.


----------



## Hershey (Aug 8, 2011)

Meep said:


> I think it'd be easier to just say what faces the alg uses, like "R U R' D R U' R' D' is an RUD alg." It may seem silly, but I personally think it's more easily and readily understood than a more technical term.


 
"R U R' D R U' R' D is an 3 gen <R,U,D> algorithm"?


----------



## Meep (Aug 8, 2011)

Hershey said:


> "R U R' D R U' R' D is an 3 gen <R,U,D> algorithm"?


 
Yeah, but people were going on about how it could be a 2 gen <R U R',D> algorithm too.


----------



## Hershey (Aug 8, 2011)

Oh wow, I just noticed that ccw U perm is 4 gen.

R2 U' R' U' R U R U R U' R=
R' R' U' R' U' R U R U R U' R

which uses <R, R' U', R U, R U'>


----------



## Sa967St (Aug 8, 2011)

Hershey said:


> Oh wow, I just noticed that ccw U perm is 4 gen.
> 
> R2 U' R' U' R U R U R U' R=
> R' R' U' R' U' R U R U R U' R
> ...


You're doing it wrong.


----------



## Hershey (Aug 8, 2011)

Oh... Nevermind then.


----------



## rcbeyer (Aug 8, 2011)

Hershey said:


> Oh wow, I just noticed that ccw U perm is 4 gen.
> 
> R2 U' R' U' R U R U R U' R=
> R' R' U' R' U' R U R U R U' R
> ...


 


StachuK1992 said:


> 2-gen can, being as correct as I know, refer also to algs solved/scrambled with <R U R', D> meaning you're allowed to apply the short sequence "R U R'", its inverse, D, or its inverse.


 
R' R' U' R' U' R U R U R U' R

this alg only consists of R, U and the inverse of them, so this would still be a 2-gen alg of the group <R, U> i believe


----------



## uberCuber (Aug 8, 2011)

Jorghi said:


> I think you are thinking about 2gll.


 
2GLL is when corner permutation is already solved. You cannot do an A perm with <R,U,M> (because M moves don't affect the corners, and you can't do an A perm with <R,U>, as evidenced by the fact that there are no A perms in 2GLL)


----------



## Erdos (Aug 9, 2011)

rcbeyer said:


> R' R' U' R' U' R U R U R U' R
> 
> this alg only consists of R, U and the inverse of them, so this would still be a 2-gen alg of the group <R, U> i believe


Mathematically, you can still write it as <R' R' U' R' U' R U R U R U' R>, which is a subgroup most likely of order 2. That is, the algorithm is the minimal non-identity element in this generated subgroup. However, you can also write it as <R,U>, which makes it no longer a minimal element in the <R,U> subgroup. In other words, the common way we write it (<R,U>) is not the _only_ way of putting the element (algorithm) in a subgroup (n-gen).


----------



## cuBerBruce (Aug 9, 2011)

Erdos said:


> Mathematically, you can still write it as <R' R' U' R' U' R U R U R U' R>, which is a subgroup most likely of order 2. That is, the algorithm is the minimal non-identity element in this generated subgroup. However, you can also write it as <R,U>, which makes it no longer a minimal element in the <R,U> subgroup. In other words, the common way we write it (<R,U>) is not the _only_ way of putting the element (algorithm) in a subgroup (n-gen).



Since <R' R' U' R' U' R U R U R U' R> has a single generator, it must be a cyclic group. The generator has order 3 so the cyclic group it generates also has order 3, meaning the group contains three elements: the generator, the generator squared (which is also the inverse of the generator), and the identity element.


----------



## blah (Aug 9, 2011)

macky said:


> I wouldn't call it anything since it's "common knowledge."


... since it's *almost trivial. (Most fundamental theorems are "common knowledge," which is why they're called fundamental theorems; however, most of them are non-trivial, which is why they get to be called fundamental theorems. Heh.)

Oh and sweet proof. Exactly what I was looking for.


----------



## macky (Aug 9, 2011)

blah said:


> macky said:
> 
> 
> > I wouldn't call it anything since it's "common knowledge."
> ...



Yeah, that's more accurate.


----------



## Tim Reynolds (Aug 9, 2011)

My preferred proof that the cube group isn't cyclic: It's non-abelian. \( a^xa^y=a^ya^x \) but RU is different from UR.

My opinion: If you're looking for a practical definition, there's hardly any reasons to talk about any generators besides the standard ones. People talk about 2-gen algorithms because there's some practical advantage to using <R,U> or <M,U> algorithms. There's no practical reason to talk about <UF,RBL> algorithms. That's why there's a term for <R,U> algorithms: they are a large set of easy-to-execute algorithms with a well-known set of properties. <M,U> falls in the same category. I can't think of any generators that are more than one turn in sets like those.

If you're trying to be cube theoretic, take a step back and try to figure out what you're actually trying to prove. Otherwise you end up with all algs being 1-gen, or something else equally useless.


----------



## Erdos (Aug 9, 2011)

cuBerBruce said:


> Since <R' R' U' R' U' R U R U R U' R> has a single generator, it must be a cyclic group. The generator has order 3 so the cyclic group it generates also has order 3, meaning the group contains three elements: the generator, the generator squared (which is also the inverse of the generator), and the identity element.


 I actually didn't pay attention to what the actual algorithm is. However, it's quite obvious that if the generator has order 3, the cyclic group (ie. the subgroup created by all elements of the generator) has the same order. That could practically be the definition.

EDIT:


Tim Reynolds said:


> My preferred proof that the cube group isn't cyclic: It's non-abelian. \( a^xa^y=a^ya^x \) but RU is different from UR.


I like this one better too. Proving a group is non-abelian is so much simpler (and trivial) than proving a subgroup isn't cyclic.


----------



## blah (Aug 9, 2011)

tim reyholds win


----------

