Update, and the combinatorics of quintic equations

A brief update. I’ve been at Cambridge for the last week or so now, and lectures have finally started. I am, tentatively, taking the following Part II classes:

• Riemann Surfaces
• Topics in Analysis Probability and Measure
• Graph Theory
• Linear Analysis (Functional Analysis)
• Logic and Set Theory

I will also attempt to sit in on Part III Algebraic Number Theory, and I will also be self-studying Part II Number Theory and Galois Theory for the Tripos.

As far as this blog goes, my current plan is to blog about interesting topics which come up in my lectures and self-study, partly as a study tool and partly because there are a few big theorems I’d like to get around to understanding this year and some of the material in my lectures will be useful for those theorems.

Today I’d like to blog about something completely different. Here is a fun trick the first half of which I learned somewhere on MO. Recall that the Abel-Ruffini theorem states that the roots of a general quintic polynomial cannot in general be written down in terms of radicals. However, it is known that it is possible to solve general quintics if in addition to radicals one allows Bring radicals. To state this result in a form which will be particularly convenient for the following post, this is equivalent to being able to solve a quintic of the form

for in terms of . It just so happens that a particular branch of the above function has a particularly nice Taylor series; in fact, the branch analytic in a neighborhood of the origin is given by

.

This should remind you of the well-known fact that the generating function for the Catalan numbers satisfies . In fact, there is a really nice combinatorial proof of the following general fact: the generating function satisfies

.

Proof

The above result follows directly from (the combinatorial form of) Lagrange inversion, but unless you’ve seen the combinatorial proof of Lagrange inversion (as detailed in, for example, Stanley), you might not know that Lagrange inversion can be thought of in terms of counting trees, and here the tree-counting can be made quite explicit.

Here’s how it works. The relation says that, if is interpreted as a combinatorial species, then a -structure is either the empty set or a set of size (the ) together with different -structures (arranged in linear order). This is precisely the recursive definition of a certain type of -ary tree; namely, a -ary tree in which each node has “children” slots which are labeled in left-to-right order, and where the tree remembers which slots are empty and which are non-empty. Since this is a somewhat lengthy definition and I do not know a concise way to put it, I will just say -ary tree in the rest of this post.

So is the number of -ary trees with nodes. There is an elegant way to count such trees using a depth-first search: starting from the root node, inspect each of the “children” slots in left to right order. Every time you inspect a new slot (aside from the first slot), write down a . If a slot is not empty, start inspecting the children of that node. Every time you need to backtrack up one level, write down a . At the end of the search, write down a last .

The above algorithm associates to every -ary tree with nodes a sequence of numbers, of which are and of which are . Moreover, it’s not hard to see that at any point, the partial sums of the sequence must be non-negative. In the other direction, given such a sequence we can construct a -ary tree step-by-step. (Exercise for the reader!) One can think of such sequences as generalized ballot sequences.

So the number of -ary trees with nodes is the same as the number of sequences satisfying the above conditions. There is an elegant way to count such sequences using the following lemma, which has a name that I always forget (even though I’ve asked Stanley more than once what it’s called).

Lemma: Let be a sequence of integers such that . Then there is a unique index such that the partial sums of the sequence (where the indices are taken ) are positive.

Proof. Extend the to a periodic function on with period and consider a plot of the sequence , which satisfies . Then the lemma is equivalent to the statement that there is a unique value of such that a horizontal line of length extending to the right from does not intersect the graph of . But now it’s not hard to see (draw a picture!) that it suffices to look at the rightmost place at which attains its minimum in a given “period.”

We apply the lemma as follows. There are ways to write down a sequence of length with different s and different s, and this sequence sums to zero. Given such a sequence, prepend an additional . The resulting sequence of length satisfies the conditions of the lemma, so there is a unique cyclic permutation of such a sequence such that all the partial sums are positive. Such a sequence must start with , so given such a cyclic permutation there are possible sequences one could have started with.

Now delete the first . The result is a sequence of length which satisfies the -ary tree conditions above. It follows that the number of such sequences is , as desired.

Advertisements