## April 26, 2007

### This Week’s Finds in Mathematical Physics (Week 250)

#### Posted by John Baez

In week250 of This Week’s Finds, start with a little puzzle about a game of flipping coins. Then learn about Popescu-Rohrlich game, which involves flipping coins and quantum entanglement!

Then, continue reading the Tale of Groupoidification — in which we start by recalling the history of special relativity, and use an example from relativity to ponder "atomic invariant relations". We’ll see these are just what mathematicians normally call "double cosets" — but we’ll see they’re also spans of groupoids equipped with extra stuff.

Posted at April 26, 2007 4:50 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1253

### Re: This Week’s Finds in Mathematical Physics (Week 250)

You might emphasize, in the description of the coin-toss game, that you and your friend are required to blurt out your guesses at the same time. Otherwise guesser #1 could say “(My coin is) heads” so guesser #2 is guaranteed to be correct.

Also, a hint for the game: there exists a perfect losing strategy!

Posted by: Allen Knutson on April 26, 2007 5:31 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

An email correspondent wrote:

About the coin flip coincidence — in order for the strategy to work the two friends must exchange one piece of information, in violation of the rules.

They need to initially agree to choose heads if heads or otherwise. If the experiment isn’t ‘prepared’ you are back to a ‘classical’ case.

To which I replied:

I understand what you mean, but:

They can adopt a strategy before the game starts; that’s not against the rules. Indeed it seems difficult to formulate a precise rule against ‘picking a strategy beforehand’.

Posted by: John Baez on April 30, 2007 9:35 PM | Permalink | Reply to this

### Coin-tossing (contains spoiler)

Here’s another way to arrive at the best (and worst) strategies for the coin game.

It’s clearly equivalent to the following game: you each flip a coin, look at the result, then declare (simultaneously) whether you think the results are the same (HH or TT) or different. And it’s clear what the best strategy for that is!

Here’s another game that can be analyzed in a similar way, i.e. by observing that it’s isomorphic to a game whose solution is obvious. I have an ordinary deck of cards, face down. I turn them face up one by one. At some point you have to say “stop”, at which point I deal the next card; you win if it’s red. (You can say stop before the first card is dealt, but you must say stop at some point before the last card is dealt.) What’s your best strategy?

I don’t actually like this sort of problem very much. But I do like the solution.

Posted by: Tom Leinster on April 26, 2007 6:07 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Someone recently posed to our group the following problem, which resembles somewhat your coin-tossing game.

100 Bayesian inference people are imprisoned in a room. The guy who has imprisoned them is mad and wants to kill everybody, but as he is really completely mad he also wants to give them a tiny chance to survive all together. In another room are 100 boxes in a row. The name of each person is in one box (and reciprocally, each box contains the name of one person). The guard takes one person (say Mr A) from the first room and sends him to the second one. Mr A has to find the box which contains his name. For this, he is allowed to open 50 boxes. After these 50 attempts, if he has not found his name then everybody (the 100 people) is killed. If he has succeeded in finding his name, then he is sent to another room, and the boxes are put once again in exactly the same state as they were at the beginning, so that no information can be left by Mr A to the following persons. Then the guard takes another person from the first room and asks them the same thing (50 attempts to find your name). If this new person fails, then everybody (including Mr A) is killed, else a third person comes, and so on.

The aim: to survive.

The 100 people can discuss between them the strategy to adopt before the guard comes and takes the first person. There is no cheat (the guard knows every name) and really NO INFORMATION can be left from one person to the following one, except the fact that they are all still alive.

Intuitively, if one person chooses 50 boxes randomly, then the chances that the group is still alive after that decrease by 50%. So that if 4 persons (among the 100) choose randomly, then the expectation to survive is already less than 10%.

There does exist a strategy for which the probability that the whole group survives is more than 30%. Find it !

Posted by: David Corfield on April 26, 2007 6:17 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

By the Law of Conservation of Sneaky Hints, and assuming that 100 is chosen as an approximation of infinity, then “more than 30%” is most probably 1 / e = 0.367879441.

“Derangement” is my follow-up clue. Which, if I’m right, proves that I know the solution, and if I’m wrong, identifies my mental state.

Posted by: Jonathan Vos Post on April 26, 2007 8:53 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

100 as an approximation of infinity is right.

$1-\mathrm{ln}2$ is approximately 30%.

Derangement belongs to the right branch of mathematics, but isn’t quite what’s wanted.

Posted by: David Corfield on April 26, 2007 10:04 PM | Permalink | Reply to this

### Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

Having used what hackers call “social engineering’ to verify that 100 is approximately infinity, and the combinatorics – one can now reverse engineer a solution based on the Alternating Harmonic Series, a.k.a. the Merctaor series, a.k.a. the Newton-Mercator series, a.k.a. the Dirichlet eta function of 1.

ln 2 = SUM[for k = 1 to infinity] [(-1)^(k-1)]/k

That is, set x = 1 in the Mercator series:

ln(1+x) = SUM[for k = 1 to infinity] (x^k)[(-1)^(k-1)]/k
= x - (1/2)x^2 + (1/3)x^3 - (1/4)x^4…

It takes an infinity (or in our case 100) steps to apply the alternating series appropriately to the boxes. I’m assuming that, though no information is passed between bayesians with the boxes, they can agree to an assignment of integers in [1,100] to themselves, and assignment of numbers say from left to right on the boxes, and then all apply the same algorithm, i.e. the one I’m hinting at which has this generating function…

Posted by: Jonathan Vos Post on April 27, 2007 5:27 PM | Permalink | Reply to this

### Re: Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

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

Posted by: Jonathan Vos Post on April 27, 2007 6:09 PM | Permalink | Reply to this

### Re: Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

George is certainly right about the strategy. Everyone receives a number from 1 to 100. Person N enters the room, opens box N, then follows the trail.

The analysis usually runs by seeing that what the people are hoping for is that the permutation on 100 symbols represented by the way the slips of paper are contained in the boxes has no cycle of length greater than 50. Then you need to find the probability that a random permutation on 100 letters has this property.

The details are here.

The resemblance to John’s problem is that the prisoners are managing to correlate their strategies so that if 1 fails at least 50 others will too.

Posted by: David Corfield on April 27, 2007 6:57 PM | Permalink | Reply to this

### Re: Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

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×\cdots ×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

(1)$\sum _{i=51}^{100}1/i$

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!

Posted by: Robin on April 27, 2007 7:50 PM | Permalink | Reply to this

### Re: Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

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?

Posted by: John Armstrong on April 27, 2007 9:45 PM | Permalink | Reply to this

### Re: Newton-Mercator series; Re: This Week’s Finds in Mathematical Physics (Week 250)

99.5

Posted by: Aaron Bergman on April 27, 2007 9:47 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Say hi to Dr. Bub for me. I remember pushing for a lot of quantum computation in his quantum philosophy course my last semester at Maryland, especially after we’d met at the quantum computation short course at that January’s AMS meeting.

Unfortunately I can’t seem to find my copy of Interpreting the Quantum World anymore. I must not have gotten it back after one of the many times I’ve lent it out.

Posted by: John Armstrong on April 26, 2007 11:07 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Darn! He walked out the door to leave just after I read this — didn’t get a chance to catch him.

It’s the last night of the conference. The chef here had a nice telescope and after dinner we all went out and looked at the rings of Saturn, mountains on the Moon, and the phase of Venus.

Posted by: John Baez on April 27, 2007 10:34 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

John Baez wrote:

Finally, if you lock yourself in a cellar and think about this for a few minutes (or months), you’ll realize that this weird-looking set is isomorphic to

H\G/K

For people like me who don’t have cellars, I’ll attempt a simple way to see what’s going on here, and hope that JB strikes me with lightning if I say anything misleading.

The quotient spaces G/H and G/K are the sets of right cosets of H and K respectively, so generic elements of each will take the form Hg1, Kg2. Now, I think the only sensible left action of G on the right quotient G/H is:

g(Hg1) = H(g1g-1)

and so the left action of G on G/H × G/K is:

g(Hg1, Kg2) = (H(g1g-1), K(g2g-1))

If we write the orbit that contains (Hg1, Kg2) as [(Hg1, Kg2)], then consider the map:

[(Hg1, Kg2)] → Hg1g2-1K

where the object on the RHS is the double coset containing g1g2-1. It’s not hard to see that this element is invariant under the left action of any g on the orbit representative. It’s also not hard to see that if we choose different representatives of our right cosets of H and K, in other words if we replace g1 by hg1 and g2 by kg2, we just get a new representative, hg1g2-1k-1, of the same double coset Hg1g2-1K.

Of course if we preferred, we could use the map:

[(Hg1, Kg2)] → Kg2g1-1H

which takes the orbits into K\G/H instead.

Sorry if this is excessively trivial! I want to post something slightly more substantial on this subject when my brain has defrosted a little more …

Posted by: Greg Egan on April 27, 2007 3:55 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Hmm, I’m not 100% sure that I used the correct cosets in the above; maybe I should have used left cosets for G/H and G/K?

But interestingly enough it seems to make no difference; everything seems to work out the same, either way. The left action of G on pairs of left cosets is simply:

g(g1H, g2K) = (gg1H, gg2K)

and we can use the map from the orbits into H\G/K:

[(g1H, g2K)] → Hg1-1g2K

or the map from the orbits into K\G/H:

[(g1H, g2K)] → Kg2-1g1H

Posted by: Greg Egan on April 27, 2007 4:34 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

“But interestingly enough it seems to make no difference; everything seems to work out the same, either way.”

Because, at the next level of abstraction, the transformation {Left –> Right, Right–>Left} changes nothing. Automorphism…

Or am I about to be struck by lightning, and turned into Cantor dust?

Posted by: Jonathan Vos Post on April 27, 2007 5:49 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Greg wrote:

Sorry if this is excessively trivial!

