The use of Schubert polynomials in SYMCHAR

A. Kohnert ^{∗}

July 1991

1 Introduction

SYMCHAR is a collection of C routines, which allows to compute with symmetric groups, multivariate polynomials, representations, characters, symmetric polynomials, wreath products and many other related structures. The routines are written in standard C, so that there is no problem to use it on any machine, which has a C compiler. This was sucessfully checked for IBM-DOS, Atari-DOS and many different UNIX-machines. The code was written in Bayreuth, Paris and Aberystwyth. The program is public domain, and you can get a copy together with documentation files if you send a 3,5” HD-discette to the author.

Schubert polynomials are a generalization of Schur polynomials, and they are used inside SYMCHAR for the multiplication of Schur functions or for the decomposition of skew Schur functions into Schur functions. Schubert polynomials where introduced by Lascoux and Schützenberger in several papers, e.g. [LS1]. Schubert polynomials are labeled by permutations, in spite of partitions, which label Schur functions. We will see how we can characterize the permutations which label Schur polynomials.

∗supported by PROCOPE and ARC

2 Schubert polynomials

Schubert polynomials are multivariate polynomials, which are defined using a differential operator ∂_{i}. Let A_{n} := {a_{1}, ..., a_{n}} be an alphabet of n commuting letters and f ∈ ZZ[A_{n}] an arbitrary polynomial. We define the operation of the elementary transpositions σ_{i} := (i, i + 1) on f. f^{σ_{i}} := f(a_{1}, ..., a_{i−1}, a_{i+1}, a_{i}, a_{i+2}, ..). Now we are able to introduce the operator ∂_{i} by

∂_{i}(f) := \frac{f − f^{σ_{i}}}{a_{i} − a_{i+1}}

The operator ∂_{i} is a symmetrizing operator, as after the application of ∂_{i} the polynomial is symmetric in a_{i} and a_{i+1}. Now we are in the position to define Schubert polynomials: We do it inductively according to the reduced length of the permutations π, which label the polynomials. Let π ∈ S_{n} and l(π) the reduced length (i.e. number of inversions). Define the Schubert polynomial X_{π} inductively:

1. For the maximal reduced length l(π) = \binom{n}{2} we put

X_{π}(a_{1}, ..., a_{n}) := a_{1}^{n−1}a_{2}^{n−2}...a_{n−1}

2. If l(π) =: k is not maximal, π =: τσ_{i}, l(τ) = k + 1, then

X_{π}(a_{1}, ..., a_{n}) := ∂_{i}(X_{τ}(a_{1}, ..., a_{n}))

This definition works, as we have

∂_{i}∂_{i+1}∂_{i} = ∂_{i+1}∂_{i}∂_{i+1}
∂_{i}∂_{j} = ∂_{j}∂_{i} |i − j| > 1

There is a second method of labeling Schubert polynomials. We define a bijection L between the permutations of S_{n} and certain elements of IN^{n} . Let π ∈ S_{n} given in the list notation, i.e. π_{i} is the image of i under π. We define

L(π)_{i} := |{j > i|π_{j} < π_{i}}|

i.e. the number of entries to the right of π_{i}, which are smaller. The image L(π) is called the Lehmer code of the permutation π. L is a bijection between S_{n} and the elements l ∈ IN^{n} with l_{i} < n − i. The computation of the bijection is clear from an example:

L([5, 6, 3, 1, 2, 8, 4, 7]) = 4, 4, 1, 0, 0, 2, 0, 0
L^{−1}(2, 3, 0, 1, 2, 0, 0) = [3, 5, 1, 4, 7, 5, 6]

If we use this labeling instead of the permutations we write

Y_{I} := X_{L^{−1}(I)},

where I is a Lehmer code. Now we have the following property: Let I = 0 ≤ I_{1} ≤ I_{2}... ≤ I_{k}, 0, ..., 0 ∈ IN^{n} be a Lehmer code. Then

Y_{I} = S_{I_{1},...,I_{k}}(A_{k})

where S_{I_{1},...,I_{k}}(A_{k}) is the Schur polynomial labeled by the partition I_{1}, ..., I_{k} in the alphabet of k letters. If we look at the following picture we will see, that for example X_{2413} = Y_{1200} is the Schur polynomial S_{12}(A_{2}).

All Schubert polynomials, labeled by permutations of the S_{4}.

