Dismiss Notice
Join Physics Forums Today!
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)

  1. Apr 27, 2007 #1
    Also available as http://math.ucr.edu/home/baez/week250.html

    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

    1) Philosophical and Formal Foundations of Modern Physics,

    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

    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

    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

    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

    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,

    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:



    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

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

    \ /
    \ /
    \ /
    \ /
    \ /
    \ /
    / \
    / \
    / \

    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:


    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:

    \ /
    \ / y
    \ /
    \ /
    \ /
    \ /
    / \
    / \
    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

    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

    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


    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


    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


    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


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


    A point in here is called a "double coset": it's an equivalence class
    consisting of all guys in G of the form


    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:


    This relies on the simpler slogan I mentioned last time:


    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


    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

    This gives a commutative diamond of spaces on which G acts

    G/(H intersect K)
    / \
    / \
    / \
    v v
    G/H G/K
    \ /
    \ /
    \ /
    v v

    We already have names for three of these spaces - and G/G is just
    a single point, say *:

    / \
    / \
    / \
    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:

    / \
    / \
    / \
    v v
    X//G Y//G
    \ /
    \ /
    \ /
    v v

    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:

    / \
    / \
    / \
    v v
    X//G Y//G
    \ /
    \ /
    \ /
    v v

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

    / \
    / \
    / \
    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:

    / \
    / \
    / \
    v v
    X//G Y//G
    \ /
    \ /
    \ /
    v v

    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

    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


    what I really meant was


    If that's too terse, let me elaborate for you: a "span of connected
    groupoids faithfully over G" is a commutative diamond

    / \
    / \
    / \
    v v
    A B
    \ /
    \ /
    \ /
    v v

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

    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:


    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:


    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


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


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


    If you just want the latest issue, go to

  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted