Also available as http://math.ucr.edu/home/baez/week250.html(adsbygoogle = window.adsbygoogle || []).push({});

April 26, 2007

This Week's Finds in Mathematical Physics (Week 250)

John Baez

Right now I'm in a country estate called Les Treilles in southern

France, at a conference organized by Alexei Grinbaum and Michel

Bitbol:

1) Philosophical and Formal Foundations of Modern Physics,

http://www-drecam.cea.fr/Phocea/Vie_des_labos/Ast/ast_visu.php?id_ast=762

It's very beautiful here, but about 20 philosophers, physicists

and mathematicians have agreed to spend six days indoors discussing

quantum gravity, the history of relativity, quantum information theory

and the like. And guess what? Now it's our afternoon off, and

I'm spending my time writing This Week's Finds! Some people just

don't know how to enjoy life.

In fact, I want to continue telling you The Tale of Groupoidification.

But before I do, here's a puzzle that Jeffrey Bub raised the other night

at dinner. It's not hard, but it's still a bit surprising.

You and your friend each flip a fair coin and then look at it.

You can't look at your friend's coin; they can't look at yours.

You can't exchange any information. Each of you must guess

whether the other person's coin lands heads up or tails up.

Your goal, as a team, is to maximize the chance that you're both

correct.

What's the best strategy, and what's the probability that you

both guess correctly?

Here's an obvious line of thought.

Since you don't have any information about your friend's coin flip,

it doesn't really matter what you guess. So, you might as well guess

"heads". You'll then have a 1/2 chance of being right. Similarly,

your friend might as well guess "heads" - or for that matter, "tails".

They'll also have a 1/2 chance of being right. So, the chance that

you're both right is 1/2 x 1/2 = 1/4.

I hope that sounds persuasive - but you can actually do much better!

How? I'll give away the answer at the end.

Jeffrey Bub is famous for his work on the philosophy of quantum

mechanics, and in his talk today he mentioned a similar but more

sophisticated game, the Popescu-Rohrlich game. Here you and your

friend each flip coins as before. But now, you each say "yes" or

"no". Your goal, as a team, is to give the same response when at

least one coin lands heads up, but different responses otherwise.

Classically the best you can do is both say "yes" - or, if you

prefer, both say "no". Then you'll have a 3/4 chance of winning.

But, if before playing the game you and your friend prepare a pair

of spin-1/2 particles in the Bell state, and you each keep one, you

can use these to boost your chance of winning to about 85%!

I think the underlying idea first appeared here:

1) S. Popescu and D. Rohrlich, Nonlocality as an axiom, Found. Phys.

24 (1994), 379-385.

For the "game" version, try this:

2) Nicolas Gisin, Can relativity be considered complete? From

Newtonian nonlocality to quantum nonlocality and beyond, available

as quant-ph/0512168.

There's a lot more to say about this - especially about the

"Popescu-Rohrlich box", a mythical device which would let you win

all the time at this game, but still not allow signalling. The

existence of such a box is logically possible, but forbidden by

quantum mechanics. It can only exist in certain "supra-quantum

theories" which allow even weirder correlations than quantum mechanics.

But, I don't understand this stuff, so you should just read this:

3) Valerio Scarani, Feats, features and failures of the PR-box,

available as quant-ph/0603017.

Okay - now for our Tale. I want to explain double cosets as spans

of groupoids... but it's best if I start with some special relativity.

Though Newton to have believed in some form of "absolute space",

the idea that motion is relative predates Einstein by a long time.

In 1632, in his Dialogue Concerning the Two Chief World Systems,

Galileo wrote:

Shut yourself up with some friend in the main cabin below decks on

some large ship, and have with you there some flies, butterflies,

and other small flying animals. Have a large bowl of water with some

fish in it; hang up a bottle that empties drop by drop into a wide

vessel beneath it. With the ship standing still, observe carefully how

the little animals fly with equal speed to all sides of the cabin. The

fish swim indifferently in all directions; the drops fall into the

vessel beneath; and, in throwing something to your friend, you need

throw it no more strongly in one direction than another, the distances

being equal; jumping with your feet together, you pass equal spaces

in every direction.

When you have observed all these things carefully (though doubtless

when the ship is standing still everything must happen in this way),

have the ship proceed with any speed you like, so long as the motion

is uniform and not fluctuating this way and that. You will discover

not the least change in all the effects named, nor could you tell

from any of them whether the ship was moving or standing still.

As a result, the coordinate transformation we use in Newtonian

mechanics to switch from one reference frame to another moving at

a constant velocity relative to the first is called a "Galilei