[figure: 1234, 1; 1243, a + b + c; 2134, a; 2143, a^{2} + ab + ac; 1324, a + b; 1342, ab + ac + bc; 1423, a^{2} + ab + b^{2}; 2314, ab; 2413, a^{2}b + ab^{2}; 1432, a^{2}b + a^{2}c+; ab^{2} + abc + b^{2}c; 4123, a^{3}; 3124,; a^{2}; 3214, a^{2}b; 2341,; abc; 2431, a^{2}bc + ab^{2}c; 3142, a^{2}b + a^{2}c; 4213, a^{3}b; 4132, a^{3}b + a^{3}c; 3241, a^{2}bc; 4231, a^{3}bc; 3412, a^{2}b^{2}; 3421, a^{2}b^{2}c; 4312, a^{3}b^{2}; 4321, a^{3}b^{2}c]

3 Monks Rule

This is the rule for the multiplication of Schubert polynomials by a single variable. The general case is unknown. This means, there is no general rule known for the multiplication of two arbitrary Schubert polynomials ( like the Littlewood Richardson rule for Schur functions).

The rule:

a_{k}X_{π} = ∑_{ρ=π(j,k),l(ρ)=l(π)+1} sign(j − k)X_{ρ}

An example:

a_{5}X_{13627458} = −X_{13672458} − X_{13726458} + X_{13628457}

To generate all the permutations on the right side of the equation, fix the number π_{k} (in the example 7) and now look to left of π_{k} which numbers π_{j} are smaller with no π_{l} between π_{j} and π_{k}. (in the example these are the numbers 2 and 6) These pairs π_{j}, π_{k} are exchanged giving a permutation on the right side with negative sign. Then look to the right of π_{k} searching for π_{j} bigger with no π_{l} in between. The exchanges of these pairs give the permutations with positve sign. (in the example the number 8) Proofs may be found in [M1] where it was proofen in the context of algebraic geometry, or in [K1] where it was proofen in the context of Schubert polynomials.

4 Transition algorithm

In general a Schubert polynomial X_{π} is not symmetric, but in the case π_{i} < π_{i+1} the polynomial is symmetric in a_{i} and a_{i+1}. This is clear from the definition. Now let X_{π} be symmetric in the first l variables, the transition algorithm is an algorithm which decomposes the symmetric part of the Schubert polynomial X_{π} (the polynomial X_{π}, where a_{l+1}, a_{l+2}, ... are set to zero) into Schur polynomials.

one step of the algorithm:

0. if only one decrease in π stop, X_{π} is Schur polynomial

X_{π}, k is the index of the last decrease in π, π_{k} > π_{k+1} < ....

1. exchange π_{k} and the biggest π_{l} with l > k, π_{l} < π_{k} 2. call the result π′

3. exchange π′_{k} with all π′_{l} with l < k such that the reduced length is increased by one.

4. call the generated permutations τ^{1}, τ^{2}, .....

one step is shortly described: input π, output τ^{1}, ...

Example:

13628457 → (k = 5)13627458 exchange 7 with 2 and 6,

giving 13726458 and 13672458.

So the input was one permutation, the output are two permutations.

To see that, we used the formula, which is a special case of the Monk rule:

a_{k}X_{π′} = X_{π} − ∑_{i} X_{τ^{i}}

k choosen as above. We look look on the symmetric part, where a_{k} becomes zero so we have the following decomposition

X_{π} = ∑_{i} X_{τ^{i}}

and if we have only Schur polynomials on the right side, we have a decomposition of the symmetric part into a sum of Schur polynomials.

The single step is applied to all newly generated permutations until the algorithm stops. So we generate a tree, on its root we have the input permutation, on the leaves there are permutations, which labels Schubert polynomials, which are Schur polynomials. So you may substitute the permutations on the leaves by the partitions. A further useful property is the invariance of the generated tree under the embedding S_{n} → S_{n+1}, π ↦ [1, π]. So if we increase the alphabet of the Schubert polynomial, the decomposition of the now bigger symmetric part into Schur polynomials is still valid.

This algorithm was introduced in [LS1]. In the original paper it was shown, that you can stop with permutations, which are socalled vexillary, but for computational reasons, it is easier to generate new permutations until you reach the Schur polynomials.

The whole algorithm is shortly described: input permutation π, output partitions λ^{1}, ... The algorithm will become clear, when we look on the examples in the two following special cases of the transition algorithm.

5 Useful applications of the transition algorithm

We consider two special cases of the transition algorithm, this means we look on special permutations as input of the algorithm.

5.1 Multiplication of Schur functions

We have two partitions: I = (0 ≤ I_{1} ≤ .. ≤ I_{k}) and J = (0 ≤ J_{1} ≤ ... ≤ J_{l}) labeling two Schur functions S_{I} and S_{J}. To compute the expansion of the product S_{I} × S_{J} we build the Schubert polynomial

