The n-Category Café

Looking at the Wikipedia article you linked, I don’t think you need to be nearly that clever to find the harmonic series formula!

How many permutations are there of 100 elements which have a cycle of length 51? To construct such a permutation you choose a cycle of length 51 and any permutation of the remaining 49 elements. The number of 51-cycles is $\frac{100\times\cdots\times 50}{51}$, and the number of permutations of the remaining 49 is $49!$. So there are $\frac{100!}{51}$ such permutations. In other words, $1/51$ of the permutations contain a 51-cycle.

The same reasoning shows that $1/52$ of the permutations have a 52-cycle, and so on. So the bad permutations, the ones that result in us all being killed, are

of the possible permutations. (We can just add the proportions because the possibilities are mutually exclusive: if there’s a 55-cycle then there isn’t a 73-cycle, etc.)

Interesting puzzle!

Well now that that’s run its course, maybe another one? Similar setup, but different mathematics (I think).

100 people are lined up, all facing the same direction along the line. Then everyone is given a red or a blue hat. Each person can see all the hats of all the people in front of them, but can’t see their own or that of anyone behind them.

The Madman starts at the back of the line. Each person he comes to must yell out the color they think their hat is (everyone hears the guesses) and if they guess wrong they’ll be shot (everyone hears the shots). What is the average number of people to survive with the best possible strategy?

It seems to me that the phenomenon you mention simply has to do with whether $H$ acts freely or not.

Let me try to place it in a broader context, and write it in the language John has been using.

Suppose we have a $G$-set $X$. We think of this as a groupoid $X // G$. Notice that in this language, if $H \subseteq G$ is a subgroup, then an “orbit of $H$”, i.e. a set of the form $H \cdot x$ where $x \in X$, is just a subgroupoid of $X//G$:

That’s nice - it means we don’t have to mention $H$ nor the point $x$ at all to understand what an “orbit” is.

Okay, now for an area where the new terminology (groupoids instead of $G$-sets) seems to work so much better : automorphisms!

In the bad old days, given $g \in G$, we could act on the left by $g$ to get a function $f_g : X \rightarrow X$. But sadly it wasn’t an automorphism, since $f_g(x) = g \cdot x$, but $f_g (h \cdot x) = gh \cdot x \neq h \cdot f_g (x)$. Nasty!

But in the groupoid picture, we can play this game. Given $g \in G$, we get a functor $F_g : X //G \rightarrow X//G$, defined by sending

The trick here is that we’re kind of allowed to ‘rotate’ our group as we go along. So - we get a nice homomorphism

Okay, back to your original question :-) Given a $G$-set $X$, a natural thing to consider is the category $Sub(X)$ of all subgroupoids of $X //G$. Objects are subgroupoids (think : orbits), while morphisms are… functors. Something like that (I’m making this up - perhaps someone can help me out).

For example, think of the orbit space $H \cdot x$. It’s a groupoid in its own right, and any $h \in H$ determines a functor $F_h$ from this groupoid to itself, in the way described above. In other words, in John’s language, $H$ is always a subgroup of the stabilizer of the orbit $H \cdot x$,

But of course it can be bigger. For if there are two arrows going from $a$ to $b$ (think of the two element set which is acted on by $\mathbb{Z}_4$), then these other arrows also give you automorphisms.

I’ll stop here, since this is too long by now.

Thanks, Dave and Todd, for encouraging my grungy calculations! If I get the tablecloth dirty, I suppose I can pay off the damage by washing some dishes.

Bruce wrote:

It seems to me that the phenomenon you mention simply has to do with whether H acts freely or not.

Thanks! That seems to be a very important part of it, though maybe we need to talk about whether G acts freely, not just H.

In the two-dimensional example I gave, where H is C_n and G is SO(2), all of G acts freely on R²\{0}. But then if you change G to O(2), H still acts freely, of course, but there will now be some reflection not in H which is a symmetry of the n-gon H⋅x.

In the four-dimensional example, if we make G the rotation symmetries of the 4-cube, then obviously it doesn’t act freely on the 4-cube’s vertices, edge-centres, etc., or on points that lie in planes that contain certain of those k-cube-centres. If we make H the order-8 cyclic group I described, then H acts freely on R⁴\{0}, but then the annoying extra symmetry of the orbit H⋅(1,1,0,0):

R:(w,x,y,z)→(z,y,x,w)

obviously doesn’t act freely on H⋅(1,1,0,0), e.g. it fixes (0,1,1,0).

