The n-Category Café

Dr. George Hockney emailed me as follows:

Well, I think Jonathan’s right but I’m not sure.
Here’s a strategy that might be best, but I don’t
need no stinking Bayesian inference:

1) Assume the 100 boxes in a row are arranged so
we can all agree on how to number them without
having seen them first. (I think this is implied)

2) Assume each person can decide which box to
open next based on the names in the previously
opened boxes. If the person has to point to 50
boxes first and then open them, we’re hosed.

3) Assume each person can remember each other
person’s name and the number we agree to assign
to that name. If not, assume we can trick the
mad guy into further humiliating us by assigning
us numbers and using the numbers in the boxes.
That way each person only has to remember his or
her own number.

Then do this: Each person opens the box with his
or her number. If that box contains that number,
we’ve won and can open other boxes at random –
it doesn’t matter. If that box contains any
other number, open that box number next. That
is, if I am number 2 and box 2 contains 17, open
box 17 next.

If everyone does this, then the probability we
all live is the same as the probability that the
longest loop is length 50 or less. In the large
N limit I think this is 1/e but I don’t know.
It’s certainly greater than 1/4.

Notice the first person always has a 50/50
chance. If the first person opened the box with
his number last, that means there is a chain of
50 boxes in a loop. Therefore, if the second
person is in that loop, she has a 100% chance of
living. If not, she also has a 100% chance
because the loop she is in can’t be longer than
50 since that’s all that’s left.

The bad case is when the first person finds his
number in the first box he tries. Then the
second person only has a 50/99 chance of living,
but this is good for our side since the first
person lived.

If assumption (2) is violated I think we can do
better than 1/2^n but not better than 1/2^(n/2).

I don’t make any use of the fact that the
previous people live in this strategy. There
might be a way to adapt given the numbers of the
people who went before me, but this strategy is
already good (it gets better as N gets smaller:
for N=1, it’s 1; N=2, 1/2; N=4, 3/8, and so
forth).

This may limit to 1/4 instead of 1/e or 1/3.

I suppose we can also try entangled quantum
strategies, but I don’t see how we can ever do
better than 1/2.

– George

Greg wrote ‘I hope these grungy calculations haven’t lowered the n-categorical tone of the café too much.’

Actually, I think they’re good for the n-categorical discourse (although I’m too busy to actually stop and digest them at the moment). I think in some ways the lack of detailed examples, due to page limits I’d imagine, ends up presenting the n-categorical stuff in a less than optimally appealing light (in my opinion).

Greg, I agree with Dave: concrete examples like yours are absolutely vital to getting a sense of what’s going on here. When Jim Dolan was first teaching me this stuff a couple of years ago, it was mainly through appeal to examples, and you’ve added some interesting ones!

By the way, Jim and I often call these double cosets ‘orientations’. Most of our examples have been of incidence geometry type, but I think ‘orientation’ still has a nice ring to it when applied to some of your other examples, such as SO(2)\SO(3)/SO(2).

Dave wrote:

I think in some ways the lack of detailed examples, due to page limits I’d imagine, ends up presenting the $n$-categorical stuff in a less than optimally appealing light (in my opinion).

Just so I don’t come across as some hoity-toity advocate of ‘example-free abstraction’, I should emphasize that I agree with this.

When trying to follow the Tale of Groupoidification, the best possible thing is to work through tons of concrete examples. It’s good for developing understanding, and it’s lots of fun.

The main reason I’m not doing this in This Week’s Finds is not quite ‘page limits’. It’s something more like ‘age limits’: I want to finish a sketchy version of the Tale before I get too old! We’re just at the very beginning of this story; there’s a lot more yet to come.

Another reason is that these examples are best described using lots of pictures, and those pictures take work to draw.

So far I’ve only emphasized three examples of atomic invariant relations (aka ‘double cosets’):

1. those between a point and a line in projective geometry. There are 2 of these: the point can lie on the line, or the point can fail to lie on the line.
2. those between a flag and a flag in projective plane geometry. In week250 I claimed there are 6 of these, as shown here:

                    \             /
         ------------x-----------x'----------
                      \         /         y
                       \       /
                        \     /
                         \   /
                          \ /
                           x"
                          / \
                         /   \
                      y'/     \y"
   

3. Those between two timelike lines in Minkowski spacetime. Here there are infinitely many. In week250 we saw there are infinitely many of these: one for each pair of nonnegative real numbers, representing relative speed and distance of closest approach (in physics also known as ‘impact parameter’).

It’s also good to look at tons of examples involving finite groups. So, I’m really glad Greg is presenting some of those.

I’ll get around to some more soon. A bunch of nice ones come from Coxeter groups. The rotation/reflection symmetry groups of $n$-cubes are the $B_n$ series of Coxeter groups. So, what Greg is doing will fit into a nice big picture.

Greg wrote:

Given a group G with an arbitrary subgroup H, and given a set X on which G has a left action, what’s the magic ingredient that guarantees that there will be some subset Y of X with a stabiliser that is isomorphic as a group to H?

