higher-dimensional algebra

higher-dimensional algebra

[John Baez]

Dear Categorists -

I thought some of you might enjoy this article about Joyal's
structure types, Fiore and Leinster's work on distributive
categories, Leinster's new book on higher categories, and a
bunch of other new papers on higher-dimensional algebra.

Best,
John Baez

..........................................................................

Also available at http://math.ucr.edu/home/baez/week202.html

February 21, 2004
This Week's Finds in Mathematical Physics - Week 202
John Baez

This week I'll deviate from my plan of discussing number theory, and
instead say a bit about something else that's been on my mind lately:
structure types.  But, you'll see my fascination with Galois theory
lurking beneath the surface.

Andre Joyal invented these in 1981 - he called them "especes de
structure".  Basically, a structure type is just any sort of structure
we can put on finite sets: an ordering, a coloring, a partition, or
whatever.  In combinatorics people count such structures using
"generating functions".  A generating function is a power series where
the coefficient of x^n keeps track of how many structures of the given
kind you can put on an n-element set.  By playing around with these
functions, you can often figure out the coefficients and get explicit
formulas - or at least asymptotic formulas - that count the structures
in question.

The reason this works is that operations on generating functions come
from operations on structure types.  For example, in "week190", I
described how addition, multiplication and composition of generating
functions correspond to different ways to get new structure types from
old.

Joyal's great contribution was to give structure types a rigorous
definition, and use this to show that many calculations involving
generating functions can be done directly with structure types.  It
turns out that just as generating functions form a *set* equipped with
various operations, structure types form a *category* with a bunch of
completely analogous operations.  This means that instead of merely
proving *equations* between generating functions, we can construct
*isomorphisms* between their underlying structure types - which imply
such equations, but are worth much more.  It's like the difference
between knowing two things are equal and knowing a specific reason WHY
they're equal!

Of course, this business of replacing equations by isomorphisms is called
"categorification".  In this lingo, structure types are categorified power
series, just as finite sets are categorified natural numbers.

A while back, James Dolan and I noticed that since you can use power
series to describe states of the quantum harmonic oscillator, you can
think of structure types as states of a categorified version of this
physical system!  This gives new insights into the combinatorial
underpinnings of quantum physics.

For example, the discrete spectrum of the harmonic oscillator
Hamiltonian can be traced back to the discreteness of finite sets!
The commutation relations between annihilation and creation operators
boil down to a very simple fact: there's one more way to put a ball in
a box and then take one out, than to take one out and then put one in.
Even better, the whole theory of Feynman diagrams gets a simple
combinatorial interpretation.  But for this, one really needs to go
beyond structure types and work with a generalization called "stuff
types".

I've been thinking about this business for a while now, so last fall
I decided to start giving a year-long course on categorification and
quantization.  The idea is to explain bunches of quantum theory,
quantum field theory and combinatorics all from this new point of view.
It's fun!  Derek Wise has been scanning in his notes, and a bunch of
people have been putting their homework online.  So, you can follow
along if you want:

1) John Baez and Derek Wise, Categorification and Quantization.
Fall 2003 notes: http://math.ucr.edu/home/baez/qg-fall2003/
Winter 2004 notes: http://math.ucr.edu/home/baez/qg-winter2004/

I'd like to give you a little taste of this subject now.  But, instead
of explaining it in detail, I'll just give some examples of how structure
types yield some far-out generalizations of the concept of "cardinality".
This stuff is a continuation of some themes developed in "week144",
"week185", "week190", so I'll start with a review.

Suppose F is a structure type.  Let F_n be the *set* of ways we can put
this structure on a n-element set, and let |F_n| be the *number* of ways
to do it.  In combinatorics, people take all these numbers |F_n| and pack
them into a single power series.  It's called the generating function of
F, and it's defined like this:

              |F_n|
|F|(x) = sum  -----  x^n
                n!

It may not converge, so in general it's just a "formal" power series -
but for interesting structure types it often converges to an interesting
function.

What's good about generating functions is that simple operations on them
correspond to simple operations on structure types.  We can use this to count
structures on finite sets.  Let me remind you how it works for binary trees!