Ultimately, I’m trying to establish necessary and sufficient conditions for the situation where the orbit of x under H has extra symmetry:

(Extra) There is some g, not in H, such that g(H⋅x)=H⋅x.

I think this is equivalent to:

There is some g, not in H, such that for all h₁ in H, there exists an h₂ in H with:

gh₁x=h₂x, or

h₂^-1gh₁x=x

But if G acts freely on x, that would imply gh₁=h₂, or putting h₁=e, that g was in H. So G acting freely is certainly sufficient for (Not Extra). I don’t think it’s a necessary condition, though; the existence of some g₁ such that g₁x=x doesn’t seem to guarantee (Extra).

I’ll have to think a bit more about the other things you wrote.

Suppose there is some g₁ in (H_G exclude H) — I won’t write that with a \, to avoid confusion! — where H_G is the normaliser of H (the elements of G that give you back H when you use them to conjugate H). Suppose also that g₁x = x, i.e. g₁ fails to act freely on the point x in our G-set X. This also implies that g₁^-1x = x.

Then for all h₁ in H, we have:

g₁h₁x = g₁h₁g₁^-1x = h₂x

for some h₂ in H. In other words, we’ve shown that g₁(H⋅x)=H⋅x, and g₁, though not in H, is an extra symmetry of the orbit H⋅x.

I don’t think the converse is true, though. If g₂ is some extra symmetry of H⋅x, there must be at least one g₁ that does not act freely on x, but what exactly can we say about g₁?

Well, the extra symmetry condition tells us that for all h₁ in H:

g₂h₁x = h₂(h₁)x

for some h₂(h₁) in H, and hence:

g₁(h₁) = h₂(h₁)^-1g₂h₁

fails to act freely on x:

g₁(h₁)x = x

Because g₂, by hypothesis, is not in H, g₁(h₁) can never be in H either. In fact, we’ve shown that there must be at least one free-action-violating group element g₁ in the double coset Hg₂H. I don’t know quite what to make of that!

I’d just like to mention a few simple examples of orbits and their stabilisers, in case anyone else is pondering this.

(Example 1) Suppose G is the group of rotational symmetries of the cube, our G-set X is the set of vertices of the cube, and our subgroup H is the order-4 cyclic group generated by a rotation by 90 degrees around the z-axis. G acts transitively, but not freely, on X, since it includes 8 rotations whose axes are the lines joining opposite pairs of vertices.

The normaliser of H contains, in addition to H itself, 180-degree rotations around the x and y axes, and 180-degree rotations around the two pairs of opposite edge-centres that lie in the x-y plane (i.e. rotations around the lines y=±x), because conjugating with those rotations just turns elements of H into other elements of H.

It’s pretty obvious that the entire normaliser of H acts freely on X, i.e. none of its elements fixes a vertex.

If we take some vertex, x, then the orbit H⋅x will just be the four vertices that lie on some face parallel to the xy plane. And it’s clear that H itself is the entire stabiliser of H⋅x.

So this serves as a counterexample to the idea that G failing to act freely could in itself guarantee an extra symmetry of H⋅x. What it doesn’t make clear is exactly what relationship between the rotations that fix vertices, and our subgroup H, keeps the stabiliser of the orbit from being enlarged. As I noted, those rotations around the vertices lie outside the normaliser of H, but I want to stress that I haven’t proved that this condition alone is sufficient (and I don’t believe it is).

(Example 2) Keep the same G and H as Example 1, but now make our G-set X the set of face-centres of the cube. Once again, G will act transitively but not freely.

This time, neither H, nor two of the elements of its normaliser that lie outside H itself, will act freely on X. If we pick x to be a face-centre in the xy plane, then H will act freely on x, but one element of the normaliser outside H will fix x.

The orbit H⋅x will consist of the four face-centres that lie in the xy plane. And this time, the full stabiliser of H⋅x will be the entire 8-element normaliser of H, rather than just H itself. The result I proved in a preceding post was that any element of the normaliser of H that fixes x and isn’t in H must nevertheless belong to the stabiliser of H⋅x, and the whole normaliser of H turns out to be the smallest group we get by adding that element.

(Example 3) Suppose G is the group of rotational symmetries of the 4-cube, our G-set X is the set of 2-face-centres of the 4-cube (i.e. ordered quadruples containing two coordinates equal to zero, and two equal to ±1), and our subgroup H is the order-8 cyclic subgroup generated by:

S:(w,x,y,z)→(-z,w,x,y)

Once again, G acts transitively, but not freely, on X, since there are many non-trivial symmetries that fix 2-face-centres.

