## Rubik’s Magic Cube

Rubik’s Cube is a classic fad from the ’80s. Invented by architecture professor Ernő Rubik in 1974 as an illustration of design principles, it became an immensely popular puzzle for a while. Now it’s a hallmark of geekiness — when I visited Dartmouth I saw at least six or seven floating around the graduate student lounge.

What’s most interesting to us here is that it’s also a big case study in group theory. The official website has a pretty good Java implementation, for those who don’t remember (or who have repressed their memories of) the cube. I’ll start talking about the cube after the jump.

Continue reading

## Graduate study offer schedule

I promised a commenter that I would try to find out about Yale’s schedule for admitting graduate students, since I’m complaining about the opacity of the hiring schedule. I’ve finally managed to wrestle some information out: the first offers are going out this week. Good luck to any who have applied for our Ph.D. program.

## Group actions

Okay, now we’ve got all the setup for one big use of group theory.

Most mathematical structures come with some notion of symmetries. We can rotate a regular -sided polygon of a turn, or we can flip it over. We can rearrange the elements of a set. We can apply an automorphism of a group. The common thread in all these is a collection of reversible transformations. Performing one transformation and then the other is certainly also a transformation, so we can use this as a composition. The symmetries of a given structure form a group!

What if we paint one side of the above -gon black and the other white, so flipping it over definitely changes it. Then we can only rotate. The rotations are the collection of symmetries that preserve the extra structure of which side is which, and they form a subgroup of the group of all symmetries of the -gon. The symmetries of a structure preserving some *extra* structure form a subgroup!

As far as we’re concerned right now, mathematical structures are all built on sets. So the fundamental notion of symmetry is rearranging the elements of a set. Given a set , the set of all bijections from to itself is a group. We’ve actually seen a lot of these before. If is a finite set with elements, is the symmetric group on letters.

Now, a group action on a set is simply this: a homomorphism from to . That is, for each element in there is a bijection of and .

It’s important to note what seems like a switch here. It’s really due to the notation, but can easily seem confusing. What’s written on the right is “do the permutation corresponding to , then the one corresponding to “. So we have to think of the multiplication in as “first do , then do “.

In what follows I’ll often write as . The homomorphism property then reads

I’ll throw out a few definitions now, and follow up with examples in later posts.

We can slice up into subsets so that if and are in the same subset, for some , and not if they’re not in the same subset. In fact, this is rather like how we sliced up itself into cosets of . We call these slices the “orbits” of the action.

As an important special case of the principle that fixing additional structure induces subgroups, consider the “extra structure” of one identified point. We’re given an element of , and want to consider those transformations in which send to itself. Verify that this forms a subgroup of . We call it the “isotropy group” or the “stabilizer” of , and write it .

I’ll leave you to ponder this: if and are in the same -orbit, show that and are isomorphic.

## Today was a good day

I didn’t even have to use my AK.

Dartmouth went well. The drive was completely clear — about two and a half hours in each direction. I got some time with Dr. Chernov, after which I have to go check on some technical points about sorts of graded Lie algebras. Also I got to see his student, Allison Henrich, and find out what she’s doing with Legendrian virtual knots. The talk itself was well-received, and the dinner afterwards was very enjoyable.

About the only sour note was the fact that Dartmouth *has* completed its postdoc search, and I’m not it. It was a bit of a stretch to fit into what they were looking for anyhow, so I’m not horribly surprised. At least now I know. And knowing is half the battle.

So I’m back in New Haven, and the other instructors from my calculus class are raising points *now* about the test that’s been printed already and is to be given *tomorrow*. No rest for the wicked.

## Open thread

Tomorrow I’m going to be gone pretty much all day. Dartmouth is a nice, straight, three-hour shot up I-91, so I’ll head out in the morning, spend the afternoon, and return at night. No sense paying for lodging or anything if I don’t have to.

Anyhow, since I won’t be able to post, I thought I’d leave this thread open. What’s on your mind? Anything you’d like to see treated here? Just who the hell are you people, anyway?

## The First Isomorphism Theorem

Today I want to walk through what’s called the “First Isomorphism Theorem” for groups. There are two more, but the first is really more interesting in my view. I’ll start with a high-level sketch: kernels of homomorphisms are normal subgroups, images are quotient groups, and every homomorphism is a quotient followed by an isomorphism.

First I’m going to need a couple homomorphisms. If we’ve got a group and a normal subgroup , there’s immediately a homomorphism . Just send each to its coset . It should be clear that every coset gets hit at least once, so this is an epimorphism, and that its kernel is exactly . We call the “canonical projection” or the “canonical epimorphism” from to .