There's a structure type T where a T-structure on a set is a way of
making it into the leaves of a binary tree drawn in the plane.  For example,
here's one T-structure on the set {a,b,c,d}:

              b   d    a   c
               \   \  /   /
                \   \/   /
                 \  /   /
                  \/   /
                   \  /
                    \/

Thanks to the choice of different orderings, the number of T-structures
on an n-element set is n! times the number of binary trees with n
leaves.  Annoyingly, the latter number is traditionally called the (n-1)st
Catalan number, C_{n-1}.  So, we have:

|T|(x) = sum C_{n-1} x^n

where the sum starts at n = 1.

There's a nice recursive definition of T:

   "To put a T-structure on a set, either note that it has one element,
    in which case there's just one T-structure on it, or chop it into
    two subsets and put a T-structure on each one."

In other words, any binary tree is either a degenerate tree with just one
leaf:

        X

or a pair of binary trees stuck together at the root:

   -----   -----
  |     | |     |
  |  T  | |  T  |
  |     | |     |
   -----   -----
     \      /
      \    /
       \  /
        \/


We can write this symbolically as

T = X + T^2

Here's why: X is a structure type called "being the one-element set",
+ means "exclusive or", and squaring a structure type means you chop your set
in two parts and put that structure on each part.  (I explained these rules
more carefully in "week190".)

I should emphasize that the equals sign here is really an *isomorphism*
between structure types - I'm only using "equals" because the isomorphism
key on my keyboard is stuck.  But if we take the generating function of
both sides we get an actual equation, and the notation is set up to make
this really easy:

|T| = x + |T|^2

In "week144" I showed how you can solve this using the quadratic equation:

|T| = (1 - sqrt(1 - 4x))/2.

and then do a Taylor expansion to get

|T| = x + x^2 + 2x^3 + 5x^4 + 14x^5 + 42x^6 + ...

Lo and behold!  The coefficient of x^n is the number of binary trees
with n leaves!

There's also another approach where we work directly with the
structure types themselves, instead of taking generating functions.
This is harder because we can't subtract structure types, or divide
them by 2, or take square roots of them - at least, not without
stretching the rules of this game.  All we can do is use the
isomorphism

T = X + T^2

and the basic rules of category theory.  It's not as efficient, but it's
illuminating.  It's also incredibly simple: we just keep sticking in
"X + T^2" wherever we see "T" on the right-hand side, over and over again.
Like this:

T = X + T^2

T = X + (X + T^2)^2

T = X + (X + (X + T^2)^2)^2

and so on.  You might not think we're getting anywhere, but if
you stop at the nth stage and expand out what we've got, you'll
get the first n terms of the Taylor expansion we had before!
At least, you will if you count "stages" and "terms" correctly.

I won't actually do this, because it's better if you do it yourself.
When you do, you'll see it captures the recursive process of building
a binary tree from lots of smaller binary trees.  Each time you see a "T"
and replace it with an "X + T^2", you're really taking a little binary
tree:

      -----
     |     |
     |  T  |
     |     |
      -----

and replacing it with either a degenerate tree with just a single leaf:


        X


or a pair of binary trees:

  -----   -----
 |     | |     |
 |  T  | |  T  |
 |     | |     |
  -----   -----
    \      /
     \    /
      \  /
       \/


So, each term in the final result actually corresponds to a specific
tree!  This is a good example of categorification: when we calculate the
coefficient of x^n this way, we're not just getting the *number* of binary
planar trees with n leaves - we're getting an actual explicit description
of the *set* of such trees.

Now, what happens if we take the generating function |T|(x) and
evaluate it at x = 1?  On the one hand, we get a divergent series:

|T|(1) = 1 + 1 + 2 + 5 + 14 + 42 + ...

This is the sum of all Catalan numbers - or in other words, the number
of binary planar trees.  On the other hand, we can use the formula

|T| = (1 - sqrt(1 - 4x))/2

to get

|T|(1) = (1 - sqrt(-3))/2

It may seem insane to conclude

1 + 1 + 2 + 5 + 14 + 42 + ... = (1 - sqrt(-3))/2

