MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.

As the SBS post describes, the Catalan numbers can be obtained as the moments of the trace of a random element of $SU(2)$ with respect to the Haar measure. This is equivalent to the integral identity $$\int_{0}^{1} (2 \cos \pi x)^{2k} (2 \sin^2 \pi x) \, dx = C_k.$$

I can prove this identity "combinatorially" as follows: let $A_n$ denote the Dynkin diagram with $n$ vertices and $n-1$ undirected edges connecting those vertices in sequence. The adjacency matrix of $A_n$ has eigenvectors $\mathbf{v}\_i$ with entries $\mathbf{v}\_{i,j} = \sin \frac{\pi ij}{n+1}$ with corresponding eigenvalues $2 \cos \frac{\pi i}{n+1}$. If $k \le n-1$, then a straightforward computation shows that the number of closed walks from one end of $A_n$ to itself of length $2k$ is $$\frac{1}{n+1} \sum_{i=1}^{n} \left( 2 \cos \frac{\pi i}{n+1} \right)^{2k} 2 \sin^2 \frac{\pi}{n+1} = C_k$$

by the combinatorial definition of the Catalan numbers. Taking the limit as $n \to \infty$ gives the integral identity; in other words, the integral identity is in some sense equivalent to the combinatorial definition of the Catalan numbers in terms of closed walks on the "infinite path graph" $A_{\infty}$. (Is this the correct notation? I mean the infinite path graph with one end.)

Now, closed walks of length $2k$ from one end of $A_n$ to itself can be put in bijection with ordered rooted trees of depth at most $n$ and $k$ non-root vertices. (Recall that the Catalan numbers also count ordered rooted trees of arbitrary depth.) The generating function $P_n$ of ordered rooted trees of depth at most $n$ satisfies the recursion $$P_1(x) = 1, P_n(x) = \frac{1}{1 - x P_{n-1}(x)}.$$

This is because an ordered rooted tree of depth $n$ is the same thing as a sequence of ordered rooted trees of depth $n-1$ together with a new root. (Recall that the generating function of the Catalan numbers satisfies $C(x) = \frac{1}{1 - x C(x)}$. In other words, $C(x)$ has a continued fraction representation, and $P_n$ is its sequence of convergents.) On the other hand, since $P_n(x)$ counts walks on the graph $A_n$, it is possible to write down the generating function $P_n$ explicitly in terms of the characteristic polynomials of the corresponding adjacency matrices, and these polynomials have roots the eigenvalues $2 \cos \frac{\pi i}{n+1}$. This implies that they must be the Chebyshev polynomials of the second kind, i.e. the ones satisfying $$q_n(2 \cos x) = \frac{\sin (n+1) x}{\sin x}.$$

But the Chebyshev polynomials of the second kind are none other than the characters of the irreducible finite-dimensional representations of $SU(2)$! In particular, they're orthogonal with respect to the Haar measure.

The overarching question I have is: how does this sequence of computations generalize, and what conceptual framework ties it together? But I should probably ask more specific sub-questions.

Question 1: I remember hearing that the relationship between the Catalan numbers and the Chebyshev polynomials generalizes to some relation between moments, continued fractions, and orthogonal polynomials with respect to some measure. Where can I find a good reference for this?

Question 2: I believe that adding another edge and considering the family of cycle graphs gives the sequence ${2k \choose k}$ and the Chebyshev polynomials of the first kind, both of which are related to $SO(2)$. According to the SBS post, this is a "type B" phenomenon, whereas the Catalan numbers are "type A." What exactly does this mean? What would happen if I repeated the above computations for other Dynkin diagrams? Do I get continued fractions for the other infinite families?

Question 3: Related to the above, in what sense is it natural to relate walks on the Dynkin diagram $A_n$ to representations of $SU(2)$? This seems to have something to do with question #16026. How do the eigenvectors of the adjacency matrices fit into the picture? I want to think of the eigenvectors as "discrete harmonics"; does this point of view make sense? Does it generalize?

As you can see, I'm very confused, so I would greatly appreciate any clarification.

share|cite|improve this question
up vote 19 down vote accepted

The Catalan numbers enumerate (amongst everything else!) the bases of the Temperley-Lieb algebras. These algebras $TL_n(q)$ are exactly $\operatorname{End}_{U_q \mathfrak{su}_2}(V^{\otimes n})$ where $V$ is the standard representation.

If $q$ is a $2k+4$-th root of unity, the semisimplified representation theory of $U_q \mathfrak{su}_2$ becomes '$A_{k+1}$': that is, it has $k+1$ simples, and the principal graph for tensor product with the standart is $A_{k+1}$. The algebra $\operatorname{End}_{U_q \mathfrak{su}_2}(V^{\otimes n})$ is now smaller (some of the summands of the tensor power cancel out when you use the quantum Racah rule), and in fact it is enumerated by loops on $A_{k+1}$ based at the first vertex. You can pick out a subset of the entire Temperley-Lieb that gives a basis: just use your description of paths as trees, and take the dual graph.

Since we're looking at a unitary tensor category, the dimension of the standard object is exactly the Frobenius-Perron eigenvalue (largest real eigenvalue of the adjacency matrix) of the principal graph.

share|cite|improve this answer
Wow! Can you specify what you mean by "the principal graph for tensor product"? Is there a readable reference on quantum groups where this kind of stuff is spelled out in detail? – Qiaochu Yuan Mar 5 '10 at 23:18
Unfortunately the "principal graph" terminology is something that only subfactor people tend to use. In a semisimple tensor category C with your favourite simple object X, the principal graph has vertices the simple objects, and an edge from A to B each time B appears inside A (x) X. When X is self-dual, you can forget the orientations on edges -- there's a bijection (Frobenius reciprocity!) between edges from A to B and edges from B to A. – Scott Morrison Mar 6 '10 at 3:18
So counting walks on the principal graph is the same thing as finding the multiplicity of simple objects in tensor powers of X. Awesome! – Qiaochu Yuan Mar 6 '10 at 17:14

Re Question 1: For the connection between walks and continued fractions (which is closely related to orthogonal polynomials, but not, as far as I know, to root systems) see Philippe Flajolet, Combinatorial Aspects of Continued Fractions, Discrete Mathematics 32 (1980), pp. 125–161. Flajolet's paper has been very influential and many people have done further work in this direction.

share|cite|improve this answer

For Question 1, you might want to consult Viennot's monograph Une theorie combinatoire des polynomes orthogonaux.

share|cite|improve this answer
There's some strange character in the link. Is this the same as ? – Qiaochu Yuan Mar 8 '10 at 16:15
I modified the link, so you can access the book now. I guess the essentials are in the article, but I didn't check. – Martin Rubey Mar 8 '10 at 19:28
A late comment: Viennot's theory is also described in Martin Aigner's book "A course in enumeration" (Chapter 7).… – Hans Lundmark Oct 2 '10 at 13:56

Caveat lector: This does not address your questions directly, but I think that it's interesting and somewhat relevant.

The $n$th Catalan number counts the number of walks of length $2n$, beginning and ending at the origin, in the positive cone of the root lattice of type $A_1$. This counts the dimension of the invariant subspace of endomorphisms of $2n$-fold tensor power of the standard irrep $V$, relating back to Scott's answer.

This phenomenon generalizes to other root systems.

share|cite|improve this answer
This should be the same as the integral of the 2nth power of the trace, right? Anyway, I'd be very interested in seeing a precise statement about what can say for more general root systems. – Qiaochu Yuan Mar 5 '10 at 23:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.