A Beautiful Analytic Combination

/ mathcination

generatingRecently, I was looking for good motivating examples for complex analysis in several variables. There was already a short discussion of this question at MathOverflow. Some further searching led me to the book Analytic Combinatorics in Several Variables by Robin Pemantle and Mark C. Wilson. What is this all about and why did I fall in love immediately?

Generating functions are one of the most magical objects in mathematics. Let us look at a first example in only one variable: the Fibonacci sequence. (This example and much more can be found in the book generatingfunctionology by Herbert Wilf.)

The Fibonacci sequence is defined recursively as:

F_0=0, F_1=1, F_{n+1} = F_n + F_{n-1} for n\geq 1.

Can we find a closed form solution for F_n?

One way to do so is by setting up the generating function F(x):=\sum_{n\geq 0} F_nx^n. This is a formal sum, the mathematical way of hanging the Fibonacci numbers on a long clothes line and labelling the n-th peg by x^n:

fibonaccipegs

In order to find F_n, we need to find the coefficient of x^n in F. Nothing won? Well, let’s see how far we can get by manipulating F.

Our original recursion tells us that \sum_{n\geq 1}F_{n+1}x^n = \sum_{n\geq 1}F_nx^n + \sum_{n\geq 1}F_{n-1}x^n. (We get this by multiplying each side by x^n and then summing over n.)

We can express this in terms of F(x) as follows (write out the sums to see this):

\frac{F(x)-x}{x} = F(x)+xF(x)

We can solve this for F to get F(x)=\frac{x}{1-x-x^2}.

With the help of partial fraction decomposition, using the factorisation 1-x-x^2=(1-x\frac{1+\sqrt{5}}{2})(1-x\frac{1-\sqrt{5}}{2}) of the denominator, and using the abbreviation r_{\pm}:=\frac{1\pm\sqrt{5}}{2}, we find that

F(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}(\frac{1}{1-xr_{+}}+\frac{1}{1-xr_{-}}).

Developing the right hand side into geometric series, we get:

F(x)=\frac{1}{\sqrt{5}}\left(\sum_{j\geq 0}r_{+}^jx^j-\sum_{j\geq 0}r_{-}^jx^j\right)

From this we can read off the n-th Fibonacci number F_n as the coefficient of x^n in the series:

F_n = \frac{1}{\sqrt{5}}(r_{+}^n-r_{-}^n)

Generating functions will not always give us closed form solutions like this but they can often give us very good asymptotics for combinatorial problems. Let’s go one step further and look at how a generating function in several variables can give us such information.

The combinatorial problem we will consider is that of computing asymptotics for the so-called Delannoy numbers. The Delannoy number d_{r,s} gives the number of paths in the grid \mathbb{Z}^2 starting at position (0, 0), ending at position (r, s), and taking steps of the form (1,0), (0, 1), or (1,1).

If we set up the generating function

F(x,y):=\sum_{r,s\geq 0}d_{r,s}x^ry^s

for this, we can use a similar trick as for the Fibonacci numbers to find a rational function form for this. For all pairs (r,s)\neq(0,0), we have the recurrence

d_{r,s} = d_{r-1,s}+d_{r,s-1}+d_{r-1,s-1}

where each term comes from one of the three possible steps in a path. Summing this over all r, s\geq 1, we get

\sum_{r,s\geq 1}d_{r,s}x^ry^s = \sum_{r,s\geq 1}d_{r-1,s}x^ry^s+\sum_{r,s\geq 1}d_{r,s-1}x^ry^s+\sum_{r,s\geq 1}d_{r-1,s-1}x^ry^s.

Now putting in F again and cleaning up any terms of the form d_{r,0}x^r and d_{0,s}x^s gives us all we need to find the expression we are looking for:

F(x,y)-d_{0,0}=xF(x,y)+yF(x,y)+xyF(x,y).

Hence, using the fact that d_{0,0}=1, this yields

F(x,y) = \frac{1}{1-x-y-xy}.

As mentioned above, we usually cannot expect to find a closed-form solution. However, there is a very useful tool from complex analysis for finding asymptotics: Cauchy’s integral formula. If our generating function is given by a function F=\sum_{\mathbf{r}\in\mathbb{N}^d}a_{\mathbf{r}}\mathbf{z}^\mathbf{r} as above, we can recover the coefficients a_{\mathbf{r}} by contour integration:

a_{\mathbf{r}} = \frac{1}{(2\pi i)^d}\int_T\mathbf{z}^{-\mathbf{r}-\mathbf{1}}F(\mathbf{z})d\mathbf{z}

(Here, \mathbf{r}, \mathbf{z}, and \mathbf{1} are vectors of dimension d corresponding to the number of variables in our generating function, T is a product of sufficiently small circles around the origin of each coordinate axis.)

In their paper Twenty combinatorial examples of asymptotics derived from multivariate generating functions, Pemantle and Wilson give a general recipe on how to evaluate this integral in the multivariate case if F is rational of the form F=G/H for polynomials G and H to find asymptotics for |\mathbf{r}|\rightarrow \infty where the direction \hat{r} := \mathbf{r}/|\mathbf{r}| is suitably controlled. A central role is played by the geometry imposed by the zeros of H. This is how the recipe is summarised (very closely following the text by Pemantle and Wilson):

  1. To find asymptotics in the direction \hat{r}, look at the geometry of the variety \mathcal{V} := \{\mathbf{z}: H(\mathbf{z})=0\} near a certain set of critical points.
  2. The set of critical points can be reduced to a subset of so-called contributing critical points which can be determined by a combination of algebraic and geometric criteria.
  3. The critical points come in three flavours: smooth, multiple, and bad.
  4. For each smooth or critical point there is an expansion for a_{\mathbf{r}} in terms of the derivatives of G and H.
  5. No general such expansion is known for bad points.

This should be vague enough to make you look up the details in the paper or the book.

Let me close by stating the result for the Delannoy numbers:

d_{rs} \sim (\frac{\sqrt{r^2+s^2}-s}{r})^{-r}(\frac{\sqrt{r^2+s^2}-r}{s})^{-s}\sqrt{\frac{1}{2\pi}}\sqrt{\frac{rs}{\sqrt{r^2+s^2}(r+s-\sqrt{r^2+s^2})^2}}

(I particularly like the fact that a Gröbner basis is used for handling \mathcal{V} in the derivation of this result.)

One thought on “A Beautiful Analytic Combination”

  1. Pingback: The Power of Involutions | Glimpses of a fascinating world

Leave a comment