higher-dimensional algebra

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