Feeds:
Posts

## Double cosets are relative positions

The goal of this post is to explain something that the cool kids all understood ages ago (David Speyer, John Baez) but that I hadn’t internalized until recently.

Let $G$ be a group and let $X$ and $Y$ be transitive $G$-sets, so $X = G/H$ and $Y = G/K$ for some subgroups $H, K$ of $G$. In “geometric” situations (in the sense of the Erlangen program), $G$ is the symmetry group of some kind of geometry (for example, affine geometry, or Euclidean geometry), and $X$ and $Y$ are spaces of “figures” in the geometry (for example, points, lines, or triangles). We’ll call the points of $X$$X$-figures” and similarly for $Y$.

Now, figures in a geometry can be in various “relative positions” (or “incidence relations”) with respect to each other: for example, a point can be contained in a line, or two lines can intersect at right angles. What makes these geometrically meaningful is that they are invariant under the symmetry group $G$ of the geometry: for example, the condition that a point is contained in a line is invariant under affine symmetries, and the condition that two lines intersect at right angles is invariant under Euclidean symmetries. This motivates the following.

Definition: A relative position of $X$-figures and $Y$-figures is a $G$-invariant subset of $X \times Y$, or equivalently a $G$-invariant relation $R : X \to Y$.

Any $G$-invariant subset of $X \times Y$ decomposes into a disjoint union of $G$-orbits: these are the atomic relative positions.

Proposition: $G$-orbits of the action of $G$ on $G/H \times G/K$ (equivalently, the atomic relative positions of $X$-figures and $Y$-figures) can canonically be identified with double cosets $H \backslash G/K$, via the map

$\displaystyle G/H \times G/K \ni ([g_1], [g_2]) \mapsto [g_1^{-1} g_2] \in H \backslash G/K$

where $[g] \in G/H$ means the image of $g \in G$ under $G \to G/H$.

This is the conceptual interpretation of double cosets. It took an annoyingly long time between the first time I was introduced to double cosets (which I believe was in 2010) and the time I internalized the above fact (which was this year, 2015). Unlike the usual definition, this interpretation naturally generalizes to a notion of “triple cosets” ($G$-orbits on a triple product $X \times Y \times Z$), and so forth.

Example. Let $G = \text{Isom}(\mathbb{R}^n)$ be the group of isometries of Euclidean space, which more explicitly is the semidirect product $\mathbb{R}^n \rtimes O(n)$. If $X = Y$ are both the $G$-space of points in $\mathbb{R}^n$, then the atomic relative positions have the form “a point has distance $r$ from another point,” where $r$ is any nonnegative real.

Example. Let $G = GL_n(k)$ be the general linear group over a field $k$ and let $H = K = B$ be the Borel subgroup of upper triangular matrices. $G/B$ is the space of complete flags in $V = k^n$. As it turns out, there are exactly $n!$ atomic relative positions of a pair of complete flags. When $k$ is a finite field these form a basis of a Hecke algebra. In general they label the Bruhat decomposition of $G$.

For example, when $n = 2$, a complete flag is just a line in $V = k^2$, and there are two atomic relative positions: the lines can be identical or they can be different. When $n = 3$, a complete flag is a line $V_1$ contained in a plane $V_2$ in $V = k^3$, and there are six atomic relative positions. Letting $W_1 \subset W_2$ denote a second complete flag, they are

• $V_1 = W_1, V_2 = W_2$,
• $V_1 = W_1, V_2 \neq W_2$,
• $V_1 \neq W_1, V_2 = W_2$,
• $V_1 \neq W_1, V_1 \subset W_2, W_1 \not\subset V_2, V_2 \neq W_2$,
• $V_1 \neq W_1, W_1 \subset V_2, V_1 \not\subset W_2, V_2 \neq W_2$,
• $V_1 \neq W_2, V_1 \not\subset W_2, W_1 \not\subset V_2, V_2 \neq W_2$.

Instead of thinking about relations as conditions on a pair of complete flags, we can also think about them as partial multi-valued functions from complete flags to complete flags. In those terms the six atomic relative positions are

• Do nothing,
• Pick a different plane,
• Pick a different line,
• Pick a different plane still containing the original line, then pick a different line not contained in the original plane,
• Pick a different plane not containing the original line, then pick a different line contained in the original plane,
• Pick a different plane not containing the original line, then pick a different line not contained in the original plane.

## The categorical exponential formula

Yesterday I described the answer to the puzzle of what the generating function

$\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots$

counts by sketching a proof of the following more general identity: if $G$ is a finitely generated group and $a_n$ is the number of subgroups of $G$ of index $n$, then

