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_4	S_5	S_6	S_7	S_8
# Coeffs	208	3600	81669	2285414	79860923
# distinct coeffs	5	12	62	332	3267

Here, we are considering the number of `Schubert-vs-Schur' Littlewood-Richardson coefficients c^w_{u,v(\lambda,k)} in the cohomology of a flag manifold, which is the coefficient of the Schubert class S_w in the product of a Schubert class S_u and a Schubert class S_\lambda pulled back from the projection to Grass(k, Fⁿ). Equivalently, this is the coefficient of a Schubert polynomial S_w in the the product of a Schubert polynomial S_u with a Schur polynomial S_\lambda(x₁,...,x_k). Here, u and w are permutations in the symmetric group S_n and \lambda is a partition.

The first row records the total number of constants c^w_{u,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 S_n, 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 S_n, 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 S_n 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 S_n 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 c^w_{u,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 S_n-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 S_n-1 to this number of `new' coefficients. For S₆, S₇, and S₈, these calculations are done using the MAPLE scripts, S6-coeffs.maple, S7-coeffs.maple , and S8-coeffs.maple. For S₄ and S₅, 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 c^w_{u,v(\lambda,k)} depends only upon \lambda and \zeta:=wu^-1 when u <_k w, thus we define c^\zeta_\lambda to be c^w_{u,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 S_n, 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 S_n, 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 S_n, 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 S₄:

Last modified: 26 August 1998