An interface to Anders Buch’s Littlewood-Richardson Calculator lrcalc#

The “Littlewood-Richardson Calculator” is a C library for fast computation of Littlewood-Richardson (LR) coefficients and products of Schubert polynomials. It handles single LR coefficients, products of and coproducts of Schur functions, skew Schur functions, and fusion products. All of the above are achieved by counting LR (skew)-tableaux (also called Yamanouchi (skew)-tableaux) of appropriate shape and content by iterating through them. Additionally, lrcalc handles products of Schubert polynomials.

The web page of lrcalc is http://sites.math.rutgers.edu/~asbuch/lrcalc/.

The following describes the Sage interface to this library.

EXAMPLES:

sage: import sage.libs.lrcalc.lrcalc as lrcalc

>>> from sage.all import *
>>> import sage.libs.lrcalc.lrcalc as lrcalc

Compute a single Littlewood-Richardson coefficient:

sage: lrcalc.lrcoef([3,2,1],[2,1],[2,1])
2

>>> from sage.all import *
>>> lrcalc.lrcoef([Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)],[Integer(2),Integer(1)])
2

Compute a product of Schur functions; return the coefficients in the Schur expansion:

sage: lrcalc.mult([2,1], [2,1])
{[2, 2, 1, 1]: 1,
 [2, 2, 2]: 1,
 [3, 1, 1, 1]: 1,
 [3, 2, 1]: 2,
 [3, 3]: 1,
 [4, 1, 1]: 1,
 [4, 2]: 1}

>>> from sage.all import *
>>> lrcalc.mult([Integer(2),Integer(1)], [Integer(2),Integer(1)])
{[2, 2, 1, 1]: 1,
 [2, 2, 2]: 1,
 [3, 1, 1, 1]: 1,
 [3, 2, 1]: 2,
 [3, 3]: 1,
 [4, 1, 1]: 1,
 [4, 2]: 1}

Same product, but include only partitions with at most 3 rows. This corresponds to computing in the representation ring of \(\mathfrak{gl}(3)\):

sage: lrcalc.mult([2,1], [2,1], 3)
{[2, 2, 2]: 1, [3, 2, 1]: 2, [3, 3]: 1, [4, 1, 1]: 1, [4, 2]: 1}

>>> from sage.all import *
>>> lrcalc.mult([Integer(2),Integer(1)], [Integer(2),Integer(1)], Integer(3))
{[2, 2, 2]: 1, [3, 2, 1]: 2, [3, 3]: 1, [4, 1, 1]: 1, [4, 2]: 1}

We can also compute the fusion product, here for \(\mathfrak{sl}(3)\) and level 2:

sage: lrcalc.mult([3,2,1], [3,2,1], 3,2)
{[4, 4, 4]: 1, [5, 4, 3]: 1}

>>> from sage.all import *
>>> lrcalc.mult([Integer(3),Integer(2),Integer(1)], [Integer(3),Integer(2),Integer(1)], Integer(3),Integer(2))
{[4, 4, 4]: 1, [5, 4, 3]: 1}

Compute the expansion of a skew Schur function:

sage: lrcalc.skew([3,2,1],[2,1])
{[1, 1, 1]: 1, [2, 1]: 2, [3]: 1}

>>> from sage.all import *
>>> lrcalc.skew([Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)])
{[1, 1, 1]: 1, [2, 1]: 2, [3]: 1}

Compute the coproduct of a Schur function:

sage: lrcalc.coprod([3,2,1])
{([1, 1, 1], [2, 1]): 1,
 ([2, 1], [2, 1]): 2,
 ([2, 1], [3]): 1,
 ([2, 1, 1], [1, 1]): 1,
 ([2, 1, 1], [2]): 1,
 ([2, 2], [1, 1]): 1,
 ([2, 2], [2]): 1,
 ([2, 2, 1], [1]): 1,
 ([3, 1], [1, 1]): 1,
 ([3, 1], [2]): 1,
 ([3, 1, 1], [1]): 1,
 ([3, 2], [1]): 1,
 ([3, 2, 1], []): 1}

