Intro to group theory

[hawkmp4]

I have a pretty good background in math (for a high school student) I've taken AP Calc AB.
But all of the sites I've found on group theory are way over my head. Could anyone link me to some kind of resource where I could learn enough group theory to at least get the concepts and apply some to the cube? If not that's fine, it may be just too much at this point in my education.

 

[cuBerBruce]

If you haven't tried these sites, you might give them a try. They both talk about group theory in relation to Rubik's Cube and other similar puzzles.

On Jaap's Puzzle Page web site, there is:
http://www.geocities.com/jaapsch/puzzles/groups.htm

It might be a little more advanced, but there is also David Joyner's Rubik's Cube course notes, that now can be found at this location:
http://www.permutationpuzzles.org/rubik/webnotes/

An extended version of this is available as a book (Adventures in Group Theory).

 

[It3ration]

I'd recommend the Ryan Heise method. He explains basic group theory and it's applications in cubing on his site.

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

 

[badmephisto]

I would recommend you get an actual Book, not an internet site. These kinds of things are better to study that way. Look for a library close to you or something with a math section.

 

[ubervern]

I just finished a BS in math with 6 credit hours specifically in group theory, and for almost all of it I have ever seen I either cannot understand it or I do not see how it would help anyone solve a cube.
Permutations and cycles are applicable but they are not really group theory.
The problem with a cube in group theory is that it only qualifies as a group via permutations, and there is no simple relation between a face turn and the effect it has upon a permutation (computers can track that stuff but not me). The first rule of a group is that it must be associative, ie (a • b) • c = a • (b • c) but this is not true in general for face turns of a cube, thus face turns are not the operators of a rubik's group and group theory doesn't help a solution very much, but since any permutation is a group, there are a few simple observations that can be made, as Ryan states clearly on his site. (actually I didn't see one of the most reassuring statements from group theory: as a finite group a rubik's cube is guaranteed to have a solution in a finite number of steps)

There is highly developed group theory for a cube and it can help discover new algs and optimal solutions, but in general it does not help someone solve a cube.

If you really are interested in group theory, I recommend Abstract Algebra by I.N. Herstein, a very compact yet thorough text.

 

[AvGalen]

I just finished a BS in math with 6 credit hours specifically in group theory, and for almost all of it I have ever seen I either cannot understand it or I do not see how it would help anyone solve a cube.
Permutations and cycles are applicable but they are not really group theory.
The problem with a cube in group theory is that it only qualifies as a group via permutations, and there is no simple relation between a face turn and the effect it has upon a permutation (computers can track that stuff but not me). The first rule of a group is that it must be associative, ie (a • b) • c = a • (b • c) but this is not true in general for face turns of a cube, thus face turns are not the operators of a rubik's group and group theory doesn't help a solution very much, but since any permutation is a group, there are a few simple observations that can be made, as Ryan states clearly on his site. (actually I didn't see one of the most reassuring statements from group theory: as a finite group a rubik's cube is guaranteed to have a solution in a finite number of steps)

There is highly developed group theory for a cube and it can help discover new algs and optimal solutions, but in general it does not help someone solve a cube.

If you really are interested in group theory, I recommend Abstract Algebra by I.N. Herstein, a very compact yet thorough text.

Group theory is indeed not (very) usefull for finding a brute-force 1 step solution to the cube and it won't help a beginner to solve a cube. However, you have stated this yourself

...The first rule of a group is that it must be associative

. I don't really understand what that means from a formal math point of view, but for me it means that you can apply group theory if you create independent groups. And that is actually the base of how we solve the cube most of the time. (Cross/F2L/OLL/PLL can be considered independent groups)

Commutators are another obvious example where you divide the cube in several groups. Having a P-part that changes only the 1st group, have a Q-part that only changes the 2nd group and undoing P and Q so the result would still be a solved cube. If P and Q only have a very small intersection (are almost non-associative) the effect on the entire cube will be very small.

And finally group part plays a very big role in really seperate groups that are used for the 2-phase solve of Cube Explorer, The human tistlewait method and most blindfolded methods.

Almost every puzzle is solved by dividing it in groups that have either no influence on each other (think blindfolded), or you just don't care about the influence (think reduction).

 

[ubervern]

I certainly agree, but these things you call groups have very little in common with mathematical group theory. Most often people wish to assign a group to a cube state that can be obtained through specific face turns, such as all positions obtainable while restricted to L2 and R2 turns. Sometimes people assign groups via block building methods, but these are not necessarily mathematical groups and learning group theory will not help you understand these things. Cycles and permutations can help, with commutators being a method of solving a permutation, and these things are often discussed in group theory but are not restrained by the rigid definitions of a group.
Basically I am claiming that mathematicians defined the word group in such a way as to not allow people to randomly assign a section of their cube as a group. Does that make sense?

 