transformation". For example:

(t, x, y, z) |-> (t, x + vt, y, z)

By the time Maxwell came up with his equations describing light,

the idea of relativity of motion was well established. In 1876,

he wrote:

Our whole progress up to this point may be described as a gradual

development of the doctrine of relativity of all physical phenomena.

Position we must evidently acknowledge to be relative, for we cannot

describe the position of a body in any terms which do not express

relation. The ordinary language about motion and rest does not so

completely exclude the notion of their being measured absolutely, but

the reason of this is, that in our ordinary language we tacitly assume

that the earth is at rest.... There are no landmarks in space; one

portion of space is exactly like every other portion, so that we

cannot tell where we are. We are, as it were, on an unruffled sea,

without stars, compass, sounding, wind or tide, and we cannot tell in

what direction we are going. We have no log which we can case out to

take a dead reckoning by; we may compute our rate of motion with

respect to the neighboring bodies, but we do not know how these bodies

may be moving in space.

So, the big deal about special relativity is *not* that motion is

relative. It's that this is possible while keeping the speed of

light the same for everyone - as Maxwell's equations insist, and as

we indeed see! This is what forced people to replace Galilei

transformations by "Lorentz transformations", which have the

new feature that two coordinate systems moving relative to each

other will disagree not just on where things are, but *when* they

are.

As Einstein wrote in 1905:

Examples of this sort, together with the unsuccessful attempts to

discover any motion of the earth relative to the "light medium",

suggest that the phenomena of electrodynamics as well as mechanics

possess no properties corresponding to the idea of absolute rest.

They suggest rather that, as has already been shown to the first

order of small quantities, the same laws of electrodynamics and

optics will be valid for all frames of reference for which the

equations of mechanics are valid. We will elevate this conjecture

(whose content will be called the "principle of relativity") to

the status of a postulate, and also introduce another postulate,

which is only apparently irreconcilable with it, namely, that

light is always propagated in empty space with a definite velocity

c which is independent of the state of motion of the emitting

body. These two postulates suffice for attaining a simple and

consistent theory of the electrodynamics of moving bodies based on

Maxwell's theory for stationary bodies.

So, what really changed with the advent of special relativity?

First, our understanding of precisely which transformations count

as symmetries of spacetime. These transformations form a *group*.

Before special relativity, it seemed the relevant group was a

10-dimensional gadget consisting of:

3 dimensions of spatial translations

1 dimension of time translations

3 dimensions of rotations

3 dimensions of Galilei transformations

Nowadays this is called the "Galilei group":

With special relativity, the relevant group became the "Poincare

group":

3 dimensions of spatial translations

1 dimension of time translations

3 dimensions of rotations

3 dimensions of Lorentz transformations

It's still 10-dimensional, not any bigger. But, it acts differently

as transformations of the spacetime coordinates (t,x,y,z).

Another thing that changed was our appreciation of the importance

of symmetry! Before the 20th century, group theory was not in the

toolkit of most theoretical physicists. Now it is.

Okay. Now suppose you're the only thing in the universe, floating in

empty space, not rotating. To make your stay in this thought experiment

a pleasant one, I'll give you a space suit. And for simplicity, suppose

special relativity holds true exactly, with no gravitational fields

to warp the geometry of spacetime.

Would the universe be any different if you were moving at constant

velocity? Or translated 2 feet to the left or right? Or turned

around? Or if it were one day later?

No! Not in any observable way, at least! It would seem exactly

the same.

So in this situation, it doesn't really make much sense to say

"where you are", or "which way you're facing", or "what time it is".

There are no "invariant propositions" to make about your location

or motion. In other words, there's nothing to say whose truth value

remains unchanged after you apply a symmetry.

Well, *almost* nothing to say! The logicians in the crowd will note

that you can say "T": the tautologously true statement. You can also

say "F": the tautologously false statement. But, these aren't terribly

interesting.

Next, suppose you have a friend also floating through space. Now

there are more interesting invariant propositions. There's nothing

much invariant to say about just you, and nothing to say about just

your friend, but there are invariant *relations*. For example, you

can measure your friend's speed relative to you, or your distance of

closest approach.

Mathematicians study invariant relations using a tool called "double

cosets". I want to explain these today, since we'll need them soon

in the Tale of Groupoidification.

"Double cosets" sound technical, but that's just to keep timid people

from understanding the subject. A double coset is secretly just an

"atomic" invariant relation: one that can't be expressed as "P or Q"

where P and Q are themselves invariant relations - unless precisely

one of P or Q is tautologously false.

