# Group structure of the Rubik's Revenge?



## mande (Mar 14, 2009)

Hi,
I read up on Wikipedia the article describing the group structure of the Rubik's cube, and I understood it. (I hope). What I am confused about is what the group structure of the 4x4 might be. Because I thought from the solved state, the centers being interchangeable keeping the cube solved might cause complications. Can anyone help me out?
Thanks.


----------



## jcuber (Mar 14, 2009)

Yes, there are things called parity (can happen on any even-layered cube) which cause either one edge to flip (orientation parity) or two edges to swap places (permutation parity). Niether of these can happen on an odd-layered cube, and there are algorithms to correct these.


----------



## TheBB (Mar 14, 2009)

mande said:


> Hi,
> I read up on Wikipedia the article describing the group structure of the Rubik's cube, and I understood it. (I hope). What I am confused about is what the group structure of the 4x4 might be. Because I thought from the solved state, the centers being interchangeable keeping the cube solved might cause complications. Can anyone help me out?
> Thanks.


Group theory isn't my strong point really, but can't you just quotient out the different center piece permutations?


----------



## mande (Mar 14, 2009)

TheBB said:


> Group theory isn't my strong point really, but can't you just quotient out the different center piece permutations?



Umm...I'm sure we could, but could you tell me the group of the different center piece permutations?
Will it be (A_4)^6?


----------



## TheBB (Mar 14, 2009)

I guess so. If that's the one with only even permutations. Can't remember.


----------



## TomZ (Mar 14, 2009)

The 24 4x4 centers can be arranged in 24! different ways. However, as there are six pairs of four indistinguishable centers, the total figure is only 24!/(4^6).


----------



## mande (Mar 14, 2009)

I got that the group for the edges is A_24, for centers (A_24)/((A_4)^6), for corners A_8 X (Z_3)^7
(these accounting only for even permutations). Would that be correct?
My main question was how to combine these 3 subgroups using some type of product of groups to get a group structure on the 4x4.


----------



## EmersonHerrmann (Mar 14, 2009)

jcuber said:


> Yes, there are things called parity (can happen on any even-layered cube)



What about 2x2?


----------



## TomZ (Mar 14, 2009)

EmersonHerrmann said:


> jcuber said:
> 
> 
> > Yes, there are things called parity (can happen on any even-layered cube)
> ...



The 2x2 has parity. And so does the 3x3 for that matter. In fact, any cube can have parity.


----------



## cmhardw (Mar 14, 2009)

jcuber said:


> Yes, there are things called parity (can happen on any even-layered cube) which cause either one edge to flip (orientation parity) or two edges to swap places (permutation parity). Niether of these can happen on an odd-layered cube, and there are algorithms to correct these.



At the risk of being the nit-picky math guy, this statement is wrong on many levels.



> Yes, there are things called parity (can happen on any even-layered cube) which cause either *one edge* to flip (orientation parity)...



It is not possible to "flip" any edge on an even cube. If you replace that with *edge group* or even better *swap two edges in the same orbit* then I might agree with you.



> ... or two edges to swap places (permutation parity).



Swapping the place of two edges in the same orbit is actually "orientation parity". I think you're thinking about edge groups, or if you want to generalize this *two pairs of edges within the same orbit*.



> Niether of these can happen on an odd-layered cube, and there are algorithms to correct these.



First off you have to use more general definitions for the n x n x n case, and second of all using the more general definitions orientation parity in terms of speed solving would typically be defined as "interchanging two edge pieces in the same orbit" and permutation parity would be defined as "interchanging two pairs of edge pieces in the same orbit, and this may span multiple if not all edge orbits". Using these more general definitions both of these cases are absolutely possible on an odd layered n x n x n cube provided n > 3

Chris

P.S. I'm not trying to be mean or elitist, but your post is spreading untruths, and I felt the need to correct it.


----------



## Lord Voldemort (Mar 15, 2009)

I think Parity (on a cube) is basically anything scarmbled with an even number of turns and solved with an odd number or vice versa. That's why they call it parity on BLD after you solve edges.


----------



## trying-to-speedcube... (Mar 15, 2009)

jcuber said:


> Yes, there are things called parity (can happen on any even-layered cube) *which cause either one edge to flip* (orientation parity) or two edges to swap places (permutation parity). Niether of these can happen on an odd-layered cube, and there are algorithms to correct these.



Try popping an edge out of your 4x4 and put in back flipped...


----------



## qqwref (Mar 15, 2009)