$\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right)$.

The main ingredient is the exponential formula, but the discussion of the proof involved some careful juggling to make sure we weren’t inappropriately quotienting out by various symmetries, and one might find this conceptually unsatisfying. The goal of today’s post is to state a categorical result which describes exactly how to juggle these symmetries and gives a conceptually clean proof of the above identity.

The key is to describe in exactly what sense a finite $G$-set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive $G$-sets (corresponding to the RHS), which is the following.

Claim: The symmetric monoidal groupoid of finite $G$-sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite $G$-sets.

From here, we’ll use a version of the exponential formula that comes from relating (weighted) groupoid cardinalities of a groupoid and of the free symmetric monoidal groupoid on it.

## The answer to the puzzle

Two days ago, as a puzzle, I asked what the generating function

$\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots$

counts. Yesterday, I suggested as a hint that it might be useful to interpret that $n!$ as $\frac{n!^2}{n!}$, and to use the exponential formula.

The answer to the puzzle can be described in several ways. Below I’ll use a description that suggests a generalization I particularly like.

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

## Operations, pro-objects, and Grothendieck’s Galois theory

Previously we looked at several examples of $n$-ary operations on concrete categories $(C, U)$. In every example except two, $U$ was a representable functor and $C$ had finite coproducts, which made determining the $n$-ary operations straightforward using the Yoneda lemma. The two examples where $U$ was not representable were commutative Banach algebras and commutative C*-algebras, and it is possible to construct many others. Without representability we can’t apply the Yoneda lemma, so it’s unclear how to determine the operations in these cases.

However, for both commutative Banach algebras and commutative C*-algebras, and in many other cases, there is a sense in which a sequence of objects approximates what the representing object of $U$ “ought” to be, except that it does not quite exist in the category $C$ itself. These objects will turn out to define a pro-object in $C$, and when $U$ is pro-representable in the sense that it’s described by a pro-object, we’ll attempt to describe $n$-ary operations $U^n \to U$ in terms of the pro-representing object.

The machinery developed here is relevant to understanding Grothendieck’s version of Galois theory, which among other things leads to the notion of étale fundamental group; we will briefly discuss this.

Previously we described $n$-ary operations on (the underlying sets of the objects of) a concrete category $(C, U)$, which we defined as the natural transformations $U^n \to U$.

Puzzle: What are the $n$-ary operations on finite groups?

Note that $U$ is not representable here. The next post will answer this question, but for those who don’t already know the answer it should make a nice puzzle.

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

## Regular and effective monomorphisms and epimorphisms

Previously we observed that although monomorphisms tended to give expected generalizations of injective function in many categories, epimorphisms sometimes weren’t the expected generalization of surjective functions. We also discussed split epimorphisms, but where the definition of an epimorphism is too permissive to agree with the surjective morphisms in familiar concrete categories, the definition of a split epimorphism is too restrictive.

In this post we will discuss two other intermediate notions of epimorphism. (These all give dual notions of monomorphisms, but their epimorphic variants are more interesting as a possible solution to the above problem.) There are yet others, but these two appear to be the most relevant in the context of abelian categories.

## Groupoids

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.

## Noncommutative probability and group theory

There are, roughly speaking, two kinds of algebras that can be functorially constructed from a group $G$. The kind which is covariantly functorial is some variation on the group algebra $k[G]$, which is the free $k$-module on $G$ with multiplication inherited from the multiplication on $G$. The kind which is contravariantly functorial is some variation on the algebra $k^G$ of functions $G \to k$ with pointwise multiplication.

When $k = \mathbb{C}$ and when $G$ is respectively either a discrete group or a compact (Hausdorff) group, both of these algebras can naturally be endowed with the structure of a random algebra. In the case of $\mathbb{C}[G]$, the corresponding state is a noncommutative refinement of Plancherel measure on the irreducible representations of $G$, while in the case of $\mathbb{C}^G$, the corresponding state is by definition integration with respect to normalized Haar measure on $G$.

In general, some nontrivial analysis is necessary to show that the normalized Haar measure exists, but for compact groups equipped with a faithful finite-dimensional unitary representation $V$ it is possible to at least describe integration against Haar measure for a dense subalgebra of the algebra of class functions on $G$ using representation theory. This construction will in some sense explain why the category $\text{Rep}(G)$ of (finite-dimensional continuous unitary) representations of $G$ behaves like an inner product space (with $\text{Hom}(V, W)$ being analogous to the inner product); what it actually behaves like is a random algebra, namely the random algebra of class functions on $G$.