## Rubik’s Group notation

Today I want to introduce some notation for discussing the cube.

Take a cube — either a real one, the Java version, or just one in your mind’s eye — and hold it with the center cubies fixed in place pointing up, down, left, right, front, and back. Twists of the faces will generate Rubik’s goup . We pick the six generators as follows

- is a twist of the upper face by a quarter turn clockwise, looking down at the top of the cube.
- is a twist of the lower face by a quarter turn clockwise, looking up at the bottom of the cube.
- is a twist of the right face by a quarter turn clockwise, looking left at the right side of the cube.
- is a twist of the left face by a quarter turn clockwise, looking right at the left of the cube.
- is a twist of the front face by a quarter turn clockwise, looking at the front of the cube.
- is a twist of the back face by a quarter turn clockwise, looking at the back of the cube.

For instance, executing involves turning the whole cube around to look at the back, twisting that face clockwise by 90°, and turning the cube back to the original orientation.

For each twist , the 180° twist of the corresponding face is , and the *anti*clockwist twist is . Four quarter-twists is the same as doing nothing, so is the identity.

It’s also useful to label the cubicles. I’ll do this by listing the faces it touches. The face cubicle on the left side of the cube is , the lower edge on the back ls or . The upper-right corner on the front of the cube is , , , , , or . The order of the faces doesn’t matter so much for a single cubicle, but becomes important when we start thinking about how maneuvers affect the state of the cube.

For instance, the effect of the maneuver has an effect on the cube I’ll write as . This takes the cubie in the front-right cubicle and puts it in the back-left cubicle, with the facelet that was in the front now in the back and the facelet from the right now on the left. It takes the cubie from the back-left cubicle and puts it in the back-right cubicle with the facelet from the back still on the back and the facelet from the left now on the right. Finally it takes the cubie from the back-right and moves it to the front-right with the right facelet still on the right and the back facelet now on the front.

As another example, takes the cubie from the upper-right-front cubicle and leaves it where it is, but twists it to the right, and similarly twists the cubie in the lower-left-back cubicle. We write this transformation as . For shorthand we’ll modify this permutation notation slightly. When a cycle brings a cubie back to its starting cubicle but rotated, we add a sign. In this example we’ll write , since if we look directly at the upper-right-front cubie it’s been rotated clockwise by 1/3 of a turn and looking directly at the lower-left-back it’s been rotated anticlockwise by 1/3 of a turn.

This notation does make sense. Let’s say that we have a maneuver whose effect contains some cycle on the corners of the cube of length . If we apply that maneuver times each cubie in the cycle comes back where it started, but the cubies may have been twisted in the process. Each one will be twisted by the same amount: either 1/3 to the right, 1/3 to the left, or untwisted. The sign in the notation tells us what that twist is.

The same notation goes for edges. The maneuver has effect , flipping those four edges. We could write this out as , but the “twisted permutation” notation is more compact.

From this notation it’s easy to compute the order of a maneuver — what power of the maneuver returns to the identity transformation. A corner cycle of length has order if there’s no twist, and order if there is a twist. Similarly, an edge -cycle has order if there’s no flip and order if there is a flip. So if we write the effect of a maneuver as a twisted permutation we can find the order of each twisted cycle. The order the the whole maneuver is the least common multiple of those orders.

As an example, consider the maneuver . This has effect . The three twisted cycles have orders 3, 15, and 7, so the total order is 105. If you actually sit and perform you’ll get back exactly where you started.

## Done TeXing

I’ve finished converting all the old entries to TeX. Oddly I found that I’m *not* allowed to use < in TeX formulæ. Anyhow, the flood of updates on the feed should stop.

## Direct Products of Groups

There are two sorts of products on groups that I’d like to discuss. Today I’ll talk about direct products.

The direct product says that we can take two groups, form the Cartesian product of their sets, and put the structure of a group on that. Given groups and we form the group as the set of pairs with in and in . We compose them term-by-term: . It can be verified that this gives us a group.