[Lucas Garron]

such as all positions obtainable while restricted to L2 and R2 turns.

<L2, R2>
I love that 2-gen!

Basically I am claiming that mathematicians defined the word group in such a way as to not allow people to randomly assign a section of their cube as a group. Does that make sense?

What's that mean. U, F, and R generate a group, right?

And who can stop me from calling the M-slice a group of 8 pieces?
(Arbitrarily, people, not randomly!)

 

[ubervern]

If you took a solved cube and limited the face turns, such as only doing M turns, you would have a sub-group of the rubiks group, so you can call the M slice a group, but it isn't very interesting. If you took a scrambled cube and limited face turns, then you obtain a subgroup of a permutation of the rubrik's group, but since it does not necessarily contain the solved position, which is the identity of the rubrik's group, it is not necessarily a sub-group of the rubrik's group. I think the parity issues of blind solves and larger cube solves exemplify this perfectly.

 

[badmephisto]

well you can use the concepts from group theory to prove all kinds of useful (non-intuitive) conjectures about rubik's cubes, such as the fact that you cannot make odd number of swaps. I wouldn't go as far as to suggest that it is not something worth looking into.

 

[cuBerBruce]

The problem with a cube in group theory is that it only qualifies as a group via permutations, and there is no simple relation between a face turn and the effect it has upon a permutation (computers can track that stuff but not me).

I'm not sure what you are really getting at here.

From Cayley's theorem (see http://en.wikipedia.org/wiki/Cayley's_theorem ), it is known that all groups can be thought of as equivalent to some permutation group. The Rubik's cube group can be considered equivalent to a permutation group describing how the of the 48 corner and edge "facelets" (mathematicians tend to use the term "facet") of the cube can be permuted.

The first rule of a group is that it must be associative, ie (a • b) • c = a • (b • c) but this is not true in general for face turns of a cube, ...

Huh? Successive application of face turns is definitely associative. (U F) R = U (F R), for example. Doing U followed by F R is the same as doing U F followed by R. It is associative! Incidently, sometimes the group operation for Rubik's cube has been described as "followed by." U F R means U followed by F followed by R. (This seems to be rather informal to me. The group operation basically describes how an ordered pair of elements of the group can be combined to produce another element of the group.)

 

[ubervern]

order of operations, PEMDAS: (U F) R means do U then F, then R. U (F R) means do parenthesis first, so do F then R then do U, clearly non-associative. If you used the "is followed by" method then associativity would be trivial, everything would be associative. In most systems (such as typical multiplication) you can cheat order of operations and continue working left to right, but this is because the operation is commutative, which is again not true for the rubrik's cube (F R is not the same as R F). When you look at U (F R) and do U first you have just cheated order of operations and commutated the elements. It will never get you in trouble with real numbers, but is quite wrong here.

All groups are isomorphic to some permutation group, but the "rubrik's group" is a permutation group, so again the statement is trivial. The only group operation I know of for the cube is a permutation. These confusions are the basis of my point, group theory is not easily nor naturally applied to a cube.

 

[badmephisto]

order of operations, PEMDAS: (U F) R means do U then F, then R. U (F R) means do parenthesis first, so do F then R then do U, clearly non-associative. If you used the "is followed by" method then associativity would be trivial, everything would be associative. In most systems (such as typical multiplication) you can cheat order of operations and continue working left to right, but this is because the operation is commutative, which is again not true for the rubrik's cube (F R is not the same as R F). When you look at U (F R) and do U first you have just cheated order of operations and commutated the elements. It will never get you in trouble with real numbers, but is quite wrong here.

All groups are isomorphic to some permutation group, but the "rubrik's group" is a permutation group, so again the statement is trivial. The only group operation I know of for the cube is a permutation. These confusions are the basis of my point, group theory is not easily nor naturally applied to a cube.

I could be wrong but I am going to side with cuberbruce on this one. It seems to me like you are confusing commutativity with associativity. And it is not true that associativity is trivial in all circumstances. Consider this simple example:
5-(3-2) != (5-3)-2

Something that means do F R first then U is simply just F R U, not U (F R). In other words it is my belief that moves on the rubik's cube are indeed associative but need not commute.

 

[JBCM627]

order of operations, PEMDAS: (U F) R means do U then F, then R. U (F R) means do parenthesis first, so do F then R then do U, clearly non-associative.