On the other hand, if is a group and is *any* subgroup, we have a homomorphism given by just sending every element of to itself inside . This is such a natural identification to make that it feels a little weird to think of it as a homomorphism at all, but it actually turns out to be quite useful. The kernel of is trivial, making it a monomorphism. We call it the “canonical injection” or “canonical monomorphism” from to .

Now consider any homomorphism . If is in the kernel of — is the identity of — and is any element of , we calculate

so is in the kernel as well. Thus the kernel is a normal subgroup.

So every kernel is a normal subgroup, and the canonical projection shows that every normal subgroup shows up as the kernel of *some* homomorphism.

Now we can write any homomorphism as a composition

where I’ve written the name of each composition next to its arrow. That is, we first project onto the quotient of the domain by the kernel of , then we send that to the image of by a homomorphism we call , and finally we inject the image into the codomain. As a bonus, is an isomorphism!

Okay, so how do we define ? If we write the kernel of as , we need to figure out what to do with a coset . If and are two elements of , then , so sends every element of to the same element of . We define .

Now let’s say . This means that , so is in already, and is the identity of . The kernel of is trivial, so is a monomorphism. On the other hand, every element in is for some , so each one is also for some . That makes an epimorphism, and thus an isomorphism. Q.E.D.

Every homomorphism works like this: you divide out some kernel, hit the quotient group with an isomorphism, and include the result into the target group. Since isomorphisms don’t really change anything about a group and the inclusion is pretty simple too, all the really interesting stuff goes on in the first step. The homomorphisms that can come out of are essentially determined by the normal subgroups of . Because of this, we call a group with no nontrivial normal subgroups “simple”. The kernel of an homomorphism from a simple group is either trivial or the whole group.

What we’re starting to see here is the tip of a much deeper approach to algebra. The internal structure of a group is intimately bound up with the external structure of the homomorphisms linking it to other groups. Each one determines, and is determined by the other, and this duality can be a powerful tool for answering questions on one side by turning them into questions on the other side.

## Knot theory

I figure that since I’m going to Dartmouth on Monday (my title and abstract aren’t posted, unfortunately), I should finally say something about what I do. Rather than dive right in, I’ll just talk about knots.

A knot is a mathematical idealization of a tangled-up loop of string in space. Formally, it’s a (smooth) path in space that closes up at the end. The thing you tie in your shoelaces is *not* a not, since it has two loose ends. If you actually used a knot, you couldn’t ever untie them!

Speaking of untying knots, it seems intuitively obvious that if we pick up a loop of string, move it around, and never break the loop, we still have “the same” knot as we started with. So we have to adjust the previous definition a bit: knots are smooth closed paths in space, but if we can deform two such paths into each other (for some suitable definition of “deform”) then they’re really the same knot. What we want to know is, “how can we tell if two knots are the same or different?” and, “what different knots are there, anyway?”

First of all, there are a *lot* of them. Dror Bar-Natan has posted up a table of knots up to ten crossings, and each one links to a page of information about the knot. When we say a knot has “*n* crossings”, we mean that there’s a way I can arrange it on the table so one strand crosses over another one *n* times, and no such arrangement for fewer than *n* crossings. There are some more technical points about the knots on this table, but for now it’s nice to just look and see a bunch of them, and know that they’re just the tip of the iceberg.

Okay, so how can we tell if two knots are the same? Say we’ve got two actual loops of string to fidget with. We can sit there all day and not make them look the same, but we still don’t know that if we played with them *just a little longer* we wouldn’t hit on something. We need some more powerful tool.

Enter invariants. An invariant is a way of assigning some value to each knot — like a number, or a polynomial, or even a group — to each knot. We want to be sure that if we move the knot around the value of the function won’t change. That is, we want it to be *invariant* when we deform the knot. A lot of the bits of information on the page for each knot in Bar-Natan’s table are the values various invariants have for that knot.

So here’s how an invariant helps us: if two knots are the same they’ll get the same value for the invariant. That means that if we have two knots that get different values, they *can’t* be the same! We know that no matter how long we play with the knot we’re not going to turn one into the other, just as surely as we’re not going to turn 1 into 0.

Unfortunately that’s not quite good enough. We can tell when knots are different, but we still can’t be sure when knots are the same. There isn’t yet known a knot invariant that’s an injection, which would assign every knot a different value. Well, strictly speaking that’s not true. There’s one that’s known to essentially be an injection, but it’s also known that it’s *impossible* to tell when two values are the same or not, so in practice it’s still not helpful. Weird.

It seems there are two ways to get invariants. The older way uses a lot of heavy topology and/or geometry, while the newer way uses a lot of combinatorial fiddling with diagrams — pictures of knots like you see on that table. The topological style really is fascinating once you get into it, and it’s bound up with all sorts of other areas of mathematics. It’s a little hard to get into without building up a lot of machinery first, though.

