# What is Group Theory and How Does It Apply to the Rubik's Cube?



## V-te (Nov 16, 2009)

Hello,
I was wondering around the internet and came across this http://en.wikipedia.org/wiki/Group_theory What exactly is Group Theory and how does it apply to the cube? I've been curious but never enough to consider about it until now. 
A nice explanation would help. 
Thank you. =)


----------



## miniGOINGS (Nov 16, 2009)

I just googled the exact tittle of your thread and got some good hits.


----------



## V-te (Nov 16, 2009)

But I still don't understand what Group theory is exactly. Can anyone please explain it?


----------



## miniGOINGS (Nov 16, 2009)

dictionary.reference.com said:


> *Group Theory*
> _–noun_
> The branch of mathematics that deals with the structure of mathematical groups and mappings between them.



That's pretty much it.


----------



## Stini (Nov 16, 2009)

Some useful sites:
http://www.jaapsch.net/puzzles/theory.htm
http://www.jaapsch.net/puzzles/groups.htm
http://www.ryanheise.com/cube/theory.html


----------



## eastamazonantidote (Nov 16, 2009)

The rubik's cube is a group. By performing certain operations in a certain order, you can find the solution.

http://en.wikipedia.org/wiki/Group_(mathematics)

There is a picture of a cube on the page. Nice article but maybe a bit complex.


----------



## hawkmp4 (Nov 17, 2009)

http://www.speedsolving.com/forum/showthread.php?t=4908
This thread may give you some useful information.


----------



## nigtv (Nov 19, 2009)

http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html

Learning HTA helped a lot with my understanding of group theory. Try it out!

EDIT: People are mean in this thread! (even though google is a good idea...)...it's a pretty simple concept that's sort of hard to explain uhm...basic idea is that if you have a solved cube, and you only turn sides 180 degrees, doesn't matter how much you scramble, you will always be able to solve it using only only 180 degree turns. This expands to opposite faces too (RFLB only 180 UD any turn) will always be solvable with those some turns.

By bringing the cube into a lower (or higher, I forget) group, you can make it a little easier to solve I guess. HTA is a pretty concrete example of how it applies to the cube, so I'd look at that.


----------



## Cangurino (Dec 2, 2009)

Group Theory is a branch of Mathematics that studies groups. Here, "group" has a very specific, mathematical meaning, which is an abstraction of common mathematical objects. Integers form a group under addition; rational numbers (or fractions) distinct from 0 form a group under multiplication; permutations form a group under composition.