So, atomic invariant relations are like prime numbers: they can't

be broken down into simpler bits. And, as we'll see, every invariant

relation can be built out of atomic ones!

Here's an example in the case we're considering:

"My friend's speed relative to me is 50 meters/second, and our

distance of closest approach is 10 meters."

This is clearly an invariant relation. It's atomic if we idealize

the situation and assume you and your friends are points - so we

can't ask which way you're facing, whether you're waving at each other,

etc.

To see *why* it's atomic, note that we can always find a frame of

reference where you're at rest and your friend is moving by like this:

-----FRIEND---->

YOU

If you and your friend are points, the situation is *completely

described* (up to symmetries) by the relative speed and distance

of closest approach. So, the invariant relation quoted above

can't be written as "P or Q" for other invariant relations.

The same analysis shows that in this example, *every* atomic invariant

relation is of this form:

"My friend's speed relative to me is s, and our distance of

closest approach is d."

for some nonnegative numbers s and d.

(Quiz: why don't we need to let s be negative if your friend is moving

to the left?)

>From this example, it's clear there are often infinitely many

double cosets. But there are some wonderful examples with just

*finitely many* double cosets - and these are what I'll focus

on in our Tale.

Here's the simplest one. Suppose we're doing projective plane

geometry. This is a bit like Euclidean plane geometry, but there are

more symmetries: every transformation that preserves lines is allowed.

So, in addition to translations and rotations, we also have other

symmetries.

For example, imagine taking a blackboard with some points and lines

on it:

\ /

------------x-----------x-----------

\ /

\ /

\ /

\ /

\ /

x

/ \

/ \

/ \

We can translate it and rotate it. But, we can also view it from

an angle: that's another symmetry in projective geometry! This

hints at how projective geometry arose from the study of perspective

in painting.

We get even more symmetries if we use a clever trick. Suppose we're

standing on the blackboard, and it extends infinitely like an endless

plain. Points on the horizon aren't really points on the blackboard.

They're called "points at infinity". But, it's nice to include them

as part of the so-called "projective plane". They make things simpler:

now every pair of lines intersects in a unique point, just as every pair

of points lies on a unique line. You've probably seen how parallel

railroad tracks seem to meet at the horizon - that's what I'm talking

about here. And, by including these extra points at infinity, we get

extra symmetries that map points at infinity to ordinary points, and

vice versa.

I gave a more formal introduction to projective geometry in "week106"

and "week145", and "week178". If you read these, you'll know that

points in the projective plane correspond to lines through the origin

in a 3d space. And, you'll know a bit about the group of symmetries in

projective geometry: it's the group G = PGL(3), consisting of 3x3

invertible matrices, modulo scalars.

(I actually said SL(3), but I was being sloppy - this is another group

with the same Lie algebra.)

For some great examples of double cosets, let F be the space of "flags".

A "flag" is a very general concept, but in projective plane geometry a

flag is just a point x on a line y:

-----------------x----------------

y

An amazing fact is that there are precisely 6 atomic invariant relations

between a pair of flags. You can see them all in this picture:

\ /

------------x-----------x'----------

\ / y

\ /

\ /

\ /

\ /

x"

/ \

/ \

y'/ \y"

There are six flags here, and each exemplifies a different

atomic invariant relation to our favorite flag, say (x,y).

For example, the flag (x',y') has the following relation to (x,y):

"The point of (x',y') lies on the line of (x,y), and no more."

By "no more" I mean that no further incidence relations hold.

There's a lot more to say about this, and we'll need to delve into

it much deeper soon... but not yet. For now, I just want to mention

that all this stuff generalizes from G = PGL(3) to any other simple

Lie group! And, the picture above is an example of a general concept,

called an "apartment". Apartments are a great way to visualize

atomic invariant relations between flags.

This "apartment" business is part of a wonderful theory due to Jacques

Tits, called the theory of "buildings". The space of *all* flags is a

building; a building has lots of apartments in it. Buildings have a

reputation for being scary, because in his final polished treatment,

Tits started with a few rather unintuitive axioms and derived everything

from these. But, they're actually lots of fun if you draw enough

pictures!

Next, let me explain why people call atomic invariant relations

"double cosets".

First of all, what's a relation between two sets X and Y? We can

think of it as a subset S of X x Y: we say a pair (x,y) is in S

if the relation holds.

Next, suppose some group G acts on both X and Y. What's an "invariant"

relation? It's a subset S of X x Y such that whenever (x,y) is in S,

so is (gx,gy). In other words, the relation is preserved by the

symmetries.

Now let's take these simple ideas and make them sound more complicated,

