It takes a lot of money to run a Presidential campaign. In 2000, Bush raised and spent a little under two hundred million dollars; Gore only got 150 million (Center for Responsive Politics). In 2004, each of the major candidates raised and spent between three and four hundred million dollars. For the 2008 race, so far Clinton has raised the most money (36 million, ibid.) and Obama is next (Romney is a close third). Mr. Clinton personally raises one hundred thousand dollars a night for his wife's campaign (New York Times). Each of the major candidates will likely (need to) raise at least half a million dollars by the general election.
Of course, all presidential candidates are reasonably affluent. Romney is the richest, with between 190 and 250 million dollars to his name, and Clinton is next, with 10 to 50 million dollars, mostly from her husband's lecture circuit (CBS News). Campaign finance laws restrict the amount of money you or I may donate to any given candidate (for 2008, individuals may not donate more than $2,300 per candidate per election), but politicians are allowed to spend as much of their own money as they want.
Which leads, of course, to Michael Bloomberg, mayor of New York City. Today he announced, while campaigning in California, that he has changed his party affiliation from Republican to Independent (he was a Democrat before running for mayor). Almost certainly he will run for President; he certainly enjoys stoking that fire. But without a major party to provide funding and machinery, does he stand a chance? To find a third-party candidate who did better than Ross Perot (close to 20% in 1992, splitting the right and assuring Clinton a win), you have to go all the way back to Roosevelt in 1912; Nader never cracked 5% (New York Times). Except that Bloomberg is Forbes' 44th richest American, with 5.5 billion dollars (Wikipedia). He will likely run on the Independence ticket --- the same one that sponsored Ross Perot, and on whose ticket he ran (along with the GOP endorsement) for mayor. He supports abortion rights and gay marriage, and is staunchly pro-business. And, it's rumored, he has already set aside $1 billion for a presidential campaign (ibid.). This is easily enough to be competitive.
Bloomberg is not, of course, my favorite of the presidential candidates, but I certainly wouldn't mind him in the White House. I'm amused by what his friend George Stephanopoulos said about his potential run (ibid.; Stephanopolous in italics):
1. 70% of the nation would need to feel as though the country is moving in the wrong direction. Check.
2. Both nominees would need to have disapproval ratings in the 40% range. Clinton and Romney.
3. 40% of the country would need to be open to a third party candidate. Likely?
4. 20-25% of the country would need to be "open to Mike Bloomberg." Time will tell.
19 June 2007
10 June 2007
Categories, trees, and polyhedra
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.
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.
30 May 2007
Solving the halting problem
Any computer user knows that, form time to time, a piece of software gets stuck, "crashing" into an endless loop of calculations, and making the computer unable to perform any other tasks. If a human user notices the computer in such a state, she will usually try to abort the task, sometimes simply by restarting the computer. Because getting into infinite tasks can drastically curtail a computer's effectiveness, operating systems and program compilers will often have checks, looking for tell-tale signs that a program might get stuck. But by a well-known theorem no such checks are perfect.
The proof of this theorem is easy. Say a program H can look at any piece of software and decide, yes or no, whether that software will eventually halt. Software can occasionally take input; perhaps H should be a function of two variables, the string encoding the software S, and the string encoding the input T: H = H(S,T). We can modify this into a new function G(S) = H(S,S), with just a few extra lines telling H that whenever it wants to look at T, actually look at the single piece of input S — i.e. G asks whether S will halt when it acts on itself. Then apply an easy alteration to G, making it less useful: if the answer is yes, rather than saying so, just start counting numbers starting at 1 and going forever. Now apply G to itself, and while you're waiting, perhaps you should get a haircut from the Barber of Seville.
However, none of this takes into consideration the actual facts of real computers. A computer is not, however much we'd like to model it as such, an idealized Turing machine. Its (finite) memory and speed depends such variables as what brand it is, and when it was built.
It is this last observation — that computers are getting faster — that allows us a solution to the Halting Problem. Computers are not just getting faster; they're getting faster exponentially. For some constant C > 1, the number of calculations one of next year's computers can perform in a minute will be at least C times faster than the number of calculations one of this year's computers can perform in a minute.
Thus, rather than run a program we expect to take a long time (if it doesn't halt, it will probably take at least a year) on just one computer, let's set up a fancy server farm, and swap out old computers for new ones. Now, let's hope that Moore was wrong, and that computer speeds grow slightly faster than he predicted, for the following reason: next year's computer, being C times as fast, has 1/C the life-span, and a new C-times better computer is released not at the end of another year, but after just 1/C of a year.
So, this year, we perform some number of calculations N, on our computers. Next year, we get a C-times better computer, but only have it for 1/C as long, so perform another N calculations. Then we get a C^2 computer, and have it for 1/C^2 years. Etc. After infinitely many iterations of this, we've performed N+N+N+... = infinitely many calculations. But our total time spent? 1+1/C+1/C^2+... = C/(C-1) < infinity.
So our algorithm to solve the Halting Problem? Eventually, we will have computers that can totally automate their own server-farm swapping and growing and building (so we really will be able to swap out old for new parts arbitrarily fast). So let's program on of these to do that — to build itself at the predicted exponential rate. And while it's doing so, run whatever program we want to know about. If in less than C/(C-1) time the program stops, then we know it will stop and after how many calculations, and even what the outcome will be. And if it doesn't, then we get the other answer.
The proof of this theorem is easy. Say a program H can look at any piece of software and decide, yes or no, whether that software will eventually halt. Software can occasionally take input; perhaps H should be a function of two variables, the string encoding the software S, and the string encoding the input T: H = H(S,T). We can modify this into a new function G(S) = H(S,S), with just a few extra lines telling H that whenever it wants to look at T, actually look at the single piece of input S — i.e. G asks whether S will halt when it acts on itself. Then apply an easy alteration to G, making it less useful: if the answer is yes, rather than saying so, just start counting numbers starting at 1 and going forever. Now apply G to itself, and while you're waiting, perhaps you should get a haircut from the Barber of Seville.
However, none of this takes into consideration the actual facts of real computers. A computer is not, however much we'd like to model it as such, an idealized Turing machine. Its (finite) memory and speed depends such variables as what brand it is, and when it was built.
It is this last observation — that computers are getting faster — that allows us a solution to the Halting Problem. Computers are not just getting faster; they're getting faster exponentially. For some constant C > 1, the number of calculations one of next year's computers can perform in a minute will be at least C times faster than the number of calculations one of this year's computers can perform in a minute.
Thus, rather than run a program we expect to take a long time (if it doesn't halt, it will probably take at least a year) on just one computer, let's set up a fancy server farm, and swap out old computers for new ones. Now, let's hope that Moore was wrong, and that computer speeds grow slightly faster than he predicted, for the following reason: next year's computer, being C times as fast, has 1/C the life-span, and a new C-times better computer is released not at the end of another year, but after just 1/C of a year.
So, this year, we perform some number of calculations N, on our computers. Next year, we get a C-times better computer, but only have it for 1/C as long, so perform another N calculations. Then we get a C^2 computer, and have it for 1/C^2 years. Etc. After infinitely many iterations of this, we've performed N+N+N+... = infinitely many calculations. But our total time spent? 1+1/C+1/C^2+... = C/(C-1) < infinity.
So our algorithm to solve the Halting Problem? Eventually, we will have computers that can totally automate their own server-farm swapping and growing and building (so we really will be able to swap out old for new parts arbitrarily fast). So let's program on of these to do that — to build itself at the predicted exponential rate. And while it's doing so, run whatever program we want to know about. If in less than C/(C-1) time the program stops, then we know it will stop and after how many calculations, and even what the outcome will be. And if it doesn't, then we get the other answer.
13 May 2007
What functions do we need for physics?
If any physicist asked to use any particular function, I would never begrudge it of her. Absolutely, if a particular mathematics is useful in calculating something about the world, by all means take advantage of it. But over the entire history of humanity we will never write down even countably many functions, and it's unlikely that any physical theory will ever require more than countably many (mathematical theories do so all the time). Moreover, it's unlikely that the physicists will ever need even easily-definable pathological functions like Weierstrass'. A fruitful way for mathematicians to help physicists is by suggesting which conditions are reasonable to assume of any theory, and which should be explored: one such question is to ask for an "upper bound" — a collection of functions that the physicists are unlikely to ever need to escape.
Of course, "real-valued functions on a real line" is one possible answer, but the whole point is that we're likely to find a better bound. Most physicists seem to believe that the universe satisfies some sort of continuity or regularity conditions, and most physicists leave such issues aside when writing their actual arguments; at the very least, I've never seen a physicist to want a function that it discontinuous at more than discretely many points. This again, though, is not all together helpful. Hoepfully, we will get down to countably many functions (or, possibly, a class of functions defined with reference to an as-yet-to-be-determined class of coefficients, so that if our possible coefficients are countably many, then so are our functions), and we're no where near there. A big step is to remind ourselves that physicists certainly will never need more than the definable functions. Still, this definition allows such functions as Weierstrass', and is terribly inductive: it would be nice to have a closed-form definition of the set in question.
What are the tools a physicist is likely to want in writing down a physical theory? It's reasonable to expect our functions to include all the constant functions, and the identity. Moreover, our set of functions should be closed under addition, subtraction, multiplication, and division. This should lead to no complaints — so far, we could stop just with rational functions.
I think, though, that every function should have an inverse (away from singularities, of course — given an allowed function and an open ball in which the function has (in the classical sense) an inverse, this inverse should also be an allowed function). Again, no problem — we can allow all algebraic functions — although now we already escape the realm of good notation (c.f. Abel's Theorem). And our class of allowed functions should be closed under composition. (Question: is the composition of two algebraic functions algebraic? By algebraic function I mean a solution y=y(x) to a polynomial equation 0=F(x,y).)
Thing is, though, we don't yet have the functions physicists use most often: the exponential and trigonometric functions. This must absolutely be fixed. Why do physicists use these? Because they solve simple differential equations.
Indeed, I don't know any functions that appear in physics that do not solve polynomial differential equations, by which I mean equations of the form 0=F(x,y,y',...). In fact, although physicists use second-order equations all the time, I have a hard time coming up with any equations that are not first order (and, of course, if we allow multiple variables, then all differential equations can be cast as first-order). This leads me to suggest that an appropriate answer to the question posed by this post is "solutions to polynomial differential equations".
Does this class of functions possess the properties I want? Certainly it includes algebraic, exponential, and trigonometric functions, and consists only of extremely smooth definable functions. And it's easily closed under inverses. To wit: given an equation 0=F(x,y,y',...) and solution y=y(x), I'm looking for an equation 0=G(y,x,x',...) for which x=x(y) is a solution (where x() is the inverse function of y(), and x'=dx/dy); it suffices, of course, to find a rational function G. But we can let G(y,x,x',...) = F(x,y,1/x',...), since by easy calculus y'=1/x', and by induction higher-order derivatives or y are also rational functions of the derivatives of x:
y^{(n)} = d(y^{(n-1)})/dx = 1/(dx/dy) d/dy [y^{(n-1)}]
But when we start to ask about the binary operations — arithmetic and composition — we see that disaster strikes. Composition is the easiest to visualize, and I will restrict to first-order ODEs.
A differential equation is a surface in 1-jet space
{0=F(x,y,y')} \subseteq \J^1(\R)
(where I use \J for {\cal J} and \R for {\mathbb R}). 1-Jet space, for us, is just \R^3 parameterized by coordinates x, y, and y'; more generally, it's the cotangent bundle cross \R. It comes equipped with a canonical contact structure 0 = dy - y' dx. When this contact structure is not tangent to the surface (a contact on \R^3 structure cannot be tangent to a surface at more than a curve), it defines curves that foliate the surface, so in small balls around generic points, solutions to the differential equation exist and are unique.
So, let's say I have to differential equations 0=F(x,y,y') and 0=G(y,z,z') and solutions y=y(x) and z=z(y) (where I'm thinking of z'=dz/dy). Then I really want a differential equation 0=H(x,Z,Z') so that Z(x)=z(y(x)) is a solution. And I'd like to be able to pick this H in some algorithmic way.
But the geometry makes this hard. Generically, what I'm setting up is a five-dimensional space with coordinates x,y,y',z,z' (or equivalently Z'=y'z'). I have surfaces in each of two three-spaces that intersect on a line. Then what in the five-space would project to two surfaces? A three-manifold. (Away from non-generic points, the surfaces are parameterized by y and another variable perpendicular to y, with a third variable running perpendicular, so the lift should be parameterized by y and two more perpendicular dimensions, with two dimensions of normal bundle.) But, generically, a three-manifold projects to a three-space in the x,Z=z,Z'=z'y' direction.
Because a first-order equation is two-dimensional, it takes one ordered pair of data (e.g. a value for x_0 and y_0=y(x_0)) to specify the particular solution. But the composition of two differential equations takes an ordered triple of data. (For comparison, the composition of two equations F(x,y)=0=G(y,z), which is what we use to compose functions, can be visualized as the quest for a lift to \R^3 of curves living in the xy- and yz-planes.) Perhaps the composition is a second-order differential equation? But our canonical three-surface does not have any Z''-direction, so this is impossible.
For the other arithmetic operations, a similar dimensional analysis occurs: we'd have two surfaces in 1-jet space, which we can think of as two fields of curves in the \R^2 bundle over the x-axis. But there's not a natural way to add, say, two curves to get another curve: with two generic curves on the plane (as opposed to two generic points), there's a whole surface worth of points that are the sum of some pair of points, one on each curve.
But this all leaves open the other version of the question. I've shown that there's no way to compose or add two generic differential equations. What I haven't answered is if the sum or composition of any two given solutions to differential equations is itself a solution to some differential equation. Probably I won't be satisfied even if it is, because I want all of physics to be definable, and I really want these differential equations (along with initial data) to _be_ the definitions of the functions. But nevertheless I cannot think of how to begin looking for a pair of functions, each solutions to polynomial differential equations, whose composition is not.
Of course, "real-valued functions on a real line" is one possible answer, but the whole point is that we're likely to find a better bound. Most physicists seem to believe that the universe satisfies some sort of continuity or regularity conditions, and most physicists leave such issues aside when writing their actual arguments; at the very least, I've never seen a physicist to want a function that it discontinuous at more than discretely many points. This again, though, is not all together helpful. Hoepfully, we will get down to countably many functions (or, possibly, a class of functions defined with reference to an as-yet-to-be-determined class of coefficients, so that if our possible coefficients are countably many, then so are our functions), and we're no where near there. A big step is to remind ourselves that physicists certainly will never need more than the definable functions. Still, this definition allows such functions as Weierstrass', and is terribly inductive: it would be nice to have a closed-form definition of the set in question.
What are the tools a physicist is likely to want in writing down a physical theory? It's reasonable to expect our functions to include all the constant functions, and the identity. Moreover, our set of functions should be closed under addition, subtraction, multiplication, and division. This should lead to no complaints — so far, we could stop just with rational functions.
I think, though, that every function should have an inverse (away from singularities, of course — given an allowed function and an open ball in which the function has (in the classical sense) an inverse, this inverse should also be an allowed function). Again, no problem — we can allow all algebraic functions — although now we already escape the realm of good notation (c.f. Abel's Theorem). And our class of allowed functions should be closed under composition. (Question: is the composition of two algebraic functions algebraic? By algebraic function I mean a solution y=y(x) to a polynomial equation 0=F(x,y).)
Thing is, though, we don't yet have the functions physicists use most often: the exponential and trigonometric functions. This must absolutely be fixed. Why do physicists use these? Because they solve simple differential equations.
Indeed, I don't know any functions that appear in physics that do not solve polynomial differential equations, by which I mean equations of the form 0=F(x,y,y',...). In fact, although physicists use second-order equations all the time, I have a hard time coming up with any equations that are not first order (and, of course, if we allow multiple variables, then all differential equations can be cast as first-order). This leads me to suggest that an appropriate answer to the question posed by this post is "solutions to polynomial differential equations".
Does this class of functions possess the properties I want? Certainly it includes algebraic, exponential, and trigonometric functions, and consists only of extremely smooth definable functions. And it's easily closed under inverses. To wit: given an equation 0=F(x,y,y',...) and solution y=y(x), I'm looking for an equation 0=G(y,x,x',...) for which x=x(y) is a solution (where x() is the inverse function of y(), and x'=dx/dy); it suffices, of course, to find a rational function G. But we can let G(y,x,x',...) = F(x,y,1/x',...), since by easy calculus y'=1/x', and by induction higher-order derivatives or y are also rational functions of the derivatives of x:
y^{(n)} = d(y^{(n-1)})/dx = 1/(dx/dy) d/dy [y^{(n-1)}]
But when we start to ask about the binary operations — arithmetic and composition — we see that disaster strikes. Composition is the easiest to visualize, and I will restrict to first-order ODEs.
A differential equation is a surface in 1-jet space
{0=F(x,y,y')} \subseteq \J^1(\R)
(where I use \J for {\cal J} and \R for {\mathbb R}). 1-Jet space, for us, is just \R^3 parameterized by coordinates x, y, and y'; more generally, it's the cotangent bundle cross \R. It comes equipped with a canonical contact structure 0 = dy - y' dx. When this contact structure is not tangent to the surface (a contact on \R^3 structure cannot be tangent to a surface at more than a curve), it defines curves that foliate the surface, so in small balls around generic points, solutions to the differential equation exist and are unique.
So, let's say I have to differential equations 0=F(x,y,y') and 0=G(y,z,z') and solutions y=y(x) and z=z(y) (where I'm thinking of z'=dz/dy). Then I really want a differential equation 0=H(x,Z,Z') so that Z(x)=z(y(x)) is a solution. And I'd like to be able to pick this H in some algorithmic way.
But the geometry makes this hard. Generically, what I'm setting up is a five-dimensional space with coordinates x,y,y',z,z' (or equivalently Z'=y'z'). I have surfaces in each of two three-spaces that intersect on a line. Then what in the five-space would project to two surfaces? A three-manifold. (Away from non-generic points, the surfaces are parameterized by y and another variable perpendicular to y, with a third variable running perpendicular, so the lift should be parameterized by y and two more perpendicular dimensions, with two dimensions of normal bundle.) But, generically, a three-manifold projects to a three-space in the x,Z=z,Z'=z'y' direction.
Because a first-order equation is two-dimensional, it takes one ordered pair of data (e.g. a value for x_0 and y_0=y(x_0)) to specify the particular solution. But the composition of two differential equations takes an ordered triple of data. (For comparison, the composition of two equations F(x,y)=0=G(y,z), which is what we use to compose functions, can be visualized as the quest for a lift to \R^3 of curves living in the xy- and yz-planes.) Perhaps the composition is a second-order differential equation? But our canonical three-surface does not have any Z''-direction, so this is impossible.
For the other arithmetic operations, a similar dimensional analysis occurs: we'd have two surfaces in 1-jet space, which we can think of as two fields of curves in the \R^2 bundle over the x-axis. But there's not a natural way to add, say, two curves to get another curve: with two generic curves on the plane (as opposed to two generic points), there's a whole surface worth of points that are the sum of some pair of points, one on each curve.
But this all leaves open the other version of the question. I've shown that there's no way to compose or add two generic differential equations. What I haven't answered is if the sum or composition of any two given solutions to differential equations is itself a solution to some differential equation. Probably I won't be satisfied even if it is, because I want all of physics to be definable, and I really want these differential equations (along with initial data) to _be_ the definitions of the functions. But nevertheless I cannot think of how to begin looking for a pair of functions, each solutions to polynomial differential equations, whose composition is not.
12 May 2007
Some politics
Polling data, a year and a half before the election, has almost no information in it. Then again, neither do those talking heads, and folks like me don't know anything either, and that's never stopped me from spouting ideas. So:
RealClearPolitics reports that, at present, Giuliani wins the GOP nomination (he's at 28% nationally; McCain is next at 20%; McCain, though, wins Iowa and New Hampshire, and Intrade is leaning towards McCain). The Democrats have fewer top contenders, and Clinton flies by with 35%, although the most recent Rasmussen poll has Obama almost tying. Gore is currently leading Edwards.
These polls are of "likely voters", and ask questions close to "if the election were help today, for whom would you vote". The more fun, and even less useful, polls are the head-to-head races, asking those polled to pick which of a particular Democrat and a particular Republican. In those, Obama currently edges by Giuliani, who squeezes past Clinton, who barely wins against McCain. Edwards does the best of leading candidates; Romney does the worst. (This is interesting: OnTheIssues has Edwards the most liberal of all of them, and Clinton and Obama exactly tied.)
I'm actually really excited about Giuliani winning the Republican nomination. He's pro-choice, and supports civil unions; he would pull the party to the left. I'm ecstatic about the idea of having two pro-choice parties in this country.
Of course, that likely means he wins the White House. This I'm not entirely unhappy with: if we lose Congress, then any Republican President would be disastrous, but provided we keep the legislative branch, we'd be able to work with Giuliani. He would not veto our social agenda, and we'd work with him on the economy — hell, Pelosi managed to work out trade bills and budgets with the current President, and these days Demorats are more fiscally conservative than Republicans. I think the country works well when we have different parties in power, and a Giuliani presidency would be a staunch repudiation of the Basest of Republicans.
Then again, perhaps he doesn't win. If spun correctly, this is still a critique of the ultra-right: the rightists nominated him, and couldn't even make good. But their spin machines are better than ours, and I worry that Giuliani losing looks more like a failure to energize the Base — it almost strengthens the ultra-right.
I still think that Clinton, of all the candidates in either party, would make the best President. She's brilliant, and extremely experienced in so many things. But will she surmount her negatives? Thirty percent of Americans right now say that they will never vote for her under any circumstances. Put her alone in a room with her and she'll win them over, of coruse — look at what she's done to Newt Gingrich and other Congressional rightists who used to abhor her. But that's not how elections are won.
Then again, I wonder if she might be the only Democrat who actually stands a chance. Her campaign machine is intense; the NYTimes reports that her husband will, come Fall, start doing campaign stops for her, and for now is bringing in over $100,000 a night fundraising. He plans to win, for her, Arkansas, Kentucky, Louisiana, and Florida.
More than that, Clinton is the only person whom I believe could withstand a Swift Boat attack. The best thing for Obama in the next few months is to air all his dirty linens, and get it out of the way. I'm glad that Fox News has already done the "he went to a madrassa! His middle name is Hussein!" thing. Yes, Obama was raised Muslim, and then converted to a particularly lefty Black Power Christianity. What's more American than that? But, no, I don't think Obama can stand up to the kind of plain lies that those cheating rightists are willing to spread. Or, rather, I don't think anyone can, and Obama hasn't yet shown himself an exception. But Clinton can: she's been in the national limelight for fifteen years, and every election they throw dirt at her, and every time she comes out even stronger.
I wonder who the veeps will be. Richardson would make a great Vice President — he was, after all, on the shortlists for both Gore and Kerry — but neither Obama nor Clinton can ask him (the latter makes the ticket too centrist-Clintonian, with the former the media will never get over a black guy and an hispanic). And Richardson is too conservative for my tastes. The ticket I'm fascinated by is Obama-Clark. Clinton could ask Obama; I desperately want Obama to be President four or eight years from now, when he's had a little more Senate time — I want him to have chaired a committee; being VP, or even VP candidate, will help him on that road. Obama should not ask Clinton, and she should say no, because she's too ambitious? Maybe, if they in fact get along really well, it would work. But I doubt it.
Besides, if she doesn't win the White House, Clinton should seriously consider party leadership in the Senate. I've never been that enamored of Harry Reid, although he's fine, and Pat Murry, Richard Durbin, and Chuck Shumer are also all kinda boring. So, to complete the fantasy: Giuliani (and a reasonably liberal VP) in the White House, and Pelosi and Clinton controlling the two houses of Congress.
RealClearPolitics reports that, at present, Giuliani wins the GOP nomination (he's at 28% nationally; McCain is next at 20%; McCain, though, wins Iowa and New Hampshire, and Intrade is leaning towards McCain). The Democrats have fewer top contenders, and Clinton flies by with 35%, although the most recent Rasmussen poll has Obama almost tying. Gore is currently leading Edwards.
These polls are of "likely voters", and ask questions close to "if the election were help today, for whom would you vote". The more fun, and even less useful, polls are the head-to-head races, asking those polled to pick which of a particular Democrat and a particular Republican. In those, Obama currently edges by Giuliani, who squeezes past Clinton, who barely wins against McCain. Edwards does the best of leading candidates; Romney does the worst. (This is interesting: OnTheIssues has Edwards the most liberal of all of them, and Clinton and Obama exactly tied.)
I'm actually really excited about Giuliani winning the Republican nomination. He's pro-choice, and supports civil unions; he would pull the party to the left. I'm ecstatic about the idea of having two pro-choice parties in this country.
Of course, that likely means he wins the White House. This I'm not entirely unhappy with: if we lose Congress, then any Republican President would be disastrous, but provided we keep the legislative branch, we'd be able to work with Giuliani. He would not veto our social agenda, and we'd work with him on the economy — hell, Pelosi managed to work out trade bills and budgets with the current President, and these days Demorats are more fiscally conservative than Republicans. I think the country works well when we have different parties in power, and a Giuliani presidency would be a staunch repudiation of the Basest of Republicans.
Then again, perhaps he doesn't win. If spun correctly, this is still a critique of the ultra-right: the rightists nominated him, and couldn't even make good. But their spin machines are better than ours, and I worry that Giuliani losing looks more like a failure to energize the Base — it almost strengthens the ultra-right.
I still think that Clinton, of all the candidates in either party, would make the best President. She's brilliant, and extremely experienced in so many things. But will she surmount her negatives? Thirty percent of Americans right now say that they will never vote for her under any circumstances. Put her alone in a room with her and she'll win them over, of coruse — look at what she's done to Newt Gingrich and other Congressional rightists who used to abhor her. But that's not how elections are won.
Then again, I wonder if she might be the only Democrat who actually stands a chance. Her campaign machine is intense; the NYTimes reports that her husband will, come Fall, start doing campaign stops for her, and for now is bringing in over $100,000 a night fundraising. He plans to win, for her, Arkansas, Kentucky, Louisiana, and Florida.
More than that, Clinton is the only person whom I believe could withstand a Swift Boat attack. The best thing for Obama in the next few months is to air all his dirty linens, and get it out of the way. I'm glad that Fox News has already done the "he went to a madrassa! His middle name is Hussein!" thing. Yes, Obama was raised Muslim, and then converted to a particularly lefty Black Power Christianity. What's more American than that? But, no, I don't think Obama can stand up to the kind of plain lies that those cheating rightists are willing to spread. Or, rather, I don't think anyone can, and Obama hasn't yet shown himself an exception. But Clinton can: she's been in the national limelight for fifteen years, and every election they throw dirt at her, and every time she comes out even stronger.
I wonder who the veeps will be. Richardson would make a great Vice President — he was, after all, on the shortlists for both Gore and Kerry — but neither Obama nor Clinton can ask him (the latter makes the ticket too centrist-Clintonian, with the former the media will never get over a black guy and an hispanic). And Richardson is too conservative for my tastes. The ticket I'm fascinated by is Obama-Clark. Clinton could ask Obama; I desperately want Obama to be President four or eight years from now, when he's had a little more Senate time — I want him to have chaired a committee; being VP, or even VP candidate, will help him on that road. Obama should not ask Clinton, and she should say no, because she's too ambitious? Maybe, if they in fact get along really well, it would work. But I doubt it.
Besides, if she doesn't win the White House, Clinton should seriously consider party leadership in the Senate. I've never been that enamored of Harry Reid, although he's fine, and Pat Murry, Richard Durbin, and Chuck Shumer are also all kinda boring. So, to complete the fantasy: Giuliani (and a reasonably liberal VP) in the White House, and Pelosi and Clinton controlling the two houses of Congress.
12 February 2007
an apology, and some category theory
I apologize for being so absent from the blogosphere. My computer died — it moved from epileptic through comatose to completely blind — in January, and since then I've been spending maybe ten minutes a day on the internet. I'm not taking classes, so my math exposure consists mostly of reading (I'm currently enjoying Hartry Fields' Science Without Numbers); instead, my time is consumed by an almost complete dance project (our main performance is Friday), running the hiring committee for next year's staff in my dorm, and getting into (and soon visiting) graduate schools around the country.
I did find the time recently to catch up on This Week's Finds, and was particularly interested in the discussion in Week 244. In it, Baez discusses an article by Tom Leinster, called The Euler characteristic of a category, which I skimmed and need to go read more thoroughly.
I certainly haven't grokked most of the material, but I did want to make two comments. First, a small one: Baez wonders at the coincidence that the character 1 has Euler characteristic 1, whereas the character 0 has Euler characteristic 0. I suggest that this has, in fact, real meaning: 1 presumably comes from a has mark, a line, a dot; any natural character for 1 ought to be readily contractible to a point. But 0, on the other hand, should represent exactly an absence: it must be filled with a point (equivalently a disk) to become a disk (equivalently a point). And this exactly defined its Euler characteristic to be 0. Somehow, the ancients, or perhaps the forces of calligraphic natural selection, understand enough naive topology to build Euler characteristics into the system.
My second comment is a little more substantive. In defining the Euler characteristic of a (for now, finite) category, we're trying to generalize
Which is all well and good. But then Leinster et al decide on what seems to me to be a bizarre idea: a category with two objects and one morphism (between them), i.e.
o---->----o
should also (along with o--<--->--o) become an interval, and so should have Euler characteristic 1.
See, in a poset, this was exactly the right thing to do. But I claim that we're then wrong to think of a poset as a category, at least in the normal way. In a category, unlike a poset, you can have morphisms both directions. An isomorphism is really two morphisms, glued together by a commuting disk. There's a difference in a category between that and a unidirectional morphism. On the other hand, in a poset, there's no chance at morphisms going both ways. Instead, a poset is really just a space, but one with a (transitive) sense of "up" and "down".
It seems really bizarre to throw away so much information from the category by ignoring the direction of morphisms when taking Euler characteristics. Instead, why not follow Baez's suggestion: "If we were willing to make up new kinds of numbers, we could make up a new number for the size of this category."
I'm willing. What properties should our new number have? I thought at first that an isomorphism was the sum of two inverse morphisms. If this were so, then we'd want to assign some value X to a "forward" morphism, and some value X^{-1} to a "backwards" one. (Of course, forward and backward are local properties, so these values might want to live locally, say as a field rather than a function, but we are also going to want to sum them.) Then, I thought, we should want X + X^{-1} to be an isomorphism, which we know has Euler characteristic -1 (either object has characteristic 1). We can, of course, solve this: X+X^{-1}=-1 means that X = -(1/2)\pm(i\sqrt{3}/2). And, I said to myself, this is cool: the "Op" operation that reverses categories is just like complex conjugation!
Alas, however, this method fails a horrible death. Because an isomorphism is not the sum of two morphisms, but the sum of two morphisms and a commuting disk. And if we decide that disks should have characteristic 1, then each morphism really should have characteristic -1: we're solving X+X^{-1}+1=-1. And a commuting disk, at least the kind in an isomorphism, really really ought to have characteristic 1, because it can go in any direction. (I am interested by those pairs of morphisms for which, e.g., fg=1 but gf is not 1. I've never totally understood how to treat them and their commuting diagrams.)
So, yes, what should our method be? Certainly I want to assign weights to morphisms that are sensitive to their direction. Perhaps I should even attend to composition and the like: in a one-object category, a nilpotent morphism should be different from an isomorphism? So I want to build some sort of field on my category, and then integrate it against some sort of measure? I definitely want Op to act like "complex conjugation". Perhaps we'll end up with choices — certainly we'll write down natural (local) conditions that the values of our field should satisfy, but their values will depend on whatfield algebraic space (I'm using "field" in the physicists' sense) we solve the equations in — but then what should happen is that we get some sort of "free" object that can map to, for instance, the reals. And so the Euler characteristic, as described by Leinster, is one (and possible the most natural) representation. But in the same way that knot theorists find more powerful tools when they look for representations that attend to crossings, we should look for representations that attend to the direction of our morphisms.
I did find the time recently to catch up on This Week's Finds, and was particularly interested in the discussion in Week 244. In it, Baez discusses an article by Tom Leinster, called The Euler characteristic of a category, which I skimmed and need to go read more thoroughly.
I certainly haven't grokked most of the material, but I did want to make two comments. First, a small one: Baez wonders at the coincidence that the character 1 has Euler characteristic 1, whereas the character 0 has Euler characteristic 0. I suggest that this has, in fact, real meaning: 1 presumably comes from a has mark, a line, a dot; any natural character for 1 ought to be readily contractible to a point. But 0, on the other hand, should represent exactly an absence: it must be filled with a point (equivalently a disk) to become a disk (equivalently a point). And this exactly defined its Euler characteristic to be 0. Somehow, the ancients, or perhaps the forces of calligraphic natural selection, understand enough naive topology to build Euler characteristics into the system.
My second comment is a little more substantive. In defining the Euler characteristic of a (for now, finite) category, we're trying to generalize
- Euler characteristic of topological space. If our category is a groupoid (all morphisms are iso), then equivalently our category is the homotopy groupoid of the space formed by including a point for each object in our category, an edge for each morphism, a disk for each commuting triangle, a 3-ball for each commuting tetrahedron, etc.
- Euler characteristic, as defined by Rota, of a poset. This motivates the idea of defining on our category such objects as a ζ function, a μ function, convolution of functions, etc., with which the Euler characteristic is defined.
Which is all well and good. But then Leinster et al decide on what seems to me to be a bizarre idea: a category with two objects and one morphism (between them), i.e.
should also (along with o--<--->--o) become an interval, and so should have Euler characteristic 1.
See, in a poset, this was exactly the right thing to do. But I claim that we're then wrong to think of a poset as a category, at least in the normal way. In a category, unlike a poset, you can have morphisms both directions. An isomorphism is really two morphisms, glued together by a commuting disk. There's a difference in a category between that and a unidirectional morphism. On the other hand, in a poset, there's no chance at morphisms going both ways. Instead, a poset is really just a space, but one with a (transitive) sense of "up" and "down".
It seems really bizarre to throw away so much information from the category by ignoring the direction of morphisms when taking Euler characteristics. Instead, why not follow Baez's suggestion: "If we were willing to make up new kinds of numbers, we could make up a new number for the size of this category."
I'm willing. What properties should our new number have? I thought at first that an isomorphism was the sum of two inverse morphisms. If this were so, then we'd want to assign some value X to a "forward" morphism, and some value X^{-1} to a "backwards" one. (Of course, forward and backward are local properties, so these values might want to live locally, say as a field rather than a function, but we are also going to want to sum them.) Then, I thought, we should want X + X^{-1} to be an isomorphism, which we know has Euler characteristic -1 (either object has characteristic 1). We can, of course, solve this: X+X^{-1}=-1 means that X = -(1/2)\pm(i\sqrt{3}/2). And, I said to myself, this is cool: the "Op" operation that reverses categories is just like complex conjugation!
Alas, however, this method fails a horrible death. Because an isomorphism is not the sum of two morphisms, but the sum of two morphisms and a commuting disk. And if we decide that disks should have characteristic 1, then each morphism really should have characteristic -1: we're solving X+X^{-1}+1=-1. And a commuting disk, at least the kind in an isomorphism, really really ought to have characteristic 1, because it can go in any direction. (I am interested by those pairs of morphisms for which, e.g., fg=1 but gf is not 1. I've never totally understood how to treat them and their commuting diagrams.)
So, yes, what should our method be? Certainly I want to assign weights to morphisms that are sensitive to their direction. Perhaps I should even attend to composition and the like: in a one-object category, a nilpotent morphism should be different from an isomorphism? So I want to build some sort of field on my category, and then integrate it against some sort of measure? I definitely want Op to act like "complex conjugation". Perhaps we'll end up with choices — certainly we'll write down natural (local) conditions that the values of our field should satisfy, but their values will depend on what
05 December 2006
Poisson brackets and scalar fields
Today's* ODEs class was rather amazing. In standard Yasha style, the topics darted around (he once explained that "It is impossible to be lost in my class. Because topic changes every two minutes, so if you are lost, you won't be lost."): a taste of KM theory, a dash of geodesics on ellipsoids, and a little infinite-dimensional Hamiltonian systems.
It is this last discussion that I found rather mind-blowing. We did not say anything new; rather, we started defining what will eventually give us the quantum behavior of fields, from an entirely classical viewpoint.
Consider one PDE \d u(x,t)/\d t = F(u), where u is a function and F is some map from functions to functions. Let's say, for example, that we're interested in complex functions on the circle: u:S\to\C is what the physicists would call a (complex) scalar field. Let V be the set of all scalar fields; I will not be precise what conditions I want (presumably some smoothness conditions, say complex-analytic, and perhaps some convergence conditions, for instance that the square integral converges. I will call maps from V \to \R "functionals" and those from V \to V "operators"; V is a (complex) vector space, so it makes sense to talk about (real-, complex-, anti-) linear functionals and operators. For instance, \d/\dx is a linear operator; (1/2\pi) \int_0^{2\pi} -- g(x) dx is a linear functional. (I will from now on write \int for \int_0^{2\pi}; consistent with half of mathematics, the volume of the circle is 2\pi.) Rather than thinking of my problem as a PDE, I should think of it as an ODE in this infinite-dimensional space.
Imposing analyticity, etc., conditions on V curtails the freedom of functions: the value of a function at a point largely determines the value at nearby points. We ought to perform a change-of-basis so that we can better tell functions apart: let's assume, for instance, that each function has a Fourier expansion
u(x) = u_0 + \sum p_k e^{-ikx} + q_k e^{ikx}
(Given, of course, by
u_0 = (1/2\pi) \int u(x) dx; p_k = (1/2\pi) \int u(x) e^{ikx} dx; q_k = (1/2\pi) \int u(x) e^{-ikx} dx.)
((Sometime soon I will figure out what I believe to be the proper class of functions with which to do physics. One might hope for (complex) holomorphic, or for complex analytic, or for real C^\infty, or real analytic, or maybe just real integrable. But the Fourier transformation is vital to modern physics, and none of these is particularly the class of things with natural Fourier transforms, because I often end up with \delta functions. I ought to study the Fourier transform a bit more, because I don't understand something basic: it seems that the \delta functions supply a continuum of basis states, whereas the fourier modes are countable. But every delta function can fourier-transform, and modulo convergence this should be a change-of-basis. Perhaps it has something to do with the fact that the Fourier transform doesn't care about individual values of functions, just their integrals. We really ought to pick a class of "functions" so that Fourier really is a legitimate "change-of-basis" in the appropriate infinite-dimensional sense.))
Then our manifold V is, more or less, an odd-dimensional manifold. We cannot hope to put a symplectic structure on it. On the other hand, the ps and qs so naturally line up that we really want to write down \omega = \sum a_k dp_k \wedge dq_k, and we can do so on the even-dimensional subspace \{u_0 = 0\}. (The coefficients a_k have yet to be determined; \omega is a symplectic form for any choice of a_k, and we should choose judiciously to match other physics. Throughout this entry, I eschew the Einstein summation conventions.)
Well, almost. This \omega is almost certainly not going to converge if you feed it most pairs of functions, and I think that to restrict our functions to those that have Fourier expansions that converge rapidly enough is premature, especially since we have yet to determine the a_k. Rather, Yasha suggests, we should discuss the Poisson bracket, which is what really controls physics.
How so? you ask. And what, fundamentally, is a Poisson bracket? Consider our original Poisson bracket \{F,G\} = \omega(X_G,X_F), where X_F is defined by \omega(X_F,-) = dF(-). Then unwrapping definitions gives that \{F,G\} = dF(X_G) = X_G[F], where on the RHS I'm treating X_G as a differential operator. Our Poisson bracket knows exactly the information needed: given a Hamiltonian H, the flow is generated by the vector field X_H = \{-,H\}.
In general, a Poisson bracket is any bracket \{,\} satisfying
(a) Bilinearity (for now \R-linear; perhaps we will ask for \C-linear soon?)
(b) Anti-symmetry and Jacobi (i.e. \{,\} is a Lie bracket)
(c) It behaves as a (first-order) differential operator in each variable: \{FG,H\} = F\{G,H\} + \{F,H\}G.
Condition (c) guarantees that a Poisson bracket never cares about overall constants in F, etc.: \{F,G\} depends only on dF and dG. Symplectic forms, being non-degenerate, are dual to antisymmetric _0^2-tensors (two raised indices), and Poisson brackets are exactly of this form. But Poisson brackets need not be nondegenerate to give us physics. Indeed, the Poisson bracket as described is plenty to define a vector field to be the "derivative" of each function. (Not quite the gradient, but an antisymmetric version of one.) And this is what's needed.
So, to describe the physics of our system, it suffices to pick an appropriate Poisson bracket. Returning now to the system we were originally interested in, of scalar fields on the circle, our Hamiltonians should be functionals of u(x). Let's assume that every functional (at least all the physical ones) can be written in Taylor expansion as polynomials in p_k and q_k. Then to define the Poisson bracket, and continuing to ignore issues of convergence, it suffices to define the brackets between our various coefficients p_k, q_l, and u_0. Given \omega = \sum a_k p_k \wedge q_k (on our subspace of u_0=0), we get \{p_k,q_k\} = a_k^{-1}, and all other brackets are 0.
What would be nice now is to find some physical reason to pick particular a_k, or to even motivate a Poisson bracket of this form at all. Perhaps you vaguely recall a physicists telling you that the Hamiltonian density functional for free scalar fields should look something like h(u(x)) = 1/2 (u^2 + m^2 u'^2), where u'(x) = du/dx. Then the Hamiltonian would be the integral of this: H(u) = \int_0^{2\pi} h(u(x)) dx = u_0^2/2 + \sum_{k=1}^\infty (1-m^2k^2) p_k q_k. With the Poisson bracket given, we can solve this explicitly: p_k(t) = p_k(t=0) e^{(m^2k^2-1) a_k t} and q_k(t) = q_k(t=0) e^{(1-m^2k^2) a_k t}. But this doesn't particularly match physical expectations --- why, for m^2 small and positive and a_k positive, should we expect fields to tend to develop lots of p_k oscillation for large k and lots of q_k oscillation for small k, and for the rest of the oscillation to die?
I'll come back to this kind of physical justification, and perhaps argue my way to a Hamiltonian and a Poisson bracket from the other direction, later. First, I want to explain why Yasha likes this set-up, via mathematical, rather than physical, elegance.
Many interesting Hamiltonians, Yasha observes, are of forms similar to the one I considered in the previous example: the functional H(u) is defined as the integral of some density functional h(x,u(x),u'(x),...). Let's consider this case. Yasha, in fact, uses a particularly restricted case: isotropy is easy (no x dependence), but Yasha also says no derivatives: h = h(u). Then H(u) = (1/2\pi) \int h(u(x)) dx
Then what happens? Well, \dot{q_k} = \{H,q_k\} = a_k \dH/\dp_k = (1/2\pi) \int a_k \dh/\dp_k, and \dot{p_k} = (-1/2\pi) \int a_k \dh/\dq_k/. Plugging these into \dot{u}(x) = \sum \dot{p_k} e^{ikx} + \dot{q_k} e^{-ikx} gives
\dot{u}(x) = (1/2\pi) \int \sum [-a_k \dh/\dq_k e^{ikx} + a_k \dh/\dp_k e^{-ikx}].
Can we recognize this as anything simpler? Recall the chain rule: \dh/\du = \sum (\dh/\dq_k \dq_k/\du + \dh/\dp_k \dp_k/\du). Then, since q_k = (1/2\pi) \int e^{ikx} u(x) dx, we see that \dq_k/\du(x) = (1/2\pi) e^{ikx}. So we see that
h'(u)(x) = \dh/\du(x) = (1/2\pi) \sum [ \dh/\dq_k e^{ikx} + \dh/\dp_k e^{-ikx} ]
This isn't quite what we want, because we have opposite signs on the two a_k. But if we differentiate h'(u) with respect to x, we get
\d/\dx [h'(u)(x)] = (1/2\pi) \sum [ ik \dh/\dq_k e^{ikx} + -ik \dh/\dp_k e^{-ikx} ]
And so, if we pick a_k = k, we see that
\dot{u}(x) = i \d/\dx [h'(u)]
I've been a bit sloppy with this calculation, and you may have trouble following the factors of 2\pi. In particular, I write \int, when I probably should have written \int_{y=0}^{2\pi} dy. But then I would have had to keep track of what's a function of what. Anyway, somewhere in here there's a delta-function, and the formula is correct.
Yasha doesn't do this calculation, preferring one a bit more general and rigorous, which I will sketch:
He observes that since we're a vector space, we can identify points and tangent vectors. Then what are the cotangent vectors? Our vector space of functions has a natural dot product: <u,v> = (1/2\pi) \int_0^{2\pi} u(x) v(x) dx; where now I'm thinking of u and v not as points but as tangent vectors at 0. So to each vector u(x) I can identify the linear functional (1/2\pi) \int u(x) -- dx, which Yasha calls \delta u. Then, knowing that he's chosen {p_k,q_k} = k, Yasha guesses a Poisson bracket:
P(\delta u,\delta v) = (1/2\pi i) \int u v' dx
Recalling the expressions for p_k and q_k as functions of u, we can recognize dp_k = \delta[e^{-ikx}] and dq_k = \delta[e^{ikx}]. Then we can check whether P is the proper Poisson bracket (really the tensor form, eating the derivatives of the functions we would feed into \{,\}) by evaluating it on our ps and qs:
\{p_k,q_k\} = P(e^{-ikx},e^{ikx}) = (1/2\pi i) int e^{-ikx} ik e^{ikx} dx = k; all other brackets are 0, and P is antisymmetric by integration by parts, so must be correct.
Then if F and G are two (real- or complex-valued) functionals on our space of scalar fields, what is their bracket \{F,G\}(u)? Let's say that F and G have the nice form F(u) = (1/2\pi) int f(u(x)) dx (and G is similar). Then \{F,G\} = P(dF,dG) ... what is dF? Well, it's the linear part of F. If \epsilon v is a small change in u, then
(1/\epsilon) (F(u + \elpsilon v) - F(u)) = (1/2\pi) \int f'(u(x)) v(x) dx
where f'(u) is the functional derivative of f with respect to u. So we can recognize dF(u) as \delta[f'(u)], and conclude that
\{F,G\}(u) = (1/2\pi i) \int (f'(u)) (g'(u))' dx
where on the second multiplicand, the inside prime is w.r.t. u, and the outside is w.r.t. x.
Then \dot(u)? Well, for any function(al) F(u), we have \dot{F} = \{H,F\}. u is not a functional, of course, but it is a vector of functionals: u(y) = (1/2\pi) \int u(x) 2\pi \delta(x-y) dx. So du(y) is the covector field (in x) given by \delta[2\pi \delta(x-y)]. (And I'm unfortunately using \delta for too many things, because I want it is an operator and as a Dirac delta function.) So, all in all,
\dot{u}(y) = -\{u(y),H\} = (-1/2\pi i) \int 2\pi \delta(x-y) (h'(u))' dx = i d/dx [h'(u)].
I would like to complete my discussion of scalar fields from entirely a different direction. Given a unit circle, I'd like to describe the propagation of "free scalar fields" around the circle, where now I'm thinking of these as some sort of wave. Remembering very little physics, I can imagine two different interesting dynamics. Either all waves move the same speed, regardless of their shape, or waves propagate at different speeds, with the "high-energy" ones moving faster.
Let's write down some differential equations and see what happens. I'm interested in \dot{u} = some functional of u. Of course, we should demand some isotropy, so x should not appear explicitly. What are the effects of different terms? Keeping everything linear — I want free field propagation, so everything should superimpose — we could ask about \dot{u} = cu, for constant c, but this is boring: the value of the field at a point never cares what the value is ant neighboring points. (Indeed, the whole field evolves by multiplication by e^{ct}. If, for instance, c=i, then sure, different "modes" move at different "speeds", but this is the wrong analysis, since really the whole field is just rotating by some time-varying phase.)
More interesting is if \dot{u} = -u', say. Then expanding u(x) = \sum_{-\infty}^\infty u_k e^{ikx}, we can solve and conclude that \dot{u_k} = -ik u_k, and \dot{u(x)} = u(x-t). So this is what happens if waves travel all at constant velocity.
But let's say that the kinds of waves we care about are surface waves. For instance, we might have a taught string, and waves are small oscillations. Then really physics should act to even out curvatures: we should expect an upwards pull on any point where the field has positive curvature. If we don't remember freshman mechanics, we might write down \dot{u} = u'', which gives us u_k(t) = e^{-k^2 t} u_k(0). This isn't bad: different modes move with velocity proportional to t. It's not quite perfect, though, because really it's the force in that direction, not the derivative, so really we should have acceleration \ddot{u} = u''. Then we get back our original waves, except we have left-movers and right-movers. (More generally, we can add a mass term, and get H(u) = (1/2\pi) \int (1/2) [\dot{u}^2 - (u')^2 + m^2 u^2] = 1/2 \sum_{-\infty}^\infty [\dot{u_k}\dot{u_{-k}} + (k^2 + m^2) u_k u_{-k}], and the modes really do move at different velocities.)
Anyway, the point is that I really do expect, in this world, to have 2\infty total dimensions: \Z worth of "position" coordinates u_k and \Z momentum coordinates, not the \Z/2 of each that Yasha was considering. By just inventing conjugate momentum coordinates v_k to position coordinates u_k, we can get, for the free field, such simple equations of motion as \dot{u_k} = v_{-k} and \dot{v_k} = (k^2+m^2) u_{-k}.
So why does every quantum field theory course start quantizing the (real) scalar field by expanding in Fourier modes and imposing a nontrivial bracket between the coefficients? Because the (free) equations of motion, not the original setup, demand relationships between the fourier modes of u and \dot{u}, and the nontrivial bracket is between u and \dot{u}.
Perhaps next time I will venture into the realm of quantum mechanics. I'd really like to understand how the classical Poisson bracket becomes the quantum Lie bracket, and where the hell that i\hbar comes from. First, of course, I will have to talk more about sets, Hilbert spaces, and the like, and I'll probably stay finite-dimensional for a while. Eventually, of course, I want to describe Feynman diagrams, and tie them back to the Penrose birdtracks and the tensors that started this series of entries.
That is, of course, if I ever get that far. I tend to be distracted by other time-consuming tasks: I am only a few hours of work away from being done applying to graduate schools.
*Of course, I started this entry a few weeks ago.
It is this last discussion that I found rather mind-blowing. We did not say anything new; rather, we started defining what will eventually give us the quantum behavior of fields, from an entirely classical viewpoint.
Consider one PDE \d u(x,t)/\d t = F(u), where u is a function and F is some map from functions to functions. Let's say, for example, that we're interested in complex functions on the circle: u:S\to\C is what the physicists would call a (complex) scalar field. Let V be the set of all scalar fields; I will not be precise what conditions I want (presumably some smoothness conditions, say complex-analytic, and perhaps some convergence conditions, for instance that the square integral converges. I will call maps from V \to \R "functionals" and those from V \to V "operators"; V is a (complex) vector space, so it makes sense to talk about (real-, complex-, anti-) linear functionals and operators. For instance, \d/\dx is a linear operator; (1/2\pi) \int_0^{2\pi} -- g(x) dx is a linear functional. (I will from now on write \int for \int_0^{2\pi}; consistent with half of mathematics, the volume of the circle is 2\pi.) Rather than thinking of my problem as a PDE, I should think of it as an ODE in this infinite-dimensional space.
Imposing analyticity, etc., conditions on V curtails the freedom of functions: the value of a function at a point largely determines the value at nearby points. We ought to perform a change-of-basis so that we can better tell functions apart: let's assume, for instance, that each function has a Fourier expansion
u(x) = u_0 + \sum p_k e^{-ikx} + q_k e^{ikx}
(Given, of course, by
u_0 = (1/2\pi) \int u(x) dx; p_k = (1/2\pi) \int u(x) e^{ikx} dx; q_k = (1/2\pi) \int u(x) e^{-ikx} dx.)
((Sometime soon I will figure out what I believe to be the proper class of functions with which to do physics. One might hope for (complex) holomorphic, or for complex analytic, or for real C^\infty, or real analytic, or maybe just real integrable. But the Fourier transformation is vital to modern physics, and none of these is particularly the class of things with natural Fourier transforms, because I often end up with \delta functions. I ought to study the Fourier transform a bit more, because I don't understand something basic: it seems that the \delta functions supply a continuum of basis states, whereas the fourier modes are countable. But every delta function can fourier-transform, and modulo convergence this should be a change-of-basis. Perhaps it has something to do with the fact that the Fourier transform doesn't care about individual values of functions, just their integrals. We really ought to pick a class of "functions" so that Fourier really is a legitimate "change-of-basis" in the appropriate infinite-dimensional sense.))
Then our manifold V is, more or less, an odd-dimensional manifold. We cannot hope to put a symplectic structure on it. On the other hand, the ps and qs so naturally line up that we really want to write down \omega = \sum a_k dp_k \wedge dq_k, and we can do so on the even-dimensional subspace \{u_0 = 0\}. (The coefficients a_k have yet to be determined; \omega is a symplectic form for any choice of a_k, and we should choose judiciously to match other physics. Throughout this entry, I eschew the Einstein summation conventions.)
Well, almost. This \omega is almost certainly not going to converge if you feed it most pairs of functions, and I think that to restrict our functions to those that have Fourier expansions that converge rapidly enough is premature, especially since we have yet to determine the a_k. Rather, Yasha suggests, we should discuss the Poisson bracket, which is what really controls physics.
How so? you ask. And what, fundamentally, is a Poisson bracket? Consider our original Poisson bracket \{F,G\} = \omega(X_G,X_F), where X_F is defined by \omega(X_F,-) = dF(-). Then unwrapping definitions gives that \{F,G\} = dF(X_G) = X_G[F], where on the RHS I'm treating X_G as a differential operator. Our Poisson bracket knows exactly the information needed: given a Hamiltonian H, the flow is generated by the vector field X_H = \{-,H\}.
In general, a Poisson bracket is any bracket \{,\} satisfying
(a) Bilinearity (for now \R-linear; perhaps we will ask for \C-linear soon?)
(b) Anti-symmetry and Jacobi (i.e. \{,\} is a Lie bracket)
(c) It behaves as a (first-order) differential operator in each variable: \{FG,H\} = F\{G,H\} + \{F,H\}G.
Condition (c) guarantees that a Poisson bracket never cares about overall constants in F, etc.: \{F,G\} depends only on dF and dG. Symplectic forms, being non-degenerate, are dual to antisymmetric _0^2-tensors (two raised indices), and Poisson brackets are exactly of this form. But Poisson brackets need not be nondegenerate to give us physics. Indeed, the Poisson bracket as described is plenty to define a vector field to be the "derivative" of each function. (Not quite the gradient, but an antisymmetric version of one.) And this is what's needed.
So, to describe the physics of our system, it suffices to pick an appropriate Poisson bracket. Returning now to the system we were originally interested in, of scalar fields on the circle, our Hamiltonians should be functionals of u(x). Let's assume that every functional (at least all the physical ones) can be written in Taylor expansion as polynomials in p_k and q_k. Then to define the Poisson bracket, and continuing to ignore issues of convergence, it suffices to define the brackets between our various coefficients p_k, q_l, and u_0. Given \omega = \sum a_k p_k \wedge q_k (on our subspace of u_0=0), we get \{p_k,q_k\} = a_k^{-1}, and all other brackets are 0.
What would be nice now is to find some physical reason to pick particular a_k, or to even motivate a Poisson bracket of this form at all. Perhaps you vaguely recall a physicists telling you that the Hamiltonian density functional for free scalar fields should look something like h(u(x)) = 1/2 (u^2 + m^2 u'^2), where u'(x) = du/dx. Then the Hamiltonian would be the integral of this: H(u) = \int_0^{2\pi} h(u(x)) dx = u_0^2/2 + \sum_{k=1}^\infty (1-m^2k^2) p_k q_k. With the Poisson bracket given, we can solve this explicitly: p_k(t) = p_k(t=0) e^{(m^2k^2-1) a_k t} and q_k(t) = q_k(t=0) e^{(1-m^2k^2) a_k t}. But this doesn't particularly match physical expectations --- why, for m^2 small and positive and a_k positive, should we expect fields to tend to develop lots of p_k oscillation for large k and lots of q_k oscillation for small k, and for the rest of the oscillation to die?
I'll come back to this kind of physical justification, and perhaps argue my way to a Hamiltonian and a Poisson bracket from the other direction, later. First, I want to explain why Yasha likes this set-up, via mathematical, rather than physical, elegance.
Many interesting Hamiltonians, Yasha observes, are of forms similar to the one I considered in the previous example: the functional H(u) is defined as the integral of some density functional h(x,u(x),u'(x),...). Let's consider this case. Yasha, in fact, uses a particularly restricted case: isotropy is easy (no x dependence), but Yasha also says no derivatives: h = h(u). Then H(u) = (1/2\pi) \int h(u(x)) dx
Then what happens? Well, \dot{q_k} = \{H,q_k\} = a_k \dH/\dp_k = (1/2\pi) \int a_k \dh/\dp_k, and \dot{p_k} = (-1/2\pi) \int a_k \dh/\dq_k/. Plugging these into \dot{u}(x) = \sum \dot{p_k} e^{ikx} + \dot{q_k} e^{-ikx} gives
\dot{u}(x) = (1/2\pi) \int \sum [-a_k \dh/\dq_k e^{ikx} + a_k \dh/\dp_k e^{-ikx}].
Can we recognize this as anything simpler? Recall the chain rule: \dh/\du = \sum (\dh/\dq_k \dq_k/\du + \dh/\dp_k \dp_k/\du). Then, since q_k = (1/2\pi) \int e^{ikx} u(x) dx, we see that \dq_k/\du(x) = (1/2\pi) e^{ikx}. So we see that
h'(u)(x) = \dh/\du(x) = (1/2\pi) \sum [ \dh/\dq_k e^{ikx} + \dh/\dp_k e^{-ikx} ]
This isn't quite what we want, because we have opposite signs on the two a_k. But if we differentiate h'(u) with respect to x, we get
\d/\dx [h'(u)(x)] = (1/2\pi) \sum [ ik \dh/\dq_k e^{ikx} + -ik \dh/\dp_k e^{-ikx} ]
And so, if we pick a_k = k, we see that
\dot{u}(x) = i \d/\dx [h'(u)]
I've been a bit sloppy with this calculation, and you may have trouble following the factors of 2\pi. In particular, I write \int, when I probably should have written \int_{y=0}^{2\pi} dy. But then I would have had to keep track of what's a function of what. Anyway, somewhere in here there's a delta-function, and the formula is correct.
Yasha doesn't do this calculation, preferring one a bit more general and rigorous, which I will sketch:
He observes that since we're a vector space, we can identify points and tangent vectors. Then what are the cotangent vectors? Our vector space of functions has a natural dot product: <u,v> = (1/2\pi) \int_0^{2\pi} u(x) v(x) dx; where now I'm thinking of u and v not as points but as tangent vectors at 0. So to each vector u(x) I can identify the linear functional (1/2\pi) \int u(x) -- dx, which Yasha calls \delta u. Then, knowing that he's chosen {p_k,q_k} = k, Yasha guesses a Poisson bracket:
P(\delta u,\delta v) = (1/2\pi i) \int u v' dx
Recalling the expressions for p_k and q_k as functions of u, we can recognize dp_k = \delta[e^{-ikx}] and dq_k = \delta[e^{ikx}]. Then we can check whether P is the proper Poisson bracket (really the tensor form, eating the derivatives of the functions we would feed into \{,\}) by evaluating it on our ps and qs:
\{p_k,q_k\} = P(e^{-ikx},e^{ikx}) = (1/2\pi i) int e^{-ikx} ik e^{ikx} dx = k; all other brackets are 0, and P is antisymmetric by integration by parts, so must be correct.
Then if F and G are two (real- or complex-valued) functionals on our space of scalar fields, what is their bracket \{F,G\}(u)? Let's say that F and G have the nice form F(u) = (1/2\pi) int f(u(x)) dx (and G is similar). Then \{F,G\} = P(dF,dG) ... what is dF? Well, it's the linear part of F. If \epsilon v is a small change in u, then
(1/\epsilon) (F(u + \elpsilon v) - F(u)) = (1/2\pi) \int f'(u(x)) v(x) dx
where f'(u) is the functional derivative of f with respect to u. So we can recognize dF(u) as \delta[f'(u)], and conclude that
\{F,G\}(u) = (1/2\pi i) \int (f'(u)) (g'(u))' dx
where on the second multiplicand, the inside prime is w.r.t. u, and the outside is w.r.t. x.
Then \dot(u)? Well, for any function(al) F(u), we have \dot{F} = \{H,F\}. u is not a functional, of course, but it is a vector of functionals: u(y) = (1/2\pi) \int u(x) 2\pi \delta(x-y) dx. So du(y) is the covector field (in x) given by \delta[2\pi \delta(x-y)]. (And I'm unfortunately using \delta for too many things, because I want it is an operator and as a Dirac delta function.) So, all in all,
\dot{u}(y) = -\{u(y),H\} = (-1/2\pi i) \int 2\pi \delta(x-y) (h'(u))' dx = i d/dx [h'(u)].
I would like to complete my discussion of scalar fields from entirely a different direction. Given a unit circle, I'd like to describe the propagation of "free scalar fields" around the circle, where now I'm thinking of these as some sort of wave. Remembering very little physics, I can imagine two different interesting dynamics. Either all waves move the same speed, regardless of their shape, or waves propagate at different speeds, with the "high-energy" ones moving faster.
Let's write down some differential equations and see what happens. I'm interested in \dot{u} = some functional of u. Of course, we should demand some isotropy, so x should not appear explicitly. What are the effects of different terms? Keeping everything linear — I want free field propagation, so everything should superimpose — we could ask about \dot{u} = cu, for constant c, but this is boring: the value of the field at a point never cares what the value is ant neighboring points. (Indeed, the whole field evolves by multiplication by e^{ct}. If, for instance, c=i, then sure, different "modes" move at different "speeds", but this is the wrong analysis, since really the whole field is just rotating by some time-varying phase.)
More interesting is if \dot{u} = -u', say. Then expanding u(x) = \sum_{-\infty}^\infty u_k e^{ikx}, we can solve and conclude that \dot{u_k} = -ik u_k, and \dot{u(x)} = u(x-t). So this is what happens if waves travel all at constant velocity.
But let's say that the kinds of waves we care about are surface waves. For instance, we might have a taught string, and waves are small oscillations. Then really physics should act to even out curvatures: we should expect an upwards pull on any point where the field has positive curvature. If we don't remember freshman mechanics, we might write down \dot{u} = u'', which gives us u_k(t) = e^{-k^2 t} u_k(0). This isn't bad: different modes move with velocity proportional to t. It's not quite perfect, though, because really it's the force in that direction, not the derivative, so really we should have acceleration \ddot{u} = u''. Then we get back our original waves, except we have left-movers and right-movers. (More generally, we can add a mass term, and get H(u) = (1/2\pi) \int (1/2) [\dot{u}^2 - (u')^2 + m^2 u^2] = 1/2 \sum_{-\infty}^\infty [\dot{u_k}\dot{u_{-k}} + (k^2 + m^2) u_k u_{-k}], and the modes really do move at different velocities.)
Anyway, the point is that I really do expect, in this world, to have 2\infty total dimensions: \Z worth of "position" coordinates u_k and \Z momentum coordinates, not the \Z/2 of each that Yasha was considering. By just inventing conjugate momentum coordinates v_k to position coordinates u_k, we can get, for the free field, such simple equations of motion as \dot{u_k} = v_{-k} and \dot{v_k} = (k^2+m^2) u_{-k}.
So why does every quantum field theory course start quantizing the (real) scalar field by expanding in Fourier modes and imposing a nontrivial bracket between the coefficients? Because the (free) equations of motion, not the original setup, demand relationships between the fourier modes of u and \dot{u}, and the nontrivial bracket is between u and \dot{u}.
Perhaps next time I will venture into the realm of quantum mechanics. I'd really like to understand how the classical Poisson bracket becomes the quantum Lie bracket, and where the hell that i\hbar comes from. First, of course, I will have to talk more about sets, Hilbert spaces, and the like, and I'll probably stay finite-dimensional for a while. Eventually, of course, I want to describe Feynman diagrams, and tie them back to the Penrose birdtracks and the tensors that started this series of entries.
That is, of course, if I ever get that far. I tend to be distracted by other time-consuming tasks: I am only a few hours of work away from being done applying to graduate schools.
*Of course, I started this entry a few weeks ago.
Subscribe to:
Posts (Atom)
