Marie Antoinette was right!

Or, rather, Marie-Therese was, when she encouraged the commoners to eat rich, expensive desserts. I recently procured a copy of Rose Levy Beranbaum's The Cake Bible, a book I highly recommend. Ultimately, I hope to try every cake she suggests; over the last two weeks, I began that project with the first five of her recipes, in order, and also a few of her cakes later on. We've had almost one cake a night — no mean feat for a family of five.

It was with great pleasure, then, that I came upon an easy vegan gem. Beranbaum loves her butter, and her ingredient-sorted categories include All Egg Yolks, All Egg Whites, and Safe For Passover, but not, for instance, Low Fat (low saturated fat, yes, e.g. meringue). So when I saw a recipe from the '50s — she says it's an original, although I will paraphrase — that was safe for my godmother's birthday (my godmother tries to avoid dairy), I knew I had to try it. It turned out fantastic.

Chocolate Cake

Preheat oven 350°F.

In a medium bowl, whisk together

• 1/3 cup unsweetened cocoa powder
• 1 cup boiling water

until smooth, and allow to cool. Whisk in

• 1 tsp vanilla
• 3/4 cup mayonnaise*.

In bowl of standing mixer with padle (or by hand in a large bowl, I guess), combine dry ingredients:

• 2 cups (sifted) cake flour
• 1 cup sugar
• 2 tsp baking soda
• 1/2 tsp salt.

Add chocolate mixture, and mix on low until everything is moistened. Increase to medium and beat 1 minute to aerate.

Prepare two 8-inch cake pans, by (spray) greasing, and then lining the bottoms with circles of baker's parchment, and greasing again. Scrape batter (very liquidy) into prepared pans; it should only fill about 1/3 full (cake expands significantly). Bake 20 to 25 minutes.

Having cherries on hand, and having made a cake with brandied cherries earlier last week, I combined some cherry preserves and the brandy-cherry-syrup in a small frypan over low heat to dissolve. After turning out the first cake, I poured a thin layer of glaze over it, so that I could glue the top layer on. I then poured more glaze on the top of the cake, so that little bits rolled down the sides, and lined the outer edge of the cake top with cherry halves.

