Here's a Zome Tool exercise that y'all can try your hand at, and then I'll tell you some of the category theory behind it, and why I was thinking of it.
Build a solid with six pentagonal faces and three quadrilateral faces. By Euler's formula, then, there are 14 vertices, all necessarily trivalent. I want this figure to be as "regular" as possible: so two of those 14 vertices should be where three pentagons meet (these ought to be antipodes) and each of the other twelve vertices is at the corner of two pentagons and a quadrilateral.
Now I'll tell you some category theory, and explain why this figure is the appropriate three-dimensional entry in the sequence that goes "point, line segment, pentagon". I don't yet know what the next (four-dimensional) figure is, but I do know that it has 42 zero-dimensional vertices, 84 one-dimensional edges, and, I think, 56 two-dimensional faces and 14 three-dimensional hyperfaces. Perhaps you can save me the trouble of actually drawing it myself, and work it out on your own. I'm curious to know what the patterns are of the number and kind of different dimensional faces. If you don't like category theory but do like combinatorics, then skip ahead until you get to pictures of rooted trees.
Much of this material is available at John Baez's website; in particular, I was thinking about this after reading some of Winter 2002 of his Quantum Gravity seminar.
Say you have some binary operation. Like multiplication in a group. Then given two elements, say A and B, there's one way to multiply them (in order): AB. Yes, I could also do BA, but for now let's say that I know A comes first. I'm thinking of A and B here as some kind of "machines" (you might say "functions") with one "IN" pipe and one "OUT" pipe. I can compose to machines by hooking them together and putting a big metal box around them, and pretending that it's one machine:
->-A->- composed with ->-B->- gives
_________
->-|-A->-B-|->- =: ->-AB->-
|_______|
Fair enough. This is what we learned back in elementary school when we first met functions. From now on, I'll use parentheses () to denote "putting a box around something" and I'll probably just write functions on a line like we normally do.
But what about multiplying three functions? There's this super cool property of function composition --- it's this property that motivates the idea of a "group" --- called "associativity". In symbols:
(AB)C = A(BC)
What does this property really mean? We defined composition to be a binary operation, and this says that the two ways to use a binary operation to create a ternary one are actually the same. More intuitively, the associative law says that there's only one interpretation for ABC, i.e. for this picture:
->-A->-B->-C->-
You can prove that the associative law is sufficient to guarantee that any unparenthesized string of symbols has a unique interpretation. If this is the full extent of our laws --- that we can draw pictures, each consisting of a (oriented) string with some number of (labeled) beads on it, and such that each picture has a unique interpretation depending only on the order of the beads, then we get a category. (Each picture is called a morphism, and the strings can also carry labels; a string label is called an object. Of course, we're allowed to have no beads on a string: ->- is the "identity morphism" for the object labeling that string. If all the strings have the same label ( i.e. if we don't allow labeled strings) then we get a monoid.)
Now, however, let's relax the associative law. In particular, rather than saying that (AB)C equals A(BC), let's just say that they're "isomorphic". We can start to develop the theory of "weak 2-categories", which I probably won't fully define here, by introducing an "associator 2-morphism", called a_{A,B,C}, which sends (AB)C to A(BC).
So far, so good. What about if we want to compose four things? Using a binary operation, there are five ways to do this. We can place them in a pentagon, with associators going between them:
((AB)C)D --a_{AB,C,D}-> (AB)(CD) --a_{A,B,CD}-> A(B(CD))
__
\ /|
\ /
a_{A,B,C} a_{B,C,D}
\ /
_\| /
(A(BC))D --a_{A,BC,D}-> A((BC)D)
Well, Mac Lane realized that a good definitions of a (weak) 2-category and of monoidal categories (like Vect, where there's a "tensor product") should involve this kind of pentagon. See, just saying that there are "associator" isomorphisms a_{A,B,C} between different ways of multiplying objects isn't enough, because a priori the isomorphisms going along the top or bottom of this diagram need not be the same. But there really should only be one way that ((AB)C)D = A(B(CD)). Mac Lane then proved that this pentagon is enough: if for any four objects this pentagon commutes, then any two ways of parenthesizing any given string will be isomorphic in a unique way. (Just like the associative law guarantees that any two parenthesizations are equal, the pentagon law guarantees that two maps between parenthesizations are equal.)
How should we draw this? Saying that this diagram commutes is like filling in the hole in the middle of the pentagon. Indeed, I'll let you on your own continue this story into higher-dimensional categories, where, for instance, you need to introduce double associators like b_{A,B,C,D} defined by the following picture:
((AB)C)D --a_{AB,C,D}-> (AB)(CD) --a_{A,B,CD}-> A(B(CD))
__
\ || /|
\ || /
a_{A,B,C} b_{A,B,C,D} a_{B,C,D}
\ || /
_\| \/ /
(A(BC))D --a_{A,BC,D}-> A((BC)D)
By the way, what's a "zero associator"? The associator a_{} gives us a morphism for each triple of objects, and the double associator b_{} gives us a 2-morphism for each quadruple of objects. The 0-associator should give us an object for each pair of objects, and thus is exactly the binary operation m_{A,B}=AB.
Ok, now I'm going to move away from category theory --- I wanted to give you a sense of where this was all coming from, to do some combinatorics and explain why and how I was thinking of the problem I had originally posed.
See, a parenthesization is, of course, really just a binary tree:
((A(BC))D)(EF) =
B C
\/
A /
\/
\ D E F
\/ \/
\ /
\/
The rule is very simple: \/ means multiplication. The symbols are written from left to right, but the multiplication is parenthesized from top to bottom. Of course, we've already counted how many binary trees there are: the Catalan numbers C(n) = (2n)!/(n!(n+1)!) give the number of binary trees with n+1 leaves. (Symmetry is not being considered here:
\/ \/
\/ and \/
are different trees.)
What about associators? Binary trees exactly label each object; what symbols can we use to accurately describe the associators?
Well, an associator describes some "continuous" transformation from
\/ \/
\/ to \/
I think of this as "sliding" that middle arm down the left side and up the right. The graph, then, must have gone trough the following as an intermediate state:
\|/
Ah ha! Associators correspond to trees with three-prong branches. Rather than continuing to write words, let me just draw some ASCII pictures, and hopefully you'll understand the pattern:
0: ab
\ /
\/
1: abc
\ / \ /
\/ >--- \ | / ---> \/
\ / \|/ \ /
\/ \/
2: abcd
\ / \ /
\ / \/ \/ \ /
\ / \/ \ / \/ \ /
\/ >--- \ | / ---> \ / >--- \ | / ---> \/
\ / \|/ \/ \|/ \ /
\/ \/
\ / || \ /
\/ || \/
\ \ \ / / __
\ \ | | / /|
\ \/ /
\ | / \||/ \ | /
\|/ \/ \|/
\ / \ /
\/ \ || / \/
_\| \||/ /
\/
\ / \ /
\/ \/
\ / \ / \ /
\/ >--- \ / ---> \/
\ / \ | / \ /
\/ \|/ \/
The thing in the middle of the pentagon is my failed attempt at a valence-four node. It is on a downward-pointing 2-morphism, like the earlier b_{}, which goes from the morphism along the top to the morphism along the bottom.
I will leave to you the challenge of drawing the next figure (with all trees with five leaves). In addition to pentagons, you will also get three quadrillaterals, with labels like
\ | /
\|/
\ | /
\ | /
\|/
that describe the commutation (in the classical sense) of two different associators: in this case, a_{a,b,c} and a_{abc,d,e}. You'll also, of course, get pentagons. The image is hard to draw symmetrically on paper, because it requires edges to cross one another; it is, a planar graph, and fits well on a sphere. The inside of the sphere, of course, should be filled in and labeled by the 5-valent node.
At higher dimensions, how much more complicated do the figures get? We can derive some numerological data about the next figure. It must have 42 vertices, because that's the next Catalan number. I.e. there are 42 binary rooted trees with six leaves. The figure should have 84 edges. Why? With six leaves, a binary rooted tree would have five branch points. An associators corresponds to a pair of adjacent branches; each branch except the bottom one has exactly one branch directly below it, and this is all pairs. So there are four pairs of branches, and hence four associators. But each associator, i.e. each edge in the figure, corresponds to two vertices. So there are 4/2= twice as many edges as vertices. Continuing this argument, we see that the n-dimensional figure, i.e. the one coming from all trees with n+2 leaves, will have C(n+1) = (2n+2)!/(n+1)!(n+2)! vertices, and (n/2)C(n+1) = (2n+1)!/(n-1)!(n+2)! edges.
What about hyperfaces of other dimensions? It's hard to continue this style of argument to two-dimensional faces, because they come in both quadrilateral and pentagonal flavors. Well, how many n-1-dimensional hyperfaces are there? The central n-dimensional piece is labeled with tree branching into n+2 leaves. A move from a j-dimensional face to a j+1-dimensional face that it's a part of consists exactly of deleting an interior (non-leaf) edge. So going from a j+1-dimensional face to one of its j-dimensional constituent faces consists of "zipping up" some k adjacent edges that all come from the same l-valent branch. Except that k cannot be 1 --- zipping up one edge doesn't do anything --- nor can it be l. So what does that leave us for n-1-dimensional faces? I want to put one pair of parentheses in among n+2 leaves (a j-dimensional face corresponds to a (partial) parenthesization with n-j pairs of parentheses). There are n+3 spots for each parenthesis to go; I want to choose two of them (the first one for the open parenthesis, the second for the close). There are, of course, (n+3)(n+2)/2 ways to do this. But n+3 of them don't count: n+2 of these ways just grab a single leaf, and one of them grabs all the leaves. So there are really n(n+3)/2 valid single-parenthesizations, and hence 14 three-dimensional hyperfaces on the four-dimensional figure. (When I was first trying to guess the number, I asked The Online Encyclopedia of Integer Sequences for the sequence 0,2,5,9, and sure enough got the right sequence.)
Baez says that at any dimension the figure you draw is homeomorphic to a solid ball. If we believe him (I have no reason not to, but he hasn't justified this claim in my reading so far, and I haven't proven it myself) then it's easy to calculate the number of two-dimensional faces on the four-dimensional entry in our sequence of polytopes: by Euler's formula, the alternating sum of the number of faces of different dimensions must be exactly 1, and so there must be 56 two-dimensional faces, coming in a mix of quadrilaterals and pentagons. I am very curious to know how many of each there are. I would also like to know what the possible three-dimensional hyperfaces are: certainly there's the 9-sided figure that I asked you to construct with Zome Tool, corresponding to each tree with one five-valent branch (the four-solid has seven of these). But there are also hyperfaces corresponding to trees with one node branching into four and one branching into three. What kind of solids are these? In even higher-dimensional figures, we could also get solids from trees with three ternary branches.
There's a family of polyhedra just waiting to be discovered. And they have deep algebraic interpretation, so they really ought to be found and studied. Even at the very lowest dimensions, I don't understand some of it: for example, the solid you built out of Zome Tool, corresponding to all the rooted trees with five leaves, has a three-fold symmetry that isn't obvious from the original set-up. Even its two-fold symmetry is different from the one in the problem: the natural north and south poles of the figure are the graphs
\ / \ / \ / \ /
\/ \/ \/ \/
\ / \ /
\ / and \ /
\/ \/
\ / \ /
\/ \/
whereas from a tree point of view the most natural endpoints are
\ / \ /
\/ \/
\ / \ /
\/ and \/
\ / \ /
\/ \/
\ / \ /
\/ \/
Indeed, the natural symmetry from the tree point of view --- reflection in the left-right direction --- manifests as the least likely of symmetries of the polyhedron: 180° rotation through one particular axis, the one connecting one of the quadrilaterals to the opposite edge. Why? I have now idea. If you have ideas, please leave a comment.
10 June 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment