Feeds:
Posts

## Archive for October, 2009

Note: as usual, I will be playing free and loose with category theory in this post. Apologies to those who know better.

One way to define a subgroup $H$ of a group $G$ is as the image of a homomorphism into $G$. Given the inclusion map $H \to G$, the functor $\text{Hom}(G, \text{End}(V))$ in the category of groups acts contravariantly to give a map $\text{Res}_H^G : \text{Rep}(G) \to \text{Rep}(H)$ called restriction. More concretely, the restricted representation $\rho|_H$ of a representation $\rho$ is defined simply by $\rho|_H(h) = \rho(h)$. Hence there is a functorial way to pass from a representation of a group $G$ to one of a subgroup $H$.

It is not obvious, however, whether there is a functorial way to pass from a representation of $H$ back to one of $G$. There is such a construction, which goes by the name of induction, and we will need it later. Today we’ll discuss the general category-theoretic context in which induction is understood, where it is called an adjoint functor. For more about adjoints, see (in no particular order) posts at Concrete Nonsense, the Unapologetic Mathematician, and Topological Musings.

## Math Overflow

The news has already been spreading around the blathosphere, but recently a website called Math Overflow modeled on Stack Overflow has opened up where anyone can post their mathematical questions. I would explain more, but the website is mostly self-explanatory.

MO couldn’t have come into existence at a better time for me. I’ve been carrying around a lot of questions I know someone should have an answer to, but I’ve never found a good way to ask them. For example, the conjecture I made at the end of my last post turned out to be a straightforward exercise in automaton theory. More generally I’m excited about the possibilities here in terms of improving the efficiency of mathematical research.

In other math-and-the-internet news, I have a Google Wave account, but (to my knowledge) nobody I do math with does! Hopefully this will be resolved eventually.

## Extracting the diagonal

Needless to say, I have been very, very busy. But enough about me.

Suppose you are given a bivariate generating function

$\displaystyle F(x, y) = \sum_{m, n \ge 0} f(m, n) x^m y^n$

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 $\mathbb{Z}_{\ge 0}^2$; then $f(m, n)$ might count the number of paths from $(0, 0)$ to $(m, n)$. If the path is only constrained by the fact that its steps must come from some set $S \subset \mathbb{Z}_{\ge 0}^2$ of steps containing only up or left steps, then we have the simple identity

$\displaystyle F_S(x, y) = \frac{1}{1 - \sum_{(a, b) \in S} x^a y^b}$.

Question: When can we determine the generating function $\displaystyle D_F(x) = \sum_{n \ge 0} f(n, n) x^n$ 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.