In essence group consists of a set of objects (for example, numbers), and a binary operation (for example, multiplication). We need to be able to multiply any two elements in our set and get another element as a result. Further requirements are the existence of a neutral element that leaves any number unchanged via multiplication, and the existence of inverses, in the sense that if you multiply a number by its inverse you obtain the neutral element. (Another requirement, associativity, is quite natural, but it's not very intuitive to explain. Basically it says that (x*y)*z=x*(y*z) ).

In the case of integers and addition, the neutral element is 0 (since 0+x = x for any x), and the inverse is the negative (since x+(-x)=0). 

In the case of non-zero rationals and multiplication, 1 is the neutral element (since 1*x=x), and the inverses are reciprocals (since x*(1/x)=1 for any x). Here we see that we have to exclude 0 since we can't form 1/0.

Permutations are invertible mappings or functions from a set onto itself. If you take the set {1,2,3,4} you can map 1->2, 2->3, 3->1, and 4->4. This defines a permutation. Permutations can be "multiplied" by composition, that is, if g and h are permutations of the same set, g*h is the permutation that is obtained by performing first g, and then h. So if g is the permutation above, then g*g would map 1 to 3 (1->2 and 2->3), and so on.

All permutations of a given set form a group, since the function that maps any element to itself acts as a neutral element, and we required that each permutation be invertible, hence we have the existence of inverses. This group is known as the "symmetric group" (of the given set).

Any subset of a symmetric group that is itself a group is called a "permutation group", since it is a group formed by permutations. Permutation group theory forms an important branch of general group theory since these groups are quite concrete (we know exactly what the elements look like), yet general enough that most groups can be represented as permutation groups. In particular this is true for all finite groups.

Given a set of permutations we can consider the smallest group which contains them. We call that the group generated by those permutations.

Now what does this have to do with cubing?? If you take your 3x3x3 and perform a U turn you move the stickers around. If this is your U side
123
456
789
then 1 gets moved to 3, 3 to 9, 9 to 7, and 7 to 1; similarly for the edge stickers, and stickers on four other sides of the cube. In other words, U is a permutation of the set of all stickers. Of course the same is true for all other moves. Now, any algorithm, say UR'U, is nothing else but a composition of elementary moves, so again it will be a permutation. What we are interested in when solving the cube is to find a permutation with restores the cube to its pristine state. So we are actually working within the permutation group which is generated by {U,R,L,D,F,B}. 

For a mathematician, this group holds the essence of the cube. We know it's a permutation group with 43 gazillion elements. So cubing is really just applied permutation group theory. The particular problem of solving the cube, i.e., expressing a given element using a restricted set of generators, is know as the "Word Problem", and is quite intractable in general.

Hope this helps.


----------



## nigtv (Dec 4, 2009)

That's a very complex post, interesting, good explanation. Maybe this isn't exactly in 'group theory' but can you explain how having say a single edge flipped (by taking a single piece out and flipping it), or some other such 'impossible' permutation/orientation (on a 3x3) violates the concepts you've explained? 

Also, this is more just something I'm wondering than something I want an answer to, but I'm wondering what can be said about symmetry between groups, mainly how often they occur (if at all) and how applicable they are to solving (say, with HTA?). Is symmetry the right word? Maybe you get what I'm saying, a position which belongs to two distinct groups (are groups mutually exclusive?)

EDIT: It seems strange to me that a position that is in {U2,D2,B2,F2,L2,R2} could also belong (I think) to {U,D,B,F,L,R} and maybe also any other group. When you say it belongs to the former, are you assuming that it belongs to all sub-groups within it, or that those are irrelevant, or what?

Second stupid question edit: If a cube is in that former group (all 2 turns), could it be solved using only commutators that also fit into that group? I'm going to be trying this out...


----------



## Cangurino (Dec 4, 2009)

nigtv said:


> That's a very complex post, interesting, good explanation. Maybe this isn't exactly in 'group theory' but can you explain how having say a single edge flipped (by taking a single piece out and flipping it), or some other such 'impossible' permutation/orientation (on a 3x3) violates the concepts you've explained?



It does not exactly violate the concepts of group theory. Maybe I should make it a bit clearer what I mean by a "generated subgroup". I said that the group generated by a set of elements is the smallest group containing all these elements. This is not very intuitive; a better way to look at it is to say that this group contains all elements that can be obtained by multiplying the generators and their powers and inverses. So, the group generated by U and R also contains R'UR. It does not however contain, say, D.

To distinguish a set of elements from the group it generates I use curly braces for sets, and angle brackets for generated groups. So the group generated by {U,R} is denoted by <U,R>. Hence, the whole group of the cube is <U,R,L,D,F,B>.

Note that for a given group there is no unique set of generators. You could also write the same group as, say <U,R'U'R,L,D',F>.

Now the "parity" problem of a single flipped edge that you referred to simply states that the permutation that flips a single edge is not contained in this group. In other words, it cannot be written as a product of the original generators. So if we face such a situation we can't solve it legally (i.e., without disassembling the cube). 

I don't know a proof of this fact right now, but my guess is that it's a bit more involved. Something along the lines of defining orientation for edges even if they are not permuted correctly, and then showing that each of the generators changes the orientation of an even number of edges. Thus you can never arrive at a situation where an odd number of edges is oriented incorrectly.





nigtv said:


> Also, this is more just something I'm wondering than something I want an answer to, but I'm wondering what can be said about symmetry between groups, mainly how often they occur (if at all) and how applicable they are to solving (say, with HTA?). Is symmetry the right word? Maybe you get what I'm saying, a position which belongs to two distinct groups (are groups mutually exclusive?)



Groups are certainly not mutually exclusive. Take the group <R2>, which has two elements, namely {id, R2}, where id is the neutral element, i.e., the permutation that doesn't change anything. Now look at the group <R> which contains the elements {id, R, R2, R'}. We see that these two groups share two elements, id and R2. In fact, <R2> is fully contained in <R>, hence we call it a subgroup of <R>.