H, however, acts freely on X.

The normaliser of H contains 32 elements. The whole 32-element subgroup is generated by S, -I, and R, where:

R:(w,x,y,z)→(z,y,x,w)

-I acts freely on X, but R doesn’t, because R fixes (0,1,1,0).

If we choose x to be the 2-face-centre (0,1,1,0), then the orbit H⋅x will be one of the bands wrapping around the 4-cube that I described in an earlier post.

The stabiliser of H⋅x turns out to have 16 elements, i.e. it’s neither just H nor the full normaliser of H, but rather it’s the 16-element subgroup generated by adding R to H.

Hi Greg,

I think it’s better to write this down in ‘co-ordinate free’ notation, where it becomes clearer. Say we have a $G$-set $X$. Define an orbit $\mathcal{O}$ in $X$ to be a subgroupoid of $X // G$. In other words, it’s an orbit of the form $H \cdot x$ for some subgroup $H \subseteq G$ and some $x$ - though I want to avoid choosing a base-point $x$, in order to keep things co-ordinate free.

So let’s say $\mathcal{O}$ is an orbit in $X$. Then it’s clear that the stabilizer of $\mathcal{O}$ consists of those $g \in G$ such that $g \cdot x$ remains on the orbit, for each $x$ on the orbit. This is nothing but your Theorem 1, as I’ll explain in a moment.

Let me draw this in the way I always think of group actions : pictures! I hope everyone else does too :-) So here is our $G$-set $X$, thought of as a groupoid $X//G$:

An “orbit” $\mathcal{O}$ will be a closed cycle (i.e. closed under composition and inverses) in that picture. Picking a baspoint $x_o \in \mathcal{O}$, we must have $\mathcal{O} = H \cdot x_0$ for some subgroup $H \subseteq G$. We’ll draw out $\mathcal{O}$ in green :

Of course, I’ve only drawn a few arrows, and there should be arrows (inverses) going the other way, but I hope you get the idea.

The stabilizer of the orbit $\mathcal{O}$ consists of those $g \in G$ which ‘stay on the orbit’, i.e. $g \cdot x \in \mathcal{O}$ for each $x \in \mathcal{O}$. That’s clear. Said differently, the stabilizer of the orbit $O$ is the largest subgroup $A subseteq G$ such that $O = A \cdot x$.

If we pick co-ordinates this is your Theorem 1. Choose a basepoint $x_0 \in \mathcal{O}$. I’ve actually done it already in the above picture. Set $K = Stab(x_0)$. Then the stabilizers of the other points of the orbit are conjugate to $K$. In other words, the obvious co-ordinate free statement that

is equivalent to your theorem

Moreover, the corollary you give is also clear in co-ordinate free notation. For if $g \in N[H]$, then it implies that a ‘black line followed by a green line is the same as a green line followed by a black line’, i.e. $hg \cdot x = gh' \cdot x$. Thus if also $g \in K$, then this means that $g$ must ‘stay on the orbit’:

In other words, we have your corollary

Anyhow, I don’t think any of this actually answers your original question. You wanted to know what was the actual mechanism explaining when $Stab(H \cdot x)$ can be larger than $H$. All of the stuff I give above - and your own answer to your question - is just a reformulation of the definition of $Stab (H \cdot x)$. It doesn’t explain anything. On the other hand, I think it’s just one of those things… sometimes $Stab (H \cdot x)$ is larger than $H$, sometimes it’s not; there’s no general underlying cause . I guess I’m getting into philosophy here :-)

I wanted to try to say something a bit more intuitive about this

Theorem: Given a $G$-set $X$, a point $x\in X$ with stabiliser $K=Stab(x)$, and a subgroup $H\subseteq G$, we claim that $Stab(H\cdot x) = \{g\in G|\forall h\in H, (H g) \cap h K h^{-1} is not empty\}$.

which I proved in a previous post. Well, the first thing might be to rewrite it slightly, to make what’s going on a bit clearer:

Theorem: Given a $G$-set $X$, a point $x\in X$, and a subgroup $H\subseteq G$, we claim that $Stab(H\cdot x) = \{g\in G|\forall h\in H, (H g) \cap Stab(h x)\, is not empty\}$.

This makes it almost obvious, because $H\cdot x$ just consists of points of the form $h x$, so what we’re really saying about g is that $\forall y\in H\cdot x$, $\exists h_2\in H$ such that $h_2 g y=y$, and hence $g y=h_2^{-1}y$, so of course $g y\in H\cdot x$.

