The Unapologetic Mathematician

Mathematics for the interested outsider

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

February 22, 2007 Posted by | Group theory, Rubik\'s Cube | 15 Comments

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.

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

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 n-sided polygon \frac{1}{n} 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 n-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 n-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 S, the set of all bijections from S to itself {\rm Bij}(S) is a group. We’ve actually seen a lot of these before. If S is a finite set with n elements, {\rm Bij}(S) is the symmetric group on n letters.

Now, a group action on a set is simply this: a homomorphism from G to {\rm Bij}(S). That is, for each element g in G there is a bijection p_g of S and p_{gh}(x)=p_g(p_h(x)).

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 h, then the one corresponding to g“. So we have to think of the multiplication in G as “first do h, then do g“.

In what follows I’ll often write p_g(x) as gx. The homomorphism property then reads (gh)x=g(hx)

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

We can slice up S into subsets so that if x and x' are in the same subset, x'=gx for some g, and not if they’re not in the same subset. In fact, this is rather like how we sliced up G itself into cosets of H. We call these slices the “orbits” of the G 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 x of S, and want to consider those transformations in G which send x to itself. Verify that this forms a subgroup of G. We call it the “isotropy group” or the “stabilizer” of x, and write it G_x.

I’ll leave you to ponder this: if x and x' are in the same G-orbit, show that G_x and G_{x'} are isomorphic.

February 20, 2007 Posted by | Algebra, Group Actions, Group Homomorphisms, Group theory | 18 Comments

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.

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

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?

February 19, 2007 Posted by | Uncategorized | 11 Comments

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 G and a normal subgroup N, there’s immediately a homomorphism \pi_{(G,N)}:G\rightarrow G/N. Just send each g to its coset gN. It should be clear that every coset gets hit at least once, so this is an epimorphism, and that its kernel is exactly N. We call \pi_{(G,N)} the “canonical projection” or the “canonical epimorphism” from G to G/N.

On the other hand, if G is a group and H is any subgroup, we have a homomorphism \iota_{(G,H)}:H\rightarrow G given by just sending every element of H to itself inside G. 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 \iota_{(G,H)} is trivial, making it a monomorphism. We call it the “canonical injection” or “canonical monomorphism” from H to G.

Now consider any homomorphism f:G\rightarrow H. If k is in the kernel of ff(k) is the identity e_H of H — and g is any element of G, we calculate

f(gkg^{-1}) = f(g)f(k)f(g^{-1}) = f(g)f(g)^{-1} = e_H

so gkg^{-1} 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 f as a composition

G\rightarrow^{\pi_{(G,{\rm Ker}(f))}}G/{\rm Ker}(f)\rightarrow^{f'} {\rm Im}(f)\rightarrow^{\iota_{(H,{\rm Im}(f)}}H

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 f, then we send that to the image of f by a homomorphism we call f', and finally we inject the image into the codomain. As a bonus, f' is an isomorphism!

Okay, so how do we define f'? If we write the kernel of f as N, we need to figure out what to do with a coset gN. If g and gn are two elements of gN, then f(gn) = f(g)f(n) = f(g), so f sends every element of gN to the same element of H. We define f'(gN) = f(g).

Now let’s say f'(gN) = e_H. This means that f(g)=e_H, so g is in N already, and gN is the identity of G/N. The kernel of f' is trivial, so f' is a monomorphism. On the other hand, every element in {\rm Im}(f) is f(g) for some g, so each one is also f'(gN) for some gN. That makes f' 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 G are essentially determined by the normal subgroups of G. 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.

February 17, 2007 Posted by | Algebra, Group Homomorphisms, Group theory | 6 Comments

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.

February 16, 2007 Posted by | Knot theory | 6 Comments

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 H in a group G.

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 H passes through the identity of H 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 gH by composing every element of H on the left with g. On the other hand, we get a right coset Hg by composing every element on the right.

Let’s let G be the group S_3, and H be the subgroup \{e, (1 2)\}, where e is the identity element. For each element of G, let’s consider its left and right cosets.

g gH Hg
e \{e, (1 2)\} \{e, (1 2)\}
(2 3) \{(2 3), (1 3 2)\} \{(2 3), (1 2 3)\}
(1 2) \{(1 2), e\} \{(1 2), e\}
(1 2 3) \{(1 2 3), (1 3)\} \{(1 2 3), (2 3)\}
(1 3) \{(1 3), (1 2 3)\} \{(1 3), (1 3 2)\}
(1 3 2) \{(1 3 2), (2 3)\} \{(1 3 2), (1 3)\}

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

  • g is in gH
  • If g is in g'H, then g' is in gH
  • If g is in g'H and g' is in g''H, then g is in g''H

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

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

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

Now we’ve got a set of cosets of H, which we write G/H. 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 g is in gH, and we can see that so is gh if h is an element of H. We just pick g' again from g'H. Now we multiply to get gg' for one choice and ghg' for the other. These are only in the same coset if there is some h' in H so that gg'h'=ghg'. That is, so that h'=g'^{-1}hg'. The requirement is this: for every g' in G and for every h in H the composition g'^{-1}hg' must land back in H. We call a subgroup with this property “normal”.

So if H 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: gH\circ g'H=(gg')H. You should verify that this composition on the set G/H of cosets of H in G actually satisfies the group axioms. We call this the “quotient group” of G by H, or “G modulo H“.

Other exercises:

  • Check to see that in the example given above (where G is S_3) 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 \mathbb{Z} (addition as the composition) consisting of all multiples of 12. Call it 12\mathbb{Z}. What is \mathbb{Z}/12\mathbb{Z}? What if we change 12 to any other number n?

February 15, 2007 Posted by | Algebra, Group theory, Subgroups and Quotient Groups | 11 Comments

Subgroups

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

  • If x and y are in H then xy is in H.
  • If x is in H then x^{-1} is in H.
  • The identity e of G is in H. [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 H and take compositions and inverses we never leave the subgroup.

The collection of all even integers is a subgroup of the group {\mathbb Z} of all integers (with addition as the operation).
The subset \{e,(1\,2\,3),(1\,3\,2)\} is a subgroup of the group S_3.
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

February 13, 2007 Posted by | Algebra, Group theory, Subgroups and Quotient Groups | 7 Comments

Billiards 2

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

a square billiard path

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

February 12, 2007 Posted by | Billiards | 2 Comments

Follow

Get every new post delivered to your Inbox.

Join 366 other followers