I could be wrong but I am going to side with cuberbruce on this one. It seems to me like you are confusing commutativity with associativity.

Ubervern or someone correct me if I am wrong. I think his point was that you still need to stick to order of operations when considering associativity. Operations in parentheses are always done first in a math equation; you simply have the luxury of ignoring this when working with pure numbers.

This may seem counterintuitive, as algorithms are time dependant, and so you are also used to reading cubing algorithms from left to right and generally ignoring ()'s. I think ubervern is considering permutations instead of algorithms because of this. As permutations are not time dependant, think of this as the end result of executing the moves A(BC), referring to order of operations as a reference for what moves to perform first; 'left to right' taking lower precedence than the order in which you should do the operations.

Of course, this is from a purely mathematical standpoint. You would *not* do this while reading it as an algorithm (time dependent), instead of a permutation (time independent).

So for practical purposes, we can define our own operations, based on time, giving it precedence over all other operations. Now operations should be read in chronological order, before considering temporally invariant operations. If the operator "A•B" means "Do A before considering B", then A•B•C translates to: do A, then do B, then do C. A•(B•C) means the same thing, as does (A•B)•C. Thus algorithms are associative.

 

[Swordsman Kirby]

"rubrik's group"

Stop it!!!

 

[JBCM627]

"rubrik's group"

Stop it!!!

Yes indeed.

 

[Stefan]

U (F R) means do parenthesis first, so do F then R then do U, clearly non-associative.

This caused my best laugh today. I have this theory that your "BS" in math doesn't stand for bachelor of science.

 

[ubervern]

U (F R) means do parenthesis first, so do F then R then do U, clearly non-associative.

This caused my best laugh today. I have this theory that your "BS" in math doesn't stand for bachelor of science.

Perhaps I am not very good at making clear explanations, but that is no reason to throw out insults.

Let me explain this in as simple terms as I can:
First a set is defined. This can be any list of objects, preferably with something in common.
Then an operation is defined. This can be anything from simple addition to the assembly of a computer.
Once these are established it is possible to begin to determine if the set with the defined operation satisfies the requirements of a group.

Associativity is defined, as I stated earlier, (X*Y)*Z = X*(Y*Z). A set, with the defined operation, is considered associative if it satisfies the above for ALL X, Y, Z in the set.
Example: addition is associative, (5+2)+3 = 5+(2+3) True
Example: division is NON-associative, (6/3)/2 = 6/(3/2) false. For the Left hand side, 6/3 is 2. 2/2 is one. For the right, 6 is to be divided by 3/2, or 1.5, yielding 4.

For the cube, it becomes difficult to define the specific operation using face turns, simply because group theory does not formally allow different operations such as F, R, and U, or even +, -, x. (this is yet another reason it is difficult to apply group theory to a cube). I am uncertain how to get around this, but assuming it was figured out, the face turns are still non associative.

 

[JBCM627]

Ok, children... be nice. Uber, read this.

 

[cuBerBruce]

For the cube, it becomes difficult to define the specific operation using face turns, simply because group theory does not formally allow different operations such as F, R, and U, or even +, -, x. (this is yet another reason it is difficult to apply group theory to a cube). I am uncertain how to get around this, but assuming it was figured out, the face turns are still non associative.

ubervern, since you see U, F, R, etc. as "operations," you seem to be trying to relate them to an operation for a group. This seems to be why you don't see the natural relationship between Rubik's Cube and group theory.

Two things that are necessary to have a group are a set and an operation (the "group operation"). And yes, you are correct in that a group has *one* group operation, not several. In the Rubik's Cube group, the "operations" U, F, R, D, B, and L are not group operations, but elements of the set for the group. (There are 43252003274489855994 other "operations" in this set, but I won't bother listing them out. ) These operations can be thought of as "permutations." (Each such set element basically describes a way the "facelets" of Rubik's Cube can be permuted.)

Permutations can be composed. That is, a permutation can be applied to the result of another permutation. The net result of composing the two permutations (and the order you compose them is important, of course) is a third permutation. The group operation for the Rubik's Cube group is basically what I just described: composition of permutations. In this post, I will explicitly use an asterisk (*) to represent the operator for the group operation, just to be clear that the group operation is a separate concept from the face turns.

So F*R represents the result of composing R with F. U*F represents the result of composing F with U. The expression (U*F)*R means the result of composing R with the result of composing F with U. The expression U*(F*R) means the result of composing R with F, and then composing the resulting permutation with U. It happens that composition of permutations is associative. Both U*(F*R) and (U*F)*R result in the same permutation. So basically we don't need to bother with the parentheses and simply write U*F*R.