Can you find linear recurrence relation for dimensions of invariant tensors? - MathOverflow

Can you find linear recurrence relation for dimensions of invariant tensors?

2010-03-09T14:50:36Z

Let $V$ be a finite dimensional highest weight representation of a (semi)-simple Lie algebra. For each $n\ge 0$ take $a_n$ to be the dimension of the space of invariant tensors in $\otimes^n V$.

In certain cases there is a formula for $a_n$. For example, for $V$ the two dimensional representation of $sl(2)$ we get $a_n=0$ if $n$ is odd and for $n$ even we get the ubiquitous Catalan numbers. In general I don't expect a formula but the sequence does satisfy a linear recurrence relation with polynomial coefficients (known as D-finite).

For example, for the seven dimensional representation of $G_2$ this sequence starts:
1, 0, 1, 1, 4, 10, 35, 120, 455, 1792, 7413, 31780, 140833, 641928, 3000361, 14338702, 69902535, 346939792, 1750071307, 8958993507, 46484716684, 244187539270, 1297395375129, 6965930587924
for more background see http://www.research.att.com/~njas/sequences/A059710

This satisfies the recurrence
$(n+5)(n+6)a_n=2(n-1)(2n+5)a_{n-1}+(n-1)(19n+18)a_{n-2}+ 14(n-1)(n-2)a_{n-3}$

Question How does one find these recurrence relations?

Then I also have a more challenging follow-up question. The space of invariant tensors in $\otimes^n V$ also has an action of the symmetric group $S_n$ and so a Frobenius character which is a symmetric function of degree $n$.

Question How does one calculate these symmetric functions?

I know these can be calculated using plethysms individually. I am hoping for something along the lines of the first question.

Further remarks David's answer solves the problem theoretically but I want to make some remarks about the practicalities. This is in case anyone wants to experiment and also because I believe there is a more efficient method.

The $sl(2)$ example can easily be extended. For the $n$-dimensional representation $a_k$ is the coefficient of $ut^k$ in
$$\frac{u-u^{-1}}{1-t\left(\frac{u^n-u^{-n}}{u-u^{-1}}\right)}$$
For the case $n=3$ see http://www.research.att.com/~njas/sequences/A005043 and http://www.research.att.com/~njas/sequences/A099323
I am not aware of any references for $n\ge 4$. I don't know if these are algebraic.

The limitation of this method is that there is a sum over the Weyl group. This means it is impractical to implement this method for $E_8$. For the adjoint representation of $E_8$ the start of the sequence is
1 0 1 1 5 16 79 421 2674 19244 156612 1423028 14320350
(found using LiE)

Answer by Martin Rubey for Can you find linear recurrence relation for dimensions of invariant tensors?

2010-03-09T16:52:25Z

The first question has a simple answer: somehow calculate the first few terms of your sequence, and feed your favorite guessing machine with them. I advertise the one built into FriCAS (because its authors are Waldek Hebisch and myself):

(1) -> guessPRec [1, 0, 1, 1, 4, 10, 35, 120, 455, 1792, 7413, 31780, 140833, 641928, 3000361, 14338702, 69902535, 346939792, 1750071307, 8958993507, 46484716684, 244187539270, 1\
297395375129, 6965930587924]

   (1)
   [
     [
       f(n):
               2                          2
           (- n  - 17n - 72)f(n + 3) + (4n  + 30n + 44)f(n + 2)
         +
               2                             2
           (19n  + 113n + 150)f(n + 1) + (14n  + 42n + 28)f(n)
           =
           0
       ,
      f(0)= 1, f(1)= 0, f(2)= 1]
     ]
                                              Type: List(Expression(Integer))

(shameless plug: using this program, you can just as well find algebraic differential equations, algebraic recurrence relations and certain functional equations)

Martin

Answer by David Speyer for Can you find linear recurrence relation for dimensions of invariant tensors?

2010-03-09T17:33:52Z

Finding the recurrence (and proving it is correct) can be done by the standard techniques for extracting the diagonal of a rational power series.

Let $\beta_1$, $\beta_2$, ..., $\beta_N$ be the weights of $V$. Let $\rho$ be half the sum of the positive roots and $\Delta = \sum (-1)^{\ell(w)} e^{w(\rho)}$ be the Weyl denominator. Then $$\sum_{n=0}^{\infty} t^n \chi \left( V^{\otimes n} \right) = \frac{1}{1- \sum_{i=1}^N t e^{\beta_i}}$$ and $$\sum_{n=0}^{\infty} t^n \dim \left( V^{\otimes n} \right)^{\mathfrak{g}} = \mbox{Coefficient of}\ e^{\rho}\ \mbox{in} \ \left( \Delta \frac{1}{1- \sum_{i=1}^N t e^{\beta_i}} \right).$$

For example, if $\mathfrak{g}=\mathfrak{sl}_2$ and $V$ is the two dimensional irrep, the right hand side is $$ \mbox{Coefficient of}\ u \ \mbox{in} \left( \frac{(u-u^{-1})}{1-tu^{-1} - tu} \right)$$ which can be seen without too much trouble to be the generating function for Catalan numbers.

The diagonal of a rational generating function is $D$-finite by a result of Lipshitz. The particular recurrence can be found by Sister Celine's method (see theorems 10 and 11). I found these references in Stanley, Enumerative Combinatorics Vol. II, solution to exercise 6.61. Stanley warns that there is a gap in Zeilberger's argument, but hopefully his algorithm is right.