Can you find linear recurrence relation for dimensions of invariant tensors? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:08:58Z http://mathoverflow.net/feeds/question/17610 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17610/can-you-find-linear-recurrence-relation-for-dimensions-of-invariant-tensors Can you find linear recurrence relation for dimensions of invariant tensors? Bruce Westbury 2010-03-09T14:50:36Z 2010-03-10T09:51:50Z <p>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$.</p> <p>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).</p> <p>For example, for the seven dimensional representation of $G_2$ this sequence starts:<br> 1, 0, 1, 1, 4, 10, 35, 120, 455, 1792, 7413, 31780, 140833, 641928, 3000361, 14338702, 69902535, 346939792, 1750071307, 8958993507, 46484716684, 244187539270, 1297395375129, 6965930587924<br> for more background see <a href="http://www.research.att.com/~njas/sequences/A059710" rel="nofollow">http://www.research.att.com/~njas/sequences/A059710</a> </p> <p>This satisfies the recurrence<br> $(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}$</p> <p><strong>Question</strong> How does one find these recurrence relations?</p> <p>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$.</p> <p><strong>Question</strong> How does one calculate these symmetric functions?</p> <p>I know these can be calculated using plethysms individually. I am hoping for something along the lines of the first question.</p> <p><strong>Further remarks</strong> 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.</p> <p>The $sl(2)$ example can easily be extended. For the $n$-dimensional representation $a_k$ is the coefficient of $ut^k$ in<br> $$\frac{u-u^{-1}}{1-t\left(\frac{u^n-u^{-n}}{u-u^{-1}}\right)}$$<br> For the case $n=3$ see <a href="http://www.research.att.com/~njas/sequences/A005043" rel="nofollow">http://www.research.att.com/~njas/sequences/A005043</a> and <a href="http://www.research.att.com/~njas/sequences/A099323" rel="nofollow">http://www.research.att.com/~njas/sequences/A099323</a><br> I am not aware of any references for $n\ge 4$. I don't know if these are algebraic.</p> <p>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<br> 1 0 1 1 5 16 79 421 2674 19244 156612 1423028 14320350<br> (found using LiE)</p> http://mathoverflow.net/questions/17610/can-you-find-linear-recurrence-relation-for-dimensions-of-invariant-tensors/17624#17624 Answer by Martin Rubey for Can you find linear recurrence relation for dimensions of invariant tensors? Martin Rubey 2010-03-09T16:52:25Z 2010-03-09T16:52:25Z <p>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):</p> <pre> (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)) </pre> <p>(shameless plug: using this program, you can just as well find algebraic differential equations, algebraic recurrence relations and certain functional equations)</p> <p>Martin</p> http://mathoverflow.net/questions/17610/can-you-find-linear-recurrence-relation-for-dimensions-of-invariant-tensors/17628#17628 Answer by David Speyer for Can you find linear recurrence relation for dimensions of invariant tensors? David Speyer 2010-03-09T17:33:52Z 2010-03-09T19:21:49Z <p>Finding the recurrence (and proving it is correct) can be done by the standard techniques for extracting the diagonal of a rational power series. </p> <p>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 <code>$$\sum_{n=0}^{\infty} t^n \chi \left( V^{\otimes n} \right) = \frac{1}{1- \sum_{i=1}^N t e^{\beta_i}}$$</code> and <code>$$\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).$$</code></p> <p>For example, if $\mathfrak{g}=\mathfrak{sl}_2$ and $V$ is the two dimensional irrep, the right hand side is <code>$$\mbox{Coefficient of}\ u \ \mbox{in} \left( \frac{(u-u^{-1})}{1-tu^{-1} - tu} \right)$$</code> which can be seen without too much trouble to be the generating function for Catalan numbers.</p> <p>The diagonal of a rational generating function is $D$-finite by a <a href="http://www.ams.org/mathscinet-getitem?mr=929767" rel="nofollow">result of Lipshitz</a>. The particular recurrence can be found by <a href="http://www.ams.org/mathscinet-getitem?mr=647562" rel="nofollow">Sister Celine's method</a> (see theorems 10 and 11). I found these references in Stanley, <em>Enumerative Combinatorics Vol. II</em>, solution to exercise 6.61. Stanley warns that there is a gap in Zeilberger's argument, but hopefully his algorithm is right.</p>