Identities of Littlewood-Richardson Coefficients for Schubert polynomials

Nantel Bergeron. bergeron@mathstat.yorku.ca

Frank Sottile. sottile@msri.org
Abstract: We describe how the following table concerning the Littlewood-Richardson coefficients for Schubert polynomials was generated:
Symmetric group S_4S_5S_6S_7S_8
# Coeffs208360081669228541479860923
# distinct coeffs512623323267
Here, we are considering the number of `Schubert-vs-Schur' Littlewood-Richardson coefficients cwu,v(\lambda,k) in the cohomology of a flag manifold, which is the coefficient of the Schubert class Sw in the product of a Schubert class Su and a Schubert class S\lambda pulled back from the projection to Grass(k, Fn). Equivalently, this is the coefficient of a Schubert polynomial Sw in the the product of a Schubert polynomial Su with a Schur polynomial S\lambda(x1,...,xk). Here, u and w are permutations in the symmetric group Sn and \lambda is a partition.

The first row records the total number of constants cwu,v(\lambda,k) which may be non-zero. That is, those triples u, w, and \lambda where u<k w are comparable in the k-Bruhat order on Sn, and \lambda is a partition of l(w)-l(u), with at most k parts. In the paper: Schubert polynomials, the Bruhat order and the geometry of Schubert varieties, we prove many identities among these constants, which show how to compute all of the constants from a relative few, the number of which are recorded in the the second row. This table is Table 1 in that paper.

For a more complete description of these questions, see the manuscript (in Post Script) or the shorter conference abstract from FPSAC'97.


To generate this table, we first obtained the following data, for each n, k, and r. These data are tabulated in the text files indicated. Here n indexes a symmetric group Sn, k ranges from 1 to n-1, it is the index of the k-Bruhat order, <k, and r is a rank.

Grassmann.betti
The number of partitions \lambda with at most k rows and n-k columns. For a fixed k and n, these are the Betti numbers of the Grassmannian of k-planes in n-space. This was generated by the C code Grassmann-Betti.c.


k-comparable.k-n
This file records the number of pairs of permutations (u,w) in Sn with u less than w in the k-Bruhat order, and the length difference rank=l(w)-l(u). We generated these data using a MAPLE script, k-comparable.maple

zeta-orbits.rank
This file records, for each n, k, and rank, the number of equivalence classes of irreducible full-support permutations \zeta in Sn with that rank (in the Grassmann-Bruhat order) with exactly k numbers a with \zeta(a)>a. The equivalence here is generated by taking inverse (which interchanges k and n-k), conjugating with the longest element of the symmetric group, and conjugating with the cycle (1,2,...,n), which we call `cyclic shift'. This was generated with the C script, zeta-orbits.c.

Representatives of these equivalence classes (for n at most 8) are listed in the file zeta-orbits.list. There, they are listed by n and k, and the cycles are written. This list was computed using the MAPLE script, zeta-orbits.maple. However, this script will output extra permutations, as it does not properly screen for irreducibility.


To compute the number of a priori non-zero coefficients cwu,v(\lambda,k), for u, w in a given symmetric group, we first take the component-wise product of the first two tables, then add up the entries. This gives the first row of the table above.

Using the identities we discovered, we can deterine the `new' coefficients for each n. By new, we mean those for which we do not have an identity linking them to a coefficient from Sn-1. We do this by taking the componentwise product of the first and third tables Thus the second row is obtained by adding the entry for Sn-1 to this number of `new' coefficients. For S6, S7, and S8, these calculations are done using the MAPLE scripts, S6-coeffs.maple, S7-coeffs.maple , and S8-coeffs.maple. For S4 and S5, we did this by hand.


Why this works

It is clear that the first row is correct.

For the second, we showed in "Schubert polynomials..." show that the coefficient cwu,v(\lambda,k) depends only upon \lambda and \zeta:=wu-1 when u <k w, thus we define c\zeta\lambda to be cwu,v(\lambda,k). We showed this constant depends upon \zeta up to a linear relabeling of the entries in a cycle, thus we may assume that \zeta has full support in Sn, for otherwise we can compute c\zeta\lambda in a smaller symmetric group or flag manifold. This constant also only depends upon \zeta up to conjugation by the longest element of Sn, and more mysteriously, only up to conjugation by the cycle (1,2,...,n), which we call `cyclic shift'. Since the constant c\zeta\lambda equals the constant c\eta\mu, where \eta is the inverse of \zeta, and \mu the transpose of \lambda, we further restrict ourselves. Lastly, c\zeta\lambda will vanish if \lambda has more parts than there are numbers a with \zeta(a)>a.

Thus we only need tabulate the equivalence classes of permutations \zeta which have full support, and with equivalence generated by cyclic shift, conjugation by longest element, and inverse. There is one further reduction possible: We have a notion of reducible permutations \zeta=\eta\cdot\xi. For these, c\zeta\lambda may be calculated from c\eta\mu and c\xi\nu.

It should be clear that the second row is correct.


The Grassmann-Bruhat Order

While not needed to compute Table 1, we have also looked at the rank distribution of this new partial order in small symmetric groups. The results of this are tabulated in neworder.ranks, which tabulates the rank statistics of elements in the Grassmann-Bruhat order on Sn, for n=1,2,...,12 We originally computed the numbers up to n=11 with the MAPLE script, neworder.maple, which computes the ranks of elements in the symmetric group in the Grassmann-Bruhat order. On the MSRI cycle server (200 MHz HP 9000), this took over 2,000 minutes of CPU time for n=11. The table has been extended using a C version of that script, neworder.c, which on Frank's little 133MHz Pentium laptop running Linux takes only 17 minutes for n=11. (240 minutes (4:10:40) when n=12.)

The Grassmann-Bruhat for S4:



Last modified: 26 August 1998