Extracting the diagonal

Suppose you are given a bivariate generating function

in “closed form,” where I’ll be vague about what that means. Such a generating function may arise, for example, from counting lattice paths in ; then might count the number of paths from to . If the path is only constrained by the fact that its steps must come from some set of steps containing only up or left steps, then we have the simple identity

.

Question: When can we determine the generating function in closed form?

I’d like to discuss an analytic approach to this question that gives concrete answers in at least a few important special cases, including the generating function for the central binomial coefficients, which is our motivating example.

The motivating example

Let’s be clear that extracting the diagonal is hard in general. As an important special case, if where are two generating functions, then extracting the diagonal allows you to compute the Hadamard product of and , and Hadamard products are hard to compute in closed form in general; we get a lot of hypergeometric series this way, such as .

Nevertheless, at least one special case of this problem has a well-known answer. If , then

and

I am aware of at least four proofs of this result, and we’ll be discussing a fifth:

1. Expand the RHS with the binomial theorem. This is perhaps the least informative proof.
2. Establish the corresponding result for the Catalan numbers using their functional equation, then differentiate.
3. Establish the corresponding result for the Catalan numbers, then use a path decomposition argument. (More on this later.)
4. Prove the identity combinatorially. Unfortunately, I don’t know this proof; I’ve been told it’s hard.

Of these, I prefer proof #3. It goes as follows: let be the usual generating function for the Catalan numbers. counts the number of paths using the step set of length which never go above (say) the diagonal , and which end at ; call these Catalan paths. counts the number of paths ending on with no such restriction; call these grand Catalan paths. We decompose a grand path as follows: mark all the points at which such a path intersects the diagonal. Between two consecutive such points the path is of the form or where is an arbitrary Catalan path. It follows that a grand Catalan path uniquely decomposes as a sequence of Catalan paths padded by two other steps in two ways, hence

.

(Note that the exponent of is half the number of steps.) A little algebra shows that the desired result follows. Unfortunately, if is more complicated this argument doesn’t readily generalize. (The proof does, however, generalize to the grand Motzkin paths, which is the case .)

So, barring a much more general combinatorial argument, how should we handle more complicated step sets ?

Fourier and complex analysis

Since the transformation is linear, what we would like to do is to find a nice linear operator such that the terms are sent to zero but the terms are sent to for some other variable . In fact, there is a very nice way to do this. Consider the substitution

.

If converges absolutely in some neighborhood of the origin in , which is true whenever satisfies some kind of growth condition – in particular, it is true if is rational – we can take to be small enough so that this is an honest-to-goodness holomorphic function in . Now observe that if then has exactly the property we want: namely, it integrates to on the circle. But the terms with integrate to . In other words,

.

This is exactly the kind of result we were looking for. Let me state the strongest result I can prove regarding when this integral is computable in “closed form.”

Theorem: If is rational, then is algebraic.

Proof. Let and write where are polynomials (after clearing out by the appropriate power of ). We want to think of as a fixed constant small enough so that is holomorphic as a function of in a disc containing the unit disc. Then one has

after the appropriate change of variables, where is the contour . Note the relationship to Cauchy’s integral formula. Now the residue theorem gives

where the sum is over all poles (as a function of ) in the unit circle and denotes the residue. These poles occur at the roots of , which will be a finite collection of algebraic functions of along with , and the residues are rational functions of the roots, hence are also going to be algebraic functions of . The rule for whether should be included in the summation is essentially that , since then every neighborhood of intersects the unit circle. And the desired result more or less follows.

(It may not be clear that the functions exist, at least in the sense that they can be distinguished from each other. I can think of two arguments that should work in most cases: either use Hensel’s lemma to show that the exist as formal power series in , or work with small enough so that the discriminant of in doesn’t vanish and the zeroes, as a function of , are distinct and vary smoothly, in fact holomorphically, so the functions have an analytic continuation.)

Example 1. Let . Then is rational, in particular

.

Then has poles

.

For sufficiently small the root tends to infinity (in other words it does not have a well-defined power series expansion at ), so we only sum the residue at , giving

.

Example 2. Let . Then is rational, in particular

.

Then has poles

.

For sufficiently small the first two roots tend to infinity, so we only sum the residues at , giving

.

Example 3. Let . Then is rational, in particular

.

Then has poles

.

For sufficiently small the root tends to infinity, so we sum over the residues at and obtain

.

This problem appeared on one of my problem sets recently and I’m curious if a path decomposition argument can be made to work.

Example 4. Let where . Then

is an algebraic function. For this appeared on one of my problem sets last year; see also this thread on ArtofProblemSolving.com where the path decomposition and differentiation argument is discussed for .

Combinatorial objections

In principle, none of the above computations should require analysis. There should be an alternate approach along the following lines: returning to our motivating case, one way to think about the binomial coefficients is that they describe all words on two letters with a fixed number of s and a fixed number of s. Then the central binomial coefficients describe the context-free language consisting of all words with the same number of s as s. (We can take the generating grammar , if I’m not mistaken.) The following is known.

Theorem: Let be a (edit: unambiguous) context-free language, let be the number of words of length , and let . Then is algebraic.

I therefore suspect that the following is true, which would imply the result proven above.

Conjecture: Let be a step set such that a map from to uniquely decodable words preserving length, extended to paths consisting of steps in , results in regular languages (read: is rational). Then the sublanguage of words corresponding to paths ending on the diagonal is context-free.

I hope it’s clear what I mean by this. Does anyone have a proof? (Probably it’s obvious.)

Edit, 10/15/09: Indeed, it is. See the proof at MathOverflow.net.