It’s not! I’ve proved this fact a few times in my life, and I did it twice more while writing week250 just to reassure myself that it was still true. But, I couldn’t figure out any way to prove it without the slightly nerve-racking calculation you just did. It’s not the sort of stuff that’s really fun to read… so I decided to ‘leave it as an exercise for the reader’. But, it’s nice to have it available here.

Hmm, I’m not 100% sure that I used the correct cosets in the above; maybe I should have used left cosets for $G/H$ and $G/K$?

To make me really happy, you would have used cosets of the form ${g}_{1}H$ and ${g}_{2}K$, because I emphasized that I was thinking of $H$ and $K$ as acting on $G$ via right multiplication, and modding out by that action — thus justifying the notation $G/H$ and $G/K$ with $H$ and $K$ on the right.

If you’d done this, there’d have been obvious left actions of $G$ on $G/H$ and $G/K$, namely

$g:{g}_{1}H\to g{g}_{1}H$

$g:{g}_{2}K\to g{g}_{2}K$

But, you used cosets of the form $H{g}_{1}$ and $K{g}_{2}$. So, to get left actions of $G$, you were forced to use a trick — the usual trick for turning right actions of groups into left actions:

$g:H{g}_{1}\to H{g}_{1}{g}^{-1}$

$g:K{g}_{2}\to H{g}_{2}{g}^{-1}$

So, you wound up defining $G$\$\left(G/H×G/K\right)$ in a slightly different way than I wanted… but it made no serious difference in the end! The differences were only inessential matters of convention, and you still got $G$\$\left(G/H×G/K\right)\cong$ H\G/K.

Normally one isn’t so pedantic about the notations $G/H$ versus $H$\$G$. But in this double coset business it’s worthwhile being careful, since one is modding out by both left and right actions of subgroups of $G$.

However, one result of all this care is to see that one can relax somewhat, since one has a nice bijection $H$\$G/K\cong K$\$G/H$.

So, in the end, it’s no big deal.

Posted by: John Baez on April 27, 2007 10:33 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

OK, I’ll try a concrete example now.

Suppose G is the set of rotational symmetries of the cube, H is an order-4 cyclic subgroup generated by a 90-degree rotation that preserves a face, and K is an order-3 cyclic subgroup generated by a 120-degree rotation that preserves a vertex.

Then G/H will have 6 cosets gH, and will be isomorphic to the set of faces of the cube, and G/K will have 8 cosets gK, and be isomorphic to the set of vertices.

The action of G on G/H × G/K will, in effect, just rigidly rotate any pair (face, vertex) together, so there will be two orbits: one consisting of pairs of faces and vertices where the vertex lies on the face, and the other consisting of pairs where the vertex lies on the opposite face.

But being a rotation group rather than a projective geometry group, this is really about angles rather than incidence. We can think of G/H as being the 6 single points at the centres of faces, rather than the whole faces, and the invariant relation is then just the angle between the face centre and the vertex. If we were working with the whole of SO(3) and H and K were both isomorphic to SO(2), then the cosets would be directions in space, and the orbits / double cosets would be angles between those directions.

Posted by: Greg Egan on April 28, 2007 3:24 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

One more concrete example, this one a bit more interesting than the last.

Suppose G is the set of rotational symmetries of the 4-cube. There are 192 elements in this group; one way to count this is to note that the full group of symmetries of the 4-cube can permute the 4 coordinate axes 4!=24 ways, as well as inverting any of them, giving 24=16 choices of inversions, for a total of 384 symmetries. Half of these, 192, will have determinant 1.

Now suppose we set both H and K equal to the order-8 cyclic subgroup generated by:

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

It’s not hard to see that S has no fixed points except the zero vector. If you analyse its eigenstructure, you can show that it rotates by 45° in one plane, and 135° in a second, orthogonal plane. These two planes contain no “features” of the 4-cube: no vertices, edge-centres, face-centres, or 3-cube centres. They can’t, because the cosines of the angles between such k-cube-centres must be rational numbers (assuming our 4-cube has integer dimensions), whereas cos 45° is irrational.

So the choice of what we call a “figure” corresponding to H isn’t so obvious. We could choose one of the regular octagons where one of the planes of rotation of S intersects the boundary of the 4-cube. Or we could choose certain orbits of faces under the action of H, such as:

B1 = H . (1,1,0,0)

Successive applications of S produce face-centres rotated by 60° from the preceding one (though this is not a simple rotation in one plane, so we get back to where we started after eight operations, not six). What we end up with for B1 is a kind of band of eight faces zig-zagging around the 4-cube.

Band of Eight Faces

Because |H|=8, there will be 192/8=24 such bands of faces, meaning that each of the 4-cube’s 24 faces will belong to 8 different bands.

What are the possible invariant relations between two bands? I haven’t actually figured out the answer yet, so I’ll post again if I’m not too lazy to work this out, and I can find a reasonably simple way to describe the calculation …

Posted by: Greg Egan on April 28, 2007 12:01 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Oops, it turns out that the stabiliser of my figure B1 is larger than the cyclic group I gave for H. The map:

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

is not a power of S, but it preserves B1. So if we’re going to look at the invariant relations between these bands, we need to expand H to the 16-element subgroup that includes R, and note that there will only be 192/16=12 bands.

Posted by: Greg Egan on April 28, 2007 1:51 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

OK, what are the invariant relations between bands of eight 2-faces wrapping around a 4-cube?

The stabiliser of one such band is the 16-element group generated by S and R, where:

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

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

S has order 8 and R has order 2. We’re setting both H and K equal to this 16-element group. We’ve taken our canonical band to be:

B1 = H.(1,1,0,0)

and we can find all 8 elements of B1 by applying successive powers of S. Since S4=-I and every 2-face in B1 is accompanied by its opposite, we only really need to mention the first four 2-faces:

(1,1,0,0), (0,1,1,0), (0,0,1,1), (-1,0,0,1)

Our G is the 192-element group of rotational symmetries of the 4-cube, so there will be |G|/|H|=12 cosets of H in G/H, and hence twelve bands. I claim that there are just 4 double cosets of H in H\G/H.

(1) The first double coset has representative I, and is just H itself. The invariant relation between two bands this corresponds to is, of course, just being the same band.

(2) The second double coset has representative:

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

If we apply N to the first four elements of B1, we get:

{(1,1,0,0), (0,1,1,0), (0,0,1,1), (-1,0,0,1)}→

{(1,-1,0,0), (0,-1,1,0), (0,0,1,-1), (-1,0,0,-1)}

These elements are all orthogonal to the corresponding ones in B1, so N(B1) will have no 2-faces in common with B1, and that’s the invariant relation to which the double coset containing N corresponds.

In fact, N(B1) is a band that lies more or less in a plane orthogonal to that of B1; more precisely, while the 2-faces of B1 contain all the vertices of one octagon where one plane of rotation of S intersects the boundary of the 4-cube, N(B1) has the same relationship to the other plane of rotation of S. So N(B1) is the only band that has this precise relationship with B1.

(3) The next double coset has representative:

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

If we apply T to the first four elements of B1, we get:

{(1,1,0,0), (0,1,1,0), (0,0,1,1), (-1,0,0,1)}→

{(1,1,0,0), (0,1,0,-1), (0,0,1,-1), (-1,0,1,0)}

The first 2-face is unchanged, but the others are mapped right out of the band. So only that first 2-face and its opposite will be in T(B1), and the invariant relation for the double coset containing T is sharing two 2-faces.

T(B1) is not unique in its relationship with B1; there are a total of 8 different bands that share two 2-faces with it, and for which the pair could be rotated into the same configuration.

(4) The last double coset has representative:

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

If we apply V to the first four elements of B1, we get:

{(1,1,0,0), (0,1,1,0), (0,0,1,1), (-1,0,0,1)}→

{(1,1,0,0), (0,1,-1,0), (0,0,-1,-1), (-1,0,0,-1)}

So V(B1) has every second 2-face, or 4 out of the 8, in common with B1, and so it corresponds to the invariant relation sharing four 2-faces.

There’s a second band besides V(B1) which has this relation to B1, and overlaps it on the other four 2-faces.

So we’ve accounted for all 12 bands:

• B1 itself;
• N(B1), which shares no 2-faces with B1;
• eight bands that are like T(B1), sharing two 2-faces with B1; and
• two bands that are like V(B1), sharing four 2-faces with B1.

I hope these grungy calculations haven’t lowered the n-categorical tone of the café too much. I can only really absorb these ideas if I work through a few specific examples and see all the greasy cogs in motion.

Posted by: Greg Egan on April 29, 2007 1:58 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

Posted by: dave tweed on April 29, 2007 9:54 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

Posted by: Todd Trimble on April 29, 2007 1:09 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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.

Posted by: John Baez on April 30, 2007 8:46 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Just to clarify: when talking about page limits I was more talking about the more formal publications (arxiv, journal, etc); the TWFs tend to be more example-rich.

One of the important points about concrete examples is that you can independently “weakly-verify” out something you believe you’ve understood in the original theory (because you can just work out things directly in the concrete example). From some of your posts I think you and your group also do this, it just isn’t obvious from reading some of the papers. As a real-life example, a while ago I tried doing some stuff in a (non-commutative) clifford algebra and it was slow going until I found the matrix representation so I could do numerical instances by computer as a weak-verification check I wasn’t implicitly using commutativity anywhere I shouldn’t have.

Posted by: dave tweed on May 1, 2007 9:00 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

If I haven’t yet bored all café readers away from this sub-thread, here’s a question I meant to ask earlier: 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?

It’s obvious that we can cook up a set X where everything works nicely: we just choose X=G/H, making the points of X the cosets of the form g1H, and the left action is:

g:g1H→(gg1)H

Then the stabiliser of the point g1H will be the subgroup g1Hg1-1.

But when we’re not free to choose X, things aren’t so clear.

I’m fairly sure that Y can’t always exist, because of the example I discussed in my last few posts, where the stabiliser of the figure I was looking at turned out to be larger than the cyclic group I originally planned to use.

Posted by: Greg Egan on April 29, 2007 5:11 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