There’s a very interesting property about this group. It comes equipped with two homomorphisms, and , the “projections” of onto and , respectively. As one might expect, , and similarly for . Even better, let’s consider any other group with homomorphisms and . There is a unique homomorphism — defined by — so that and . Here’s the picture.

The vertical arrow from to is , and I assert that that’s the only homomorphism from to so that both paths from to are the same, as are both paths from to . When we draw a diagram like this with groups on the points and homomorphisms for arrows, we say that the diagram “commutes” if any two paths joining the same point give the same homomorphism between those two groups.

To restate it again, has homomorphisms to and , and any other group with a pair of homomorphisms to and has a *unique* homomorphism from to so that the above diagram commutes. This uniqueness means that has this property is unique up to isomorphism.

Let’s say two groups and have this product property. That is, each has given homomorphisms to and , and given any other group with a pair of homomorphisms there is a unique homomorphism to and one to that make the diagrams commute (with or in the place of ). Then from the diagram with in place of we get a unique homomorphism . On the other hand, from the diagram with in place of , we get a unique homomorphism . Putting these two together we get homomorphisms and .

Now if we think of the diagram for with *itself* in place of , we see that there’s a unique homomorphism from to itself making the diagram commute. We just made one called , but the identity homomorphism on also works, so they must be the same! Similarly, must be the identity on , so and are inverses of each other, and and are isomorphic!

So let’s look back at this whole thing again. I take two groups and , and I want a new group that has homomorphisms to and and so any other such group with two homomorphisms has a unique homomorphism to . Any two groups satisfying this property are isomorphic, so if we can find *any* group satisfying this property we know that any other one will be essentially the same. The group structure we define on the Cartesian product of the sets and satisfies just such a property, so we call it the direct product of the two groups.

This method of defining things is called a “universal property”. The argument I gave to show that the product is essentially unique works for any such definition, so things defined to satisfy universal properties are unique (up to isomorphism) if they actually exist at all. This is a viewpoint on group theory that often gets left out of basic treatments of the subject, but one that I feel gets right to the heart of why the theory behaves the way it does. We’ll definitely be seeing more of it.

## TeX comes to WordPress!

I just noticed that WordPress has added Tex support. This will make my life a lot simpler, and it may even work in the comments. Now to go back and change all the *G* to and so on. Fun!

## Generators and Relations

Now it’s time for the reason why free groups are so amazingly useful. Let be any set, be the free group on , and be any other group. Now, every function from into extends to a unique *homomorphism* . Just write down any word in , send each letter into like the function tells you, and multiply together the result!

So what does this get us? Well, for one thing every group is (isomorphic to) a quotient of a free group. If nothing else, consider the free group on the set of itself. Then send each element to itself. This extends to a homomorphism from to whose image is clearly all of . Then the First Isomorphism Theorem tells us that is isomorphic to . That’s pretty inefficient, but it shows that we *can* write like that if we want to. How can we do better?

Continue reading

## A few more facts about group actions

There’s another thing I should have mentioned before. When a group acts on a set , there is a bijection between the orbit of a point and the set of cosets of in . In fact, if and only if if and only if is in if and only if . This is the the bijection we need.

This has a few immediate corollaries. Yesterday, I mentioned the normalizer of a subgroup . When a subgroup acts on by conjugation we call the isotropy group of an element of the “centralizer” of in . This gives us the following special cases of the above theorem:

- The number of elements in the conjugacy class of in is the number of cosets of in .
- The number of subgroups conjugate to in is the number of cosets of in .

In fact, since we’re starting to use this “the number of cosets” phrase a lot it’s time to introduce a bit more notation. When is a subgroup of a group , the number of cosets of in is written . Note that this doesn’t have to be a finite number, but when (and thus ) is finite, it is equal to the number of elements in divided by the number in . Also notice that if is normal, there are elements in .