* Note: I used only 1/3 cup mayonnaise, since I misread the recipe. It worked fine. More will only make it richer. And I'm sure that vegan mayonnaise substitutes, such as Nayonnaise would work just as well. I would even be interested in trying this cake with Wildwood Garlic Aioli — I've had a mayonnaise cake made with garlic aioli before (a plain yellow cake; the cook also substituted rice flour for cake flour to make it gluten free, and it still turned out good), and Khymos suggests that chocolate and garlic might go well together with the addition of coffee. This recipe would definitely be good with some added instant espresso (I'd put in between a tsp and a Tbsp in the first step with the cocoa powder).

A note on ultrafilters and voting.

Terence Tao has a very nice discussion of ultrafilters in his most recent post. In his comment thread, I posed two problems (and provided an embarrassingly incorrect solution to one of them), which I will repeat here; then I'll write about another aspect of Tao's post.

Problem (1): Construct (with Axiom of Choice, of course) a bounded sequence and an ultrafilter so that the sequence has no large convergent subsequences.

Problem (2): Open-ended. Continuum Hypothesis, I've heard it claimed, is (at least sufficient to guarantee that) ultrapowers by different (nonprinciple) ultrafilters are equivalent. I first heard (a version of) this claim from Conway, and I believe he suggested that this was actually equivalent to CH, although that could be a faulty memory. A commenter says that it's not the case that two nonprinciple ultrafilters are themselves isomorphic (in the sense of there existing a bijection on \N that takes one ultrafilter to the other), but it's not clear to me why not. So, why not? And, more generally, is there a reasonably easy way to see the first claim in this paragraph?


Lastly, I would like to point out another extremely cool fact that Tao breezes through. To explain ultrafilters, Tao uses an analogy with voting theory: an ultrafilter is a way of deciding which side wins when infinitely many people vote.

This, then, suggests a proof of Arrow's Theorem.

Let me explain.

Given a set A of alternatives, and a set P of people, let's define a social welfare function (SWF) as a function that takes as input each person's (linear) rankings of the elements of A and gives as output a global ranking of the elements of A (the output may have ties). There are many conditions a "fair" SWF might satisfy; Arrow singles out three:

1. Pareto (P): if the input consists of identical lists, then this list is the produced output,<\li>
   
2. Independence of Irrelevant Alternatives (IIA): given two separate inputs such that, person-by-person, the relative rankings of two particular alternatives x and y are the same, then the outputs have the same relative rankings of alternatives


3. Monotonicity (M): Say the output has x higher-ranked than y. Then if some people who originally ranked y above x switch their positions, then the output will still have x above y. Except for the possibility of ties, this property is strictly stronger than property P.

By the way, although originally we allowed SWF to produce ties in the output, properties P and IIA are sufficient to guarantee (if A has at least three alternatives) that ties never occur. Indeed, say a certain input yields a tie between x and y. Let X be the set of people who prefer x to y, and Y the set of people who prefer y to x. Taking another alternative z, we can, using IIA, insert it so that all of X prefer x>z>y and all of Y prefer z>y>x; then IIA says x and y are still tied, and P says z>y and hence also x; inserting so that, for X, x>y>z, and for Y, y>z>x, then P says z<y and hence also x; but the relative rankings of z and x are the same in each insertion, so IIA gives us the desired contradiction. Thus, from now on, I will assume that our SWF does not result in ties.

Arrow's theorem says that, if A has size at least three, and if P is finite, then the only SWF satisfying both P and IIA is a single-person dictatorship. Since M is also natural, and since the book* I'm glancing at for my definitions does so too, I will show that SWFs satisfying all three conditions are single-person dictatorships.

Well, an ultrafilter \F can give us a SWF: if you want to know the relative ranking of x versus y, just see whether the set of people who put x above y is \F-large (i.e. in \F) or not. This binary relation is then definitely an ordering, because of ultrafilter properties: for instance, if x > y and y > z in the output, then there are \F-large sets X and Y in P, but then X \cap Y is \F-large, and so since the individual rankings are linear orderings, we must have x > z in the final ranking. Such a SWF obviously satisfies properties IIA and M (and hence P) above.

On the other hand, a SWF \F satisfying IIA and M gives us an ultrafilter. How? Let's pick two particular elements a and b in A. Then for any X \subseteq P, consider feeding \F a collection of rankings so that everyone in X put a > b everyone else puts b > a. If the SWF declares a > b, then declare X to be an a,b-large subset of P. IIA makes this well-defined, and M guarantees that supersets of large sets are large. But this definition does not depend on the choices of a and b: given another c, inserting so that X ranks a>b>c and everyone else ranks b>c>a, then by P, \F yields a>b>c, and so X is a,c-large; similarly, it's c,b-large by a different insertion, and by continuing this type of argument you can get that an a,b-large X is x,y-large for any x,y\in A.

Is the finite intersection of two large sets also large? It suffices to show that the division of a large set into two sets yields a large set and a small set. Say X = Y \cup Z is large, with Y and Z disjoint; then assign Y as b>a>c and Y gets a>c>b and everyone else gets c>b>a. As X is large, certainly \F assigns a>c. Of the three possible (relative) places for \F to put b, either b>c, in which case Y is large, or a>b, in which case Z is large.

Thus \F generates an ultrafilter on A. Writing A! for the set of permutations on A, it's clear how a SWF=ultrafilter \F acts: take our P-sequence of points in A!, and take the (ultra)limit. In the case when A is finite, then the ultraproduct of A! is just A! — i.e. the limit is just another permutation.

In any case, Arrow's theorem is thus equivalent to the statement that there are no nonprinciple ultrafilters on a finite set.


Some discussion is warranted. In justifying that a SWF satisfying the desired criteria is an ultrafilter, I all but proved Arrow's theorem. Given that the statement that "there are no nonprinciple ultrafilters on a finite set" is rather trivial, this is not too surprising. Also, I had to use the fact that A had at least three elements throughout the argument, because Arrow's theorem fails when there are only two options (for instance, Majority Rules works). So it's not immediate to translate Arrow's criteria into the definition of an ultrafilter. Possibly, though, my argument could be cleaned a bit to make it more immediate. Also, it seems that monotonicity is required in guaranteeing that our SWF gives an ultrafilter, but Arrow's theorem holds even if you drop that condition.

On the other hand, this analysis does allow us to understand Arrow-style voting systems with infinitely many people. Or with continuously many people. Or other topologies. And, you know the US is very large — if we could use Axiom of Choice in practice, then perhaps we can pretend that the population of the US is infinite and pick a nonprinciple ultrafilter to be our voting system.


* For a very fine text, suitable for someone who's never seen any mathematics or someone who's seen a lot, on Arrow's Theorem and related topics, I highly recommend Mathematics and Politics: Strategy, Voting, Power, and Proof by Alan D. Taylor (Springer, 1995).

Money

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.

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.

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.

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.

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.