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.