The Unapologetic Mathematician

Mathematics for the interested outsider

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 G. We pick the six generators as follows

  • U is a twist of the upper face by a quarter turn clockwise, looking down at the top of the cube.
  • D is a twist of the lower face by a quarter turn clockwise, looking up at the bottom of the cube.
  • R is a twist of the right face by a quarter turn clockwise, looking left at the right side of the cube.
  • L is a twist of the left face by a quarter turn clockwise, looking right at the left of the cube.
  • F is a twist of the front face by a quarter turn clockwise, looking at the front of the cube.
  • B is a twist of the back face by a quarter turn clockwise, looking at the back of the cube.

For instance, executing B 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 T, the 180° twist of the corresponding face is T^2, and the anticlockwist twist is T^{-1}. Four quarter-twists is the same as doing nothing, so T^4 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 l, the lower edge on the back ls db or bd. The upper-right corner on the front of the cube is urf, ufr, ruf, rfu, fur, or fru. 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 R^2U^{-1}DB^2UD^{-1} has an effect on the cube I’ll write as (fr\,bl\,br). 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, (R^{-1}U^2RB^{-1}U^2B)^2 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 (urf\,rfu\,fur)(dlb\,lbd,bdl). 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 (+urf)(-dlb), 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 k. If we apply that maneuver k 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 RUD^{-1}FUD^{-1}LUD^{-1}BUD^{-1} has effect (+ur)(+fr)(+fl)(+bl), flipping those four edges. We could write this out as (ur\,ru)(fr\,rf)(fl\,lf)(bl\,lb), 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 k has order k if there’s no twist, and order 3k if there is a twist. Similarly, an edge k-cycle has order k if there’s no flip and order 2k 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 RU. This has effect (+urf)(-ufl\,ulb\,ubr\,bdr\,dfr)(fr\,uf\,ul\,ub\,ur\,br\,dr). The three twisted cycles have orders 3, 15, and 7, so the total order is 105. If you actually sit and perform (RU)^{105} you’ll get back exactly where you started.

February 28, 2007 Posted by | Group theory, Rubik\'s Cube | Leave a comment

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.

February 28, 2007 Posted by | Uncategorized | Leave a comment

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 G and H we form the group G\times H as the set of pairs (g,h) with g in G and h in H. We compose them term-by-term: (g_1,h_1)(g_2,h_2)=(g_1g_2,h_1h_2). 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, \pi_G and \pi_H, the “projections” of G\times H onto G and H, respectively. As one might expect, \pi_G(g,h)=g, and similarly for \pi_H. Even better, let’s consider any other group X with homomorphisms f_G:X\rightarrow G and f_H:X\rightarrow H. There is a unique homomorphism f_G\times f_H:X\rightarrow G\times H — defined by f_G\times f_H(x)=(f_G(x),f_H(x)) — so that \pi_G(f_G\times f_H(x))=f_G(x) and \pi_H(f_G\times f_H(x))=f_H(x). Here’s the picture.

Universal Property of Products

The vertical arrow from X to G\times H is f_G\times f_H, and I assert that that’s the only homomorphism from X to G\times H so that both paths from X to G are the same, as are both paths from X to H. 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, G\times H has homomorphisms to G and H, and any other group X with a pair of homomorphisms to G and H has a unique homomorphism from X to G\times H so that the above diagram commutes. This uniqueness means that has this property is unique up to isomorphism.

Let’s say two groups P_1 and P_2 have this product property. That is, each has given homomorphisms to G and H, and given any other group with a pair of homomorphisms there is a unique homomorphism to P_1 and one to P_2 that make the diagrams commute (with P_1 or P_2 in the place of G\times H). Then from the P_1 diagram with P_2 in place of X we get a unique homomorphism f_1:P_2\rightarrow P_1. On the other hand, from the P_2 diagram with P_1 in place of X, we get a unique homomorphism f_2:P_1\rightarrow P_2. Putting these two together we get homomorphisms f_1f_2:P_2\rightarrow P_2 and f_2f_1:P_1\rightarrow P_1.

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

So let’s look back at this whole thing again. I take two groups G and H, and I want a new group G\times H that has homomorphisms to G and H and so any other such group with two homomorphisms has a unique homomorphism to G\times H. 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 G and H 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.

February 27, 2007 Posted by | Algebra, Group theory, Structure of Groups, Universal Properties | 13 Comments

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 G and so on. Fun!

February 25, 2007 Posted by | Uncategorized | 3 Comments

