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
Compute a single Littlewood-Richardson coefficient:
sage: lrcalc.lrcoef([3,2,1],[2,1],[2,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}
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}
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}
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}
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}
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}
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}
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' = \) 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]]]
Todo
Use this library in the SymmetricFunctions
code, to
make it easy to apply it to linear combinations of Schur functions.
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)¶
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 partitionall
– an integer
If
all
is non-zero then all terms are included in the result. Ifall
is zero, then only pairs of partitions(part1, part2)
for which the weight ofpart1
is greater than or equal to the weight ofpart2
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)]
- sage.libs.lrcalc.lrcalc.lrcoef(outer, inner1, inner2)¶
Compute a single Littlewood-Richardson coefficient.
Return the coefficient of
outer
in the product of the Schur functions indexed byinner1
andinner2
.INPUT:
outer
– a partition (weakly decreasing list of non-negative integers)inner1
– a partitioninner2
– 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 uselrcoef_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
- sage.libs.lrcalc.lrcalc.lrcoef_unsafe(outer, inner1, inner2)¶
Compute a single Littlewood-Richardson coefficient.
Return the coefficient of
outer
in the product of the Schur functions indexed byinner1
andinner2
.INPUT:
outer
– a partition (weakly decreasing list of non-negative integers)inner1
– a partitioninner2
– 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
- sage.libs.lrcalc.lrcalc.lrskew(outer, inner, weight=None, maxrows=- 1)¶
Iterate over the skew LR tableaux of shape
outer / inner
.INPUT:
outer
– a partitioninner
– a partitionweight
– 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]]]
- sage.libs.lrcalc.lrcalc.mult(part1, part2, maxrows=None, level=None, quantum=None)¶
Compute a product of two Schur functions.
Return the product of the Schur functions indexed by the partitions
part1
andpart2
.INPUT:
part1
– a partitionpart2
– a partitionmaxrows
– (optional) an integerlevel
– (optional) an integerquantum
– (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
andlevel
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, bothmaxrows
andlevel
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)¶
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
andw2
.INPUT:
w1
– a permutationw2
– a permutationrank
– 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)]
- sage.libs.lrcalc.lrcalc.skew(outer, inner, maxrows=- 1)¶
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 partitionouter
that are not ininner
.INPUT:
outer
– a partitioninner
– a partitionmaxrows
– an integer orNone
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)]