The positions in a 4x4 actually do not form a group!

Why not? The basic reason is because of the interchangeable centers. This actually leads to us not being able to decide what the product of any two positions is - the operation itself is ambiguous. In the 3x3 we can just apply the first position and then apply the second to that, but on the 4x4 there are multiple positions that look the same so we can get many different results from this seemingly simple calculation.

Let me explain with an example. Here are two 4x4 patterns that look the same:
r U' l' U r' U' l U
F U' l' U r U' l U r' F'
Call this position "A", and call the position achieved from a simple d move position "B". Now let's *try* to calculate what the product BA is. The surprising result is that, depending on which of the first two algorithms we use, we get different patterns! They both give the same position A, but when we try to tack on a d move at the beginning we actually get different positions. So we actually cannot multiply B and A!

Remember that on 3x3 we always have a unique way to combine two permutations, since every piece is distinct. No matter what sequence of moves we use to set up A and B, we will always get the same result for AB or BA, so we have a valid group structure. But the 4x4 does not give us a valid single-valued way to multiply two positions, and so we can't make a group out of it that would correspond to the way an actual 4x4 works.


----------



## JBCM627 (Mar 15, 2009)

qqwref said:


> The positions in a 4x4 actually do not form a group!
> 
> Why not? The basic reason is because of the interchangeable centers. This actually leads to us not being able to decide what the product of any two positions is - the operation itself is ambiguous. In the 3x3 we can just apply the first position and then apply the second to that, but on the 4x4 there are multiple positions that look the same so we can get many different results from this seemingly simple calculation.
> 
> ...



I don't follow your logic here. This example only illustrates to me that A and B do not commute.

As best I can tell, the 4x4 satisfies all the requirements listed here.


----------



## Ton (Mar 15, 2009)

qqwref said:


> The positions in a 4x4 actually do not form a group!
> 
> Why not? The basic reason is because of the interchangeable centers. This actually leads to us not being able to decide what the product of any two positions is - the operation itself is ambiguous. In the 3x3 we can just apply the first position and then apply the second to that, but on the 4x4 there are multiple positions that look the same so we can get many different results from this seemingly simple calculation.
> 
> ...



In the 3x3 group description we discard the center, -there are more solved states if you would mark the center- For the 4x4 we could mark the centers as Ra Rb Rc Rd etc


----------



## Lucas Garron (Mar 15, 2009)

Ton said:


> qqwref said:
> 
> 
> > The positions in a 4x4 actually do not form a group!
> ...


Well, yes, the 4x4x4 supercube has a group. But that's a different puzzle!

JCBM: Associativity fails, because, as qq showed, composition is not consistently definable.
Even better, consider
A = [U r U', l']
B = [l, F r' F']

A B = e, but B A ≠e
Breaks inverses.


----------



## mande (Mar 15, 2009)

qqwref said:


> The positions in a 4x4 actually do not form a group!
> 
> Why not? The basic reason is because of the interchangeable centers. This actually leads to us not being able to decide what the product of any two positions is - the operation itself is ambiguous.



Doesn't quotienting the whole "group" by the group of permutations of the center pieces solve that problem?


----------



## Lucas Garron (Mar 15, 2009)

mande said:


> qqwref said:
> 
> 
> > The positions in a 4x4 actually do not form a group!
> ...


If by "quotienting" you mean "ignoring," yes. But that's not the same puzzle...


----------



## qqwref (Mar 15, 2009)

As I showed, there is no way to construct a group that will really represent the 4x4. Any construction that seems to - like yours - will construct a group that probably won't represent anything like the 4x4 if you look more closely.


----------



## TheBB (Mar 15, 2009)

I guess you mean to say (A_4)^6 isn't normal in the 4x4 supergroup.


----------



## mande (Mar 15, 2009)

qqwref said:


> As I showed, there is no way to construct a group that will really represent the 4x4. Any construction that seems to - like yours - will construct a group that probably won't represent anything like the 4x4 if you look more closely.



Well, that certainly surprises me, your argument seems to imply that there is no way to construct a group that represents any nxnxn cube (n>3)? Are you sure that is right?


----------



## JBCM627 (Mar 15, 2009)

Lucas Garron said:


> Associativity fails, because, as qq showed, composition is not consistently definable.


Composition of permutations is also easily definable in a consistent manner; that is, it is possible to define it so that it works for any composition for a cube in any state, as opposed to the view of it not working for select compositions in select states. As you said, this may be changing the idea behind the puzzle, but with minimal change, this is still a valid view of the 4x4. In other words, it is ok to distinguish center pieces if you consider multiple states as solved - it is still the same puzzle.



