Seminar Sophus Lie 2 (1992) 63–66

The rule of Littlewood/Richardson and its treatment by a computer

Hartmut Schlosser

1. Introduction

The irreducible summands of the sum decomposition of the tensor product of two irreducible representations of a classical group or algebra are computable by aid of the rule of Littlewood/Richardson (shortly LR-rule). The LR-rule is effective also for other decomposition problems. It originated from the task to decompose the product of two Schur functions into a sum of Schur functions. The idea connecting all these problems is the characterization of the objects by a partition l = (l_{1}, l_{2}, …, l_{p}), l_{1} ≥ l_{2} ≥ ... ≥ l_{p} ≥ 0, l_{i} ∈ ℕ or by a Young frame with p rows and l_{i} boxes in the i-th row (i = 1, …, n). We get the summands of the product of two such objects adding the boxes of the second frame in a various way to the first frame. With the LR-rule we have to expect certain restrictions. It is possible that two frames with only a few rows give a great number of summands. So the use of a computer for the calculation appears to be indicated; for this purpose the LR-rule will be translated in a formula.

2. The rule of Littlewood/Richardson

We consider two Young frames l = (l_{1}, l_{2}, ..., l_{p}) and m = (m_{1}, m_{2}, ..., m_{q}). In the j -th row of m we write in all the boxes the number j and denote these boxes by j -boxes. Now we add the boxes of m to l beginning with the 1-boxes, next the 2-boxes etc. In the built frame the following conditions must be satisfied:

I. The frame gotten from l after the addition of the 1-boxes (2-boxes,...) must be admissible, i.e., the length of successive rows are non-increasing.

II. The frame does not contain boxes with equal labels appearing in a column.

III. The number of (j + 1)-boxes is never greater than the number of j - boxes if we count up the boxes in the rows from the right to the left and from top to bottom (j = 1, ..., q − 1).

We sum symbolically all Young frames built in this way and denote this sum as the result of the multiplication of l and m.

Example: The two factors are  and  ((1,1) and (2,1) resp.).

We fill the second frame with numbers: ^{21 1} .

Now we add the 1-boxes to the first frame:

(1)  ^{1 1} (2)  1 1 (3) 1 1 (4) 1 1 (5) 1 1

By I. is forbidden: (4); by II. are forbidden: (2),(5). Now we add the 2-box to (1) and (3):

(1a)  ^{1 1 2} (1b)  ^{1 1 2} (1c) ^{1 1 2} (3a) ^{1 1 2} (3b) ^{1 1 2}

(3c) ^{1 1 2} (3d) 1 1 2

By I. are forbidden: (3c); by III. are forbidden: (1a), (3a). The result is the following:(1b),(1c),(3b) and (3d) or (3,2),(3,1,1),(2,2,1) and (2,1,1,1).

3. A closed formula for the LR-rule

A general formula for the LR-rule is given in [S91]. There we can find also formulas for some Clebsch-Gordan-series of classical Lie algebras and superalgebras. Here we will prove only a special case, but the same idea leads to the general proof. We look to l = (l_{1}, …, l_{p}) und m =(m_{1}, m_{2}) and complete l by l_{p+1} = l_{p+2} = 0. We consider an admissible distribution of the 1-boxes and the 2-boxes of m at l and denote the number of i-boxes in theh-th row by k_{hi}. If we put first k_{p+1,1} 1-boxes to the (p + 1)-th row of l, then k_{p1} 1-boxes to the p-th row etc., we have the following restrictions by I. and II.:

k_{h1} ≤ min(l_{h−1} − l_{h}, m_{1} − ∑_{j=h+1}^{p+1} k_{j1}) = Min(l, m; h, 1)

k_{11} = m_{1} − ∑_{j=2}^{p+1} k_{j1}

for h = 2, ...p + 1. For the parameters k_{h2}we get from I. and II.:

k_{h2} ≤ min((l_{h−1} + k_{h−1,1}) − (l_{h} + k_{h1}), m_{2} − ∑_{j=h+1}^{p+2} k_{j2}) = Min(l, m; h, 2)

k_{11} = m_{1} − ∑_{j=2}^{p+1} k_{j1}

for h = 2, ...p + 2.

Now we have to consider also condition III. :

∑_{j=2}^{h} k_{j2} ≤ ∑_{j=1}^{h−1} k_{j1}

or

∑_{j=3}^{h} k_{j2} + m_{2} − ∑_{j=3}^{p+2} k_{j2} ≤ ∑_{j=2}^{h−1} k_{j1} + m_{1} − ∑_{j=2}^{p+1} k_{j1}

or

m_{2} − m_{1} − ∑_{j=h+2}^{p+2} k_{j2} + ∑_{j=h}^{p+1} k_{j1} ≤ k_{h+1,2}

for h = 2, ..., p + 1.

So we get

Max(m; h, 2) = max(0, m_{2} − m_{1} + ∑_{j=h−1}^{p+1} k_{j1} − ∑_{j=h+1}^{p+2} k_{j2}) ≤ k_{h2}

(h = 3, ...p + 1) and can press the LR-rule in the following form:

l ∗ m =

∑_{k_{p+1,1}} … ∑_{k_{21}} ∑_{k_{p+2,2}} … ∑_{k_{32}}(l_{1} + k_{11}, l_{2} + k_{21} + k_{22}, …, l_{p+1} + k_{p+1,1} + k_{p+2,2}, l_{p+2} + k_{p+2,2})

0 ≤ k_{h1} ≤ Min(l, m; h, 1)

Max(m; h, 2) ≤ k_{h2} ≤ Min(l, m; h, 2)

k_{11} = m_{1} − ∑_{j=2}^{p+1} k_{j1}, k_{22} = m_{2} − ∑_{j=3}^{p+2} k_{j2}

4. Treatment by a computer

This formula and the general formula also can be treated by a computer. We have written in Greifswald a C-program which give the result of the LR-rule using the proved formula. For example, we have computed the following cases: (1) (5,3,1)∗(2,2,1) (2) (6,5,3,3,1)∗(3,2,1) (3) (8,6,5,4,2,1)∗(4,2,2,1) The sums consists of (without consideration of multiplicities) 37 summands (1), 436 summands (2), 10483 summands (3). These results show that it is necessary to use a computer. It is possible to compute the summands of the LR-rule by an other procedure. This procedure is realized in Bayreuth using the special computer-algebra- system SYMCHAR. The theoretical basis of this procedure is given in the paper [LS85] of Lascoux/Schützenberger. The first comparisons show that this procedure should be a little quicker than our computation. But it seems that an advantage of the formulas of [S91] consist in the possibility of computing the Clebsch-Gordan-series of representations of classical Lie algebras and superalgebras without change of the program: We only have to replace the definition of Max(m; h, i) and Min(l, m; h, i) by a similar definition.

References

[LS85] Lascoux, A. and Schützenberger, M.-P., Schubert polynomials and the Littlewood-Richardson rule, Letters in Math. Phys. 10(1985), 111–124.

[S91] Schlosser, H., A closed formula for the rule of Littlewood/Richardson with applications in the theory of representations of gl(V) and the superalgebra pl(V), Math. Nachr. 151 (1991), 315–326.

Fachrichtungen Mathematik/Informatik Ernst Moritz Arndt Universität Friedrich Ludwig Jahn-Straße 15a O-2200 Greifswald, Germany

Received March 31, 1992