# The Unapologetic Mathematician

## 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

## 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 $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.

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

## 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?

February 24, 2007

## 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

## 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.

February 23, 2007

## 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?

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