to prove we're mathematicians. Some of you may want to take a little

nap right around now - I'm just trying to make contact with the usual

way experts talk about this stuff.

First, let's use an equivalent but more technical way to think of an

invariant relation: it's a subset of the quotient space G\(X x Y).

Note: often I'd call this quotient space (X x Y)/G. But now I'm

writing it with the G on the left side, since we had a *left* action

of G on X and Y, hence on X x Y - and in a minute we're gonna need

all the sides we can get!

Second, recall from last Week that if G acts *transitively* on both

X and Y, we have isomorphisms

X = G/H

and

Y = G/K

for certain subgroups H and K of G. Note: here we're really modding

out by the *right* action of H or K on G.

Combining these facts, we see that when G acts transitively on both

X and Y, an invariant relation is just a subset of

G\(X x Y) = G\(G/H x G/K)

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

This notation may freak you out at first - I know it scared me!

The point is that we can take G, mod out by the right action of K

to get G/K, and then mod out by the left action of H on G/K, obtaining

H\(G/K).

Or we can take G, mod out by the left action of H to get H\G, and then

mod out by the right action of K on H\G, obtaining

(H\G)/K.

And, these two things are isomorphic! So, we relax and write

H\G/K

A point in here is called a "double coset": it's an equivalence class

consisting of all guys in G of the form

hgk

for some fixed g, where h ranges over H and k ranges over K.

Since subsets of H\G/K are invariant relations, we can think of a

point in H\G/K as an "atomic" invariant relation. Every invariant

relation is the union - the logical "or" - of a bunch of these.

So, just as any hunk of ordinary matter can be broken down into atoms,

every invariant statement you can make about an entity of type X and

an entity of type Y can broken down into "atomic" invariant relations -

also known as double cosets!

So, double cosets are cool. But, it's good to fit them into the "spans

of groupoids" perspective. When we do this, we'll see:

A SPAN OF GROUPOIDS EQUIPPED WITH CERTAIN EXTRA STUFF IS

THE SAME AS A DOUBLE COSET.

This relies on the simpler slogan I mentioned last time:

A GROUPOID EQUIPPED WITH CERTAIN EXTRA STUFF IS

THE SAME AS A GROUP ACTION.

Let's see how it goes. Suppose we have two sets on which G acts

transitively, say X and Y. Pick a figure x of type X, and a figure y

of type Y. Let H be the stabilizer of x, and let K be the stabilizer

of y. Then we get isomorphisms

X = G/H

and

Y = G/K

The subgroup (H intersect K) stabilizes both x and y, and

Z = G/(H intersect K)

is another set on which G acts transitively. How can we think of this

set? It's the set of all pairs of figures, one of type X and one of

type Y, which are obtained by taking the pair (x,y) and applying

an element of G. So, it's a subset of X x Y that's invariant under

the action of G. In other words, its an invariant relation between

X and Y!

Furthermore, it's the smallest invariant subset of X x Y that contains

the pair (x,y). So, it's an *atomic* invariant relation - or in other

words, a double coset!

Now, let's see how to get a span of groupoids out of this. We have

a commutative diamond of group inclusions:

H intersect K

/ \

/ \

/ \

v v

H K

\ /

\ /

\ /

v v

G

This gives a commutative diamond of spaces on which G acts

transitively:

G/(H intersect K)

/ \

/ \

/ \

v v

G/H G/K

\ /

\ /

\ /

v v

G/G

We already have names for three of these spaces - and G/G is just

a single point, say *:

Z

/ \

/ \

/ \

v v

X Y

\ /

\ /

\ /

v v

*

Now, in "week249" I explained how you could form the "action groupoid"

X//G given a group G acting on a space X. If I were maniacally

consistent, I would write it as G\\X, since G is acting on the left.

But, I'm not. So, the above commutative diamond gives a commutative

diamond of groupoids:

Z//G

/ \

/ \

/ \

v v

X//G Y//G

\ /

\ /

\ /

v v

*//G

The groupoid on the bottom has one object, and one morphism for each

element of G. So, it's just G! So we have this:

Z//G

/ \

/ \

/ \

v v

X//G Y//G

\ /

\ /

\ /

v v

G

So - voila! - our double coset indeed gives a span of groupoids

Z//G

/ \

/ \

/ \

v v

X//G Y//G

X//G is the groupoid of figures just like x (up to symmetry), Y//G is

the groupoid of figures just like y, and Z//G is the groupoid of

*pairs* of figures satisfying the same atomic invariant relation as

the pair (x,y). For example, point-line pairs, where the point lies