Ỹ := Y0, I, \underbrace{0, ...., 0}_{I_{k} times}, J, 0, ...

Now the transition algorithm starting from Ỹ gives ∑ c_{K}S_{K}, and we have

S_{I} × S_{J} ∩ A_{k} = Ỹ ∩ A_{k} = ∑ c_{K}S_{K} ∩ A_{k}

As the algorithm is invariant under the embedding of S_{n} into S_{n+1} the decomposition is independent from the size of the alphabet A_{k}, so we have really the decomposition of the product of two Schur functions. This algorithm was first introduced in a paper of Lascoux and Schützenberger [LS1]. This method has been implemented and is used in SYMCHAR for the multiplication of two Schur functions. The algorithm becomes clear, when we look at the following example: decomposition of Schur function product S_{12} × S_{3}

135249678 Code : 012003000

135248679 ↓

↙  ↘
↓  ↓
138245679  135284679
= S_{15}  135274689
↓
↙  ↘
↓  ↓
137254689  135724689
137245689  = S_{123}
↓
↙  ↘
↓  ↓
147235689  137425689
= S_{24}  137245689
↓
↓
↓

237145689 = S_{114}

So we get: S_{12} × S_{3} = S_{24} + S_{114} + S_{123} + S_{15}

5.2 Decomposition of Skew Schur functions

We have a skewpartition I = (0 ≤ I_{1} ≤ .. ≤ I_{k})/J = (0 ≤ J_{1} ≤ ... ≤ J_{k}) labeling the skew Schur function S_{I/J}. In order to decompose into a sum of Schur functions, we build the following Schubert polynomial:

Ỹ := Y \underbrace{0, ..., 0}_{l leading zeros} ... \underbrace{I_{k−1} − J_{k−1}}_{position l+k−1+J_{k−1}}, 0..0, \underbrace{I_{k} − J_{k}}_{position l+k+J_{k}}, 0, ...

The transition starting from Ỹ gives ∑ c_{K}S_{K}, and we have

S_{I/J} ∩ A_{l} = Ỹ ∩ A_{l} = ∑ c_{K}S_{K} ∩ A_{l}

The same argument as in the case of the product of Schur functions, shows that we have a decomposition of skew Schur functions. This algorithm was presented in [K2]. Again we look on an example: decomposition of Skew Schur function S_{133/12}

10

12437586 Code : 00102010

12437568 ↓

↓
↓

12437658 12437568 ↓

↙  ↘
↓  ↓
12537468 12457368 Code : 00112000
12536478  = S_{112}
↓
↙  ↘
↓  ↓
12635478  12563478 Code : 00220000
12634578  = S_{22}

↓

↓

↓ 12643578 12634578

↓

↓

↓

13624578 Code : 01300000

= S_{13} And we have S_{133/12} = S_{112} + S_{22} + S_{13}.

12

6 Implementation

The algorithm has been implemented in the system SYMCHAR. It is written in standard C. To implement the generation of the tree we use a stack, of permutations. If the top level permutation is one which labels a Schur polynomial, it is written to the output, if not, the top level permutation is substituted by the permutations, which are generated in one step of the algorithm. The run time of this algorithm depends heavily on the structure which is used to store the result, if we use a tree structure for the result (= list of partitions with coefficent) we get nice run times. These are listed on the last table.

The run times where taken on a HP9000-425, runing UNIX Version 7.0.5, the files where compiled using the optimizer. As an example we used the decomposition of skew Schur functions.

skewpartition  degree of number of parts run time
result  in result  (sec.)
123456/1234  11  283  0.1
1234567/12345  13  1833  0.5
12345678/123456  15  13561  4.7
123456789/1234567  17  112745  46.6
12345678910/12345678 19  1039929  658.8

References

[K1] Kohnert A., Die computerunterstützte Berechnung von Littlewood-Richardson Koeffizienten mit Hilfe von Schubertpolynomen, Diplomarbeit Bayreuth 1987

[K2] Kohnert A., Skew Schur functions and Schubert polynomials, preprint 1991

[LS1] Lascoux A. & Schützenberger M.P., Schubert Polnomials and the Littlewood Richardson Rule, Letters in Math. Physics 10 (1985) 111-124

[M1] Monk D., The Geometry of Flag Manifolds, Proc. London Math. Soc. (3) 9 (1959) 253-286

Adress of the author:

Axel Kohnert Lehrstuhl Mathematik II Universität Bayreuth Postfach 101251 D-W8580 Bayreuth axel@btm2x2.mat.uni-bayreuth.de