Lucas Garron said:


> A B = e, but B A ≠e
> Breaks inverses.


There are a couple of assumptions initially made in this argument, namely: B is an inverse, and the 4x4 is a group. Since BA≠e, B obviously isn't an inverse element. Since there is still an element that does satisfy BA=AB=e, The 4x4 can still be a group.


----------



## Lucas Garron (Mar 15, 2009)

JBCM627 said:


> Lucas Garron said:
> 
> 
> > A B = e, but B A ≠e
> ...


B is an inverse: Yes, because it satisfies AB=e (this is equivalent to defining an inverse as AB=BA=e).
The 4x4 is a group: You're presuming exactly this fact, and I'm trying to show that it does not satisfy the definition.

It's an elementary property of groups that being a right-inverse/left-inverse to an element is equivalent. Let's consider C the inverse you like:
A = [U r U', l']
B = [l, F r' F']
C = [l', U r U]


```
C
= C e       [Existence of Identity]
= C (A B)   [AB=e]
= (C A) B   [Associativity]
= e B       [CA=e]
= B         [Identity]
```

Thus, we get C = B, which you can easily verify is false - it's a contradiction. Our assumption that the 4x4x4 can be a group is false.

The best thing you can do to make it a group is to consider the 4x4x4 a supercube with multiple solved states - but that's still a supercube group, not a 4x4x4 group!



mande said:


> Well, that certainly surprises me, your argument seems to imply that there is no way to construct a group that represents any nxnxn cube (n>3)? Are you sure that is right?


That's right. Unless with "represents" you don't mean "represents exactly."


----------



## JBCM627 (Mar 15, 2009)

Lucas Garron said:


> JBCM627 said:
> 
> 
> > Lucas Garron said:
> ...


There are still holes in this though. AB=e is not equivalent to saying AB=BA=e, as demonstrated by your example, since [A,B]≠0. And anyway, AB=e only for a select few cubes.


```
C
= C e       [Existence of Identity]
= C (A B)   [AB=e]
= (C A) B   [Associativity]
= e B       [CA=e]
= B         [Identity]
```
As I said above, AB doesn't necessarily = e. Since you have (AB) after C, then in this case, (AB)≠e, and your 3rd line is not true.

If you can explain this further, I'd agree, but there are too many disputable points otherwise.


----------



## Lucas Garron (Mar 15, 2009)

JBCM627 said:


> As I said above, AB doesn't necessarily = e. Since you have (AB) after C, then in this case, (AB)≠e, and your 3rd line is not true.





JBCM627 said:


> A = [U r U', l']
> B = [l, F r' F']
> C = [l', U r U]


Do you deny that AB=e? (left-to-right composition)

If so, please explain how you can have a group where AB=e sometimes and AB≠e at other times.


----------



## qqwref (Mar 15, 2009)

JBCM, please go look up some basic facts about group theory. The stuff Lucas is talking about is very basic group identities... and the fact that you're trying to dispute (mathematically) obvious points shows that you don't really understand what a group is.


----------



## JBCM627 (Mar 16, 2009)

Lucas Garron said:


> Lucas Garron said:
> 
> 
> > A = [U r U', l']
> ...


In some cases, yes, AB=e. But do AB on almost any randomly scrambled cube, and AB will not = e.

I will ask one of my teachers to clarify this, I guess.


----------



## Lucas Garron (Mar 16, 2009)

JBCM627 said:


> Lucas Garron said:
> 
> 
> > Lucas Garron said:
> ...


Exactly. This cannot happen if the 4x4x4 is a group.


----------



## cuBerBruce (Mar 16, 2009)

There are generally considered to be approximately 7.4*(10^45) positions for the non-supercube 4x4x4 (or 24 times that many if you consider the orientation of the cube to matter). qqwref (and Lucas) are correctly claiming that these positions do not map 1-to-1 with the elements of a group in the same way that the positions of the 3x3x3 map to elements of a group.

JBCM627 is looking at the permutation effects that move sequences can have on the 4x4x4 as group elements. Of course, this requires many more group elements than 7.4*(10^45), and really models the 4x4x4 supercube group rather than just the states that the 4x4x4 can have when centers that belong on the same face are considered to indistinguishable from each other. 

To have a group theory model of the 4x4x4 (non-supercube), JBCM627's approach needs to be modified to reduce the number of states to the actual number of 4x4x4 states. (As qqwref and Lucas point out, this will not actually be a group.)

You could take the subgroup of the 4x4x4 supercube group that fixes corners, fixes edges, and only permutes centers within the same face. Let's call this subgroup H, and the 4x4x4 supercube group G. You could then model the non-supercube 4x4x4 positions as a coset space formed by G/H. I note that there is a parity constraint between corners and centers in the supercube. Since H has the corners fixed, the centers in H must have even parity, so H only contains (|S_4|^6)/2 (95551488) elements. The number of ways the centers can be permuted (for the supercube) is |S_24| = 24!, but half of these positions require the corners to be in an odd parity configuration. So the number of non-supercube positions of the centers is |A_24|/|H| or (24!/2)/((4!^6)/2) = 24!/(4!^6). So basically the 4x4x4 (non-supercube) is a coset space rather than a group. I have to think this is the concept mande had in mind when saying "quotienting the group."

There is also the issue of positions differing only by cube orientation. One way of handling that is to only consider generators for the supercube group that keep one of the cubies (such as the DBL corner) fixed. So using <U,u,d,Uud',R,r,l,Rrl',F,f,b,Ffb'> for instance rather than <U,u,d,D,R,r,l,L,F,f,b,B> to define the supercube group will avoid redundant positions due to cube orientations.


----------



## TMOY (Mar 17, 2009)

cuBerBruce said:


> Since H has the corners fixed, the centers in H must have even parity, so H only contains (|S_4|^6)/2 (95551488) elements. The number of ways the centers can be permuted is |S_24|/(|S_4|^6) but half of these positions require the corners to be in an odd parity configuration.


You're counting the parity constraint twice here. In fact every one of the |S_24|/(|S_4|^6) centers permutations can be reached with the corners being in an even parity configuration.


----------



## cuBerBruce (Mar 17, 2009)

TMOY said:


> cuBerBruce said:
> 
> 
> > Since H has the corners fixed, the centers in H must have even parity, so H only contains (|S_4|^6)/2 (95551488) elements. The number of ways the centers can be permuted is |S_24|/(|S_4|^6) but half of these positions require the corners to be in an odd parity configuration.
> ...



Oops, thanks. The supercube centers have |S_24| permutations with only half reachable with the corners in an even parity configurations. But the number of configurations of the non-supercube centers is 
|S_24|/(|S_4|^6) regardless of the corner parity. Or |A_24|/|H|.


----------



## mande (Mar 17, 2009)

cuBerBruce said:


> You could take the subgroup of the 4x4x4 supercube group that fixes *centers*, fixes edges, and only permutes centers within the same face. Let's call this subgroup H, and the 4x4x4 supercube group G. You could then model the non-supercube 4x4x4 positions as a coset space formed by G/H
> So basically the 4x4x4 (non-supercube) is a coset space rather than a group. I have to think this is the concept mande had in mind when saying "quotienting the group."



I guess you meant corners there...anyway, thanks a lot for the explanation . I seemed to assume that H was normal in G, thus assuming G/H to be a group, but as it isn't normal I now realize that G/H will just be a coset space as you mentioned.


----------



## MatsBergsten (Apr 11, 2009)

*Parity on the 4x4*

We had a 4x4BLD scramble that at least three of us tried. Mike noted that he had double parity. I got that too.

BUT, and here you theorists may help, CAN YOU SKIP PARITY JUST BY CHOOSING
another orientation of the cube? I did not think so. For corners I have tried and failed (both practically and mentally). (When you solve corners you don't alter the permutation of the centers, or maybe you could?) Corner (OLL) parity in a solve is in the scramble (permutation of the corners), not in the orientation of the cube. Am I not right? 

As for edges I am not as sure? When I solve centers I choose commutator from what
feels most convenient (both regarding setup moves and actual execution). So maybe you can fix edge parity by just choosing the right center solving methods. As bld solving centers (and corners and edges) means NOT affecting anything else edge parity is preserved.


----------



## qqwref (Apr 11, 2009)

Well, the question is: can you do a cube rotation and change the parity of edges or corners? We only need to consider (say) an x rotation since every rotation can be made out of 90-degree rotations around a face.

So what does an x rotation do? Well, for centers it does 6 4-cycles, for edges it does 6 4-cycles, and for corners it does 2 4-cycles. So actually the rotation won't change the parity of any orbit. If you have parity you pretty much just have to deal with it (although of course you could always try a u premove).


----------