(1)$\mathrm{transitive}G-\mathrm{sets}↔\mathrm{subgroups}H\subseteq G\mathrm{up}\mathrm{to}\mathrm{conjugation}.$

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

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

Doing $←$ and then $\to$, we get the subgroup $H\left(X\left(H\right),{H}^{\prime }\right)={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}\left(G\right)$ of maximal tori (maximal abelian closed subgroups) of $G$.

$G$ also acts on $Tori\left(G\right)$ 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}\left(G\right)$ is some kind of ‘coarse-graining’ of $\Lambda G$. The stabilizers in $\mathrm{Tori}\left(G\right)$ 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?

Posted by: Bruce Bartlett on April 29, 2007 11:22 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Maybe I can make my own question clearer. If you hand me a G-set X and a subgroup H of G, my “generic expectation” (for want of a more precise criterion) would be that if I pick a generic point x in X, its orbit under H will have no extra symmetries other than those of H itself. The reason for this intuition goes back to Euclidean geometry. Suppose G is SO(2), X is the fundamental representation of SO(2) on R2, and H is the cyclic subgroup generated by a rotation by 2π/n. Unless I’m very unlucky and pick the origin as x, the orbit of x under H will consist of the vertices of a regular n-gon, and will have H as its stabiliser.

And in the example I’ve been puzzling over, where H is the cyclic subgroup generated by this linear operator on R4:

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

(which happens to be a rotational symmetry of the 4-cube) if I choose a generic point x in R4, the stabiliser of its orbit under H will be H itself. But if my G-set is restricted down to any of the k-cube-centres of the 4-cube (e.g. face-centres, vertices, etc.), the stabiliser turns out to be a larger group, with H as a subgroup.

So I guess what I’m trying to do is put my finger on precisely what makes one case of this construction “sufficiently generic” and another not.

Posted by: Greg Egan on April 29, 2007 1:51 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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$:

(1)$\mathrm{Orbit}H\cdot x\phantom{\rule{1em}{0ex}}↔\phantom{\rule{1em}{0ex}}\mathrm{subgroupoid}\mathrm{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\to X$. But sadly it wasn’t an automorphism, since ${f}_{g}\left(x\right)=g\cdot x$, but ${f}_{g}\left(h\cdot x\right)=\mathrm{gh}\cdot x\ne h\cdot {f}_{g}\left(x\right)$. Nasty!

But in the groupoid picture, we can play this game. Given $g\in G$, we get a functor ${F}_{g}:X//G\to X//G$, defined by sending

(2)$\stackrel{h}{←}x\phantom{\rule{1em}{0ex}}↦\phantom{\rule{1em}{0ex}}\stackrel{{\mathrm{ghg}}^{-1}}{←}g\cdot x.$

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

(3)$G\to \mathrm{Aut}\left(X//G\right)!$

Okay, back to your original question :-) Given a $G$-set $X$, a natural thing to consider is the category $\mathrm{Sub}\left(X\right)$ 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$,

(4)$H\subseteq \mathrm{Aut}\left(H\cdot x//H\right).$

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 ${ℤ}_{4}$), then these other arrows also give you automorphisms.

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

Posted by: Bruce Bartlett on April 29, 2007 6:57 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

The trick here is that we’re kind of allowed to ‘rotate’ our group as we go along. So - we get a nice homomorphism $G\to \mathrm{Aut}\left(X//G\right)!$

Nice point!

Secretly – in one of the private corners of the $n$-Café – we were talking about this in the context of principal bundles, where $X={P}_{x}$ would be a fiber of such a bundle.

Now, this seems to suggest an interesting relation to some other meme inhabiting the $n$-Café. Schreier theory combined with the integrated Atiyah sequence tells us that, given the principal $G$-space ${P}_{x}$, we first form ${P}_{x}{×}_{G}G\phantom{\rule{thinmathspace}{0ex}},$ (where the $G$-action of $G$ on $P$ is the standard one (here taken to be from the right) and that on $G$ itself is by the adjoint action).

This is a group. For $t\in {P}_{x}$ the group operation is $\left(t,g\right)\left(t,g\prime \right)=\left(t,gg\prime \right)\phantom{\rule{thinmathspace}{0ex}}.$ If, on the other hand, we multiply $\left(t,g\right)$ with $\left(t\prime ,g\prime \right)$ we first find $\stackrel{˜}{g}$ such that $t\prime =t\stackrel{˜}{g}\phantom{\rule{thinmathspace}{0ex}},$ which gives us $\left(t\prime ,g\prime \right)=\left(t,\stackrel{˜}{g}g\prime {\stackrel{˜}{g}}^{-1}\right)\phantom{\rule{thinmathspace}{0ex}};$ and then use the above formula.

So this group ${P}_{x}{×}_{G}G$ is isomorphic to $G$. But not canonically so. Every element of ${P}_{x}$ defines one group isomorphism ${P}_{x}{×}_{G}G\simeq G$.

Interestingly, also torsor automorphisms $F$ act on this group, but only by inner automorphisms: $\left(t,g\right)↦\left(F\left(t\right),g\right)=\left(t\stackrel{˜}{g},g\right)=\left(t,\stackrel{˜}{g}g{\stackrel{˜}{g}}^{-1}\right)\phantom{\rule{thinmathspace}{0ex}}.$

Anyway, we can form the automorphism 2-group of this: $\mathrm{AUT}\left({P}_{x}{×}_{G}G\right)\phantom{\rule{thinmathspace}{0ex}}.$

This now reminds me a lot of your $\mathrm{Aut}\left({P}_{x}//G\right)\phantom{\rule{thinmathspace}{0ex}}.$

What precisely is the relation between the two?

Posted by: urs on April 30, 2007 5:39 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

What precisely is the relation between the two?

Okay, I am short of time, but let’s see what can be done.

First: what is the most general automorphism of the groupoid $\mathrm{Aut}\left(X//G\right)$, in the case that $G$ acts free and transitively?

Let $F$ be such an automorphism. Pick some element $x\in X$. It will be sent to $y=F\left(x\right)\phantom{\rule{thinmathspace}{0ex}}.$ Moreover, it is clear that $F$ has to act by group automorphisms of $G$ on morphisms. So $F:\left(x\cdot h\stackrel{h}{←}x\right)↦\left(y\cdot F\left(h\right)\stackrel{F\left(h\right)}{←}y\right)\phantom{\rule{thinmathspace}{0ex}}.$ This shows that $F$ is now also already fixed on all objects.

So: every choice $\left(x,y\right)\in X×X$ of a pair of points in $X$ together with a choice $F\in \mathrm{Aut}\left(G\right)$ of a group automorphisms defines an automorphism of the action groupoid $X//G$. And every such automorphism is obtainable this way.

But not all such choices gives different automorphisms:

let $x=\stackrel{˜}{x}\cdot g$ and $y=\stackrel{˜}{y}\cdot F\left(g\right)\phantom{\rule{thinmathspace}{0ex}}.$

Then the above assignment reads $F:\left(\stackrel{˜}{x}\cdot gh\stackrel{h}{←}\stackrel{˜}{x}\cdot g\right)↦\left(\stackrel{˜}{y}\cdot F\left(gh\right)\stackrel{F\left(h\right)}{←}\stackrel{˜}{y}\cdot F\left(g\right)\right)\phantom{\rule{thinmathspace}{0ex}},$ which is the same as that defined by $\left(\left(\stackrel{˜}{x},\stackrel{˜}{y}\right),F\right)\phantom{\rule{thinmathspace}{0ex}}.$ This means we can always fix $x$ and only vary $y$. So pick that fixed element $x$ once and for all. Then automorphisms are given by pairs $\left(y,F\right)\in X×\mathrm{Aut}\left(G\right)\phantom{\rule{thinmathspace}{0ex}}.$

When Bruce defined the morphism $G\to \mathrm{Aut}\left(X//G\right)$ he used $g↦\left(x\cdot g,{\mathrm{Ad}}_{g}\right)\phantom{\rule{thinmathspace}{0ex}}.$

Hm, no time to ponder what this is now telling us…

Posted by: urs on April 30, 2007 6:11 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Good question. But since ${P}_{x}{×}_{G}G$ is isomorphic to $G$ as a group (even though the isomorphism is not canonical), it must be that their automorphism 2-groups are isomorphic,

(1)$\mathrm{AUT}\left({P}_{x}{×}_{G}G\right)\cong \mathrm{AUT}\left(G\right).$

Also, inner automorphisms of the one go over into inner automorphisms of the other.

On the other hand, consider $\mathrm{Aut}\left({P}_{x}//G\right)$. It seems there are three basic types of automorphisms :

(1) Torsor automorphisms, i.e. maps satisfying $F\left(x\cdot g\right)=F\left(x\right)\cdot g$ (using a right-action). We think of these as functors which send

(2)$x\stackrel{g}{\to }\phantom{\rule{1em}{0ex}}↦\phantom{\rule{1em}{0ex}}F\left(x\right)\stackrel{g}{\to },$

(2) ‘Rotating’ automorphisms for each $h\in G$, which send

(3)$x\stackrel{g}{\to }\phantom{\rule{1em}{0ex}}↦x\cdot h\stackrel{{h}^{-1}\mathrm{gh}}{\to },$

(3) Other, ‘outer’ automorphisms.

Heh, I guess I’m hedging my bets and avoiding your question! All I want to say here is that I would think of both the first two types as ‘inner’. Moreover, it’s clear that these two 2-groups are not the same… at least not obviously the same! For in the case of $\mathrm{Aut}\left({P}_{x}//G\right)$, each $h\in G$ gives a distinct automorphism, while in the case $\mathrm{AUT}\left({P}_{x}{×}_{G}G\right)$, the inner automorphisms are quite few in number. I mean if $G$ is abelian, there is only one inner automorphism.

Posted by: Bruce Bartlett on April 30, 2007 6:57 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Moreover, it’s clear that these two 2-groups are not the same… at least not obviously the same!

I’d be surprised if they were not related, as I said. Maybe equivalent, maybe one being a sub-thing of the other.

Both are 2-groups that are canonically associated - up to equivalence already - with a group $G$ and the notion of a torsor of it. Nothing else. Both essentially already look like $\mathrm{AUT}\left(G\right)$ already - up to choices of elements in a $G$-torsor.

So that’s why I would be surprised if they were not related.

But I should work it out.

Posted by: urs on May 2, 2007 9:43 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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 Cn and G is SO(2), all of G acts freely on R2\{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 R4\{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 h1 in H, there exists an h2 in H with:

gh1x=h2x, or

h2-1gh1x=x

But if G acts freely on x, that would imply gh1=h2, or putting h1=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 g1 such that g1x=x doesn’t seem to guarantee (Extra).

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

Posted by: Greg Egan on April 30, 2007 1:36 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

Then for all h1 in H, we have:

g1h1x = g1h1g1-1x = h2x

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

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

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

g2h1x = h2(h1)x

for some h2(h1) in H, and hence:

g1(h1) = h2(h1)-1g2h1

fails to act freely on x:

g1(h1)x = x

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

Posted by: Greg Egan on April 30, 2007 7:33 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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.

Posted by: Greg Egan on April 30, 2007 2:42 PM | Permalink | Reply to this

### Correction to previous post; Re: TWF 250

I wrote (in Example 3 in my previous post)

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

The normaliser of H does indeed contain 32 elements, including -I, but -I is S4. The other generator I should have listed was:

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

T acts freely on our G-set X of 2-face-centres, and it does not end up in the 16-element stabiliser of the orbit.

Posted by: Greg Egan on April 30, 2007 4:00 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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.

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

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}\left(3,ℝ\right)$ 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!

Posted by: John Baez on May 1, 2007 12:26 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

In response to a post by Greg, I wrote:

First, let me pose your question a bit more compactly…

I now think I drastically changed Greg’s question when I posed it. When he said ‘the stabilizer of a subset $Y\subseteq X$’, I thought he meant ‘the stabilizer of any point in the subset $Y\subseteq X$’. But now I think he meant what he actually said!

I don’t have the energy to re-tackle his question now; I hope my previous reply is not completely dull to everyone, though it was only combining a couple of very standard ideas.

Posted by: John Baez on May 1, 2007 12:36 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

John wrote:

I now think I drastically changed Greg’s question when I posed it. […] But now I think he meant what he actually said!

I did mean what I said! Alas, I’ve been too lazy to use MathML, which has led to me writing long-winded English descriptions for things that mathematicians probably find much easier to follow in compact notation — especially when they’re jet-lagged! So I’ll stop being lazy, and start using proper notation.

I think I’ve pretty much answered my own question, or at least something close enough to it to make me happy. I’ll write this out as a formal proof, then I’ll try to follow up with another post saying something a bit more intuitive about it.

Definitions and notation:

(i) Given a $G$-set $X$ and some point $x\in X$, we define the stabiliser of $x$, $\mathrm{Stab}\left(x\right)$, to be $\left\{g\in G\mid gx=x\right\}$. Given some subset $Y\subseteq X$, we define the stabiliser of $Y$, $\mathrm{Stab}\left(Y\right)$, to be $\left\{g\in G\mid \forall y\in Y,gy\in Y\right\}$.

(ii) Given some subgroup $H\subseteq G$ and some $x\in X$ we will write the orbit of $x$ under $H$, $\left\{hx\mid h\in H\right\}$, as $H\cdot x$.

(iii) Given some subgroup $H\subseteq G$, we define the normaliser of $H$, which we will write as $N\left[H\right]$, to be the subgroup $\left\{g\in G\mid gH{g}^{-1}=H\right\}$. Clearly $H\subseteq N\left[H\right]\subseteq G$, and $H$ is a normal subgroup of $N\left[H\right]$.

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

Proof: First, suppose $g\in \mathrm{Stab}\left(H\cdot x\right)$. This means that $\forall h\in H,\exists {h}_{2}\in H$ such that $ghx={h}_{2}x$. So ${h}_{2}^{-1}ghx=x$, and hence ${h}_{2}^{-1}gh\in K$. That in turn means that ${g}_{2}\equiv h{h}_{2}^{-1}g\in hK{h}^{-1}$. Clearly, we also have ${g}_{2}\in Hg$, so $\left(Hg\right)\cap hK{h}^{-1}$ is not empty.

Now suppose that we have some $g\in G$ such that $\forall h\in H,\left(Hg\right)\cap hK{h}^{-1}$ is not empty. Then $\forall h\in H,\exists k\in K$, and $\exists {h}_{2}\in H$, such that ${h}_{2}g=hk{h}^{-1}$. Then $gh={h}_{2}^{-1}hk$, and $ghx={h}_{2}^{-1}hkx={h}_{2}^{-1}hx$, so $ghx\in H\cdot x$.

Corollary: $N\left[H\right]\cap K\subseteq \mathrm{Stab}\left(H\cdot x\right)$.

Proof: If $k\in N\left[H\right]\cap K$ then by definition of $N\left[H\right]$, $\forall h\in H,kh{k}^{-1}\in H$, but equally well we can demand that $k{h}^{-1}{k}^{-1}\in H$. Define ${h}_{2}\equiv k{h}^{-1}{k}^{-1}$. Then $h{h}_{2}k=hk{h}^{-1}$; the LHS of this clearly belongs to $Hk$ and the RHS to $hK{h}^{-1}$, so the intersection $\left(Hk\right)\cap hK{h}^{-1}$ is non-empty, and by our theorem $k\in \mathrm{Stab}\left(H\cdot x\right)$.

Posted by: Greg Egan on May 1, 2007 6:26 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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 $𝒪$ 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 $𝒪$ is an orbit in $X$. Then it’s clear that the stabilizer of $𝒪$ 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” $𝒪$ will be a closed cycle (i.e. closed under composition and inverses) in that picture. Picking a baspoint ${x}_{o}\in 𝒪$, we must have $𝒪=H\cdot {x}_{0}$ for some subgroup $H\subseteq G$. We’ll draw out $𝒪$ 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 $𝒪$ consists of those $g\in G$ which ‘stay on the orbit’, i.e. $g\cdot x\in 𝒪$ for each $x\in 𝒪$. That’s clear. Said differently, the stabilizer of the orbit $O$ is the largest subgroup $A\mathrm{subseteq}G$ such that $O=A\cdot x$.

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

(1)$\mathrm{Stab}\left(𝒪\right)=\left\{g\in G\mid g\cdot x\in 𝒪\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\forall x\in 𝒪\right\}$

(2)$\mathrm{Stab}\left(H\cdot {x}_{0}\right)=\left\{g\in G\mid \forall h\in H,\left(\mathrm{Hg}\right)\cap {\mathrm{hKh}}^{-1}\mathrm{is}\mathrm{not}\mathrm{empty}\right\}.$

Moreover, the corollary you give is also clear in co-ordinate free notation. For if $g\in N\left[H\right]$, 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. $\mathrm{hg}\cdot x=\mathrm{gh}\prime \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

(3)$N\left[H\right]\cap K\subseteq \mathrm{Stab}\left(H\cdot {x}_{0}\right)$

Anyhow, I don’t think any of this actually answers your original question. You wanted to know what was the actual mechanism explaining when $\mathrm{Stab}\left(H\cdot x\right)$ 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 $\mathrm{Stab}\left(H\cdot x\right)$. It doesn’t explain anything. On the other hand, I think it’s just one of those things… sometimes $\mathrm{Stab}\left(H\cdot x\right)$ is larger than $H$, sometimes it’s not; there’s no general underlying cause . I guess I’m getting into philosophy here :-)

Posted by: Bruce Bartlett on May 1, 2007 11:55 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Hi Bruce

Thanks, those pictures were enlightening! I should try drawing that kind of thing myself more often.

You wrote:

I think it’s just one of those things … sometimes $\mathrm{Stab}\left(H\cdot x\right)$ is larger than $H$, sometimes it’s not; there’s no general underlying cause.

Well, I’m not pretending that these attempts I’m making to re-arrange the definitions into something more useful is very deep. Mainly, what I’ve been looking for is a practical way of checking, reasonably efficiently, whether $\mathrm{Stab}\left(H\cdot x\right)$ will be bigger than $H$ or not, but I think I’ve also gained a little more insight into when this can happen than I had before. You’re obviously starting way ahead of me on this, but in the process of all this scribbling and thinking out loud, I certainly managed to correct a lot of my own misconceptions.

Posted by: Greg Egan on May 1, 2007 2:18 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

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 $\mathrm{Stab}\left(H\cdot x\right)=\left\{g\in G\mid \forall h\in H,\left(Hg\right)\cap \mathrm{Stab}\left(hx\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{is}\mathrm{not}\mathrm{empty}\right\}$.

This makes it almost obvious, because $H\cdot x$ just consists of points of the form $hx$, 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}gy=y$, and hence $gy={h}_{2}^{-1}y$, so of course $gy\in H\cdot x$.

But the main thing I want to focus on is the issue of “how does the extra symmetry creep into $\mathrm{Stab}\left(H\cdot x\right)$”, 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 \mathrm{Stab}\left(H\cdot x\right)$, $g\notin H$, really only gets there thanks to some $k\in \mathrm{Stab}\left(H\cdot x\right)$, where $k\in K=\mathrm{Stab}\left(x\right)$, and $k\notin H$. In other words, the whole of $\mathrm{Stab}\left(H\cdot x\right)$ 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 \mathrm{Stab}\left(H\cdot x\right)=\left\{k\in K\mid \forall h\in H,\left(Hk\right)\cap \mathrm{Stab}\left(hx\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{is}\mathrm{not}\mathrm{empty}\right\}$. In other words:

$k$ will sneak into $\mathrm{Stab}\left(H\cdot x\right)$ 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=\left(1,1,1\right)$, and then we have:

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

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\left[H\right]\cap K$ into $\mathrm{Stab}\left(H\cdot x\right)$ (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 $\left(1,1,1\right)$. 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.

Top of cube  (1,-1,1)  (1,0,1)  (1,1,1)  (0,1,1)  (-1,1,1)  (-1,0,1)  (-1,-1,1)  (0,-1,1)
• If we rotate the edge with centre $\left(0,1,1\right)$ into $\left(1,0,1\right)$ (a 120° rotation around $\left(1,1,1\right)$), then rotate 90° around the $z$-axis, we bring $\left(0,1,1\right)$ back to itself. So we have a rotation that preserves an edge.
• If we follow the 120° rotation around $\left(1,1,1\right)$ with a 180° rotation around the $z$-axis, the edge-centre $\left(0,1,1\right)$ is mapped to $\left(-1,0,1\right)$, which means the net rotation is around the vertex those two edges share, $\left(-1,1,1\right)$. Note that this vertex is adjacent to $\left(1,1,1\right)$.
• If we follow the 120° rotation around $\left(1,1,1\right)$ with a 270° rotation around the $z$-axis, the edge-centre $\left(0,1,1\right)$ is mapped to $\left(0,-1,1\right)$. If we check what happens to $\left(1,0,1\right)$ as well, it ends up at $\left(1,-1,0\right)$, 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 $\left(-1,-1,1\right)$, which lies diagonally opposite $\left(1,1,1\right)$ across the square of $H\cdot x$. From the symmetry of the situation, this will disqualify both rotations in $K$ from joining $\mathrm{Stab}\left(H\cdot x\right)$, so $\mathrm{Stab}\left(H\cdot x\right)$ remains equal to $H$ itself.

Posted by: Greg Egan on May 1, 2007 1:44 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I wrote

$k$ will sneak into $\mathrm{Stab}\left(H\cdot x\right)$ 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$.

I’m beginning to come around to Bruce’s point of view, that there is nothing to be gained by my rephrasing here of the simpler fact:

$k$ either preserves the orbit, or it doesn’t

Certainly all the group multiplication I did in that post to try to account for what happens in Example 1 was much less efficient than just checking whether the generator of K preserved the figure.

So I guess the only thing I’ve really learnt is that I should be looking at the generators of K that are not in H, and checking individually whether or not they preserve $H\cdot x$. (This might have been obvious to other people from the start, but it wasn’t obvious to me!) Beyond that, there doesn’t seem to be any general shortcut, unless you already know $N\left[H\right]$, in which case you know that $N\left[H\right]\cap K\subseteq \mathrm{Stab}\left(H\cdot x\right)$.

I wrote:

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!

I suppose if the matrix group is finite you can always exclude all fixed points from ${R}^{n}$, and so you end up with a free action. If I’d taken that approach with the cyclic group generated by:

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

I would have got a zig-zagging non-planar octagon as the orbit, with this cyclic subgroup as its entire stabiliser. Still, it’s nice to know when you can get away with something less generic.

Posted by: Greg Egan on May 2, 2007 3:42 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

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

Right - this is a good point. I think I’ve finally got it! Mmm… I’ve just concluded I don’t understand Klein geometry at all (actually all I ever learnt about it came from this blog!), since I can’t see how to answer your question in geometric terms. I will have to go and read Klein’s original lecture. First I’m going to wait around a bit to see if you can get to the bottom of this. It seems you are a hair’s breadth away. Nice picture!

Posted by: Bruce Bartlett on May 2, 2007 9:55 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I seem to have reached a bit of a cul-de-sac on the completely general question of when, for some $G$-set $X$ and some subgroup $H\subseteq G$, $\exists Y\subseteq X$ such that $\mathrm{Stab}\left(Y\right)=H$.

So, in the hope that linearity might come to the rescue, over the next few days (if the café owners don’t mind!) I’m going to try to answer the following question:

Given a subgroup $H\subseteq G\subseteq \mathrm{GL}\left(n,F\right)$ (for $F$ either the real numbers or the complex numbers), when is there a subset $Y\subseteq {F}^{n}$ whose stabiliser $\mathrm{Stab}\left(Y\right)\subseteq G$ is precisely equal to $H$? And in those cases where such a $Y$ exists, suppose we have a proper subgroup ${H}_{1}\subset H$; when is there a subset ${Y}_{1}\subset Y$ such that $\mathrm{Stab}\left({Y}_{1}\right)={H}_{1}$?

I’m going to start with the easiest possible case: $H=\left\{I\right\}$, where $I$ is the identity operator on ${F}^{n}$.

If $n=1$, then if $x\ne 0$, $Y=\left\{x\right\}\subset F$ clearly has $\mathrm{Stab}\left(Y\right)=\left\{I\right\}$.

For $n>1$, set $v=\left(1,2,...,n\right)\in {F}^{n}$ and $Y=B\cup \left\{v\right\}$, where $B$ is the canonical basis for ${F}^{n}$. Then if $T\in \mathrm{Stab}\left(Y\right)\subseteq \mathrm{GL}\left(n,F\right)$, $T$ must induce some permutation on the $n+1$ elements of $Y$. If that permutation leaves $v$ fixed, it simply permutes the $n$ basis elements, but clearly the only permutation of the basis elements that leaves $v$ fixed is the identity permutation. If $Tv\ne v$, $v$ must be swapped with some ${e}_{j}\in B$, while the rest of the basis, $B$\$\left\{{e}_{j}\right\}$ is permuted, so we have:

$Tv={e}_{j}$
$T{e}_{j}=v$
$T\left(v-j{e}_{j}\right)={e}_{j}-jv$
$T\left(1,2,...j-1,0,j+1...n\right)=\left(-j,-2j,...1-{j}^{2}...-nj\right)$

Since $T$ just permutes $B$\$\left\{{e}_{j}\right\}$, the last equation is clearly impossible. So for any $G\subseteq \mathrm{GL}\left(n,F\right)$ we have $\mathrm{Stab}\left(Y\right)=\left\{I\right\}=H$.

Posted by: Greg Egan on May 3, 2007 5:41 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

In view of this path you are taking us on, from

A SPAN OF CONNECTED GROUPOIDS FAITHFULLY OVER G IS THE SAME AS A DOUBLE COSET

to

A SPAN OF GROUPOIDS FAITHFULLY OVER G IS THE SAME AS A SPAN OF G-SETS

via the observation

Things get even simpler if we drop the “faithfulness” assumption, and simply work with groupoids over G, and spans of these.

so that soon we will be able to complete a third slogan

A SPAN OF GROUPOIDS OVER G IS THE SAME AS A …,

might it pay when categorifying, rather than attempt to do so for double cosets as in the first slogan, as we desperately tried to do in our Klein 2-geometry project, to reverse the phylogenetic order and start with the third slogan? I.e., begin in the 21st century?

This takes us out of the traditional realm of group actions on sets, and into the 21st century! And that’s where we want to go.

In other words, complete the slogan

A SPAN OF 2-GROUPOIDS OVER G (A 2-GROUP) IS THE SAME AS A…

Posted by: David Corfield on April 28, 2007 8:41 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

David wrote:

soon we will be able to complete a third slogan

A SPAN OF GROUPOIDS OVER $G$ IS THE SAME AS A …

I’m not sure how to complete this. My idea was that once you grokked the less general, more complicated slogans, you wouldn’t even need a slogan in this case! But maybe I should attempt a slogan here too.

The less general, more complicated slogans are actually theorems:

A SPAN OF CONNECTED GROUPOIDS FAITHFULLY OVER $G$ IS THE SAME AS A DOUBLE COSET.

A SPAN OF GROUPOIDS FAITHFULLY OVER $G$ IS THE SAME AS A SPAN OF $G$-SETS.

But I don’t think I want a theorem as my final slogan — I think I want something fuzzier. If you’re willing to buy my earlier fuzzy slogans:

A SPAN OF GROUPOIDS IS AN INVARIANT WITNESSED RELATION.

and

A GROUPOID IS A ‘SET WITH SYMMETRIES’.

then maybe you can also buy this:

A GROUPOID OVER $G$ IS A ‘SET WITH SYMMETRIES’ WHOSE SYMMETRIES MAP TO ELEMENTS OF $G$.

in which case you’ll in principle buy this too:

A SPAN OF GROUPOIDS OVER $G$ IS AN INVARIANT WITNESSED RELATION BETWEEN ‘SETS WITH SYMMETRIES’ WHOSE SYMMETRIES MAP TO ELEMENTS OF $G$.

However, this slogan is not sufficiently crunchy to be worth printing on bumper stickers… it doesn’t really capture how nice spans of groupoids over a fixed group(oid) are!

Might it pay when categorifying, rather than attempt to do so for double cosets as in the first slogan, as we desperately tried to do in our Klein 2-geometry project, to reverse the phylogenetic order and start with the third slogan? I.e., begin in the 21st century?

That’s probably true. But, one thing the Tale of Groupoidification makes clear is that even understanding plain old Klein geometry is already a project for the 21st century!

In other words, complete the slogan

A SPAN OF 2-GROUPOIDS OVER G (A 2-GROUP) IS THE SAME AS A….

This may be a project for the 10’s — the 2010’s, that is — after we’ve fully brought Klein geometry up to date.

You’ll recall how our Klein 2-geometry project wound up finding lots of categorified stuff hiding in ordinary Klein geometry. I now think the reason our program temporarily stalled out is that we didn’t dig deeply enough into this stuff.

In other words: we should understand Klein geometry before trying to categorify it!

Posted by: John Baez on April 30, 2007 9:31 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

In other words: we should understand Klein geometry before trying to categorify it!

Yes, I think you’re right. But I did have one idea last night which I shall jot down in case I forget.

2-groups measure the symmetry of a category. A vector bundle can be considered a category. Each point of the base is an object, and the elements of a fibre are its arrows with addition as composition.

Now, take a bundle such as the trivial bundle over the sphere with fibre equal to ${ℝ}^{2}$. Consider the cornucopia of figures we could look to preserve: a point on the sphere; a point in the fibre above a particular point; a subspace of the fibre above a particular point; a great circle; a section of the bundle restricted to a circle; a sub-bundle of the bundle restricted to the circle, such as an infinitely wide Möbius strip winding about over the equator; etc.

Presumably each has as stabilizer a sub-2-group of the 2-group of automorphism of the bundle. And presumably the respective quotients give the space (2-space?) of figures of that type. And double quotienty things give incidence relations.

Posted by: David Corfield on May 1, 2007 8:34 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

My coin-tossing puzzle seems to have triggered a lot of discussion about puzzles! I’m terrible at puzzles, but some people are good at them — and some even enjoy them. Gary Kennedy of Ohio State emailed me the following, which I provide for the delectation of such folks:

One hundred prisoners, numbered 1 to 100, are given a chance to gain their freedom. In a room are located 100 boxes, numbered 1 to 100, containing slips of paper, likewise numbered and assigned at random, one slip per box. One at a time, each prisoner will be allowed into the room to open 50 boxes. During this time and afterwards they cannot communicate with their fellow prisoners. After each prisoner’s attempt all the boxes will be closed up again. If every prisoner finds the slip with his own number they will all be freed. Otherwise they will all remain imprisoned.

What strategy maximizes their probability of freedom?

Posted by: John Baez on May 1, 2007 12:48 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Find the answer to the isomorphic puzzle above in the thread, then translate it to this version.

Posted by: John Armstrong on May 1, 2007 1:46 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Here’s another puzzle, similar in spirit to those that appeared here.

100 people are forced to wear hats. Some hats are black and some white but nobody knows the colour of her own hat. The people look at each other and simultaneously guess each the colour of her own hat. They are allowed to communicate before this procedure, but not from the point they wear the hats. What strategy should they choose if they wish to _ensure_ the maximal number of correct guess (i.e. the worst case scenario is what counts).

Posted by: Squark on May 1, 2007 5:16 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Greg Egan wrote:

I seem to have reached a bit of a cul-de-sac on the completely general question of when, for some $G$-set $X$ and some subgroup $H\subseteq G$, $\exists Y\subseteq X$ such that $\mathrm{Stab}\left(Y\right)=H$.

I have a lot of catching up to do on this thread, but I just want to say a couple of things.

First, while I’m no expert, this seems like a very hard problem at this extremely high level of generality. Maybe with some work we can find some useful sufficient conditions for such a subset $Y$ to exist for some $H\subseteq G$. Maybe we can find some necessary conditions. But a complete criterion seems tough unless we pick a particular $G$.

Here’s one way to see why. We’re studying actions of groups on sets. These are analogous to representations of groups on vector spaces. They’re more fundamental, I believe. They’re harder in some ways, easier in others.

The analogue of the ‘direct sum’ of group representations is the ‘disjoint union’ of group actions.

So, the analog of an irreducible representation of $G$ on a vector space $V$ is a transitive action of $G$ on a set $X$.

Every rep of $G$ is a sum of irreps (at least if we restrict to finite-dimensional reps of finite groups). Similarly, every $G$-set is a disjoint union of transitive $G$-sets (without any parenthetical fine print).

Your question is about taking an action of $G$ on a set $X$ and trying to completely understand the resulting action of $G$ on the power set ${2}^{X}$. I would state your question this way: given a $G$-set $X$, how can we decompose ${2}^{X}$ into a disjoint union of transitive $G$-sets?

(Do you see why this is another way of saying the same thing?)

To see why this question is tough, let’s consider its analogue in the world of group representations.

The analogue of ${2}^{X}$ is the exterior algebra $\Lambda V$, since given any basis of $V$, the subsets of that basis form a basis for $\Lambda V$.

So, the question you’re asking is like this: given an rep of $G$ on $V$, how can we decompose $\Lambda V$ into irreps?

This is a very interesting question, but it’s quite substantial. It can be completely settled for particular groups… but not in any very nice way, I think, for an arbitrary group.

So, I’d glad you plan to tackle some specific groups. But, tackling all groups $G\subseteq \mathrm{GL}\left(n,F\right)$ is not very specific! Any finite group is of this form, for example. So is any compact Lie group. You’ll get much further if you zoom in on something more specific.

Posted by: John Baez on May 3, 2007 6:37 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Thanks for the warning, John! I’ll probably concentrate on $G\subseteq \mathrm{SO}\left(n\right)$, and see if I can say anything useful about $G\subseteq \mathrm{GL}\left(n,F\right)$ along the way.

Posted by: Greg Egan on May 3, 2007 7:10 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Greg wrote:

I’ll probably concentrate on $G\subseteq \mathrm{SO}\left(n\right)$,…

Again, for really complete results you’ll need to specialize to particular choices of $G$, since any finite group is a subgroup of some $\mathrm{SO}\left(n\right)$, and the problem you’re tackling is — in its full generality — way too hard if you try it for all finite groups.

Of course, by making other restrictions on your problem, instead of restrictions on $G$, you may still get interesting results. So, don’t let me scare you too much.

Posted by: John Baez on May 3, 2007 8:23 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I’ve finally pinned down what it is I want to say about figures and subgroups. It’s really very modest, so it might come as a bit of an anticlimax; it’s mainly about ridding myself of some foolish misconceptions that I’d let myself develop by reading too much into a limited number of lower-dimensional examples, such as the Platonic solids and Klein’s quartic curve. I’m afraid I’m not going to spectacularly attempt to classify all isomorphism classes of all $G$-sets for all subgroups of $\mathrm{GL}\left(n,F\right)$! Rather, the heart of it is this very simple result:

Theorem (Existence of Figures): Let $G$ and $H$ be finite subgroups, $H\subseteq G\subseteq \mathrm{GL}\left(n,F\right)$, for $F$ either the real or complex numbers. Then $\exists Y\subset {F}^{n}$ such that ${\mathrm{Stab}}_{G}\left(Y\right)\equiv \left\{g\in G\mid \forall y\in Y,gy\in Y\right\}=H$.

Proof: Define $\mathrm{Fix}\left(g\right)=\left\{x\in {F}^{n}\mid gx=x\right\}$. Then for $g\ne I$, $\mathrm{Fix}\left(g\right)$ will always be a subspace of ${F}^{n}$ of dimension $d.

Define $X=\left\{x\in {F}^{n}\mid x\notin {\cup }_{g\in G,g\ne I}\mathrm{Fix}\left(G\right)\right\}$. Because $G$ is finite, it’s clear from dimensional considerations that $X$ is not empty. $G$ acts freely on $X$, i.e. $\forall x\in X,gx=x\mathrm{iff}g=I$.

Pick any ${x}_{0}\in X$, and define $Y\equiv H\cdot {x}_{0}\equiv \left\{h{x}_{0}\mid h\in H\right\}$. Then if $g\in {\mathrm{Stab}}_{G}\left(Y\right)$, that means $\forall h\in H,\exists {h}_{2}\in H$ such that $gh{x}_{0}={h}_{2}{x}_{0}$, and hence ${h}_{2}^{-1}gh{x}_{0}={x}_{0}$. Because $G$ acts freely on $X$, this means that ${h}_{2}^{-1}gh=I$, and $g={h}_{2}{h}^{-1}\in H$. So ${\mathrm{Stab}}_{G}\left(Y\right)\subseteq H$. Clearly, though, $H\subseteq {\mathrm{Stab}}_{G}\left(Y\right)$, so we have ${\mathrm{Stab}}_{G}\left(Y\right)=H$.

In other words, for $G$ a finite subgroup of any (real or complex) matrix group, and the $G$-set coming from the fundamental representation, we can always find a sufficiently generic point ${x}_{0}$ such that $H\cdot {x}_{0}$ for any subgroup $H\subseteq G$ has $H$ as its stabiliser.

This theorem is probably obvious to everyone reading this blog, and it certainly wasn’t a surprise to me. The misconception I’ve been labouring under was that we could get away with much less generic orbits, as we usually can with the Platonic solids. Even that does depend on the context, though! We use, say, the cube to illustrate the finite group of rotational symmetries it possesses, but it’s only the fact that we rule out reflections by fiat that allows us to do that. If we want a subset $Y\subset {R}^{3}$ such that ${\mathrm{Stab}}_{O\left(3\right)}\left(Y\right)$ consists of only the rotational symmetries of the cube, then we can’t use the cube itself, we need to use a chiral solid whose 24 vertices are the orbit of a generic point.

If we look for subsets of the vertices of the Platonic solids whose stabilisers (with respect to the rotational symmetry group of the full solid) are equal to subgroups, I think we can always find them, with just one exception: there is no subset of the vertices of the tetrahedron whose stabiliser is the trivial group $\left\{I\right\}$. So even the lower-dimensional luck for the Platonic solids isn’t quite perfect! But by the time you get to 4 dimensions, the luck runs out more spectacularly, and there is no subset of the vertices of the 4-cube whose stabiliser is the order-8 subgroup generated by:

$S:\left(w,x,y,z\right)\to \left(-z,w,x,y\right)$

So the memo to myself when looking for nice illustrations of JB’s discussion of Kleinian geometry is to be careful and stop expecting things to work like they do for the Platonic solids. I previously proved that I can be sure that things are going bad when $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)⊈H$, and that’s worth knowing, but the only surefire method of guaranteeing that $\mathrm{Stab}\left(H\cdot {x}_{0}\right)=H$ is to choose a fully generic ${x}_{0}$, which means working with a polytope with 192 vertices rather than the 4-cube, if I want to use a single polytope to illustrate all the subgroups of the rotational symmetry group of the 4-cube.

What about infinite subgroups? There usually won’t be a subset of ${F}^{n}$ on which all of $G$ acts freely, so if you stick to ${F}^{n}$ as your $G$-set you just have to treat things in a case-by-case fashion. For $\mathrm{SO}\left(n\right)\subset O\left(n\right)$, there is no subset of ${F}^{n}$ whose stabiliser is $\mathrm{SO}\left(n\right)$, but for $\mathrm{SO}\left(n-1\right)\subset O\left(n\right)$ there is, e.g. a helix for $n=3$. The diagnostic $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)⊈H$ does separate these cases, i.e. the fact that $\mathrm{SO}\left(n\right)$ is a normal subgroup of $O\left(n\right)$ is the killer, but as I’ve lamented several times, it’s not enough to catch all cases.

BTW, does anyone know a counterexample, to make it clear that you can have $\mathrm{Stab}\left(H\cdot {x}_{0}\right)\ne H$ even when $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)\subseteq H$?

Posted by: Greg Egan on May 4, 2007 5:28 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Greg wrote:

I’ve finally pinned down what it is I want to say about figures and subgroups. It’s really very modest…

It’s actually quite nice! I hadn’t absorbed the intuition that was driving you until now, mainly because I hadn’t read your earlier posts carefully enough.

Your proof should work whenever the field $F$ is infinite. This, together with the fact that $G\subseteq \mathrm{GL}\left(n,F\right)$ is finite, is what guarantees the existence of a nonempty set of ‘generic’ elements of ${F}^{n}$ — that is, elements with trivial stabilizer. And this is what lets you create figures with any desired stabilizer.

In my previous posts I’d been envisioning finite groups acting on finite sets. Ironically, this makes it much harder.

You also use the linearity of the action to help understand the fixed-point sets of arbitrary group elements.

I’ll ponder your latest puzzle later, but right now I just want to mention a famous bunch of examples of your construction!

A Coxeter group is a finite subgroup of $\mathrm{GL}\left(n,ℝ\right)$ generated by reflections. These are incredibly beautiful things. They’ve been completely classified. Examples include the rotation-reflection groups of $n$-cubes and regular $n$-simplices, and other Weyl groups.

Given a Coxeter group $G\subseteq \mathrm{GL}\left(n,ℝ\right)$, people love to study your set

$X=\left\{x\in {ℝ}^{n}\mid x\notin {\cup }_{g\in G,g\ne I}\mathrm{Fix}\left(G\right)\right\}.$

It’s the complement of a finite set of hyperplanes, one for each reflection in the Coxeter group. It’s a disjoint union of open sets called Weyl chambers.

So, you’ve generalized some of this stuff…

Posted by: John Baez on May 4, 2007 5:54 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

John, thanks for putting my comments in a nice context. Weyl chambers certainly are beautiful!

I wrote:

BTW, does anyone know a counterexample, to make it clear that you can have $\mathrm{Stab}\left(H\cdot {x}_{0}\right)\ne H$ even when $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)\subseteq H$?

Just to remind readers of the context for this question, if you can find a group element $g$ that fixes a point ${x}_{0}$ in your $G$-set $X$, and also lies in the normaliser of the subgroup $H$ which you applied to ${x}_{0}$ in the hope of creating an orbit $H\cdot {x}_{0}$ whose stabiliser would be just $H$ itself, then $g$ will lie in $\mathrm{Stab}\left(H\cdot {x}_{0}\right)$. Why? Because $g\in \mathrm{Stab}\left({x}_{0}\right)$ implies that ${g}^{-1}{x}_{0}={x}_{0}$, so $\forall h\in H,gh{x}_{0}=gh{g}^{-1}{x}_{0}={h}_{2}{x}_{0}$ for some ${h}_{2}\in H$, since $g\in N\left[H\right]$. So, $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)\subseteq \mathrm{Stab}\left(H\cdot {x}_{0}\right)$. And if we have $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)⊈H$, that is sufficient to destroy any hope that $\mathrm{Stab}\left(H\cdot {x}_{0}\right)=H$.

I suspected that the converse was false, but I wanted a counterexample to put the matter to rest: to prove that sometimes $\mathrm{Stab}\left(H\cdot {x}_{0}\right)$ could be bigger than $H$ despite the fact that $N\left[H\right]\cap \mathrm{Stab}\left({x}_{0}\right)\subseteq H$. Actually, if the action is trivial (i.e. $\forall g\in G,x\in X,gx=x$), then that’s a counterexample whenever $N\left[H\right]=H$, but that’s cheating. I’ve finally figured out a simple non-trivial counterexample.

Let our group $G$ be ${S}_{4}$, the group of permutations of 4 objects, and let the $G$-set $X$ be $G$ itself, with the conjugate action, i.e. $g:x\to gx{g}^{-1}$.

Let $H$ be ${S}_{3}$ as a subgroup of ${S}_{4}$, i.e. the 6-element subgroup of permutations that leave the 4th object fixed. I claim that $N\left[H\right]=H$, i.e. for any $g\notin H,\exists h\in H:{g}^{-1}hg\notin H$. Any $g\notin H$ is going to swap the 4th object for one of the first 3 objects, and then some $h\in H$ is going to move it elsewhere, so it won’t be in the right place to be restored to position 4 by ${g}^{-1}$.

Let ${x}_{0}$ be the cyclic permutation $\left(1234\right)$, which takes the 1st object to the 2nd position, the 2nd object to the 3rd position, etc. The orbit $H\cdot {x}_{0}$ will consists of 6 distinct cyclic permutations of order 4, because conjugation by elements of $H$ effectively just relabels the first 3 objects of the set being permuted in all 3! possible ways. So we have: $H\cdot {x}_{0}=\left\{\left(1234\right),\left(2314\right),\left(3124\right),\left(1324\right),\left(2134\right),\left(3214\right)\right\}.$ But in fact, there are only 4!/4=6 cycles of order 4 in the whole of ${S}_{4}$, since each cycle of length 4 can be written 4 different ways; e.g. $\left(1234\right)=\left(2341\right)=\left(3412\right)=\left(4123\right)$. Since conjugation can’t change the order of a permutation, conjugation with any element of $G$ will necessarily preserve the orbit $H\cdot {x}_{0}$, and so $\mathrm{Stab}\left(H\cdot {x}_{0}\right)=G$.

Posted by: Greg Egan on May 5, 2007 12:51 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I wrote:

If we look for subsets of the vertices of the Platonic solids whose stabilisers (with respect to the rotational symmetry group of the full solid) are equal to subgroups, I think we can always find them, with just one exception: there is no subset of the vertices of the tetrahedron whose stabiliser is the trivial group $\left\{I\right\}$.

In fact, there’s at least one more exception! The dihedral group for the square, ${D}_{4}$, as a subgroup of the rotational symmetries of the cube, carries any vertex of the cube into all 8 vertices, a subset which is obviously stabilised by the full group. (I think I’ve been playing a mental shell game where in cases like that I just switch to face centres or edge centres instead of vertices, which is certainly convenient for illustrative purposes, but strictly speaking is still cheating.)

What’s more, that’s an even simpler counterexample than the one I just gave, because $N\left[{D}_{4}\right]={D}_{4}$.

Posted by: Greg Egan on May 5, 2007 5:30 PM | Permalink | Reply to this

### Snub Cube; Re: This Week’s Finds in Mathematical Physics (Week 250)

Greg Egan,

You know this, and so probably were were referring to it obliquely.

The sub cube is the chiral polyhedron with the symmetry group you want; has 60 edges and the 24 vertices which you specify.

Posted by: Jonathan Vos Post on May 11, 2007 4:41 AM | Permalink | Reply to this

### 24-cell; Re: This Week’s Finds in Mathematical Physics (Week 250)

Pressumably the symmetry order 192 polytope we refer to is the the 4-dimensional polytope formed by the root vectors of the D4 Lie algebra Spin(0,8), namely the 24-vertex 24-cell. The self-dual polytope neatly connects octonions with Weyl groups and the rotational symmetry group of the 4-cube. And it is unique to 4-D Euclidean geometry. But you and John Baez know that.

Posted by: Jonathan Vos Post on May 11, 2007 4:52 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Jonathan Vos Post wrote:

Pressumably the symmetry order 192 polytope we refer to is the the 4-dimensional polytope formed by the root vectors of the D4 Lie algebra Spin(0,8), namely the 24-vertex 24-cell.

No, the symmetry group of the 24-cell has 1152 elements, including reflections. The 4-dimensional cube has 192 rotational symmetries, not including reflections. If you include reflections, it has twice as many symmetries: ${2}^{4}\cdot 4!=16\cdot 24=384$ symmetries. In general, an $n$-cube has ${2}^{n}n!$ symmetries.

Projected down to a plane, the 24-cell looks like this:

The 4 coordinate axes are drawn as dotted lines.

To get the vertices of the 24-cell, what we’ve done is take the vertices of a 4-dimensional cube:

together with the vertices of its dual polytope, called a ‘cross-polytope’ — the 4-dimensional analogue of an octahedron:

shown here in quaternion coordinates.

As a result, the symmetries of the 24-cell include those of the 4-dimensional cube. So, the ratio of the sizes of these groups must be an integer: $1152/384=3$

I leave it as a puzzle to explain why the ratio is 3.

Greg was talking about 4d polytopes with 192 vertices having the rotational symmetry group of the 4d cube as their symmetries. I don’t know a really beautiful example of these. But, the ‘dual of the Coxeter complex of ${D}_{4}$’ is a beautiful 4d polytope with 384 vertices: precisely the size of the symmetry group of the 4-dimensional cube if we include reflections as well as rotations. And, this symmetry group acts as symmetries of this polytope with a free and transitive action on the set of vertices.

Posted by: John Baez on May 11, 2007 9:53 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

John wrote:

Your question is about taking an action of $G$ on a set $X$ and trying to completely understand the resulting action of $G$ on the power set ${2}^{X}$.

So, the question you’re asking is like this: given an rep of $G$ on $V$, how can we decompose $\Lambda V$ into irreps?

How do you extend an action of $G$ on $X$ to an action of $G$ on the power set ${2}^{X}$? I can’t see how. You can do this with exterior products because you can take linear combinations:

(1)$g\cdot \left(a\wedge b\right):=\left(g\cdot a\right)\wedge \left(g\cdot b\right)$

Nevertheless, I think I get your intuition about this. Mmm… Perhaps one can think about extending a $G$-action on $X$ to a $G$-action on ${2}^{X}$ using spans (our substitute for linear combinations), but I’m not sure how.

Posted by: Bruce Bartlett on May 3, 2007 10:44 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Woops! Silly me - I see now it’s clear how to extend an action of $G$ on $X$ to an action of $G$ on ${2}^{X}$, just set

(1)$g\cdot \left\{{x}_{1},\dots ,{x}_{n}\right\}=\left\{g\cdot {x}_{1},\dots ,g\cdot {x}_{n}\right\}.$

Sorry about that . It’s actually the kind of ‘coarse-graining’ I was talking about earlier on this thread… though I had clearly not understood what I was saying properly ;-). Anyhow, I see your analogy with breaking down exterior products into irreps… nice!

Posted by: Bruce Bartlett on May 3, 2007 11:04 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Bruce wrote:

Good, so you see how an action of $G$ on $X$ gives an action of $G$ on the power set ${2}^{X}$:

$g\cdot \left\{{x}_{1},\dots ,{x}_{n}\right\}=\left\{g\cdot {x}_{1},\dots ,g\cdot {x}_{n}\right\}$

And I want to emphasize: the analogy between the power set ${2}^{X}$ of a set $X$ and the exterior algebra $\Lambda V$ of a vector space $V$ is no joke! It’s part of an enormous systematic analogy between combinatorics and linear algebra… an analogy so far-reaching that people now say:

FINITE SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITH 1 ELEMENT

This will be a big part of the Tale of Groupoidification.

In particular: in quantum mechanics we use $\Lambda V$ as a ‘Fock space for fermions’. Fermions are particles with the property that no two can occupy the same state. If $V$ is the space of states of a single fermion, the Fock space $\Lambda V$ is the space of states of a collection of fermions. So, if we have a basis $\left\{{e}_{i}{\right\}}_{i\in X}$ of $V$ describing states of a single fermion, we get a basis of $\Lambda V$ by taking vectors like

${e}_{{x}_{1}}\wedge \cdots \wedge {e}_{{x}_{n}}$

where $\left\{{x}_{1},\dots ,{x}_{n}\right\}$ is any subset of $X$. So, if $V$ has a basis indexed by $X$, $\Lambda V$ has a basis index by ${2}^{X}$.

Now for a puzzle: how does it work with bosons? We have an analogy:

$\mathrm{fermions}:\mathrm{exterior}\mathrm{algebra}:\mathrm{power}\mathrm{set}::\mathrm{bosons}:??:???$

where $??$ is some construction on vector spaces and $???$ is some corresponding construction on sets.

Posted by: John Baez on May 3, 2007 8:44 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

?? = symmetric algebra
??? = set of unordered n-tuples of elements of X, for arbitrary n. Is there a good name for this already?

Posted by: John Armstrong on May 3, 2007 9:18 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Oh of course.. It’s the underlying set of the free commutative monoid on X

Posted by: John Armstrong on May 3, 2007 9:20 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Yes, the combinatorial analog of the ‘symmetric algebra on a vector space $V$’ is the ‘free commutative monoid on a set $X$’.

I don’t know a shorter name for this gadget, but I know a name for its elements: they’re called multisubsets of $X$. A multiset is sort of like a set, but it can contain the same element more than once: in fact, any finite number of times! A formal definition can be found here. A multiset is also called a bag.

Apparently the fact that we’re made of fermions caused us to invent set theory before multiset theory, even though the combinatorial analogue of the exterior algebra is a bit more mysterious than for the symmetric algebra, given the absence of minus signs in set theory!

Posted by: John Baez on May 3, 2007 10:06 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

FINITE SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITH 1 ELEMENT’

I have seen it that way, but I have also seen, as Durov says,

FINITE POINTED SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITH 1 ELEMENT’

and he continues

FINITE SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITHOUT ELEMENTS’.

The latter ‘field’ is just the trivial algebraic monad.

Posted by: David Corfield on May 4, 2007 6:56 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

David wrote:

John wrote:

FINITE SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITH 1 ELEMENT’

I have seen it that way, but I have also seen, as Durov says,

FINITE POINTED SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITH 1 ELEMENT’

Everything I wrote in week185 and subsequent Weeks agrees with Durov: (finite) pointed sets are like (finite-dimensional) vector spaces over ${𝔽}_{1}$… and therefore, plain old sets are like projective spaces over ${𝔽}_{1}$. All the $q$-deformation of combinatorics works wonderfully with this interpretation.

But, right now I seem to be pretending that sets rather than pointed sets are like vector spaces. So, maybe I should avail myself of Durov’s second slogan:

FINITE SETS ARE LIKE ‘VECTOR SPACES OVER THE FIELD WITHOUT ELEMENTS’.

That could be why I always get confused — two different interpretations of finite sets: as vector spaces over ${𝔽}_{0}$, and as projective spaces over ${𝔽}_{1}$!

By the way, does anyone understand some of the other weird ‘generalized rings’ that Durov mentions, like ${ℤ}_{\infty }$?

It’s nice that he considers the tropical ring, aka the rig of costs.

Posted by: John Baez on May 4, 2007 6:06 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Hmm. The algebraic monad corresponding to ${ℤ}_{\infty }$ sends a set to the octahedral linear combinations of elements of the set, i.e., real linear combinations of elements with finitely many non-zero coefficients whose absolute sum is less than or equal to 1.

Posted by: David Corfield on May 8, 2007 3:13 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Thanks for explaining ‘${ℤ}_{\infty }$’, David!

Can you tell why it’s called ${ℤ}_{\infty }$? It’s a very nice name, but I don’t see why it’s appropriate for this entity.

Indeed I was hoping that Spekkens’ ‘toy bits’ had generalized octahedra (usually called cross-polytopes) as their spaces of mixed states… just as the classical mechanics of a system with finitely many pure states has a simplex as its space of mixed states! That would be really cool, since

$\mathrm{simplices}:\mathrm{cross}-\mathrm{polytopes}::{A}_{n}:{D}_{n}$

But alas, I think it’s just a fluke that when you know half the information there is to know about a system whose pure states take 2 bits to completely describe, there are 6 choices of what you might know, nicely arranged as the vertices of an octahedron.

The next case of Spekkens’ setup would be ‘knowing half the information there is to know about a system whose pure states take 4 bits to completely describe’. I don’t know how many choices there are then, and I don’t see why they’d form the vertices of another cross-polytope!

Posted by: John Baez on May 11, 2007 8:21 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I believe the reasoning for the designation ${ℤ}_{\infty }$ goes something like this. The $p$-adic completion of the rationals $ℚ$ is denoted ${ℚ}_{p}$. The $p$-adic integers are denoted ${ℤ}_{p}$.

The completion of $ℚ$ at the ‘real prime’, ${ℚ}_{\infty }$, is $ℝ$. It’s ‘archimedean valuation ring’ is ${ℤ}_{\infty }$ by analogy with ${ℤ}_{p}$.

The norm of a $p$-adic integer is always less than or equal to 1. So we might expect $\infty$-adic integers to fall in the range [$-1$, $+1$].

Still to understand is why a ${ℤ}_{\infty }$-structure on a finite-dimensional real space $E$ is “essentially a Banach norm on $E$”.

Posted by: David Corfield on May 11, 2007 9:32 AM | Permalink | Reply to this
Read the post Klein 2-Geometry VIIIS
Weblog: The n-Category Café
Excerpt: Some odd remarks about Klein 2-geometry which occurred to me in slack moments in Amsterdam. (The 'S' of the title represents a half.) 2-groups measure the symmetry of a category. Perhaps the simplest type of non-trivial, non-discrete category have...
Tracked: May 7, 2007 2:17 PM

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Minor comment on perspective in the middle of your original post: I have found that if people look at something at an angle that they know from straight on e.g. a circle straight on slooks like an ellipse but unless it is tilted seriously, people who don’t know what they are supposed to see won’t see it. Rather that look at your picture from an angle, consider an overhead projector which typically is not projecting a rectangle, but rather a trapezoid or worse. The technical term is ‘keystoning’.

Posted by: jim stasheff on May 7, 2007 10:19 PM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

I found an article on keystoning and overhead projectors, and they gave a nice example. If we apply a lot of keystoning to this:

we get this:

But, you’re saying that the eye automatically compensates for a little keystoning.

In terms of projective geometry, we now have the nice term ‘keystoning’ for certain transformations in $\mathrm{PGL}\left(2,ℝ\right)$.

Posted by: John Baez on May 8, 2007 1:26 AM | Permalink | Reply to this

### Re: This Week’s Finds in Mathematical Physics (Week 250)

Going off-topic, but a this is part of the area I work in: “compensates” is probably the wrong term. Even though you may “know” consciously that you’re looking at a planar surface, and so if the figure should be interpreted with the same geometry as the text, the visual system is probably using a hardwired equivalent of a Bayesian recogniser and decides to interpret something that could easily be a circle on a slightly differently slanted plane as a circle on a slightly differently slanted plane. (One thing I’ve never understood is why we’re so certain about circles, given that actual circles don’t occur in the evolutionary environment virtually at all.) There’s a trend in computational neuroscience/computer vision towards explaining most optical illusions/artifacts in terms of informal Bayesian inference (see, eg, this pdf article), although given the difficulty of doing ethical and comprehensive experiments on things as complicated as people and animals, it’s difficult to be totally convinced at the present time if this explanation is real or a “just so” story.

The real point I’m making though is that, unless you really consciously analyse on what you’re looking at, your eyes will apply their `inbuilt’ interpretation of the likely geometry of what you’re looking at rather than the geometry you’re consciously thinking about viewing.

Posted by: dave tweed on May 8, 2007 12:06 PM | Permalink | Reply to this
Read the post The n-Café Quantum Conjecture
Weblog: The n-Category Café
Excerpt: Why it seems that quantum mechanics ought to be the de-refinement of a refined theory which lives in one categorical degree higher than usual.
Tracked: June 8, 2007 6:28 PM

Post a New Comment