but Lawvere noticed that there's a kind of strange sense to it.

The trick is to work not with generating function |T| but with the structure
type T itself.  Since |T|(1) is equal to the *number* of planar binary trees,
T(1) should be naturally isomorphic to the *set* of planar binary trees.
And it is - it's obvious, once you think about what it really means.

The number of binary planar trees is not very interesting, but the set of
them is.  In particular, if we take the isomorphism

T = X + T^2

and set X = 1, we get an isomorphism

T(1) = 1 + T(1)^2

which says

     "a planar binary tree is either the tree with one leaf or
      a pair of planar binary trees."

Starting from this, we can derive lots of other isomorphisms involving
the set T(1), which turn out to be categorified versions of equations
satisfied by the number

|T|(1) = (1 - sqrt(-3))/2

For example, this number is a sixth root of unity.  While there's no
one-to-one correspondence between 6-tuples of trees and the 1 element
set, which would categorify the formula

|T|(1)^6 = 1

there *is* a very nice one-to-correspondence between 7-tuples of
trees and trees, which categorifies the formula

|T|(1)^7 = |T|(1)

Of course the set of binary trees is countably infinite, and so is the
set of 7-tuples of binary trees, so they can be placed in one-to-one
correspondence - but that's boring.  When I say "very nice", I mean
something more interesting: starting with the isomorphism

T = x + T^2

we get a one-to-one correspondence

T(1) = 1 + T(1)^2

which says that any binary planar tree is either degenerate or a
pair of binary planar trees... and using this we can *construct*
a one-to-one correspondence

T(1)^7 = T(1)

The construction is remarkably complicated.  Even if you do it
as efficiently as possible, I think it takes 18 steps, like this:

T(1)^7 = T(1)^6 + T(1)^8
       = T(1)^5 + T(1)^7 + T(1)^8
       .
       .
       .
       = 1 + T(1) + T(1)^2 + T(1)^4
       = 1 + T(1) + T(1)^3
       = 1 + T(1)^2
       = T(1)

I'll let you fill in the missing steps - it's actually quite fun if you
like puzzles.

If you get stuck, you can look up the answer in a couple of different places.
While Lawvere was the first to figure this out, the first to write it up was
Andreas Blass:

2) Andreas Blass, Seven trees in one, Jour. Pure Appl. Alg. 103 (1995),
1-21.  Also available at http://www.math.lsa.umich.edu/~ablass/cat.html

There's also a nice treatment based on more general results here:

3) Marcelo Fiore, Isomorphisms of generic recursive polynomial
types, to appear in 31st Symposium on Principles of Programming
Languages (POPL04).  Also available at
http://www.cl.cam.ac.uk/~mpf23/papers/Types/recisos.ps.gz

In fact, Fiore and Leinster have a nice general theory that explains why
the set T(1) acts so much like a sixth root of unity:

4) Marcelo Fiore and Tom Leinster, Objects of categories as complex numbers,
available as math.CT/0212377.

The idea is that when we have an object Z in a distributive category
(a category with finite products and coproducts, the former distributing
over the latter), and it's equipped with an isomorphism

Z = P(Z)

where P is a polynomial with natural number coefficients, we can associate
to it a "cardinality" |Z|, namely any complex solution of the equation

|Z| = P(|Z|)

Which solution should we use?  Well, for simplicity let's consider the
case where P has degree at least 2 and the relevant Galois group acts
transitively on the solutions of this equation, so "all roots are created
equal".  Then we can pick *any* solution as the cardinality |Z|.  Any
polynomial equation with natural number coefficients satisfied by one
solution will be satisfied by *all* solutions, so it doesn't matter
which one we choose.

Now suppose the cardinality |Z| satisfies such an equation:

Q(|Z|) = R(|Z|)

where neither Q nor R is constant.  Then the results of Fiore and
Leinster say we can construct an isomorphism

Q(Z) = R(Z)

in our distributive category!  In other words, a bunch of equations satisfied
by the object's cardinality automatically come from isomorphisms involving the
object itself.

This explains why the set T(1) of binary trees acts like it has cardinality