>>> from sage.all import *
>>> lrcalc.coprod([Integer(3),Integer(2),Integer(1)])
{([1, 1, 1], [2, 1]): 1,
 ([2, 1], [2, 1]): 2,
 ([2, 1], [3]): 1,
 ([2, 1, 1], [1, 1]): 1,
 ([2, 1, 1], [2]): 1,
 ([2, 2], [1, 1]): 1,
 ([2, 2], [2]): 1,
 ([2, 2, 1], [1]): 1,
 ([3, 1], [1, 1]): 1,
 ([3, 1], [2]): 1,
 ([3, 1, 1], [1]): 1,
 ([3, 2], [1]): 1,
 ([3, 2, 1], []): 1}

Multiply two Schubert polynomials:

sage: lrcalc.mult_schubert([4,2,1,3], [1,4,2,5,3])
{[4, 5, 1, 3, 2]: 1,
 [5, 3, 1, 4, 2]: 1,
 [5, 4, 1, 2, 3]: 1,
 [6, 2, 1, 4, 3, 5]: 1}

>>> from sage.all import *
>>> lrcalc.mult_schubert([Integer(4),Integer(2),Integer(1),Integer(3)], [Integer(1),Integer(4),Integer(2),Integer(5),Integer(3)])
{[4, 5, 1, 3, 2]: 1,
 [5, 3, 1, 4, 2]: 1,
 [5, 4, 1, 2, 3]: 1,
 [6, 2, 1, 4, 3, 5]: 1}

Same product, but include only permutations of 5 elements in the result. This corresponds to computing in the cohomology ring of \(Fl(5)\):

sage: lrcalc.mult_schubert([4,2,1,3], [1,4,2,5,3], 5)
{[4, 5, 1, 3, 2]: 1, [5, 3, 1, 4, 2]: 1, [5, 4, 1, 2, 3]: 1}

>>> from sage.all import *
>>> lrcalc.mult_schubert([Integer(4),Integer(2),Integer(1),Integer(3)], [Integer(1),Integer(4),Integer(2),Integer(5),Integer(3)], Integer(5))
{[4, 5, 1, 3, 2]: 1, [5, 3, 1, 4, 2]: 1, [5, 4, 1, 2, 3]: 1}

List all Littlewood-Richardson tableaux of skew shape \(\mu/\nu\); in this example \(\mu=[3,2,1]\) and \(\nu=[2,1]\). Specifying a third entry \(M' = ``maxrows`\) restricts the alphabet to \(\{1,2,\ldots,M\}\):

sage: list(lrcalc.lrskew([3,2,1],[2,1]))
[[[None, None, 1], [None, 1], [1]], [[None, None, 1], [None, 1], [2]],
[[None, None, 1], [None, 2], [1]], [[None, None, 1], [None, 2], [3]]]

sage: list(lrcalc.lrskew([3,2,1],[2,1],maxrows=2))
[[[None, None, 1], [None, 1], [1]], [[None, None, 1], [None, 1], [2]],
 [[None, None, 1], [None, 2], [1]]]

>>> from sage.all import *
>>> list(lrcalc.lrskew([Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)]))
[[[None, None, 1], [None, 1], [1]], [[None, None, 1], [None, 1], [2]],
[[None, None, 1], [None, 2], [1]], [[None, None, 1], [None, 2], [3]]]

>>> list(lrcalc.lrskew([Integer(3),Integer(2),Integer(1)],[Integer(2),Integer(1)],maxrows=Integer(2)))
[[[None, None, 1], [None, 1], [1]], [[None, None, 1], [None, 1], [2]],
 [[None, None, 1], [None, 2], [1]]]

Todo

Use this library in the SymmetricFunctions code, to make it easy to apply it to linear combinations of Schur functions.

See also

Underlying algorithmic in lrcalc