This is why we could calculate the number of permutations with a given cycle type the way we did: we picked a representative of the conjugacy class and calculated .

One last application: We call a group action “free” if every element other than the identity has no fixed points. In this case, is always the trivial group, so the number of points in the orbit of is is the number of elements of . We saw such a free action of Rubik’s Group, which is why every orbit of the group in the set of states of the cube has the same size.

## Conjugacy classes in symmetric groups

Let’s work out how symmetric groups act on themselves by conjugation. As I’m writing I notice that what I said before about composition of permutations is sort of backwards. It’s one of those annoying conventions that doesn’t really change anything, but can still be a bit confusing. From here on when we write permutations in cycle notation we compose by reading the cycles *from right to left*. That is, . Before I was reading them left to right. The new way behaves more like group actions. The exposition comes after the jump.

Continue reading

## Carny Folk

So the second Carnival of Mathematics is up at Good Math, Bad Math. My first post on Rubik’s Cube is up there, as well as one about algebraic topology at UM regular Mikael Johansson’s place, and one on permutation cycle types at The Universe of Discourse.

That last topic is actually really monumentally important, and I’ll be getting back to it after class and the graduate student seminar today.

## Outer billiards has an unbounded orbit

This just popped up on the arXiv, so I thought I should mention it: Richard Schwartz has a paper up showing that there is a shape for an “outer billiards” table and a starting point whose path gets as far away from the shape as you want. Even better, it’s one of the shapes from the Penrose tiling. Curiouser and curiouser. The first section or so of the paper are very readable, and gives a much better explanation (with pictures!) of outer billiards than I could manage. The proof itself is heavily aided by computer calculations, but seems to be tightly reasoned apart from needing help to handle a lot of cases.

I’m not quite sure how billiards and outer billiards are related. My intuition is that there’s some sort of duality going on, which would exchange lengths of segments in outer billiards with angles in billiards. On the other hand, if there were such a straightforward translation, couldn’t the enormous machinery of billiards have been brought to bear on this problem before now? Do any billiard theorists in the audience know anything about outer billiards?

## Conjugation

One of the most useful examples of a group acting on a set comes directly from group theory itself. Let be a group and be a subgroup of . The subgroup acts on the set of all subgroups of as follows.

If is any subgroup of and is any element of , then the set of elements of of the form with in is another subgroup of . Indeed, if we take two elements and of this set, their product is , which is again of the proper form since is in . We call this subgroup the conjugation of by .

Given two elements of we can check that , so conjugating by is the same as conjugating by , then by . That is, this defines an action of on the set of all subgroups of .

Even better, is not just another subgroup of , it is isomorphic to . In proving that is a subgroup we showed that the function sending to is a homomorphism. We can undo it by conjugating by , so it’s an isomorphism. We say that two subgroups of related by a conjugation are conjugate.

The subgroup of sending to itself — those in so that — is called the normalizer of in , written . We can verify that is a normal subgroup in , and that is normal in exactly when .

One orbit is particularly interesting to consider: is always sent to itself by conjugation. That is, given an element of the homomorphism sending to is an automorphism of . In fact, given any group , the automorphisms of *themselves* form a group, called . Conjugation gives us a homomorphism from to : given an element , is the automorphism of conjugation by .

We call automorphisms arising in this way “inner automorphisms”. The group of inner automorphisms on is the image of in . If is an element of and is any automorphism of , then is the automorphism sending in to

Which is just conjugation of by . This proves that is normal in . The quotient is the group of outer automorphisms .

The kernel of is the set of elements so that for all in G. That is, for any we have , so the kernel of is the subgroup of consisting of elements that commute with *every* element of . We call this subgroup the center of .

Now, consider the group of permutations on letters. Determine how this group acts on itself by conjugation. Write out some conjugations in cycle notation to get an idea of what the answer should be.