|T|(1) = (1 - sqrt(-3))/2

or equally well,

|T|(1) = (1 + sqrt(-3))/2

(Since the relevant Galois group interchanges these two numbers, we can
use either one.)  More generally, the set T(n) consisting of binary trees
with n-colored leaves acts a lot like the number |T|(n).

This has gotten me interested in trying to find a nice example of a
"Golden Object": an object G in some distributive category that's
equipped with an isomorphism

G^2 = G + 1

The Golden Object doesn't fit into Fiore and Leinster's formalism,
since this isomorphism is not of the form G = P(G) where P has natural
number coefficients.  But, it still seems that such an object deserves
to have a "cardinality" equal to the golden number:

|G| = (1 + sqrt(5))/2 = 1.618033988749894848204586834365...

James Propp came up with an interesting idea related to the Golden Object:
consider what happens when we evaluate the generating function for binary
trees at -1.  On the one hand we get an alternating sum of Catalan numbers:

|T|(-1) = -1 + 1 - 2 + 5 - 14 + 42 + ...

On the other hand, we can use the formula

|T| = (1 - sqrt(1 - 4x))/2

to get

|T|(1) = (1 - sqrt(5))/2

which is -1 divided by the golden number.  Of course, it's possible we
should use the other sign of the square root, and get

|T|(1) = (1 + sqrt(5))/2

which is just the golden number!  Galois theory says these two roots are
created equal.  Either way, we get a bizarre and fascinating formula:

- 1 + 1 - 2 + 5 - 14 + 42 + ... = (1 +- sqrt(5))/2

Can we fit this into some clear and rigorous framework, or is it just nuts?
We'd like some generalization of cardinality for which "the set of binary
trees with -1-colored leaves" has cardinality equal to the golden number.

James Propp suggested one avenue.  Following Schanuel's ideas on Euler
characteristic as a generalization of cardinality, it makes sense to
treat the real line as a "space of cardinality -1".  This will sound
crazy unless you go back and read "week147", so please do that!
Anyway, using this idea it seems reasonable to consider the space of
binary trees with leaves labelled by real numbers as a rigorous
version of "the set of binary trees with -1-colored leaves".  So, we
just need to figure out what generalization of Euler characteristic
gives this space an Euler characteristic equal to the golden number.
It would be great if we could make this space into a Golden Object in
some distributive category, but that may be asking too much.

Whew!  There's obviously a lot of work left to be done here.  Here's
something easier: a riddle.  What's this sequence?

      un, dos, tres, quatre, cinc, seis, set, vuit, nou, deu,...

The answer is at the end of this article.

Now I'd like to mention some important papers on n-categories.  You
may think I'd lost interest in this topic, because I've been talking
about other things.  But it's not true!

Most importantly, Tom Leinster has come out with a big book on n-categories
and operads:

5) Tom Leinster, Higher Operads, Higher Categories, Cambridge U. Press,
Cambridge, 2003.  Also available as math.CT/0305049.

As you'll note, he managed to talk the press into letting him keep his book
freely available online!  We should all do this.  Nobody will ever make much
cash writing esoteric scientific tomes - it takes so long, you could earn
more per hour digging ditches.  The only *financial* benefit of writing such
a book is that people will read it, think you're smart, and want to hire you,
promote you, or invite you to give talks in cool places.  So, maximize your
chances of having people read your books by keeping them free online!  People
will still buy the paper version if it's any good....

And indeed, Leinster's book has many virtues besides being free.  He
gracefully leads the reader from the very basics of category theory
straight to the current battle front of weak n-categories, emphasizing
throughout how operads automatically take care of the otherwise mind-numbing
thicket of "coherence laws" that inevitably infest the subject.  He doesn't
take well-established notions like "monoidal category" and "bicategory"
for granted - instead, he dives in, takes their definitions apart, and
compares alternatives to see what makes these concepts tick.  It's this sort
of careful thinking that we desperately need if we're ever going to reach the
dream of a clear and powerful theory of higher-dimensional algebra.  He
does a similar careful analysis of "operads" and "multicategories" before
presenting a generalized theory of operads that's powerful enough to support
various different approaches to weak n-categories.  And then he describes
and compares some of these different approaches!