Here is some additional information regarding the main low-level C-functions in \(lrcalc\). Given two partitions outer and inner with inner contained in outer, the function:

skewtab *st_new(vector *outer, vector *inner, vector *conts, int maxrows)

constructs and returns the (lexicographically) first LR skew tableau of shape outer / inner. Further restrictions can be imposed using conts and maxrows.

Namely, the integer maxrows is a bound on the integers that can be put in the tableau. The name is chosen because this will limit the partitions in the output of skew() or mult() to partitions with at most this number of rows.

The vector conts is the content of an empty tableau(!!). More precisely, this vector is added to the usual content of a tableau whenever the content is needed. This affects which tableaux are considered LR tableaux (see mult() below). conts may also be the NULL pointer, in which case nothing is added.

The other function:

int *st_next(skewtab *st)

computes in place the (lexicographically) next skew tableau with the same constraints, or returns 0 if st is the last one.

For a first example, see the skew() function code in the lrcalc source code. We want to compute a skew Schur function, so create a skew LR tableau of the appropriate shape with st_new (with conts = NULL), then iterate through all the LR tableaux with st_next(). For each skew tableau, we use that st->conts is the content of the skew tableau, find this shape in the res hash table and add one to the value.

For a second example, see mult(vector *sh1, vector *sh2, maxrows). Here we call st_new() with the shape sh1 / (0) and use sh2 as the conts argument. The effect of using sh2 in this way is that st_next will iterate through semistandard tableaux \(T\) of shape sh1 such that the following tableau:

     111111
     22222    <--- minimal tableau of shape sh2
     333
*****
**T**
****
**

is a LR skew tableau, and st->conts contains the content of the combined tableaux.

More generally, st_new(outer, inner, conts, maxrows) and st_next can be used to compute the Schur expansion of the product S_{outer/inner} * S_conts, restricted to partitions with at most maxrows rows.

AUTHORS:

  • Mike Hansen (2010): core of the interface

  • Anne Schilling, Nicolas M. Thiéry, and Anders Buch (2011): fusion product, iterating through LR tableaux, finalization, documentation

sage.libs.lrcalc.lrcalc.coprod(part, all=0)[source]#

Compute the coproduct of a Schur function.

Return a linear combination of pairs of partitions representing the coproduct of the Schur function given by the partition part.

INPUT:

  • part – a partition

  • all – an integer

If all is non-zero then all terms are included in the result. If all is zero, then only pairs of partitions (part1, part2) for which the weight of part1 is greater than or equal to the weight of part2 are included; the rest of the coefficients are redundant because Littlewood-Richardson coefficients are symmetric.

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import coprod
sage: sorted(coprod([2,1]).items())
[(([1, 1], [1]), 1), (([2], [1]), 1), (([2, 1], []), 1)]

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import coprod
>>> sorted(coprod([Integer(2),Integer(1)]).items())
[(([1, 1], [1]), 1), (([2], [1]), 1), (([2, 1], []), 1)]
sage.libs.lrcalc.lrcalc.lrcoef(outer, inner1, inner2)[source]#

Compute a single Littlewood-Richardson coefficient.

Return the coefficient of outer in the product of the Schur functions indexed by inner1 and inner2.

INPUT:

  • outer – a partition (weakly decreasing list of non-negative integers)

  • inner1 – a partition

  • inner2 – a partition

Note