One interesting fact to note is that the _intersection_ of two groups, that is, the collection of elements which belong to both, forms again a group. 

Not sure if I answered your question. But certainly a given configuration can belong to several groups.



nigtv said:


> EDIT: It seems strange to me that a position that is in {U2,D2,B2,F2,L2,R2} could also belong (I think) to {U,D,B,F,L,R} and maybe also any other group. When you say it belongs to the former, are you assuming that it belongs to all sub-groups within it, or that those are irrelevant, or what?




If you change the notation to <U2,D2,B2,F2,L2,R2> and <U,D,B,F,L,R>, then yes, an element can belong to both of them. In fact, since the first is a subgroup of the second, any element in the first group also belongs to the second one.

For the second part you have it backwards. If an element is contained in one group, then it is also contained in all overgroups (which is just the opposite of subgroups).



nigtv said:


> Second stupid question edit: If a cube is in that former group (all 2 turns), could it be solved using only commutators that also fit into that group? I'm going to be trying this out...



This is a property specific to the group in question, and I don't know the answer (but I'm going to find out). For the whole group <U,D,B,F,L,R> it is true, at least if you use "commutator" in the mathematical sense. So, any scramble can be written in the form xyx'y' for an appropriate choice of algorithms x and y.


Edit: Actually what I wrote in the previous paragraph is incorrect. What is correct is that any scramble can be solved using a sequence of commutators. For the half turn subgroup this is not the case. For example, U2 can't be solved using commutators made up of half moves.


----------



## Tim Reynolds (Dec 4, 2009)

Cangurino said:


> This is a property specific to the group in question, and I don't know the answer (but I'm going to find out). For the whole group <U,D,B,F,L,R> it is true, at least if you use "commutator" in the mathematical sense. So, any scramble can be written in the form xyx'y' for an appropriate choice of algorithms x and y.
> 
> 
> Edit: Actually what I wrote in the previous paragraph is incorrect. What is correct is that any scramble can be solved using a sequence of commutators. For the half turn subgroup this is not the case. For example, U2 can't be solved using commutators made up of half moves.



Careful, commutators can only be even permutations.

Also, I'm not sure I believe that any even scramble in <U,D,B,F,L,R> can be written as a commutator. Product of commutators, maybe, but I'm not so sure about pure commutators. Proof?


----------



## nigtv (Dec 5, 2009)

By the commutator thing, what I meant to say was not "Can any position be solved using commutators", although I suppose it's also applicable. I mean can a cube in *2 (its hell to write out the sets) ALWAYS be solved using commutators consisting only of turns that do not cross out of the group. 

I personally don't think so, but who knows, could be way off. Thanks again for the posts, very informative!


----------



## Cangurino (Dec 5, 2009)

Tim Reynolds said:


> Careful, commutators can only be even permutations.
> 
> Also, I'm not sure I believe that any even scramble in <U,D,B,F,L,R> can be written as a commutator. Product of commutators, maybe, but I'm not so sure about pure commutators. Proof?



Hmm, looks like you're right. What I did was take the group G=<U,D,B,F,L,R> and computed its derived subgroup G'. I got that G'=G. However, since U is an odd permutation (consisting of 5 4-cycles in its action on stickers) something's wrong. I'm gonna look into that.

And yes, I meant that every scramble can be expressed as a product of commutators.


----------