In short: if you want to learn more about operads and n-categories, this is
*the* book to read.

Leinster doesn't say too much about what n-categories are good for, except for
a nice clear introduction entitled "Motivation for Topologists", where he
sketches their relevance to homology theory, homotopy theory, and cobordism
theory.  But this is understandable, since a thorough treatment of their
applications would vastly expand an already hefty 380-page book, and diffuse
its focus.  It would also steal sales from *my* forthcoming book on higher-
dimensional algebra - which would be really bad, since I plan to retire on
the fortune I'll make from this.

Secondly, Michael Batanin has worked out a beautiful extension of his ideas
on n-categories which sheds new light on their applications to homotopy
theory:

6) Michael A. Batanin, The Eckmann-Hilton argument, higher operads and
E_n spaces, available as math.CT/0207281.

Michael A. Batanin, the combinatorics of iterated loop spaces, available as
math.CT/0301221.

Getting a manageable combinatorial understanding of the space of loops
in the spaces of loops in the space of loops... in some space has
always been part of the dream of higher-dimensional algebra.  These
"k-fold loop spaces" or have been important in homotopy theory since
the 1970s - see the end of "week199" for a little bit about them.
People know that k-fold loop spaces have k different products that
commute up to homotopy in a certain way that can be summarized by
saying they are algebras of the E_k operad, also called the "little
k-cubes operad".  However, their wealth of structure is still a bit
mind-boggling.  James Dolan and I made some conjectures about their
relation to k-tuply monoidal categories in our paper "Categorification"
(see "week121"), and now Batanin is making this more precise using
his approach to n-categories - which is one of the ones described in
Leinster's book.

There's also been a lot of work applying higher-dimensional algebra to
topological quantum field theory - that's what got me interested in
n-categories in the first place, but a lot has happened since then.
For a highly readable introduction to the subject, with tons of great
pictures, try:

7) Joachim Kock, Frobenius Algebras and 2D Topological Quantum Field
Theories, Cambridge U. Press, Cambridge, 2003.

This is mainly about 2d TQFTs, where the concept of "Frobenius algebra"
reigns supreme, and everything is very easy to visualize.

When we go up to 3-dimensional spacetime life gets harder, but also more
interesting.  This book isn't so easy, but it's packed with beautiful math
and wonderfully drawn pictures:

8) Thomas Kerler and Volodymyr L. Lyubashenko, Non-Semisimple Topological
Quantum Field Theories for 3-Manifolds with Corners, Lecture Notes in
Mathematics 1765, Springer, Berlin, 2001.

The idea is that if we can extend the definition of a quantum field
theory to spacetimes that have not just boundaries but *corners*, we
can try to build up the theory for arbitrary spacetimes from its
behavior on simple building blocks - since it's easier to chop
manifolds up into a few basic shapes if we let those shapes have
corners.  However, it takes higher-dimensional algebra to describe all
the ways we can stick together manifolds with corners!  Here Kerler
and Lyubashenko make 3-dimensional manifolds going between 2-manifolds
with boundary into a "double category"... and make a bunch of famous
3d TQFTs into "double functors".

Closely related is this paper by Kerler:

9) Thomas Kerler, Towards an algebraic characterization of 3-dimensional
cobordisms, Contemp. Math. 318 (2003) 141-173.  Also available as
math.GT/0008204.

It relates the category whose objects are 2-manifolds with a circle as
boundary, and whose morphisms are 3-manifolds with corners going
between these, to a braided monoidal category "freely generated by a
quasitriangular Hopf algebra object".  (I'm leaving out some fine
print here, but probably putting in more than most people want!)  It
comes close to showing these categories are the same, but suggests
that they're not quite - so the perfect connection between topology
and higher categories remains elusive in this important example.

Answer to the riddle: these are the Catalan numbers - i.e., the natural
numbers as written in Catalan.  This riddle was taken from the second
volume of Stanley's book on enumerative combinatorics (see "week144").

-----------------------------------------------------------------------
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/twf.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