Feeds:
Posts

## Walks on graphs and tensor products

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let $G$ be a compact group and let $\text{Rep}(G)$ denote the category of finite-dimensional unitary representations of $G$. As in the finite case, due to the existence of Haar measure, $\text{Rep}(G)$ is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation $V \in \text{Rep}(G)$. What is the multiplicity of the trivial representation in $V^{\otimes n}$?

Read Full Post »

The problems from IMO 2009 are now available. I haven’t had much time to work on them, though.

There are two classical geometry problems, which I already know I won’t attempt. While I am well aware that classical geometry often requires a great deal of ingenuity, I am also aware of the existence of the field of automatic geometric theorem proving. On this subject I largely agree with Doron Zeilberger: it is more interesting to find an algorithm to prove classes of theorems than to prove individual theorems. The sooner we see areas like classical geometry as “low-level,” the sooner we can work on the really interesting “high-level” stuff. (Plus, I’m not very good at classical geometry.)

Zeilberger’s typical example of a type of theorem with a proof system is the addition or multiplication of very large numbers: it is more interesting to prove $(a + 1)(a - 1) = a^2 - 1$ symbolically than it is to prove individual “theorems” such as $999 \cdot 1001 = 999999$. Zeilberger himself played a significant role in the creation of another proof system, but for the far less trivial case of hypergeometric identities (which includes binomial identities as a special case).

But so I can make my point concretely, I’d like to discuss some examples based on the types of problems most of us had to deal with in middle or high school.

Read Full Post »

## The Catalan numbers, regular languages, and orthogonal polynomials

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let $C(x) = \sum_{n \ge 0} C_n x^n$ be the ordinary generating function for the ordered rooted trees on $n+1$ vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

$\displaystyle C(x) = \frac{1}{1 - xC(x)}$.

The generating function $\frac{1}{1 - x} = 1 + x^2 + ...$ describes the species $\textsc{Seq}$ of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of $C(x)$, but we can instead recursively apply the above to obtain the beautiful continued fraction

$\displaystyle C(x) = \frac{1}{1 - \frac{x}{1 - \frac{x}{1 - ...}}}$.

Today’s discussion will center around this identity and some of its consequences.

Read Full Post »