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

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.oeis.org/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.oeis.org/A005043 and http://www.oeis.org/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)

-
Do you have a reference for your claim that a_n is always D-finite? – Qiaochu Yuan Mar 9 '10 at 15:49
The only proof I know is the proof given by David Speyer below. I have not seen this in print. – Bruce Westbury Mar 9 '10 at 20:15
The diagonal of a two variable rational generating function is algebraic. (See Stanley, Vol II, Chapter 6.) So these $\mathfrak{sl}_2$ examples are algebraic. If what you care about is the recurrence, though, I don't know that this fact will be helpful. – David Speyer Mar 10 '10 at 13:19
Thanks for pointing that out. I am interested in the recurrence. I mentioned algebraic because it came up as a question to your answer. – Bruce Westbury Mar 10 '10 at 14:59
Trying to improve a suggested edit of @dimension10 I corrected the three hyperlinks. – Giuseppe Tortorella Nov 4 '13 at 8:43

## 2 Answers

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.

-
I just noticed that the original question was about the tensor algebra of V, not the symmetric algebra. I have made edits accordingly. – David Speyer Mar 9 '10 at 19:22
This is a method for solving the first problem. I need to look into Sister Celine's method and I would be interested to know which computer algebra systems implement this. Thanks. I am not sure this is the final answer as my recollection is that I once saw a more efficient method but I have no way of recovering the reference. – Bruce Westbury Mar 9 '10 at 20:42
David, how many variables is the rational function you're taking the diagonal of? For (semi)simple Lie algebras is the resulting diagonal always algebraic? – Qiaochu Yuan Mar 10 '10 at 1:14
@Qiaochu The number of variables is the rank. The diagonal is algebraic in the simple example giving the Catalan numbers. I don't see any reason to expect this to hold in general. In particular, I don't see any reason to think the $G_2$ example I give is algebraic. – Bruce Westbury Mar 10 '10 at 2:43
I don't think the diagonal will be algebraic. I don't even think it is algebraic for $\mathfrak{sl}_3$ acting on its defining representation. I get that the generating function there is $$2 \sum_n t^{3n} \frac{(3n)!}{n! (n+1)! (n+2)!}$$. If that were algebraic, so would $\sum t^n \frac{(3n)!}{n! n! n!}$ be, and I think I recall that the latter is a standard example of a transcendental $D$-finite function. – David Speyer Mar 10 '10 at 12:30

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

-
This is the method that was used by Mihailovs to find this recurrence relation. It's not a proof, it's a plausible guess. To make it a proof you would have to prove bounds on the degree of the recurrence relation and bounds on the degrees of the polynomial coefficients. The second problem is that you have to calculate the first "few terms". This could easily be a hundred terms. I don't know a better way to do this than to use the rational function in David Speyer's answer. – Bruce Westbury Mar 9 '10 at 20:33
Did you mean to include this link fricas.sourceforge.net in your plug? – Bruce Westbury Mar 9 '10 at 20:44
Bruce: sorry, yes and thank you for providing the link! Concerning your other comment: of course you are right. In fact, I thought about adding these caveats, but I was too lazy then. Sorry again. – Martin Rubey Mar 9 '10 at 21:31