\documentclass [12pt]{article}
\def\IN{{\rm I \kern -0.2em N}}
\def\IR{{\rm I \kern -0.2em R}}
\def\ZZ{\hbox{\rm Z\kern -0.3em Z}}

\title{The use of Schubert polynomials in SYMCHAR}
\author{ A. Kohnert \thanks { supported by PROCOPE and ARC } }
\date{July 1991 }

\begin{document}
\maketitle

\section {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\"utzenberger
in several papers, e.g. \cite {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.



\section {Schubert polynomials}


Schubert polynomials are multivariate polynomials, which are defined
using a differential operator $\partial_i$.
Let $A_n := \{ a_1,...,a_n \} $ be an alphabet of n commuting
letters and
 $f \in \ZZ[A_n]$ an arbitrary polynomial.
We define the operation of the elementary transpositions $\sigma_i :=
(i, i+1)$ on $f$.
$f^{\sigma_i} := f(a_1,...,a_{i-1},a_{i+1},a_i,a_{i+2},..) $. Now we
are able to introduce the operator $\partial_i$ by

$$ \partial_i(f) : = { {f - f^{\sigma_i} } \over { a_i - a_{i+1} } } $$

The  operator $\partial_i$
is a symmetrizing operator, as after the application of $\partial_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 $\pi$,
which label the polynomials.
Let
$ \pi \in S_n $ and  $l(\pi)$ the reduced length (i.e. number of inversions).
Define the {\bf Schubert polynomial $X_{\pi} $} inductively:

\bigskip

1. For the maximal reduced length $l(\pi) = {n \choose 2 }$ we put

$$ X_{\pi} (a_1,...,a_n) := a_1^{n-1} a_2^{n-2} ... a_{n-1} $$

2. If $l(\pi) =: k$ is not maximal, $ \pi =: \tau \sigma_i, l(\tau) = k+1 $,
then

$$ X_{\pi} (a_1,...,a_n) := \partial_i ( X_{\tau} (a_1,...,a_n) )
$$
This definition works, as we have


\begin{eqnarray*}
 \partial_i \partial_{i+1} \partial_i & =&  
 \partial_{i+1} \partial_{i} \partial_{i+1}\\
\partial_i \partial_j & = & \partial_j \partial_i \quad \quad |i-j|>1
\end {eqnarray*}


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 $\pi \in S_n$ given in the list notation, i.e. $\pi_i$ is the image
of $i$ under $\pi$. We define
$$ L(\pi)_i := | \{ j > i | \pi_j < \pi_i \} | $$
i.e. the number of entries to the  right of $\pi_i$, which are smaller.
The image $L(\pi)$ is called the
{\bf Lehmer code} of the permutation $\pi$.
$L$ is a bijection between $S_n$ and the elements $l \in \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\le I_1 \le I_2 ...
\le I_k, 0,...,0 \in \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)$.

\vfill
\eject
All Schubert polynomials, labeled by permutations of the $S_4$.


\unitlength0.8cm
\begin{picture}(18,20)
\put(9,1){\line(3,1){3}}
\put(5,2){\line(3,1){3}}
\put(1.5,10){\line(3,1){3}}
\put(13,7.5){\line(3,1){3}}
\put(9.5,15.5){\line(3,1){3}}
\put(5.5,16.5){\line(3,1){3}}
\put(9,1){\line(-4,1){4}}
\put(12,2){\line(-4,1){4}}
\put(15.5,10){\line(-4,1){4}}
\put(12.5,16.5){\line(-4,1){4}}
\put(6,7.5){\line(-4,1){4}}
\put(9.5,15.5){\line(-4,1){4}}
\put(9,1){\line(1,6){0.5}}
\put(1.5,5.5){\line(1,6){0.5}}
\put(1.5,10){\line(1,6){0.5}}
\put(15.5,5.5){\line(1,6){0.5}}
\put(15.5,10){\line(1,6){0.5}}
\put(8,14.5){\line(1,6){0.5}}
\put(8,3){\line(0,1){4.5}}
\put(1.5,5.5){\line(0,1){4.5}}
\put(15.5,5.5){\line(0,1){4.5}}
\put(2,8.5){\line(0,1){4.5}}
\put(16,8.5){\line(0,1){4.5}}
\put(9.5,11){\line(0,1){4.5}}
\put(9.5,4){\line(1,1){3.5}}
\put(12,2){\line(1,1){3.5}}
\put(9.5,4){\line(-1,1){3.5}}
\put(5,2){\line(-1,1){3.5}}
\put(8,7.5){\line(1,1){3.5}}
\put(8,7.5){\line(-1,1){3.5}}
\put(9.5,11){\line(-1,-1){3.5}}
\put(8,14.5){\line(1,-1){3.5}}
\put(12.5,16.5){\line(1,-1){3.5}}
\put(8,14.5){\line(-1,-1){3.5}}
\put(5.5,16.5){\line(-1,-1){3.5}}
\put(9.5,11){\line(1,-1){3.5}}
\put(9,0.5) { $1234, 1$ }
\put(12.5,2){$1243, a+b+c$ }
\put(4.5,1.5){$2134, a$}
\put (8.5,3) { $2143, a^2 + ab +ac $}
\put(10,4){$1324, a+b$}
\put(13.5,7) {$1342, ab+ac +bc$}
\put(16,5.5) {$1423, a^2 + ab + b^2$}
\put(2,5.5) {$2314,ab$}
\put(8.5,7.5){$2413, a^2 b + a b^2$}
\put(16.2,8.5){$1432, a^2 b + a^2 c+ $}
\put (17,8){$  a b^2 + abc + b^2 c$}
\put(16.2,10){$4123, a^3$}
\put(5,7){$3124,$}
\put(5,6.5){$ a^2$}
\put(2.5,8.5){$3214, a^2b$}
\put(0,10) {$2341,$}
\put(0,9.5){$ abc$}
\put(5,11) {$ 2431, a^2 bc + ab^2 c$}
\put(9.7,11.2){$ 3142, a^2 b + a^2 c$}
\put(11.5,10){$ 4213, a^3 b$}
\put(16,13){$4132, a^3 b + a^3 c$}
\put(2.5,13){$3241, a^2 bc$}
\put(8,14.5){$4231, a^3 bc$}
\put(10,15){$3412, a^2 b^2$}
\put(2.5,16.5){$3421, a^2 b^2 c$}
\put(12.5, 16.5){$4312, a^3 b^2$}
\put(8.5,17.5){$4321, a^3 b^2 c$} 
\end{picture}
\vfill
\eject
\section { 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).

\bigskip
The rule:
$$
a_k X_{\pi} = \sum _{  \rho = \pi (j,k) ,
	l(\rho) = l(\pi) + 1  }    sign(j-k) X_{\rho}
$$

\bigskip

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 $\pi_k$ (in the example 7) and now look to left of $\pi_k$
which numbers $\pi_j$ are smaller with no $\pi_l$ between $\pi_j$ and
$\pi_k$. (in the example these are the numbers 2 and 6) These pairs
$\pi_j,\pi_k$ are exchanged giving a permutation on the right side with
negative sign. Then look to the right of $\pi_k$ searching for $\pi_j$ bigger
with no $\pi_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
\cite {M1} where it was proofen in the context of algebraic geometry, or
in \cite {K1} where it was proofen in the context of Schubert polynomials.


\section{Transition algorithm}

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



\bigskip
{\bf one step of the algorithm:}


0. if only one decrease in $\pi$ stop, $X_{\pi}$ is Schur polynomial

\medskip
$X_{\pi} $, $k$ is the index of the last decrease in $\pi$,
$\pi_k > \pi_{k+1} < .... $

\medskip

1. exchange $\pi_k$ and the biggest $\pi_l$ with $l>k, \pi_l < \pi_k$

2. call the result $\pi '$

3. exchange $\pi'_k$ with all $\pi'_l$ with $ l < k $
   
   \ \ \ such that the reduced length is increased by one.

4. call the generated permutations $\tau^1, \tau^2, ....$.

\bigskip
one step is shortly described: input $\pi$, output $\tau^1,..$.

\bigskip
{\bf Example:}

$13628457 \rightarrow (k = 5) 13627458$
exchange 7 with 2 and 6, 

giving
$13726458 $ and $ 13672458 $.

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

\bigskip
To see that, we used the formula, which is a special case of the Monk rule:
$$a_k  X_{\pi'} = X_{\pi} - \sum_i X_{\tau^i} $$
$k$ choosen as above. We look
look on the symmetric part, where $a_k$ becomes zero so 
we have the following decomposition
$$ X_{\pi} = \sum_i X_{\tau^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.

\bigskip
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 \rightarrow S_{n+1},
\pi \mapsto [1,\pi] $. So if we increase the alphabet of the 
Schubert polynomial, the decomposition of the now bigger symmetric
part into Schur polynomials is still valid.

\bigskip
This algorithm was introduced in \cite {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.
\bigskip

The whole
algorithm is shortly described: input permutation $\pi$, output partitions
$\lambda^1,..$.
The algorithm will become clear, when we look on the examples in the two
following special cases of the transition algorithm.


\newpage
\section{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.

\subsection{ Multiplication of Schur functions}

We have two partitions:
$ I = ( 0 \le I_1 \le .. \le I_k)$ and $ J= (0\le J_1 \le ... \le J_l)$
labeling two Schur functions $S_I$ and $S_J$. To compute the expansion
of the product $S_I \times S_J$ we build the Schubert polynomial
$$ \tilde Y := Y_{\displaystyle 0, 
\displaystyle I, \underbrace {0,....,0}_{I_k {\rm  \ times}} , 
\displaystyle J, \displaystyle 0,...}$$
Now
the transition algorithm 
starting from $\tilde Y$ gives $\sum c_K S_K$, and we have
$$ S_I \times S_J \cap A_k = \tilde Y \cap A_k = \sum c_K S_K \cap 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\"utzenberger \cite {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:

\newpage
decomposition of Schur function product $S_{12} \times S_{3}$

$$
\matrix { 
		&		& 135249678 & Code: 012003000 \cr
		&		& 135248679 \cr
&& \downarrow\cr
\cr
&  \swarrow& &  \searrow \cr
\cr
&  \downarrow &&  \downarrow\cr
		&138245679&		& 135284679 \cr
		& = S_{15}&		& 	  135274689 \cr
&&&  \downarrow \cr
\cr
&&  \swarrow &&  \searrow \cr
\cr
&&  \downarrow &&  \downarrow \cr
		& & 137254689             & & 135724689 \cr
		& & 137245689		&           &= S_{123} \cr
&& \downarrow\cr
\cr
&  \swarrow& &  \searrow \cr
\cr
&  \downarrow &&  \downarrow\cr
		&147235689		& & 137425689 \cr
		&= S_{24}		& & 137245689 \cr
 &&&  \downarrow\cr
\cr
 &&&  \downarrow\cr
\cr
 &&&  \downarrow\cr
	&	&	& 237145689 \cr
	&	&	& = S_{114} \cr
\cr
\cr
\cr
\cr
\cr
}
$$
So we get: $S_{12} \times S_3 = S_{24} + S_{114} + S_{123} + S_{15} $

\newpage

\subsection {Decomposition of Skew Schur functions}

We have a skewpartition 
$ I = ( 0 \le I_1 \le .. \le I_k)/ J= (0\le J_1 \le ... \le 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:
$$ \tilde Y:= 
Y_{ \displaystyle \underbrace {0,...,0}_{l {\rm \ leading \ zeros}} 
...\underbrace {I_{k-1}-J_{k-1}}_{{\rm  \ position\   } l+k-1+J_{k-1}},
\displaystyle 0.. \displaystyle 0,
\underbrace {I_{k}-J_{k}}_{{\rm  \ position\   } l+k+J_{k}}, 
\displaystyle 0,...}$$
The transition starting from $\tilde Y$ gives $\sum c_K S_K$, and we have
$$ S_{I/J} \cap A_l = \tilde Y \cap A_l = \sum c_K S_K \cap 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 \cite {K2}.
Again we look on an example:

\newpage
decomposition of Skew Schur function $S_{133/12}$

$$
\matrix { 
		&		& 12437586 & Code: 00102010 \cr
		&		& 12437568 \cr
&& \downarrow \cr
\cr
&& \downarrow \cr
\cr
&& \downarrow \cr
		&		& 12437658 \cr
		&		& 12437568 \cr
&& \downarrow \cr
\cr
& \swarrow && \searrow \cr
\cr
& \downarrow && \downarrow \cr
		& 12537468      &              & 12457368 & Code: 00112000\cr
		& 12536478 	&		& = S_{112} \cr
& \downarrow \cr
\cr
 \swarrow && \searrow \cr
\cr
 \downarrow && \downarrow \cr
12635478        &		& 12563478 & Code: 00220000\cr
12634578 	&		& = S_{22} \cr
 \downarrow \cr
\cr
 \downarrow \cr
\cr
 \downarrow \cr
12643578 \cr
12634578 \cr
 \downarrow \cr
\cr
 \downarrow \cr
\cr
 \downarrow \cr
13624578 	& Code: 01300000\cr
= S_{13} \cr
}
$$
And we have $S_{133/12} = S_{112} + S_{22} + S_{13} $.
\vfill
\newpage
\section{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.


\begin{tabular}{llrr}
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 \\
$123456789 10 /12345678 $ & $19$ & $1039929$ & 658.8 \\
\end {tabular}


\begin {thebibliography}{999}
\bibitem[K1]{K1} Kohnert A., Die computerunterst\"utzte Berechnung von 
Littlewood-Richardson Koeffizienten mit Hilfe von Schubertpolynomen,
Diplomarbeit Bayreuth 1987
\bibitem[K2]{K2} Kohnert A., Skew Schur functions and Schubert polynomials,
preprint 1991
\bibitem[LS1]{LS1}Lascoux A. \& Sch\"utzenberger M.P., Schubert Polnomials
and the Littlewood Richardson Rule, Letters in Math. Physics 10 (1985) 111-124
\bibitem[M1]{M1} Monk D., The Geometry of Flag Manifolds, Proc. 
London Math. Soc. (3) 9 (1959) 253-286
\end {thebibliography}

Adress of the author:

Axel Kohnert

Lehrstuhl Mathematik II

Universit\"at Bayreuth

Postfach 101251

D-W8580 Bayreuth

axel@btm2x2.mat.uni-bayreuth.de
\end {document}