The combinatorial style, on the other hand, is a great on-ramp for playing with knots. There were some combinatorial calculations of invariants in the past, but they usually had some topology hiding behind them. The real explosion in this style came with Vaughn Jones’ discovery of what’s now called the “Jones polynomial”. It’s really straightforward to calculate it, but the definition came completely out of left field, and took pretty much everyone by surprise back in the early ’80s. It’s still uncertain what the geometric or topological meaning behind it is, but everyone’s sure there’s something there. I have some thoughts in this direction, but I’ll leave those until I’ve laid out some more of knot theory in general and my own research program in particular.

## Cosets and quotients

I know I’ve been doing a lot of theory here for a while, but just hold on a little longer, it’s about to pay off.

Now we know what a group is and what a subgroup is. Today I want to talk about the cosets of a subgroup in a group .

A subgroup is sort of like a slice through a group. The cosets of a subgroup are like slices “parallel” to the group. We know that passes through the identity of already, so we want to find a “parallel copy” through any other element we choose.

Now, cosets come in two flavors: left and right. We get a left coset by composing every element of on the left with . On the other hand, we get a right coset by composing every element on the right.

Let’s let be the group , and be the subgroup , where is the identity element. For each element of , let’s consider its left and right cosets.

Notice that the element is in both and , since the identity is in . Also notice that if is in then is the same as , and similarly for right cosets. In fact, you should be able to verify that

- is in
- If is in , then is in
- If is in and is in , then is in

and three other similar statements for right cosets. Together, these say that we can separate the elements of into “equivalence classes”. If and are not in the same class then and share no elements at all. But if and are in the same class, and are the same set — the equivalence class itself.

Okay, so we’ve sliced up the group into (left) cosets of the subgroup . If we consider two of them, and , we can multiply everything in the first by to get things in the second, and everything in the second by to get things in the first. These two transformations undo each other, so each coset of is “the same size”. If is a finite group this means that each coset has the same number of elements — the number of elements in . We’ve sliced into a bunch of pieces that never overlap, and all having the same number of elements. This merits some emphasis.

If is a finite group and is a subgroup, then the number of elements in must divide the number of elements of !

Now we’ve got a set of cosets of , which we write . What’s really nice is that sometimes *this set is a group too*! The natural idea to multiply two cosets is to take an element of each and multiply *them* and see what its coset is. Unfortunately this doesn’t always work. The answer might depend on which elements we choose

To see what goes wrong, let’s pick two elements in the first coset. We know that is in , and we can see that so is if is an element of . We just pick again from . Now we multiply to get for one choice and for the other. These are only in the same coset if there is some in so that . That is, so that . The requirement is this: for every in and for every in the composition must land back in . We call a subgroup with this property “normal”.

So if is normal, then our naïve idea for how to multiply two cosets does work right, and doesn’t depend on how we choose the element of each coset to multiply: . You should verify that this composition on the set of cosets of in actually satisfies the group axioms. We call this the “quotient group” of by , or “ modulo “.

Other exercises:

- Check to see that in the example given above (where is ) that the subgroup isn’t normal. Find one that is, and see what the quotient is.
- Show that any subgroup of an abelian group is normal.
- Consider the subgroup of (addition as the composition) consisting of all multiples of 12. Call it . What is ? What if we change 12 to any other number ?

## Subgroups

A subgroup is pretty straightforward. It’s a little group living inside a bigger group. If you’ve got a group and some collection of elements of so that is a group using the same composition as , then is a subgroup. To be more explicit, you need that

- If and are in then is in .
- If is in then is in .
- The identity of is in .
*[added at the suggestion of Toby Bartels]*

We say that a subgroup is “closed” under composition and inverse, meaning that if we start with elements of and take compositions and inverses we never leave the subgroup.

The collection of all even integers is a subgroup of the group of all integers (with addition as the operation).

The subset is a subgroup of the group .

Every group has two “trivial” subgroups: the whole group itself, and the subgroup consisting of just the identity element.

There are two ways of getting subgroups that I want to spend a bit more time on: “images” and “kernels”.

Continue reading

## Billiards 2

After looking for images of billiards I could use with no luck I just sat down and sketched an example.

The billiard table itself is the lower left square. I’ve drawn a path moving towards the upper right and bouncing around a few times. The other three squares are the reflections of the original table that I spoke of. We can imagine the path continuing into them in a straight line, and wrapping from one side of the big square to the other, and from the top to the bottom. The sides marked “A” are identified, as are the sides marked “B”. When we wrap up the sides as marked we get a donut-shaped surface called a “torus”.

Now we didn’t have to start with a square table. If we start with a rectangle we’ll get pretty much the same picture, except the torus we get will either be longer and thinner or shorter and fatter. There are a lot of different tori out there, but they all come from taking some parallelogram and identifying the opposite sides like we did here. So, what sorts of parallelograms are there?

Continue reading