But the main thing I want to focus on is the issue of “how does the extra symmetry creep into $Stab(H\cdot x)$”, where by “extra” I mean symmetries that aren’t in $H$. Why am I obsessing about this? Well, as I understand it, the whole point of Kleinian geometry is the idea that “subgroups correspond to figures”, but while I can see that it’s always possible to make subgroups $H$ up to conjugacy into the points of a $G$-set that you cook up yourself, namely $G$\$H$, I want to know when this idea continues to make sense in the context of a $G$-set that we’ve been given by some other route, the most obvious being the fundamental representation of a matrix group. If you give me a subgroup $H$ of a matrix group and tell me it corresponds to a figure, I want to know if I can draw a picture in $R^n$ of some shape that has $H$ as its stabiliser! And the most obvious candidate to start with for such a shape will be $H\cdot x$ for some x.

Now, if you stare at the first version of the theorem for a bit, it soon becomes clear that every $g\in Stab(H\cdot x)$, $g\notin H$, really only gets there thanks to some $k\in Stab(H\cdot x)$, where $k\in K=Stab(x)$, and $k\notin H$. In other words, the whole of $Stab(H\cdot x)$ is generated by $H$ and some subset of $K$; all the other elements come from multiplying those $k$s by elements of $H$.

So an interesting set to think about is $K\cap Stab(H\cdot x)=\{k\in K|\forall h\in H, (H k) \cap Stab(h x)\, is not empty\}$. In other words:

$k$ will sneak into $Stab(H\cdot x)$ if multiplying it on the left by elements of $H$ can yield a member of the stabiliser of each individual point in the orbit $H\cdot x$.

(Of course that’s trivially possible if $k\in H$, but we’re interested in the non-trivial cases where $k\notin H$.)

Let’s apply this recipe to one of the examples I discussed previously.

(Example 1) Suppose G is the group of rotational symmetries of the cube, our G-set X is the set of vertices of the cube, and our subgroup H is the order-4 cyclic group generated by a rotation by 90° around the z-axis. We set $x=(1,1,1)$, and then we have:

$H\cdot x=\{(1,1,1),(-1,1,1),(-1,-1,1),(1,-1,1)\}$

i.e. the four vertices of the face with $z=1$. Now, instead of merely noting that we’re unable to apply the corollary of the theorem that lets us bring elements of $N[H]\cap K$ into $Stab(H\cdot x)$ (which, in so many words, is all I could say when I discussed this example previously), we can look at each non-trivial element of $K$ and see why it doesn’t sneak in.

The two non-trivial elements of $K$ are the two rotations, by 120° and 240°, around the vector $(1,1,1)$. To sneak in, we need to be able to follow one of these rotations by an element of $H$, i.e. a rotation around the $z$-axis by some multiple of 90°, so that the product will give us an element of the stabiliser of each of the points in the orbit, i.e. a rotation by 120° or 240° around each of those four vertices. Of course this test is passed trivially for the stabiliser of $x$ itself. If we note the following examples, symmetry will tell us all we need to deal with the other cases.

• If we rotate the edge with centre $(0,1,1)$ into $(1,0,1)$ (a 120° rotation around $(1,1,1)$), then rotate 90° around the $z$-axis, we bring $(0,1,1)$ back to itself. So we have a rotation that preserves an edge.
• If we follow the 120° rotation around $(1,1,1)$ with a 180° rotation around the $z$-axis, the edge-centre $(0,1,1)$ is mapped to $(-1,0,1)$, which means the net rotation is around the vertex those two edges share, $(-1,1,1)$. Note that this vertex is adjacent to $(1,1,1)$.
• If we follow the 120° rotation around $(1,1,1)$ with a 270° rotation around the $z$-axis, the edge-centre $(0,1,1)$ is mapped to $(0,-1,1)$. If we check what happens to $(1,0,1)$ as well, it ends up at $(1,-1,0)$, and we see that the net rotation is 90° around the $x$-axis.

What we see is that the three non-trivial rotations in $H$ can only transform a rotation around a vertex in $K$ into a rotation around one other vertex, which will be adjacent to the original one. So there’s no hope that this process is ever going to yield a rotation around the vertex $(-1,-1,1)$, which lies diagonally opposite $(1,1,1)$ across the square of $H\cdot x$. From the symmetry of the situation, this will disqualify both rotations in $K$ from joining $Stab(H\cdot x)$, so $Stab(H\cdot x)$ remains equal to $H$ itself.