Generators and Relations

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

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

February 24, 2007 Posted by | Algebra, Group theory, Structure of Groups | 5 Comments

A few more facts about group actions

There’s another thing I should have mentioned before. When a group G acts on a set S, there is a bijection between the orbit of a point x and the set of cosets of G_x in G. In fact, gx=hx if and only if h^{-1}gx=x if and only if h^{-1}g is in G_x if and only if gG_x=hG_x. This is the the bijection we need.

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

  • The number of elements in the conjugacy class of x in G is the number of cosets of C_G(x) in G.
  • The number of subgroups conjugate to K in G is the number of cosets of N_G(K) in G.

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 H is a subgroup of a group G, the number of cosets of H in G is written \left[G:H\right]. Note that this doesn’t have to be a finite number, but when G (and thus H) is finite, it is equal to the number of elements in G divided by the number in H. Also notice that if H is normal, there are \left[G:H\right] elements in G/H.

This is why we could calculate the number of permutations with a given cycle type the way we did: we picked a representative g of the conjugacy class and calculated \left[S_n:C_{S_n}(g)\right].

One last application: We call a group action “free” if every element other than the identity has no fixed points. In this case, G_x is always the trivial group, so the number of points in the orbit of x is \left[G:G_x\right] is the number of elements of G. 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.

February 24, 2007 Posted by | Algebra, Group Actions, Group theory | 5 Comments

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, (1\,2)(1\,3)=(1\,3\,2). Before I was reading them left to right. The new way behaves more like group actions. The exposition comes after the jump.
Continue reading →

February 23, 2007 Posted by | Algebra, Group Actions, Group theory | 3 Comments

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.

February 23, 2007 Posted by | Uncategorized | Leave a comment

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?

February 23, 2007 Posted by | Billiards | 4 Comments

Conjugation

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

If K is any subgroup of G and h is any element of H, then the set hKh^{-1} of elements of G of the form hkh^{-1} with k in K is another subgroup of G. Indeed, if we take two elements hkh^{-1} and hk'h^{-1} of this set, their product is hkh^{-1}hk'h^{-1}=hkk'h^{-1}, which is again of the proper form since kk' is in K. We call this subgroup the conjugation of K by h.

Given two elements of H we can check that (hh')K(hh')^{-1}=hh'Kh'^{-1}h^{-1}, so conjugating by hh' is the same as conjugating by h', then by h. That is, this defines an action of H on the set of all subgroups of G.

Even better, hKh^{-1} is not just another subgroup of G, it is isomorphic to K. In proving that hKh^{-1} is a subgroup we showed that the function sending k to hkh^{-1} is a homomorphism. We can undo it by conjugating by h^{-1}, so it’s an isomorphism. We say that two subgroups of G related by a conjugation are conjugate.

The subgroup of H sending K to itself — those h in H so that hKh^{-1}=K — is called the normalizer of K in H, written N_H(K). We can verify that K is a normal subgroup in N_G(K), and that K is normal in G exactly when N_G(K)=G.

One orbit is particularly interesting to consider: G is always sent to itself by conjugation. That is, given an element h of G the homomorphism sending g to hgh^{-1} is an automorphism of G. In fact, given any group G, the automorphisms of G themselves form a group, called {\rm Aut}(G). Conjugation gives us a homomorphism c from G to {\rm Aut}(G): given an element g, c(g) is the automorphism of conjugation by g.

We call automorphisms arising in this way “inner automorphisms”. The group {\rm Inn}(G) of inner automorphisms on G is the image of c in {\rm Aut}(G). If g is an element of G and f is any automorphism of G, then f\circ c(g)\circ f^{-1} is the automorphism sending x in G to

f(gf^{-1}(x)g^{-1})=f(g)f(f^{-1}(x))f(g^{-1})=f(g)xf(g)^{-1}

Which is just conjugation of x by f(g). This proves that {\rm Inn}(G) is normal in {\rm Aut}(G). The quotient {\rm Aut}(G)/{\rm Inn}(G) is the group of outer automorphisms {\rm Out}(G).

The kernel of c is the set of elements g so that gg'g^{-1}=g' for all g' in G. That is, for any g' we have gg'=g'g, so the kernel of c is the subgroup of G consisting of elements that commute with every element of G. We call this subgroup the center of G.

Now, consider the group S_n of permutations on n 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.

February 22, 2007 Posted by | Algebra, Group Actions, Group theory | 7 Comments

« Previous Entries