Groups vs. abelian groups

A few weeks ago on MathOverflow Greg Muller asked, “why do groups and abelian groups feel so different?” The answers were very interesting and came from several different perspectives, but I still don’t feel as if the question was resolved. So I’ll try to synthesize and summarize some of the answers and hopefully something will be clearer in the end.

The orthogonality relations for representations of finite groups

In order to continue our discussion of symmetric functions it will be useful to have some group representation theory prerequisites, although I will use many of the results in the representation theory of the symmetric groups as black boxes. I had planned on using this post to discuss Frobenius reciprocity, but got so carried away with motivating it that this post now stands alone.

Today I’d like to discuss the representation theory of finite groups over . As these are strong assumptions, the resulting theory is quite elegant, but I always found the proofs a little unmotivated, so I’m going to try to use the categorical perspective to fix that. Admittedly, I don’t have much experience with this kind of thing, so this post is for my own benefit as much as anyone else’s. The main focus of this post is motivating the orthogonality relations.

GILA III: The orbit-counting lemma and baby Polya

The orbit-stabilizer theorem implies, very immediately, one of the most important counting results in group theory. The proof is easy enough to give in a paragraph now that we’ve set up the requisite machinery. Remember that we counted fixed points by looking at the size of the stabilizer subgroup. Let’s count them another way. Since a fixed point is really a pair such that , and we’ve been counting them indexed by , let’s count them indexed by . We use to denote the set of fixed points of . (Note that this is a function of the group action, not the group, but again we’re abusing notation.) Counting the total number of fixed points “vertically,” then “horizontally,” gives the following.

Proposition: .

On the other hand, by the orbit-stabilizer theorem, it’s true for any orbit that , since the cosets of any stabilizer subgroup partition . This immediately gives us the lemma formerly known as Burnside’s, or the Cauchy-Frobenius lemma, which we’ll give a neutral name.

Orbit-counting lemma: The number of orbits in a group action is given by , i.e. the average number of fixed points.

In this post we’ll investigate some consequences of this result.

GILA II: Orbits, stabilizers, and classifying group actions

Now that we’ve discussed group actions a bit, it’s time to characterize them. In this post I’d like to take a leaf from Tim Gowers’ book and try to make each step taken in the post “obvious.” While the content of the proofs is not too difficult, its motivation is rarely discussed.

First, it’s important to note that there is a way to take direct sums or disjoint unions (category theorists would say coproducts) of group actions: given a group acting on two sets , one defines an action on their disjoint union in the obvious way: pick one action or the other. (Disjoint unions differ from unions in the usual sense because we relabel the elements of the sets so that they cannot intersect.) There’s a great reason to do this, and cycle decomposition showed us a special case: every group action is a direct sum or disjoint union of the action on its orbits.

This is the first step toward a structure theorem. Since the group action cannot “mix” between two orbits, it acts “independently” on orbits, and any question we might want to ask about the group action can be answered by looking at each orbit separately. A group action with a single orbit is called transitive, which means that for every in the underlying set there exists such that . So to classify group actions it suffices to classify transitive group actions.

GILA I: Group actions and equivalence relations

Sometimes I worry that I should be more consistent or more lenient about the background I expect of my readers. (Readers, I have to admit that I still don’t really know who you are!) Considering how important I think it is that mathematicians value communicating their ideas to non-specialists (what John Armstrong calls the Generally Interested Lay Audience (GILA)), I should probably be putting my money where my mouth is.

So, inspired by the Unapologetic Mathematician, I have decided on a little project: to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory. Posts in this project, or any subsequent similar projects, will be labeled “GILA.” The general plan is to talk about group actions in general, the orbit-stabilizer theorem, the lemma formerly known as Burnside’s, and generating functions on the way. Much of this discussion can be found in Section 7 of Stanley’s lectures on algebraic combinatorics.

The PET is a very general way to think about questions of the following nature:

1. How many ways are there to paint the faces of a cube if we consider two colorings related by some rotation to be the same?
2. How many ways are there to paint the beads on a necklace if we consider two colorings related by a rotation of the necklace to be the same?
3. How many ways are there to place some balls into some urns if we consider two placements related by a relabeling of the balls to be the same? (In other words, we want the balls to be “indistinguishable.”)
4. How many graphs with a fixed number of vertices and edges are there if we consider two graphs related by a relabeling of the vertices to be the same? (In other words, we want the graphs to be “non-isomorphic.”)

The general situation is that we have a (finite) set of slots and another (for now, finite) set of objects we want to put into those slots, which it is useful to think of as a set of colors that we can “paint” the slots. We also have a (finite) group of symmetries that controls when we consider two colorings to be “the same.” To understand this situation, it is first necessary to understand something about group actions.

Non-canonical isomorphisms

I find non-canonical isomorphisms very interesting, but I wish I knew more examples. To be vague, an isomorphism (perhaps in a category) is said to be non-canonical if it requires making an “arbitrary choice.” One of the reasons I find them interesting is that we often think of objects only up to isomorphism, but in order for certain things to make more sense we must distinguish between objects that are non-canonically isomorphic. Here are the examples I know of.