on the line! For us, a pair of figures is just a more complicated

sort of figure.

But, this span of groupoids is a span "over G", meaning it's part of a

commutative diamond with G at the bottom:

Z//G

/ \

/ \

/ \

v v

X//G Y//G

\ /

\ /

\ /

v v

G

If you remember everything in "week249" - and I bet you don't -

you'll notice that this commutative diamond is equivalent to diamond

we started with:

H intersect K

/ \

/ \

/ \

v v

H K

\ /

\ /

\ /

v v

G

We've just gone around in a loop! But that's okay, because we've

learned something en route.

To tersely summarize what we've learned, let's use the fact that a

groupoid is equivalent to a group precisely when it's "connected":

that is, all its objects are isomorphic. Furthermore, a functor between

connected groupoids is equivalent to an inclusion of groups precisely

when it's "faithful": one-to-one on each homset. So, when I said that

A SPAN OF GROUPOIDS EQUIPPED WITH CERTAIN EXTRA STUFF IS

THE SAME AS A DOUBLE COSET.

what I really meant was

A SPAN OF CONNECTED GROUPOIDS FAITHFULLY OVER G

IS THE SAME AS A DOUBLE COSET.

If that's too terse, let me elaborate for you: a "span of connected

groupoids faithfully over G" is a commutative diamond

C

/ \

/ \

/ \

v v

A B

\ /

\ /

\ /

v v

G

where A,B,C are connected groupoids and the arrows are faithful

functors.

This sounds complicated, but it's mainly because we're trying to toss

in extra conditions to make our concepts match the old-fashioned "double

coset" notion. Here's a simpler, more general fact:

A SPAN OF GROUPOIDS FAITHFULLY OVER G

IS THE SAME AS A SPAN OF G-SETS.

where a "G-set" is a set on which G acts. This is the natural partner

of the slogan I explained last Week, though not in this language:

A GROUPOID FAITHFULLY OVER G

IS THE SAME AS A G-SET.

Things get even simpler if we drop the "faithfulness" assumption, and

simply work with groupoids over G, and spans of these. 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.

Indeed, for the last couple weeks I've just been trying to lay out the

historical context for the Tale of Groupoidification, so experts can

see how the stuff to come relates to stuff that's already known. In

some ways things will get simpler when I stop doing this and march

ahead. But, I'll often be tempted to talk about group actions on

sets, and double cosets, and other traditional gadgets... so I feel

obliged to set the stage.

Okay - here's the answer to the puzzle. Close your eyes if you want

to think about it more.

An optimal strategy is for you and your friend to each look at your

own coin, and then guess that the other coin landed the other way:

heads if yours was tails, and tails if yours was heads. With this

strategy, the chance you're both correct is 1/2.

Or, you can both guess that the other coin landed the *same* way.

This works just as well.

The point is, you and your friend can do twice as well at this game

if you each use the result of your own coin toss to guess the result

of the other's coin toss!

It seems paradoxical that using this random and completely uncorrelated

piece of information - the result of your own coin toss - helps you

guess what your friend's coin will do, and vice versa.

But of course it *doesn't*. You each still have just a 1/2 chance of

guessing the other's coin toss correctly. What the trick accomplishes

is correlating your guesses, so you both guess right or both guess wrong

together. This improves the chance of winning from 1/2 x 1/2 (the

product of two independent probabilities) to 1/2.

By the way, the translation of the passage by Einstein is due to

Michael Friedman, a philosopher at Stanford; he used it in his talk

at this conference. There's a lot more to say about talks at this

conference. Let's see if I get around to it.

Also by the way: if you fix a collection of n G-sets, there's always a

Boolean algebra of n-ary invariant relations. Only the case n = 2 is

related to double cosets, but everything else I said generalizes

easily to higher n using "n-legged spans" of groupoids: an obvious

generalization of the 2-legged spans I've been discussing so far. In

Boolean algebra people often use the term "atom" to stand for an

element that can't be written as "P or Q" unless exactly one of P or

Q is tautologously false.

-----------------------------------------------------------------------

Previous issues of "This Week's Finds" and other expository articles on

mathematics and physics, as well as some of my research papers, can be

obtained at

http://math.ucr.edu/home/baez/

For a table of contents of all the issues of This Week's Finds, try

http://math.ucr.edu/home/baez/twfcontents.html

A simple jumping-off point to the old issues is available at

http://math.ucr.edu/home/baez/twfshort.html

If you just want the latest issue, go to

http://math.ucr.edu/home/baez/this.week.html

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums - The Fusion of Science and Community**