This function converts its inputs into Partition()’s. If you don’t need these checks and your inputs are valid, then you can use lrcoef_unsafe().

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import lrcoef
sage: lrcoef([3,2,1], [2,1], [2,1])
2
sage: lrcoef([3,3], [2,1], [2,1])
1
sage: lrcoef([2,1,1,1,1], [2,1], [2,1])
0

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import lrcoef
>>> lrcoef([Integer(3),Integer(2),Integer(1)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
2
>>> lrcoef([Integer(3),Integer(3)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
1
>>> lrcoef([Integer(2),Integer(1),Integer(1),Integer(1),Integer(1)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
0
sage.libs.lrcalc.lrcalc.lrcoef_unsafe(outer, inner1, inner2)[source]#

Compute a single Littlewood-Richardson coefficient.

Return the coefficient of outer in the product of the Schur functions indexed by inner1 and inner2.

INPUT:

  • outer – a partition (weakly decreasing list of non-negative integers)

  • inner1 – a partition

  • inner2 – a partition

Warning

This function does not do any check on its input. If you want to use a safer version, use lrcoef().

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import lrcoef_unsafe
sage: lrcoef_unsafe([3,2,1], [2,1], [2,1])
2
sage: lrcoef_unsafe([3,3], [2,1], [2,1])
1
sage: lrcoef_unsafe([2,1,1,1,1], [2,1], [2,1])
0

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import lrcoef_unsafe
>>> lrcoef_unsafe([Integer(3),Integer(2),Integer(1)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
2
>>> lrcoef_unsafe([Integer(3),Integer(3)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
1
>>> lrcoef_unsafe([Integer(2),Integer(1),Integer(1),Integer(1),Integer(1)], [Integer(2),Integer(1)], [Integer(2),Integer(1)])
0
sage.libs.lrcalc.lrcalc.lrskew(outer, inner, weight=None, maxrows=-1)[source]#

Iterate over the skew LR tableaux of shape outer / inner.

INPUT:

  • outer – a partition

  • inner – a partition

  • weight – a partition (optional)

  • maxrows – a positive integer (optional)

OUTPUT: an iterator of SkewTableau

Specifying maxrows = \(M\) restricts the alphabet to \(\{1,2,\ldots,M\}\).

Specifying weight returns only those tableaux of given content/weight.

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import lrskew
sage: for st in lrskew([3,2,1],[2]):
....:     st.pp()
.  .  1
1  1
2
.  .  1
1  2
2
.  .  1
1  2
3

sage: for st in lrskew([3,2,1],[2], maxrows=2):
....:     st.pp()
.  .  1
1  1
2
.  .  1
1  2
2

sage: list(lrskew([3,2,1],[2], weight=[3,1]))
[[[None, None, 1], [1, 1], [2]]]

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import lrskew
>>> for st in lrskew([Integer(3),Integer(2),Integer(1)],[Integer(2)]):
...     st.pp()
.  .  1
1  1
2
.  .  1
1  2
2
.  .  1
1  2
3

>>> for st in lrskew([Integer(3),Integer(2),Integer(1)],[Integer(2)], maxrows=Integer(2)):
...     st.pp()
.  .  1
1  1
2
.  .  1
1  2
2

>>> list(lrskew([Integer(3),Integer(2),Integer(1)],[Integer(2)], weight=[Integer(3),Integer(1)]))
[[[None, None, 1], [1, 1], [2]]]
sage.libs.lrcalc.lrcalc.mult(part1, part2, maxrows=None, level=None, quantum=None)[source]#

Compute a product of two Schur functions.

Return the product of the Schur functions indexed by the partitions part1 and part2.

INPUT:

  • part1 – a partition

  • part2 – a partition

  • maxrows – (optional) an integer

  • level – (optional) an integer

  • quantum – (optional) an element of a ring

If maxrows is specified, then only partitions with at most this number of rows are included in the result.

If both maxrows and level are specified, then the function calculates the fusion product for \(\mathfrak{sl}(\mathrm{maxrows})\) of the given level.

If quantum is set, then this returns the product in the quantum cohomology ring of the Grassmannian. In particular, both maxrows and level need to be specified.

EXAMPLES:

   sage: from sage.libs.lrcalc.lrcalc import mult
   sage: mult([2],[])
   {[2]: 1}
   sage: sorted(mult([2],[2]).items())
   [([2, 2], 1), ([3, 1], 1), ([4], 1)]
   sage: sorted(mult([2,1],[2,1]).items())
   [([2, 2, 1, 1], 1), ([2, 2, 2], 1), ([3, 1, 1, 1], 1),
    ([3, 2, 1], 2), ([3, 3], 1), ([4, 1, 1], 1), ([4, 2], 1)]
   sage: sorted(mult([2,1],[2,1],maxrows=2).items())
   [([3, 3], 1), ([4, 2], 1)]
   sage: mult([2,1],[3,2,1],3)
   {[3, 3, 3]: 1, [4, 3, 2]: 2, [4, 4, 1]: 1, [5, 2, 2]: 1, [5, 3, 1]: 1}
   sage: mult([2,1],[2,1],3,3)
   {[2, 2, 2]: 1, [3, 2, 1]: 2, [3, 3]: 1, [4, 1, 1]: 1}
   sage: mult([2,1],[2,1],None,3)
   Traceback (most recent call last):
   ...
   ValueError: maxrows needs to be specified if you specify the level

The quantum product::

   sage: q = polygen(QQ, 'q')
   sage: sorted(mult([1],[2,1], 2, 2, quantum=q).items())
   [([], q), ([2, 2], 1)]
   sage: sorted(mult([2,1],[2,1], 2, 2, quantum=q).items())
   [([1, 1], q), ([2], q)]

   sage: mult([2,1],[2,1], quantum=q)
   Traceback (most recent call last):
   ...
   ValueError: missing parameters maxrows or level
sage.libs.lrcalc.lrcalc.mult_schubert(w1, w2, rank=0)[source]#

Compute a product of two Schubert polynomials.

Return a linear combination of permutations representing the product of the Schubert polynomials indexed by the permutations w1 and w2.

INPUT:

  • w1 – a permutation

  • w2 – a permutation

  • rank – an integer

If rank is non-zero, then only permutations from the symmetric group \(S(\mathrm{rank})\) are included in the result.

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import mult_schubert
sage: result = mult_schubert([3, 1, 5, 2, 4], [3, 5, 2, 1, 4])
sage: sorted(result.items())
[([5, 4, 6, 1, 2, 3], 1), ([5, 6, 3, 1, 2, 4], 1),
 ([5, 7, 2, 1, 3, 4, 6], 1), ([6, 3, 5, 1, 2, 4], 1),
 ([6, 4, 3, 1, 2, 5], 1), ([6, 5, 2, 1, 3, 4], 1),
 ([7, 3, 4, 1, 2, 5, 6], 1), ([7, 4, 2, 1, 3, 5, 6], 1)]

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import mult_schubert
>>> result = mult_schubert([Integer(3), Integer(1), Integer(5), Integer(2), Integer(4)], [Integer(3), Integer(5), Integer(2), Integer(1), Integer(4)])
>>> sorted(result.items())
[([5, 4, 6, 1, 2, 3], 1), ([5, 6, 3, 1, 2, 4], 1),
 ([5, 7, 2, 1, 3, 4, 6], 1), ([6, 3, 5, 1, 2, 4], 1),
 ([6, 4, 3, 1, 2, 5], 1), ([6, 5, 2, 1, 3, 4], 1),
 ([7, 3, 4, 1, 2, 5, 6], 1), ([7, 4, 2, 1, 3, 5, 6], 1)]
sage.libs.lrcalc.lrcalc.skew(outer, inner, maxrows=-1)[source]#

Compute the Schur expansion of a skew Schur function.

Return a linear combination of partitions representing the Schur function of the skew Young diagram outer / inner, consisting of boxes in the partition outer that are not in inner.

INPUT:

  • outer – a partition

  • inner – a partition

  • maxrows – an integer or None

If maxrows is specified, then only partitions with at most this number of rows are included in the result.

EXAMPLES:

sage: from sage.libs.lrcalc.lrcalc import skew
sage: sorted(skew([2,1],[1]).items())
[([1, 1], 1), ([2], 1)]

>>> from sage.all import *
>>> from sage.libs.lrcalc.lrcalc import skew
>>> sorted(skew([Integer(2),Integer(1)],[Integer(1)]).items())
[([1, 1], 1), ([2], 1)]