Feeds:
Posts

## The p-group fixed point theorem

The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.

Theorem: Let $G$ be a finite $p$-group acting on a finite set $X$. Let $X^G$ denote the subset of $X$ consisting of those elements fixed by $G$. Then $|X^G| \equiv |X| \bmod p$; in particular, if $p \nmid |X|$ then $G$ has a fixed point.

Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.

## Connected objects and a reconstruction theorem

A common theme in mathematics is to replace the study of an object with the study of some category that can be built from that object. For example, we can

• replace the study of a group $G$ with the study of its category $G\text{-Rep}$ of linear representations,
• replace the study of a ring $R$ with the study of its category $R\text{-Mod}$ of $R$-modules,
• replace the study of a topological space $X$ with the study of its category $\text{Sh}(X)$ of sheaves,

and so forth. A general question to ask about this setup is whether or to what extent we can recover the original object from the category. For example, if $G$ is a finite group, then as a category, the only data that can be recovered from $G\text{-Rep}$ is the number of conjugacy classes of $G$, which is not much information about $G$. We get considerably more data if we also have the monoidal structure on $G\text{-Rep}$, which gives us the character table of $G$ (but contains a little more data than that, e.g. in the associators), but this is still not a complete invariant of $G$. It turns out that to recover $G$ we need the symmetric monoidal structure on $G\text{-Rep}$; this is a simple form of Tannaka reconstruction.

Today we will prove an even simpler reconstruction theorem.

Theorem: A group $G$ can be recovered from its category $G\text{-Set}$ of $G$-sets.

## Groupoid cardinality

Suitably nice groupoids have a numerical invariant attached to them called groupoid cardinality. Groupoid cardinality is closely related to Euler characteristic and can be thought of as providing a notion of integration on groupoids.

There are various situations in mathematics where computing the size of a set is difficult but where that set has a natural groupoid structure and computing its groupoid cardinality turns out to be easier and give a nicer answer. In such situations the groupoid cardinality is also known as “mass,” e.g. in the Smith-Minkowski-Siegel mass formula for lattices. There are related situations in mathematics where one needs to describe a reasonable probability distribution on some class of objects and groupoid cardinality turns out to give the correct such distribution, e.g. the Cohen-Lenstra heuristics for class groups. We will not discuss these situations, but they should be strong evidence that groupoid cardinality is a natural invariant to consider.

My current top candidate for a mathematical concept that should be and is not (as far as I can tell) consistently taught at the advanced undergraduate / beginning graduate level is the notion of a groupoid. Today’s post is a very brief introduction to groupoids together with some suggestions for further reading.

## The Schrödinger equation on a finite graph

One of the most important discoveries in the history of science is the structure of the periodic table. This structure is a consequence of how electrons cluster around atomic nuclei and is essentially quantum-mechanical in nature. Most of it (the part not having to do with spin) can be deduced by solving the Schrödinger equation by hand, but it is conceptually cleaner to use the symmetries of the situation and representation theory. Deducing these results using representation theory has the added benefit that it identifies which parts of the situation depend only on symmetry and which parts depend on the particular form of the Hamiltonian. This is nicely explained in Singer’s Linearity, symmetry, and prediction in the hydrogen atom.

For awhile now I’ve been interested in finding a toy model to study the basic structure of the arguments involved, as well as more generally to get a hang for quantum mechanics, while avoiding some of the mathematical difficulties. Today I’d like to describe one such model involving finite graphs, which replaces the infinite-dimensional Hilbert spaces and Lie groups occurring in the analysis of the hydrogen atom with finite-dimensional Hilbert spaces and finite groups. This model will, among other things, allow us to think of representations of finite groups as particles moving around on graphs.

## Nationals 2010

MIT is hosting the United States Rubik’s Cube Championships this summer, August 6-8. All ages welcome! Normally I wouldn’t post about such things, but

• I happen to be a member of the Rubik’s Cube club here, and
• Some people use the Rubik’s cube group to motivate group theory. I’m a fan of hands-on mathematics, and there’s a lot to learn from the cube; for example, you quickly understand that groups are not in general commutative. The Rubik’s cube itself is also a good example of a torsor.

Actually, just so this post has some mathematical content, there’s something about the Rubik’s cube group that is probably very simple to explain, but which I don’t completely understand. It’s a common feature of Rubik’s cube algorithms that they need to switch around some parts of the cube without disturbing others; in other words, the corresponding permutation needs to have a lot of fixed points. This seems to be done by writing down a lot of commutators, but I’m not familiar with any statements in group theory of the form “commutators tend to have fixed points.” Can anyone explain this?

## Fractional linear transformations and elliptic curves

The following two lemmas might be encountered in a basic course in complex analysis (the first in a basic course in group theory, even).

Lemma 1: Fix a field $F$. The group of fractional linear transformations $PGL_2(F)$ acts triple transitively on $\mathbb{P}^1(F)$ and the stabilizer of any triplet of distinct points is trivial.

Lemma 2: The group of fractional linear transformations on $\mathbb{P}^1(\mathbb{C})$ preserving the upper half plane $\mathbb{H} = \{ z \in \mathbb{C} | \text{Im}(z) > 0 \}$ is $PSL_2(\mathbb{R})$.

I used to only know extremely boring computational proofs of both of these statements. However, I now know better! Today I’d like to give shorter and conceptual proofs of both of these, and then briefly discuss how they come about in the study of elliptic curves (a subject I’d like to talk about in more detail once this semester is over).

## Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

$\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k$.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial $C(t)$ with non-negative integer coefficients and $C(0) = 0$, let $r_1, ... r_n$ be the reciprocals of the roots of $C(t) - 1 = 0$. Then

$\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k$.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by $C(t)$. Today we’ll describe this species when $C(t)$ is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

## GILA V: The Polya enumeration theorem and applications

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors $1, 2, ... n$ (represented by variables $r_1, r_2, ... r_n$), and we have a set of slots $S$ with $|S| = m$ acted on by a group $G$ where each slot will be assigned a color. Define $f_G(t_1, ... t_n)$ to be the number of orbits of functions $S \to \{ 1, 2, ... n \}$ under the action of $G$ where color $i$ is used $t_i$ times. (Since the action of $G$ only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

$\displaystyle F_G(r_1, r_2, ... r_n) = \sum_{t_1 + ... + t_n = m} f_G(t_1, t_2, ... t_n) r_1^{t_1} r_2^{t_2} ... r_n^{t_n}$.

Note that setting $r_1 = r_2 = .... = r_n = 1$ we recover $F_G(n)$, which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

$\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |(r_1, r_2, ... r_n)$

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

## 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 $(g, x)$ such that $gx = x$, and we’ve been counting them indexed by $x$, let’s count them indexed by $g$. We use $\text{Fix}(g)$ to denote the set of fixed points of $g$. (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: $\displaystyle \sum_{x \in S} |\text{Stab}(x)| = \sum_{g \in G} | \text{Fix}(g) |$.

On the other hand, by the orbit-stabilizer theorem, it’s true for any orbit $O$ that $\displaystyle \sum_{x \in O} | \text{Stab}(x) | = |G|$, since the cosets of any stabilizer subgroup partition $|G|$. 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 $\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |$, i.e. the average number of fixed points.

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