In the precise way you’ve written down this question: I don’t know.

But you’ve written it down in a strange way, haven’t you? I’m assuming you agree with the standard correspondence between

Given a $G$-set $X$, pick $x\in X$ and form $H(X,x)=\mathrm{Stab}(x)$. On the other hand, given $H\subset G$, form the set $X(H)=G/H$ on which $G$ acts from the left.

Doing $\to$ and then $\leftarrow$, we get a transitive $G$-set $X(H(X,x))$, each of whose stabilizer groups (of any point) are conjugate to $H$.

Doing $\leftarrow$ and then $\to$, we get the subgroup $H(X(H),H^{\prime })=H^{\prime }$ since we had to pick an element (read : coset) $H^{\prime }$. But we know $H^{\prime }$ is conjugate to $H$ by construction.

But you’ve asked your question in a different way. You haven’t said that your $G$-sets are transitive - which I assume is just a typo - but you also talk about the stabilizers of subsets $Y\subset X$ instead of the stabilizer of a point $x\in X$. This puts you out of the ‘first-order’ theory .

Actually, it’s a question worth asking. I’m assuming that we agree on our notion of stabilizer : the stabilizer of a subset $Y\subset X$ is the set of all $g\in G$ which leave $Y$ fixed as a set , i.e. they don’t have to fix $Y$ element-wise.

So, question :

What information can you get out by considering stabilizers of subsets instead of points?

This actually comes up in the context of Lie groups. Consider a Lie group $G$ acting on itself by conjugation, we call the resulting $G$-set $\Lambda G$. On the other hand, consider the set $\mathrm{Torii}(G)$ of maximal tori (maximal abelian closed subgroups) of $G$.

$G$ also acts on $Tori(G)$ by conjugation, and it is a theorem (at least for compact Lie groups, I think) that this it acts transitively.

On the other hand, it’s clear that $\mathrm{Tori}(G)$ is some kind of ‘coarse-graining’ of $\Lambda G$. The stabilizers in $\mathrm{Tori}(G)$ are exactly the stabilizers of subsets in $\Lambda G$, and they’re related to the Weyl group, etc. Is there a nice way to understand this?

Greg wrote:

Given a group $G$ with an arbitrary subgroup $H$, and given a set $X$ on which $G$ has a left action, what’s the magic ingredient that guarantees that there will be some subset $Y$ of $X$ with a stabiliser that is isomorphic as a group to $H$?

Sorry not to answer sooner. I just got back from France, and I’ve had a night’s sleep. Maybe this has been hammered out to your satisfaction by now, but let me take a crack at it.

First, let me pose your question a bit more compactly, like this:

Given a $G$-set $X$ and a subgroup $H\subseteq G$, when does some element $x\in X$ have a stabilizer isomorphic to $H$?

I don’t know an interesting answer to this question. I only know an interesting answer to a similar question, and a dull answer to your actual question.

We start with three basic facts:

First, there’s a unique way to take any $G$-set $X$ and write it as the disjoint union of subsets on which $G$ acts transitively. For lack of a better term, let’s call these subsets the blocks of $X$.

Second, any transitive $G$-set is isomorphic to the $G$-set $G/H$ for some subgroup $H\subseteq G$.

Third, the stabilizer of any element of $G/H$ is not only isomorphic but actually conjugate to $H$.

Given these, there’s an interesting answer to a slightly modified version of your question. If you’d asked:

Given a $G$-set $X$ and a subgroup $H\subseteq G$, when does some element $x\in X$ have a stabilizer conjugate to $H$?

I could correctly answer: this happens iff one of the blocks of $X$ is isomorphic as a $G$-set to $G/H$.

However, for your actual question:

Given a $G$-set $X$ and a subgroup $H\subseteq G$, when does some element $x\in X$ have a stabilizer isomorphic to $H$?

the best answer I can find is: this happens iff one of the blocks of $X$ is isomorphic as a $G$-set to $G/K$, where $K\subseteq G$ is isomorphic as an abstract group to $H$.

The point is that being isomorphic as abstract groups is weaker than being conjugate as subgroups of $G$.

So, here’s a puzzle, helpful for understanding this issue more deeply:

Find a group $G$ with two subgroups $H,K\subseteq G$ that are isomorphic as abstract groups, but not conjugate in $G$. Compare the $G$-sets $G/H$ and $G/K$.

Here’s a possible nice solution, though I always get mixed up about this, due to a certain ‘paradox’ which I could explain if pressed.

Suppose $G=\mathrm{PGL}(3,ℝ)$ is the symmetry group of the real projective plane. Let $H$ be the subgroup that stabilizes your favorite point, and let $K$ be the subgroup that stabilizes your favorite line. Then $H$ and $K$ are isomorphic as abstract groups, but I think they’re not conjugate in $G$.

Another point, in case it’s not obvious, is that chopping a $G$-set into blocks is a bit like chopping a representation of $G$ into irreducible representations. But, it has the advantage that you can always do it, and you can always do it in a unique way!

In response to