%version archiv\'ee le 2 fevrier 89 apr\`es reintroduction
% des hexagones manquant ; keyt123 jusqu'\`a page 25

\magnification= 1200

\centerline{\bf K E Y S \ \& \ S T A N D A R D \ B A S E S}

\vskip 5mm
\centerline{Alain Lascoux \& Marcel-Paul Sch\"utzenberger}

\hfill \it quatri\`eme version: d\'ecembre 88

\rm\vskip 10mm
\noindent
\bf1.  Introduction.       
\rm The irreducible characters of the linear group on 
$C$ (\it Schur Functions\rm) are combinatorially interpreted as 
sums of \it Young tableaux\rm. 

Demazure \bf[D1] [D2] \rm has given a "Formule des caract\`eres" which 
interpolates between a dominant weight
, corresponding to a partition $I$ , 
and the Schur function of index $I$ . 
For every permutation $\mu$ , he obtains a 
"partial" character which can be interpreted 
as the class of the space of 
section  ${\cal V }_{I,\mu } $  of the line bundle associated 
to $I$ over the Schubert 
variety of index $\mu$ , in an appropriate 
Grothendieck ring ; identifying this 
ring with the ring of polynomials, we can view 
${\cal V}_{I,\mu}$ as a polynomial $\cal D(\mu,I) $ .

An independent study of the same spaces 
${\cal V}_{I,\mu}$ , and more precisely, of 
their "standard bases", is due to 
Lakshmibai-Musili-Seshadri \bf[L-M-S]\rm.
Extending the work of Hodge, they interpret 
Young tableaux as products 
of \it Pl\"ucker coordinates \rm of the flag variety
 and associate to them \it chains \rm of 
permutations to describe the different bases (see also \bf[L-W]\rm).

The link between the two constructions is not immediate. Moreover, 
none of these two point of view
 furnishes the multiplicative structure of 
sections which is needed in geometry to describe the 
\it postulation \rm of 
Schubert varieties. Indeed, the product 
${\cal V}_{I,\mu}\otimes\cdot\cdot\cdot\otimes{\cal V}_{I,\mu}$  contains more 
than the sections corresponding to a multiple 
of the weight $I$ and thus the 
products of standard bases are not standard bases.

The answer comes from working in the free algebra
 rather than the 
Grothendieck ring or the ring of coordinates. 
Young tableaux (2.1) are now 
\it words \rm which are representatives of certain 
congruence classes (th.2.4). 
More general words (\it frank words \rm, 2.7)
 obtained from tableaux by 
permutation allow to associate to each 
congruence class two special 
tableaux (\it right \rm and \it left keys \rm2.9). 
The set of keys (2.12) is in fact the 
image of the embedding of the symmetric group in the set of tableaux 
(embedding originally defined by Ehresmann \bf[E] 
\rm to describe how cells attach 
in a cellular decomposition of the flag variety).

Now, a standard basis is a set (or a sum)
 of tableaux having the same 
right key (th 3.6 ). To generate it,
 one uses \it symmetrizing operators \rm(3.5) 
on the free algebra which lift the 
operators on the ring of polynomial used 
by Demazure and Bernstein-Gelfand-Gelfand.
 Thus, the polynomial $\cal D(I,\mu)$ is 
just the commutative image of a sum of standard bases (th.3.8).

For what concerns the multiplicative structure of sections,
 the answer is also given by keys 
: the product of two tableaux $t, t' $
belongs to a 
standard basis iff the right key of  $t$ is 
less than the left key of $t'$ (2.11 
and 4.2) . This allows us in section 4 to give a combinatorial 
interpretation of the Hilbert function associated 
to a weight as an enumeration of chains of tableaux 
(th.4.3 and 4.4). See {\bf [L-S6] } for the 
related order on the symmetric group 
and its Eulerianity properties. The link between keys, reduced 
decompositions of permutations and the Schubert 
cycles (i.e. the classes of the Schubert 
varieties in the cohomology ring 
of the flag manifold) is given in \bf[L-S4]\rm.

In section 5, we explicit some different 
ways of describing the standard bases.

In appendix 6, we have isolated a property of actions of the 
symmetric group which is of independent interest.
\vskip 5mm
\bf Caution. \rm As usual, operators operate \it on their left \rm.

\vskip 15mm
\noindent
\bf2.  Frank words and keys .      \rm Let $A^*$ be the 
free monoid generated by the 
alphabet $A = \{a_1<a_2<...\}$. A word 
$v = x_1...x_r  (x_i\in A)$ is called a \it column 
\rm iff $x_1>...>x_r$  and a \it row \rm iff 
$x_1\leq x_2\leq\cdot\cdot\cdot\leq x_r$ . Let $V$ denote the set of all 
columns. Every word $w\in A^*$ admits a unique 
factorisation as a product of a 
minimal number of columns : $w = v_1 v_2\cdot\cdot\cdot v_k \big(v_i\in V\big)$.
 We shall call it the 
\it column factorisation \rm of $w$ and denote it occasionally by 
$w = v_1\bullet v_2\bullet\cdot\cdot\cdot\bullet v_k $ , 
$v_1$ being the \it left column \rm$w\bf L\rm$ of $w$ and $v_k$ the 
\it right column \rm$w{\bf \$}$ of $w$ . 
The \it shape \rm of $w$ is the sequence
$ \Vert w\Vert = (|v_1| ,...,|v_r|) $ of the degrees (or 
lengths) of the column factors of $w$ . 

To use a traditional term (see \bf[Mc]\rm),
$ \Vert w\Vert$ is a \it composition \rm of the 
integer$ |w|$ and the $|v_i|$ are the parts of $\Vert w\Vert$ .
 On the set of compositions, 
one has the following preorder 
: $I \geq J$ iff for every $k$, the sum of the $k$ 
biggest parts of $I$ is bigger than the sum 
of the $k$ biggest parts of $J$ . It 
is clear that if $I\geq J$ and $J\geq I$ , 
then $I$ is a permutation of $J$ , and that 
if H is any composition, $IH \geq JH \Leftrightarrow I \geq J$ .
 One can imbedd the set of 
compositions into the set of words :
$ I = (1I, 2I, ..., rI) \rightarrow 
\big(1I\cdot\cdot\cdot1\big)\big((1I+2I)\cdot\cdot\cdot(1I+1)\big)\cdot\cdot\cdot
\big((1I+2I+\cdot\cdot\cdot+rI)\cdot\cdot\cdot(1I+2I+\cdot\cdot\cdot+(r-1)I)\big)  $.
 We note this word $I\bf M\rm$ and call it a \it composition word \rm.
 It can be looked as the 
maximal element (as a permutation) of the Young group 
${\cal S}_I \hookrightarrow {\cal S}_{1I+\cdot\cdot\cdot+rI} $ . 
For instance, the composition word 
$(2,4,1)\bf M\rm$ is $(21)(6543)(7)$ , which is the maximal 
element of the subgroup ${\cal S}_2 \times {\cal S}_4 \times {\cal S}_1$  of ${\cal S}_7 $.

Taking the underlying set of a column defines a 
bijection $v \rightarrow \{v\} $ 
between the set $V$ of the columns and 
 the family $2^A$ of the subsets of $A$ ; 
one extends to $V$ the order $\leq$ on $A$ 
by letting $u\leq v$ iff there is an 
increasing injection of $\{u\}$ into $\{v\}$ .
 Thus  $u\leq v$ is the least order 
on $V$ that contains 
both the inclusion order $\{u\} \subset \{v\}$
 and the term to term order between 
equipotent subsets of $A$ .

\vskip 5mm
\noindent
\bf Definition 2.1.  \rm A \it contretableau \rm is a word 
which is an increasing product of columns.

\vskip 5mm
For instance, if $A = \{1<2<3<\cdot\cdot\cdot\}$ , the word 
$2 3 41 421$ is a 
contretableau because of $2\leq3\leq41\leq421$ .

It is convenient to define another order $\triangleright$ 
on $V$ by letting $u\triangleright v$ iff 
there is a decreasing injection of 
$\{v\}$ into $\{u\}$ and to call a \it tableau \rm any 
product $u_1 u_2 \cdot\cdot\cdot u_k $ where the columns 
$u_i$ are decreasing for $\triangleright$ , i.e. 
$u_1\triangleright u_2\triangleright \cdot\cdot\cdot \triangleright u_k $. 
For instance, $321 31 2 4$  is a tableau because 
$321\triangleright 31\triangleright 2\triangleright 4 $.


The two orders $\leq$ and $\triangleright$ are linked 
by the fact that $u\triangleright v$ iff $v'\leq u'$ 
where $ v \rightarrow v' $ is the bijection on $V$ 
induced by the "reversal" of the alphabet $A$
 assumed to be finite (i.e. by the morphism $a_i
\rightarrow a_{n+1-i} \ , \ n $ being the cardinal of $A$).

It follows from the definitions that the shape of 
any tableau $t$ is a 
partition of its degree. 
This suggests writing the letters of $t$ into the 
boxes of the Ferrers diagramm of $\Vert t\Vert$ . 
For instance, $321 \ 31 \ 2 \ 4 $ can be 
represented by  $
\matrix{ \scriptstyle 
3 & & & \cr
\scriptstyle 2 &\scriptstyle 3 & & \cr
\scriptstyle \scriptstyle 1 &\scriptstyle 1 
&\scriptstyle 2 &\scriptstyle 4 \cr
} $ .
 A similar remark holds for contretableaux and we can 
represent $2 \ 3 \ 41 \ 421 $ by 
$  \matrix{ \scriptstyle
2 &\scriptstyle 3 &\scriptstyle 4 &\scriptstyle 4 \cr
 & &\scriptstyle 1 &\scriptstyle 2 \cr
 & & &\scriptstyle 1 \cr  }$ . It is a direct consequence of 
the definition of the orders $\leq$ and $\triangleright$ that 
each row of the planar writings 
of tableaux or contretableaux is a weakly increasing
sequence of letters.

There is essentially one natural congruence 
$\equiv$ on $A^*$ that admits as a 
section the set of contretableaux, 
where \it natural \rm means that it commutes 
with the order preserving injections of alphabets.
 It is called the \it plactic congruence\rm.
 As shown by D.Knuth, it can be 
defined by the following 
identities where $a, b, c$ are any three letters 
of $A$ such that $a<b<c $ :$$
baa \ \equiv \ aba \ ; \ bba \ \equiv \ bab \ 
; \ cab \ \equiv \ acb \ ; \ bca \ \equiv \ bac
\leqno \bf(2.2)  \rm$$

As it has been observed by \bf[K-L]\rm, these generating congruences are 
exactly all the pairs of words of degree 3 that are not a column nor a 
line and that differ by the transposition of two adjacent letters. Thus 
one member of each pair is a tableau 
(e.g. $ \matrix{ b & \cr
a &c \cr } $ or  
$ \matrix{ b & \cr
a &a \cr } $
 ) and the other one, a contretableau (e.g.
$ \matrix{ b &c \cr
 &a \cr } $  or 
$ \matrix{ a &b \cr
 &a \cr } $ ) .

It turns out that the set of all tableaux
 is also a section of the 
plactic congruence and the defining relations 
(2.2) are simply the 
expression of this fact for the words of degree 3.

Another remarkable property of the plactic 
congruence is that every tableau 
(or contretableau) is congruent to the 
word obtained when reading 
by rows (from top to bottom) its 
planar representation. For instance, 
$ \ 321 \ 31 \ 2 \ 4 \ \equiv \ 3 \ 23 \ 1124  $
 or $2 \ 3 \ 41 \ 421 \ \equiv \ 2344 \ 12 \ 1 $.

This phenomenon is closely tied with another
 definition of the plactic 
congruence $ \equiv $ as one of the least congruences on $A^*$
 such that the subalgebra 
of $ Z(A^*/\equiv) $ generated by the (non commutative) symmetric sums 
$$\Lambda_p = \sum \{v: v\in V\ , |v|=p\} \ , \ p = 1,2,   $$
is a commutative algebra isomorphic to 
the usual algebra of symmetric 
polynomials in the letters of $A$ .

To obtain the complete characterisation of the plactic 
congruence, one needs to add a further condition which 
follows immediately from 2.2 and  
which will be used later.

\vskip 5mm
\noindent
\bf Proposition 2.3.      \rm The plactic congruence $\equiv$ is the 
least congruence on $A^*$  for which $\Lambda_1 \Lambda_2 \equiv \Lambda_2 \Lambda_1 $, 
and which moreover satisfies 
for any interval $B$ of $A$ the relation  $$
w \equiv w'  \Rightarrow w \cap B^* \equiv w' \cap B^*$$
\big($ w \cap B^* $ denotes the word obtained by erasing
 the letters not in $B$ \big).

\vskip 5mm
Taking $B$ equal to a single letter, 2.3 implies that the plactic 
congruence commutes with the natural morphism  
$w \rightarrow \underline w  $ of $A^*$ onto the free 
commutative monoid ; this can also be directly checked on relations 2.2.

The plactic congruence is no other than the algebraic formalization of 
Schensted's construction, whose main result can be summarized in the 
following theorem (\bf[Sche] \rm, \bf[L-S1] \rm).

\vskip 5mm
\noindent
\bf THEOREM 2.4.    \rm\it1) \rm Each plactic class contains 
a unique tableau $t$ and a 
unique contretableau\it.

2) \rm The elements of the class of $t$ are in 
bijection with the set of 
permutation tableaux (called \it insertion tableaux\rm)
 of the same shape as $t$ .

\vskip 5mm
By a permutation tableau, we mean, of course, 
a permutation (of any 
alphabet) which is at the same time a tableau. 
Given any word $w$, we note $w\bf R \rm$
the tableau congruent to it and $w\bf@ \rm$ its insertion tableau. 
It is well known 
(see \bf[Schu]\rm) that the involution $w \rightarrow w^{-1} $ 
on permutation words corresponds to 
the exchange of $w\bf R\rm$ and $w\bf@ \rm$ ; we shall not use this fact.

More explicitely, the insertion tableau 
(which is the Q-symbol of 
Schensted) of a word $w =  x_1 x_2 ...$ 
describes the increasing sequence of the 
shapes of the tableaux  $x_1\bf R \rm\ , \ x_1 x_2\bf R \rm\ $ ,  
$x_1 x_2 x_3\bf R \rm\ , \ldots $ .
The particular 
choice of the alphabet being irrelevant,
${}^{2}_{13} $ , ${}^{6}_{28}$  and ${}^{\beta}_{\alpha \gamma} $ 
, with $\alpha < \beta < \gamma$ , 
must be considered as the same insertion tableau 
representing the sequence 
of shapes $ \emptyset \rightarrow \ \diamond \ \rightarrow \ \matrix{\diamond \cr
\diamond \cr }  \ \rightarrow 
\ \matrix{\diamond & \cr
\diamond &\diamond \cr }  \  $ .

More generally, any word congruent to $w {\bf@\rm} $ 
will be called an \it insertion word \rm for $w$ . 
Insertion words are compatible with restriction of alphabets 
(see \bf[L-S1]\rm) :

\vskip 5mm
\noindent
\bf Lemma 2.5.  \rm Given any word  
$ w = x_1 ...x_{m-1} x_m ... x_{m+r} x_{m+r+1} ... $, 
then the word  $ w{\bf@\rm}\cap\{ m, ..., m+r\} $ 
is an insertion word for the factor 
$x_m \* \cdots \* x_{m+r} $ .

\vskip 5mm
In particular, as pointed out by Schensted,  
$w\bf@\rm$  contains the subword  
$m\ m+1 $ iff $x_m\leq x_{m+1} $ and the subword $m+1 \ m$
  iff $ x_m>x_{m+1} $ .
 Call \it file \rm of a permutation of 
$\{ 1,2,3 \ldots \}$ any maximal subword of the type 
$(m+k)\cdot\cdot\cdot(m+1)m$ . 
The shape $\Vert w\Vert$ corresponds to the 
files of any insertion word for $w$ . More 
precisely, one has the following lemma :

\vskip 5mm
\noindent
\bf Lemma 2.6.  \rm Let $w = v_1\bullet\cdot\cdot\cdot\bullet v_k  $ 
be a word, $\mu$ an insertion word for $w$ . Then 

\it1) \rm The files of $\mu$ are the same as those of
 the composition word $\Vert w\Vert \bf M  \rm$.

\it2) \rm$\Vert w\Vert \leq \Vert w\bf R\Vert \rm$ ; equality happens iff 
$\Vert w\Vert\bf M \rm$ is an insertion word for $w$ .

\it3) \rm For each permutation $J$ of the shape 
$\Vert w\bf R\Vert \rm$ , there exists one and only one 
word of shape $J$ congruent to $w$ .

\vskip 5mm
Proof. Assertion \it1) \rm is a direct corollary of 2.5 : the files of
 $\mu$ are the same as the files of 
$w\bf@ \rm$ and they encode exactly the inequalities 
$ x_i\leq x_{i+1} $ or 
$ x_i>x_{i+1} $ for all the pairs of adjacent letters in 
$w$ . For what concerns \it2)\rm, 
it is easy to check that the tableau 
$\mu\bf R \rm$ has shape greater than the 
composition corresponding to the files of 
$\mu$ ; this composition being $\Vert w\Vert $
and the shape of $\mu\bf R \rm= w\bf@ \rm$ 
being equal to that of $w\bf R \rm$,
 we get the required 
inequality. In the case of equality, the tableau 
$\mu\bf R \rm$ is determined by its 
files : consecutive entries in a file must be in consecutive rows of 
$\mu\bf R \rm$. A mild intimacy with the jeu de taquin shows that this last 
condition is equivalent to requiring that 
$\Vert w\Vert\bf M \equiv \mu R \rm$. Finally, condition \it3) 
\rm is a rewriting of the case where 
$\Vert w\Vert$ is a permutation of $\Vert w\bf R\Vert\rm$ ; we just saw 
that in this case the insertion tableau 
$w\bf@ \rm$ is uniquely determined, which 
means, thanks to the bijection 2.4.\it2 \rm that $w$ is uniquely determined.           
\hfill  $Q.E.D.$

\vskip 5mm
For example, $w = 53\bullet61\bullet2\bullet4$ has shape 
$2211 \leq 321 = \Vert w\bf R\Vert \rm$ ; the sequence 
of tableaux congruent to the left factors of 
$ w \ : \  \emptyset \longrightarrow 5 \longrightarrow 
\matrix{5 \cr
3 }
 \longrightarrow 
\matrix{5 & \cr
3 &6 \cr }
 \longrightarrow 
\matrix{5 & \cr
3 & \cr
1 &6 \cr }
 \longrightarrow 
\matrix{5 & \cr
3 &6 \cr
1 &2 \cr }
\longrightarrow 
\matrix{5 & & \cr
3 &6 & \cr
1 &2 &4 \cr }$
  shows that $w{\bf@\rm} = 
\matrix{4 & & \cr
2 &5 & \cr
1 &3 &6 \cr }$
; $w$ admits the insertion word $\mu = 452361 $ , since 
$\mu \equiv w{\bf@\rm} $; the files of 
$\mu$ are  $21, \ 43, \ 5, \ 6 $ and are identical to those of the 
composition word $\Vert w\Vert\bf M \rm\ = \ 21 \ 43 \ 5 \ 6 $.
 On the other hand, in the same 
congruence class, we have a unique word $w'$
 of shape $213 $ \ ; it is determined 
by its insertion tableau congruent to the composition 
word $ 213\bf M \rm\ = \ 21 \ 3 \ 654
\ \equiv \ 
\matrix{6 & & \cr
2 &5 & \cr
1 &3 &4 \cr }$
 . Indeed, $w'\ = \ 51 \ 3 \ 642 $ as we can check from the sequence of 
tableaux congruent to its left factors :  
$ \emptyset \longrightarrow 5 \longrightarrow 
\matrix{5  \cr
1 \cr }
\longrightarrow 
\matrix{5 & \cr
1 &3 \cr }
 \longrightarrow 
\matrix{5 & & \cr
1 &3 &6 \cr }
 \longrightarrow 
\matrix{5 &6 & \cr
1 &3 &4 \cr }
 \longrightarrow 
\matrix{5 & & \cr
3 &6 & \cr
1 &2 &4 \cr }$
 . The 
words corresponding to the other permutations of 
$321 $ are given next page.

The preceeding lemma has detached in the congruence class of a tableau 
$t$ , the set of those words $w$ (among which the tableau and the 
contretableau) for which $\Vert w\Vert$ is a permutation of $\Vert t\Vert$ :

\vskip 5mm
\noindent
\bf Definition 2.7.   \rm A word $w$ is \it frank \rm iff 
$\Vert w\Vert$ is a permutation of $\Vert w\bf R\Vert\rm$ .

\vskip 5mm
Equivalently, thanks to 2.6.\it2 \rm, a word $w $ is frank iff it admits the 
composition word $\Vert w\Vert\bf M\rm$ as an insertion word.

For a two-columns tableau $t$ ,
 finding its congruent contretableau $t'$ 
can be considered as using the generator $\flat$ of the symmetric group 
${\cal S}(2)$ to 
transpose the two columns of $t$ . 
This is best done with the jeu de taquin 
(\bf[L-S1]\rm) :
$\matrix{4 & \cr
3 &6 \cr
1 &2 \cr } \Rightarrow
\matrix{4 &6 \cr
1 &3 \cr
 &2 \cr }$
 . We shall write $t' = t^{\flat} $ and $t = t^{\prime \flat } $    . 
Notice that $t{\bf \$} = 62 $ is a subword of 
$t'{\bf \$} = 632 $ 
and that 
$t'{\bf L} = 41 $ is a subword of $t{\bf L} = 431 $.

More generally, on the set of k-columns words, one has an action (not 
everywhere defined ; we use the symbol $\emptyset$ when it is not defined) of the 
symmetric group ${\cal S}(k)$ . First, if the factor 
$v_rv_{r+1} $ of $w = v_1\bullet \cdots \bullet v_k $ , $v_i \in V $ , 
 is a tableau or a contretableau, then the image of 
$w$  by the simple 
transposition $\sigma_r \ , \ 1\leq r<k $ , is set equal to 
$v_1\cdot\cdot\cdot v_{r-1} (v_rv_{r+1})^{\flat}  v_{r+2} \cdot\cdot\cdot v_k $
if moreover this last word has still k columns. 
In all other cases, the 
image of $w$ by $\sigma_r $ is set equal to
 $\emptyset$  . It is checked in section 6 that 
this extends to an action of the symmetric group for which frank words play 
a special r\^ole that we summarize in the following theorem ( \it1 \rm and \it2 \rm being a 
rewriting of 2.6.\it2 \rm and 2.6.\it3\rm) :

\vskip 5mm
\noindent
\bf Theorem 2.8.  \rm\it1) \rm For each word $w$ , one has 
$\Vert w\Vert\geq\Vert w\bf R\Vert\rm$ , with equality iff $w$ is frank.

\it2) \rm The set of frank words in the plactic class of a tableau $t$ is in 
bijection with the set of permutations of the shape of $t$ .

\it3)  \rm The product of two frank words $w$ , $w'$
 is frank iff  $u{\bf \$}\bullet u'{\bf L}$
 is frank for any pair of frank words $u 
, u' $, with $u\equiv w$ and $u'\equiv w'$ .


\vskip 5mm
For example, the class of $531 \ 62 \ 4$ contains the six frank words 
(read vertically !) which correspond to the six permutations of the shape 
$321$ :

\setbox2=\hbox{ $\matrix{5 &6 & \cr 1 &3 & \cr
 &2 &4 \cr  & & }$ }
\setbox3=\hbox{$\matrix{5 & & \cr 1 &3 &6\cr & &4 \cr  & &2 \cr}$}
\setbox4=\hbox{$\matrix{5 & & \cr 3 &6 & \cr 1 &2 &4 \cr}$ }
\setbox5=\hbox{$\matrix{
1 &5 &6 \cr &3 &4 \cr & &2 \cr}$ }
\setbox6=\hbox{$\matrix{5 & & \cr  3 & & \cr 
 1 &2 &6 \cr & &4 \cr}$ }
\setbox7=\hbox{$\matrix{
1 &5 & \cr &3 &6 \cr &2 &4 \cr}$ }

$$ \matrix{  & &\box2  \ \longrightarrow  \ &\box3  \cr
&\nearrow  & & &\searrow \cr 
\box4 & &  & & &\box5 \cr
&\searrow  & & &\nearrow \cr
& &\box6 \ \longrightarrow \  &\box7 \cr}$$

On the other hand, the product of the two frank 
words $31 \ 42$ and $4 \ 51$ is not frank : the insertion 
tableau of $31 \ 42 \ 4 \ 51$ is $721 \ 43 \ 5 \ 6 $, which is not 
congruent to $21 \ 43 \ 5 \ 76 $. Indeed, $4 \ 51 \ \equiv \ 41 \ 5 $, and 
condition \it3) \rm is violated, because $42\bullet41$ is not frank .

\vskip 5mm
\noindent
We now come to the study of keys.

By definition, a \it key \rm is a tableau such that its columns are pairwise
comparable for the inclusion order. This condition implies that the 
action of the symmetric group giving the frank words is simply the 
permutation of the columns because this is true (and easily verified
) in the special case of two-columns keys\it, \rm where the operation
$\flat$ reduces to just commutation. 
For example, $531 \ 53 \ 3 $ is a key and the frank words in its 
congruence class are 

\setbox2=\hbox{ $\matrix{5 &5 & \cr 3 &3 & \cr 
 &1 &3\cr }$ }
\setbox3=\hbox{$\matrix{5 & & \cr 3 &3 &5 \cr   & &3 \cr & &1 \cr}$}
\setbox4=\hbox{$\matrix{5 & & \cr 3 &5 & \cr   1 &3 &3 \cr}$}
\setbox5=\hbox{$\matrix{
3 &5 &5 \cr  &3 &3\cr & &1\cr} $}
\setbox6=\hbox{$\matrix{5 & & \cr   3 & & \cr     
1 &3 &5 \cr & &3 \cr} $}
\setbox7=\hbox{$\matrix{
3 &5 & \cr &3 &5 \cr &1 &3 \cr}$ }

$$ \matrix{  & &\box2 \  \longrightarrow  \ &\box3  \cr
&\nearrow  & & &\searrow \cr 
\box4 & &  & & &\box5 \cr
&\searrow  & & &\nearrow \cr
& &\box6  \ \longrightarrow \  &\box7 \cr}$$


\vskip 5mm
\noindent
\bf Definition 2.9.  \rm The \it right key \rm$t{\bf K_+ \rm}$ of a tableau $t$ (or 
of any word congruent to  $t$) is the tableau of the 
same shape as $t$ whose columns belong to the set of 
columns $\{ u{\bf \$} \ , \ u\equiv t $ and $u$ frank $\}$. The \it left key 
\rm$t{\bf K_- \rm}$ of $t$ is the tableau of the same shape as $t$ whose 
columns belong to the set $ \{ u{\bf L} \ , \ u\equiv t $ and $u$ 
frank $\}$.

\vskip 5mm
In other words, the left key (resp.right key) of 
$t$ is made of the left (resp. right) columns, repeated 
the appropriate number of times so as to fill the 
shape of $t$,  of the frank words in the class of $t$ . 
For instance, the above hexagon for the tableau $531 
\ 62 \ 4 $ give the keys $t{\bf K_- \rm} \ = \ \matrix{
5 & & \cr 3 &5 &\cr 1 &1 &1\cr }  $ and $t{\bf K_+  \rm}\ =   \ 
\matrix{
6 & & \cr 4 &6 \cr 2 &4 &4 \cr } $  . 
Notice that a tableau is a key iff it is 
equal to its right (resp. left) key. In other case, 
the keys of a tableau belong to different plactic classes.


Since the test that the product of two frank 
words $w, w'$ is frank involves exactly the columns 
composing $w{\bf K_+ \rm}$ and $w'{\bf K_- \rm} $, we can reformulate th.2.8 :

\vskip 5mm
\noindent
\bf Theorem 2.10. \rm\it1)  \rm A word $w$ is frank iff $\Vert w\bf R\Vert\rm$ is a 
permutation of $\Vert w\Vert$ .

\it2) \rm A product  $ww'$ of two frank words $w, w' $ is frank 
iff the shape of $ww'\bf R \rm$ is the union of the shapes $\Vert w{\bf R\rm}\Vert $
and $\Vert w'{\bf R\rm}\Vert $.

\it3) \rm A product  $ww'$ of two frank words $w, w' $ is frank 
iff $(w{\bf K_+ \rm})(w'{\bf K_- \rm})$ is frank.

\vskip 5mm

If a pair of columns satisfies  $u \leq v$ , then $u'\leq v'$ 
for any other pair of columns $u', v'$ such that 
$\{ u' \} \subseteq \{ u \} \ , \ \{ v' \} \supseteq \{ v \} $ ; similarly
, $u \triangleright v $ implies $u' \triangleright v' $ 
for any pair such that $\{ u' \} \supseteq \{ u \} \ , \ 
\{ v' \} \subseteq \ \{ v \} $. Thus, in the special case of two 
frank words $w , w' $ having the same shape up to a 
reordering, condition \it3) \rm can be restricted to the 
comparison of columns in $w{\bf K_+ \rm} $ and $w'{\bf K_- \rm} $ of the same 
length instead of all pairs of columns (as required 
by 2.8.\it3 \rm). Recall that for columns of the same 
length, the order $\leq$ is the componentwise order on 
words of the same degree (that we can denote by the 
same symbol $\leq$ ). In short, one can replace in that 
case 2.10.\it3 \rm by :

\vskip 5mm
\noindent
\bf Theorem 2.11.  \rm Assume that $w, w'$ are two frank words 
such that $\Vert w{\bf R \rm}\Vert \ = \ \Vert w'{\bf R \rm}\Vert $ , then $ww' $ is frank iff 
$w{\bf K_+ \rm} \leq w'{\bf K_- \rm}  $ .

\vskip 5mm
For example, the product of the two tableaux $w \ = 
421 \ 41 \ 3 $ and $w' \ = \ 432 \ 32 \ 4 $ is not frank ; condition 
\it2) \rm is violated since $(421 \ 41 \ 3)(432 \ 32 \ 4){\bf R \rm} \ = \ 421 \ 431 
\ 432 \ 3 \ 4 $ is a tableau of shape ($=33311$) different from  
$332211$ . In fact, $421 \ 41 \ 3 \ \cong \ 421 \ 1 \ 43 $ and $432 \ 32 \ 4 \ \cong 
\ 32 \ 432 \ 4 $ , but $ (43 32)^{\flat}  \ =\ \emptyset $ , and thus condition \it3) 
\rm of the theorem is violated. Condition 2.11 has the 
same fate, since $431 \ 43 \ 3 \ \big(\ =(421 41 3){\bf K_+  } \big) $ is not 
smaller than $432 \ 32 \ 3 \ \big(\ = (432 \ 43 \ 4){\bf K_- } \big)  $ .

On the other hand, $421 \ 31 \ 3 \ 432 \ 32 \ 4 \ {\bf R \rm} 
\ = \ 421 \ 431 \ 32 \ 32 \ 3 \ 4 $ has shape $332211$
 , as is insured by the inequality 
$431 \ 31 \ 3 \ \big(\ = \ (421 \ 31 \ 3) {\bf K_+ } \big) \ \leq \ 432 \ 32 \ 3 \ \big( \ = 
(432 \ 43 \ 4) {\bf K_- } \big) $ required by 2.11.

\vskip 5mm
\noindent
\bf Definition 2.12.     \rm\it Key of a permutation \rm: to each 
pair consisting of a permutation $\zeta \in {\cal S }(n) $ , and a 
partition $I = (1I , 2I , \ldots ) $ ,  Ehresmann \bf[E]  \rm has 
associated a key, noted $ {{\bf K } } (\zeta , I) $ , by taking the 
sequence of left reordered factors of $\zeta$ (considered 
as a word) of successive degrees $ 1I, 2I, \ldots $ .

\vskip 5mm
For example, $\zeta = 316452 $ and $I = 532 $ give the key  
$65431 \ 631 \ 31 $ . 
In case that $I = n...21 $ , we shall simply write 
$ {\bf K } (\zeta) $ instead of $ {\bf K  } (\zeta, n...21) $ ; 
thus $\zeta \rightarrow {\bf K } (\zeta) $ is an 
embedding of ${\cal S } (n) $ into the set of tableaux of shape 
$n...21 $ . The reader may notice that the so-called "strong" 
, "Bruhat order" on permutations (see \bf[Bj]\rm) is a special case of the
pervading order on words (componentwise) which we have been 
repeatedly using, by way of the equivalence due to Ehresmann :

$$ \eta \leq \zeta \quad \Leftrightarrow \quad  {\bf K }(\eta) \ \leq \ {\bf K } (\zeta) \leqno \bf(2.13) \rm$$

For example, the keys associated to $ \zeta = 3241, \eta = 
2143 $ and $\mu = 1423 $ are ${\bf K } (\zeta) \ = \ 4321 \ 432 \ 32 \ 3 $
 , $ {\bf K } (\eta) \ = \ 4321 \ 421 \ 21 \ 1 $ , 
$ {\bf K } (\mu) \ = \ 4321 \ 421 \ 41 \ 1 $ ; thus $\zeta \geq \eta $ , 
but $\zeta$ and $\mu$ are not comparable since the two columns $32 $
and $41$ are not comparable.


\vskip 10mm
\noindent
\bf3 .  Symmetrizations .   \rm The definition of 
tableaux is strictly dependent upon a 
choosen total order on $A$ . It is remarkable that 
nonetheless the commutative image of the sum $S_I$ of all 
tableaux of a given shape $I$ be a symmetrical 
function : this is the most constructive definition
of the \it Schur Function \rm of 
index $I$. To understand this phenomenom (see nevertheless 
Knuth's proof \bf[B-K]\rm), one must define an action 
of the symmetric group on the free algebra such 
that the $S_I$ are invariant under this action.
Further, this action must induce the usual action
of the symmetric group when projected by $w \rightarrow \underline w $
on the commutative algebra.
By the duality $ w \rightarrow w^{-1} $ for permutation words,
 the new action we shall define now can be specialized 
to give the action that we have been using in our study
of frank words.

Consider first the case of a two-letters
 alphabet $A = \{a,b \}$ . 
It is clear that the image by the 
transposition $\sigma=\sigma_{ab} $ of the tableau $t=(ba)^h a^k 
b^m $ must be $t^\sigma = (ba)^h a^m b^k $ , since  $t^\sigma $ is the 
only tableau of the same shape as $t$ whose 
commutative 
image is the monomial $a^{m+h} b^{h+k} $.

More generally, because words $w$ in $a, b $ are 
determined by their insertion tableau $w\bf@ \rm$ and 
their commutative image $\underline{w}$ \  \big( we 
recover $w\bf R \rm$ from 
its content $\underline{w} $ and its shape, equal 
to that of $w\bf@ \rm$
\big), one defines  $w^\sigma $ to be the word : 

$$(w^\sigma )\bf@  \rm=   w\bf@  \rm\quad \&  \quad ( \underline{w} )^\sigma \ = 
\underline{(w^\sigma ) }\leqno {\bf (3.1)}$$

In other terms, $\sigma$ , as it has been defined, 
preserves the insertion tableau 
and commutes with the projection  $Z<a,b> \ \rightarrow Z[a,b]  $.

For example, the image by $\sigma$ of the word  $baa  \bf a  \rm bbaa  \bf aa  \rm b  
$ is $baa  \bf b  \rm bbaa  \bf bb  \rm b $ (we have marked the letters which 
change) because these two words have the same 
insertion tableau, equal to ${}^{167}_{0234589X} $ , and 
they project onto $a^7b^4 $  and $a^4b^7 $ in $Z[a,b] $.


Since the column ba commutes (plactically) with 
$a$ and $b$ , shifting the factors $ba$ of a word $w$ in 
$a,b$ generates the congruence class of $w$ .This 
remark implies the following easy algorithm to 
compute $w \rightarrow w^\sigma $ : 

\vskip 5mm
\noindent
{\bf (3.2)} \quad fix the 
successive factors $ba$ of $w$ , then change the remaining
 subword $a^kb^m$ into $a^mb^k$.  

\vskip 5mm
For instance the preceeding word gives $(ba) \ aa 
\ \big(b(ba)a\big) \ aab $ and we have to change the remaining 
word $ aa \ aab $ into $ab \ bbb $ to get 
$(ba) \ ab \ \big(b(ba)a\big) \ bbb \ = \ w^\sigma  $.

Consider now the more general case of a simple  
tranposition $\sigma_i $ of consecutive letters $a_i,a_{i+1} $ . 
One defines  $w^{\sigma_i } $  to be the word in which the 
subword $w \cap \{ a_i , a_{i+1} \} $ has been modified according 
to 3.1 or 3.2, the other letters being left 
unchanged. For example, denoting by $x...x$ any 
word in letters different from $a$ and $b$, the above 
computation shows that the image of 
$bxaxax{\bf a \rm}xbxbxaxax{ \bf a\rm}x{\bf a \rm}xb$ is $bxaxax{\bf b \rm}xbxbxaxax{\bf b \rm}x{\bf b \rm}xb $.


It is proven in \bf[L-S1] \rm that  $w \rightarrow w^{\sigma_i } $  extends 
to an action of the symmetric group on $Z<A>$ , 
i.e. that given a permutation $\mu$ and a word w , 
all factorizations of $\mu = \sigma \ \sigma' \ldots \ \sigma"$  into simple 
transpositions produce the same word  
$ \big((w^\sigma) ^{\sigma'}\ldots \big)^{\sigma"}$ denoted $w^\mu $.


One can note in reference to a previous remark 
that in section 2, we have 
acted on the insertion words to generate from a tableau 
the frank words which are congruent to it, thus 
preserving $w\bf R \rm$,and that the action described here 
preserves $w\bf@ \rm$.


At the commutative level, on $Z[A]$, we have at 
our disposal other actions of the symmetric group 
${\cal S }(A) $ (see \bf[L-S 2]\rm). 


In particular, 
two operators $ \overline{\pi_\mu } $  and $\pi_\mu $ on $Z[A]$ 
are associated to each permutation $\mu$ . For 
a simple transposition $\sigma_i$ the operator $\overline{\pi_{\sigma_i} } $ 
(abbreviated $\overline{\pi_i }$ , and acting as always on its left) is  
$$
f \ \longrightarrow \big( f^{\sigma_i }-f\big) \Bigm/ \big(1-a_i/a_{i+1}) \ = \ f\overline{\pi_i }
\leqno \bf(3.3) \rm$$
  and the operator   $\pi_i $ is just the sum of $\overline{\pi_i }$ and the 
identity :
$$
\pi_i  \ = \ \overline{\pi_i }  + 1 \leqno \bf(3.4) \rm$$

Let $\underline{w} = \underline{v} a_i^k \ \in \ Z[A] $ , with 
$\underline{v} $ symmetrical in $a_i$ and $a_{i+1} $. 

Then direct computation gives

$$
\underline{w} \pi_i \ = \ \underline{v} a_i^k + 
\underline{v} a_i^{k-1} a_{i+1} + \cdots + \underline{v} a_{i+1}^k$$

i.e. $\underline{w} \pi_i $ is the sum of all monomials between 
$\underline{w} $ and $\underline{w}^{\sigma_i} $ , and 
$\underline{w} \overline{\pi_i } $  is the same sum apart 
from the first term (=$w$) missing.

This indicates how we can lift  $\overline{\pi_i }$ into an 
operator, denoted $\theta_i$ , on the free algebra. Given 
$i$ and a word $w$ , let its degree in $a_{i+1} $ be $m$ and 
its degree in $a_i $ be $m+k$ . Then $w$ and  $w^{\sigma_i }$  differ 
by the exchange of a subword  ${\bf a \rm}_i^k $ into  ${\bf a \rm}_{i+1}^k $ if 
$k\geq0$, or of ${\bf a \rm}_{i+1}^{-k} $ into ${\bf a \rm}_i^{-k} $  if $k\leq0 $.

In the first case, we define  $w\theta_i $ to be the 
sum of all words in which the subword  ${\bf a \rm}_i^k $ has 
been changed respectively into  ${\bf a \rm}_i^{k-1}{\bf a \rm}_{i+1} $ , 
${\bf a \rm}_i^{k-2} {\bf a \rm}_{i+1}^2  $ , $\cdots  , {\bf a \rm}_{i+1}^k  $ ;  in the second, we 
put $ w\theta_i =  -\big(w^{\sigma_i }\big)\theta_i $ as in the commutative case. In 
other terms, $\theta_i $ interpolates between the identity 
and $\sigma_i $ for the words having more occurences of $a_i $
than of $a_{i+1} $ . The corresponding algorithm is in 
this case ($k\geq0$), putting $a_i=a , a_{i+1}=b , \theta = \theta_i $ :

\vskip 5mm
\noindent
{\bf (3.5)}  
fix the succesive factors $ba$ of $w$ , then change the remaining 
subword $a^{m+k}b^m $ into successively  $a^{m+k-1}b^{m+1} \ , \ a^{m+k-2}b^{m+2} \ , 
\ldots , \ a^mb^{m+k}$ and take the sum of all the words so obtained.

\vskip 5mm
For instance, for the word studied in 3.2, 
we have $(ba)  aa  \big(b(ba)a\big)  aab  \theta  =  (ba)\*aa\*\big(b(ba)a\big) 
\*abb  +  (ba)\*aa\*\big(b(ba)a\big)\*bbb 
 +  (ba)\*ab\*\big(b(ba)a\big)\*bbb  $.

More generally, we can transform $w$ by 
changing its subword $a^{m+k}b^m \ , \ k\in Z $ , into any row 
$a^rb^{2m+k-r} $ of the same degree. This operation will 
preserve the insertion tableau, as does $\sigma_i$ (which 
is a special case). In particular, we shall need 
the projection of $a^{m+k}b^m $ onto $a^{2m+k} $, $ k\in Z $ , that 
we shall denote $\lambda$ (and $\lambda_i$ for the pair of letters 
$a_i , a_{i+1}$ ) :

\vskip 5mm
\noindent
{\bf (3.6) }  
fix the successive factors $ba$ of $w$ , then change the remaining
 $a^{m+k}b^m$ into $a^{2m+k}$ to obtain $w\lambda$.

\vskip 5mm
Since $\sigma_i=\sigma , \theta_i=\theta , \lambda_i=\lambda $ preserve the insertion 
tableau, they are also compatible with the right 
and left keys : if $w$ is a frank word congruent to 
$t$, then $w^\sigma$ and $w\lambda $ are also frank, and $w\theta $ is a sum 
of frank words ; $ w^\sigma{\bf \$} $ and $w\lambda{\bf \$} $ are 
equal to $w{\bf \$}^\sigma $ or $w{\bf \$} $ . Thus $ t^\sigma{\bf K_+  \rm}$, 
$t\lambda{\bf K_+  \rm} $ and $t'{\bf K_+ \rm} $, with any $t'$ in the sum $t\theta $ , are 
equal to $t{\bf K_+ \rm} $ or $(t{\bf K_+ \rm})^\sigma$ . We shall give a more 
precise statement in theorem 3.8.

The operators $\theta_i $ do not satisfy the Coxeter 
relations $\theta_i\theta_{i+1}\theta_i = \theta_{i+1}\*\theta_i\*\theta_{i+1} $, contrary to the 
operators ${\overline \pi_i } , \pi_i $ and $\lambda_i$ ; thus, if $\sigma_i \cdots \sigma_j $ and 
$\sigma_h \cdots \sigma_k $ are two reduced decompositions of the 
same permutation , the operators $\theta_i \cdots \theta_j $ and 
$\theta_h \cdots \theta_k $ will in general be different and there is 
no canonical way of defining operators $\theta_\mu $ by 
products of operators $\theta_i $ .

Nevertheless, we recover this lost Coxeter 
relation when acting on dominant monomials, as we 
shall see in 3.8.

\vskip 5mm
\noindent
{\bf Definition 3.7.  \rm} The \it standard 
basis \rm${\cal U }(\mu,I) $ associated to the pair $\mu,I $ ($\mu$  
permutation, $I$ partition) is the sum in the free 
algebra of all tableaux having right key ${\bf K \rm}(\mu,I) $. 
The \it costandard basis \rm${\cal B }(\mu,I) $ is the sum of all 
contretableaux having right key ${\bf K \rm}(\mu,I) $.

\vskip 5mm

Since by definition all the elements in a 
plactic class have the same right key, it is 
clear that ${\cal U }(\mu,I) \ \equiv \ {\cal B }(\mu,I) $, and more precisely, 
that ${\cal B }(\mu,I){\bf R \rm} \ = \ {\cal U }(\mu,I) $.

To any partition $I = (1I, 2I, ...) $ on 
associates the \it dominant \rm monomial  $a^I \ = \ (a_{1I} \ldots a_2 
a_1)\*(a_{2I}... a_2 a_1)\*(a_{3I}... a_2 a_1) \ldots $.


\vskip 5mm
\noindent
\bf THEOREM 3.8.   \rm\it Let \rm$a^I$  \it be a dominant monomial and  
\rm$\sigma_i\sigma_j...\sigma_k $ \it be any reduced decomposition of a 
permutation \rm$\mu$ \it. Then  
\rm$${\cal U }(\mu,I) = a^I \theta_i\theta_j\cdots \theta_k   .$$

\vskip 2mm
Proof. Let $\mu$ and $i$ be such that $\ell (\mu\sigma)>\ell (\mu) $, with 
$\sigma=\sigma_i , a_i=a, a_{i+1}=b$. If $w$ is a frank word such 
that $w{\bf K_+ \rm}= {\bf K \rm}(\mu,I)$ or$ {\bf K \rm}(\mu\sigma,I)$ , then $w\lambda {\bf K_+ \rm}= 
{\bf K \rm}(\mu,I)$. Let $t$ be a tableau such that $t{\bf K_+ \rm}= {\bf K \rm}(\mu,I) 
, t^\sigma{\bf K_+ \rm}\neq {\bf K \rm}(\mu,I)$  \big(this implies that $t^\sigma{\bf K_+ \rm}= 
{\bf K \rm}(\mu\sigma ,I)$ \big) . Then there exists a frank word $w \equiv t $
such that the right factor  $w^\sigma{\bf \$} $ of $w^\sigma $
contains the letter $b$ and not the letter $a$ ; thus $w$ 
contains $a$ and not $b$ ; this implies that $t\lambda  = t$ . 
One checks moreover that all the tableaux 
(not only $t^\sigma$) in the sum $t\theta $ have the same right 
key ${\bf K \rm}(\mu,I) $. 

Conversely, if $t$ is such that $t{\bf K_+ \rm}= t^\sigma{\bf K_+ \rm}= 
{\bf K \rm}(\mu,I) $, then $(t+t^\sigma)\theta = 0$. Supposing the theorem 
true for $\mu$ , it is also true for $\mu\sigma $.    \hfill       $Q.E.D.$

\vskip 5mm
For instance, suppose that we already know 
${\cal B }(426135,321) $; we compute ${\cal B }(436125,321)$ by using 
the operator $\theta = \theta_2  $, the contretableaux $t$ such 
that $t^\sigma $ also belong to ${\cal B }(426135,321) $ give a zero 
contribution ; the others are of the type $t = t\lambda_2 $ :
$$\matrix{
4 &4\bf2 \rm&64\bf2 \rm& & & &    &\longrightarrow \quad    4 &42  &643 &+ &4 &43 &643 \cr
4 &41 &64\bf2 \rm& & & &    &\longrightarrow \quad        4 &41 &643\cr
3 &42 &64\bf2 \rm& & & & &\longrightarrow  \quad       3 &42 &643   \cr
\bf2 \rm&41 &64\bf2 \rm& & & & &\longrightarrow  \quad  2 &41 &643 &+ &3 &41 &643 \cr
3 &41 &642 & & & &   &\longrightarrow \quad     & & &0 \cr
3 &32 &642 & & & &  &\longrightarrow   \quad    & & &0 \cr
3 &31 &642 &+ &2 &31 &642    &\longrightarrow    & & &0 \cr } $$

All the contretableaux belonging to a 
costandard basis ${\cal B }(\mu,I) $ having the same right 
column (since it is the reordering of the factor 
of $\mu$ of length $1I$), we have a faster way to 
compute the costandard bases, by induction on the 
number of parts of $I$ :

\vskip 5mm
\noindent
\bf Lemma 3.9.   \rm Let $p$ be a positive integer, $I  = 
(1I,...,rI)$ be a partition with $r \geq p$, $I'$ the 
resulting partition after deletion of the part $pI $
, $\mu$ a permutation , $v$ the column such that $\{ v \} = 
\{ 1\mu ,...,(pI) \mu \} $. Then there exist permutations $\nu , 
\eta \ldots $ such that
$${\cal B }(\mu,I) = \big[{\cal B }(\nu,I') + {\cal B }(\eta,I') + \cdot\cdot\cdot \big] v  $$

\vskip 2mm
Proof. Two congruent frank words $w, w' $ have the 
same right column $w{\bf \$} = w'{\bf \$} $ iff 
$| w{\bf \$} | =  | w'{\bf \$} | $. Thus, to compute the 
right key of a tableau, we need only to generate 
a set of frank words $w^{(1)}, w^{(2)}, \ldots $   such that $ \{ 
|w^{(1)}{\bf \$}| , |w^{(2)}{\bf \$}| , \ldots \} = \{ 1I, 2I, 
\ldots \} $. We can require that the shapes of these 
frank words be  $(rI,\ldots ,2I,pI,1I)$ , 
$(rI,...,1I,pI,2I), \ldots, ((r-1)I,...,1I,pI,rI) $. 
The images of $w^{(1)}, \ldots , w^{(r)} $ by the 
transposition (of columns) $\sigma_{r-1} $ will be frank 
words with right column of degree $pI $. Thus the 
right key of any frank word $w = v_1\bullet\cdot\cdot\cdot\bullet v_r  $ is 
equal to that of the frank word 
$\big(v_1\bullet\cdot\cdot\cdot\bullet v_{r-1} {\bf K_+ \rm}\big)\bullet v_r  $ . To describe a standard 
basis, we need only to look for frank words of 
the type $w = w'\bullet v $ , $w'$ being a key of shape $I'$ 
and $v$ the column: $\{ v_r \} = \{ 1\mu,...,(pI)\mu \} $, such 
that $w{\bf K_+  \rm}= {\bf K \rm}(\mu,I) $ . \hfill $Q.E.D.$

\vskip 5mm
This lemma gives a fast induction when we 
taking $p=1$ to factorize the column of maximal 
length. For example, let $\mu = 32514 \ , \ I =4321 $. 
Then $v = 5321 , I' = 321 $ ; $ {\cal B }(32514,4321) = \big( 32 
\ 532 \ v \ + \ 3 \ 31 \ 532 \ v \ + \ 2 \ 31 \ 532 \ v \big) $ + $ \big( 3 \ 32 
\ 432 \ v \ + \ 3 \ 31 \ 432 \ v \ + \ 2 \ 31 \ 432 \ v \big) $ decomposes into 
$\big[{\cal B }(32514,321)+{\cal B }(32415,321)\big]\ v $ .


% Lascoux-Schutzenberger : Continuation of "keys"

\vskip 10mm
\noindent
\bf4 . Postulation .  \rm Let ${\cal A }$ be a vector bundle on any
 variety ${\cal M } \ ,\  {\cal F }({\cal A }) \rightarrow {\cal M } $ the 
relative flag manifold of complete flags of 
quotient bundles of ${\cal A }$ . If ${\cal A}$ is of rank 
$n$ , one has from definition (see \bf[Gr]\rm) $n$ 
tautological line 
bundles $L_1 ,\ldots , L_n $ on ${\cal F}({\cal A})$ . The Grothendieck 
ring ${\cal K}\big({\cal F}({\cal A})\big) $ of classes of vector bundles is a 
quotient of the ring of polynomials  ${\cal K}({\cal M})[A]$ 
, $A$ being an alphabet of cardinal $n$, by a certain 
ideal 
$\cal I$ , the images of $a_1 , \ldots , a_n $ being repectively 
the classes of $L_1 , \ldots , L_n $.

Since all constructions given here are 
compatible with $\cal I$, we can replace ${\cal K}\big({\cal F}({\cal A})\big) 
$ by $Z[A]$ and ${K}({\cal M})$ by the ring of symmetric 
polynomials $Z[A]^{{\cal S }(A)} $. The projection ${\it p\rm} : 
{\cal F}(A) \rightarrow {\cal M} $ induces a 
morphism ${\it p\rm}_* : {\cal K}\big({\cal F}(A)\big) \rightarrow {\cal K}({\cal M}) $ which corresponds in 
fact to the operator $ \mu_\omega : Z[A] \rightarrow Z[A]^{{\cal S }(A)} $
associated to the maximal permutation of ${\cal S}(A) $. We 
can express $\mu_\omega $ as a product of simple operators 3.4 
, but it can be directly defined by the following 
global expression (see \bf[L-S2]\rm) :

$$           Z[A] \ni f \ \longrightarrow \ \sum_{\mu\in{\cal S}(A)} \big[ f\big/ \prod_{i<j} (1-a_j/a_i) \big]^\mu
\leqno \bf(4.1)  \rm$$

In case that ${\cal M}$ is a point, the morphism ${\it p\rm}_* $
associates to any vector bundle ${\cal B}$ the 
Euler-Poincar\'e characteristics : $ \sum_i (-1)^i dim {\cal H}^i({\cal B}) $
; in terms of polynomials, this should be 
interpreted as $Z[A] \ni f \ \rightarrow \ f \pi_\omega \varepsilon_A $, $f$ being any 
polynomial lifting the class of ${\cal B}$ and $\varepsilon_A $ being the 
specialisation $a_1\rightarrow 1 ,\ldots, a_n \rightarrow 1 $.

Let $J$ be a partition, $I$ its conjugate, $L$  the 
line bundle  $L = 
L_1^{1J} \otimes L_2^{2J} \otimes \cdot\cdot\cdot$. From Demazure's construction, 
[\bf D1\rm] [\bf D2\rm] [\bf L-S5\rm] we have that the number $a^I\pi_\mu\varepsilon_A $ is 
the postulation (that is to say, the dimension of 
the cohomology ${\cal H}^0 $ ; the other spaces ${\cal H}^i$ being null, 
the postulation co\"\i ncide in that case with the 
Euler-Poincar\'e characteristics) of the line bundle 
$L$ on the Schubert variety of index $\omega\mu^{-1} $ .

More generally, considering simultaneously all 
the powers of $L$ together, we have 
the \it Hilbert series \rm${\cal H}_{I,\mu}(z) = (1-za^I)^{-1} 
\pi_\mu\varepsilon  $ relative to $L$ 
of the Schubert variety $ {\it Schub\rm}_{\omega\mu^{-1 }}  $ \quad 
\big( $L$ defines an embedding of the flag variety into a projective 
space if $1I> 2I> \ldots$ \big).

From considerations of dimension, we know that 
the series ${\cal H}_{I,\mu}(z) $ is rational of the type  
${\cal N}_{I,\mu}(z)\bf/\rm(1-z)^{\ell (\mu)+1 } $, ${\cal N}_{I,\mu}(z) $ being a polynomial of 
degree $\leq \ell (\mu) $. However $(1-za^I)^{-1}\pi_\mu $ has in general 
a denominator of degree greater than $ \ell (\mu)+1 $. 
Raising up to the free algebra, we shall get a 
combinatorial interpretation (4.4) of the Hilbert 
series and clarify in particular this drop in 
the degrees.

From 3.8 , given any reduced decomposition  
$\sigma_i...\sigma_j $ of $\mu$ , then  
$ \underbrace{a^I \ldots a^I}_{k} \*(\theta_i+1)\cdots \*(\theta_j+1) $  is a 
sum of words having the same insertion tableau as 
$a^I \ldots...a^I $, thus it is a product of $k$ tableaux of 
shape $I$ . On the other hand, again according to 
3.8, $  \big(a_{1I}...a_1\big)^k \big(a_{2I}...a_1\big)^k \cdots (\theta_i+1)...(\theta_j+1) $ is 
the sum of tableaux  ${\cal T}(\mu, I^k) $, $I^k $ denoting the partition 
$ \underbrace{1I \ldots 1I }_{k } \ 
\underbrace{1I \ldots 1I }_{k } \cdots $.

Since the operators $\theta_i $ are compatible with the 
plactic congruences, comparing the two sums gives 
that each tableau $t$ in ${\cal T}(\mu, I^k) $ is congruent to a 
frank word which is a product $t_1 \cdots t_k $ of tableaux 
of shape $I$ .

Conversely, from 2.11, we see that a product  
$t^{(1)}\cdots t^{(k)} $  of tableaux belonging to ${\cal T}(\mu, I) $ is 
congruent to a tableau $t \in {\cal T}(\mu, I^k)$
iff the following inequalities are satisfied :
$$   t^{(1)}{\bf K_+\rm} \leq  t^{(2)}{\bf K_-\rm} \ ; 
\  t^{(2)}{\bf K_+\rm} \leq t^{(3)}{\bf K_-\rm} \ ; \ldots; \ t^{(k-1)}{\bf K_+\rm} \leq t^{(k)}{\bf K_-\rm}  
\leqno \bf(4.2)    \rm$$
Moreover, in such a case, if $v_1 \bullet\bullet\bullet v_r $ is the right 
key of  $t^{(k)}$, then  $v_1^k \cdots v_r^k  $ is the right key of 
$t^{(1)} \ldots t^{(k)}  $ because each frank word in the class 
of $t^{(1)}\cdots t^{(k)}$  has a right column which is one 
the columns  $v_1 , \ldots , v_r $ . 

Let us call $I$-\it chain of length \rm$k$ a product of 
tableaux of the same shape $I$ satisfying the 
inequalities 4.2 ; the \it right key \rm of a chain will be 
the right key of its last tableau, \it the left key \rm of 
a chain being the left key of its first tableau. 

The preceeding results may be summarized in 
the following theorem :

\vskip 5mm
\noindent
\bf THEOREM 4.3. \rm\it Let \rm$I$ \it be a partition, \rm$\mu$  \it a permutation 
in \rm${\cal S}(A) $ , $\sigma_i \ldots \sigma_j $  \it any 
reduced decomposition of \rm$\mu$ \it. Then 
\rm$$(1-a^I)^{-1} \theta_i\cdot\cdot\cdot\theta_j \ = \ \sum_\Gamma  \big\{ \Gamma : {\bf K_+\rm}(\Gamma) < {\bf K\rm}(I,\mu) \big\}$$
\it sum of all \rm$I$-\it chains \rm$\Gamma$ \it of right key  \rm${\bf K\rm}(I,\mu) $ \it and
\rm$$(1-a^I)^{-1} (\theta_i+1)\cdot\cdot\cdot(\theta_j+1) \ =\  \sum_\Gamma  \big\{ \Gamma : {\bf K_+\rm}(\Gamma) \leq {\bf K\rm}(I,\mu) \} $$
\it sum of all \rm$I$-\it chains \rm$\Gamma$ \it of right key less or equal to \rm${\bf K\rm}(I,\mu) $\it.

\rm\vskip 5mm
      For instance, the 21 chains of length $2$ for 
${\cal S}(3) $ are all the $27$ products $\neq\emptyset $ of two tableaux of 
shape $21$ described below, and correspond 
bijectively to the $27 $ tableaux of shape $42$. There 
are $8$ tableaux of shape $21$, only two being not keys 
; for them, one has  ${\bf K_-\rm}\big({}^2_{13} \big)
 \ = \ \big({}^2_{12} \big) $
and $  {\bf K_+\rm}\big({}^2_{13} \big) \ = \ \big({}^3_{13} \big) $
\ , \ $ {\bf K_-\rm} \big({}^3_{12} \big) \ = \ \big({}^3_{11} \big)$
and $ {\bf K_+\rm}\big({}^3_{12} \big) \ = \ \big({}^3_{22} \big) $ .
 On the second row of the figure, for example, one reads that the chain 
${}^2_{12}  \bullet {}^2_{13} $ 
  factorizes the tableau 
${}^{22}_{1123}  $ 
 , its left key being 
$ {\bf K_-\rm}\big({}^2_{12} \big) $
  and its right key being $ {\bf K_+\rm} \big({}^2_{13} \big) $ .

\vskip 10mm


\quad\quad $\matrix{& & &{ }^{2}_{11} &{ }^{2}_{12 } &{ }^{3}_{11 }
&{ }^{2}_{13} &{ }^{3}_{13} &{ }^{3}_{12 } &{ }^{3}_{22 }
&{ }^{3}_{23} \cr
& & & & & & & & & &  \cr \cr
{ }^{2 }_{11} & & &{ }^{22}_{1111}  &{ }^{22}_{1112} &{ }^{23}_{1111}
&{ }^{22}_{1113} &{ }^{23}_{1113} &{ }^{23}_{1112} &{ }^{23} _{1122}
  &{ }^{23}_{1123}   \cr\cr
{ }^{2}_{12 } & & &\emptyset  &{ }^{22}_{1122} &\emptyset   &{ }^{22}_{1123}
&{ }^{22}_{1133} &\emptyset  &{ }^{23}_{1222} &{ }^{23} _{1223} \cr\cr
{}^{3}_{11} & & &\emptyset &\emptyset &{}^{33}_{1111} &\emptyset &{}^{33}_{1113}
&{}^{33}_{1112} &{}^{33}_{1122}  &{}^{33}_{1123}  \cr\cr
{}^{2}_{13} & & &\emptyset &\emptyset &\emptyset &\emptyset 
&{}^{23}_{1133} &\emptyset &\emptyset &{}^{23}_{1233}  \cr\cr
{}^{3}_{13} & & &\emptyset &\emptyset &\emptyset &\emptyset 
&{}^{33}_{1133} &\emptyset &\emptyset &{}^{33}_{1233}  \cr\cr
{}^{3}_{12} & & &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset 
&{}^{33}_{1222}  &{}^{33}_{1223}  \cr\cr
{}^{3}_{22} & & &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset 
&{}^{33}_{2222}  &{}^{33}_{2223}  \cr  \cr
{}^{3}_{23} & & &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset &\emptyset 
&\emptyset  &{}^{33}_{2233}  \cr } $ 

\vskip 10mm


Reintroducing a parameter $z$ , projecting to 
$Z[A]$ and using the specialization $\varepsilon_A \ : \ A \rightarrow  \{ 1, 
\ldots , 1 \} $ , we get :

\vskip 5mm
\noindent
\bf Corollary 4.4.  \rm Let $I$ be a partition, $\mu$ a 
permutation in ${\cal S}(A) $. Then the postulation 
$(1-za^I)^{-1} \overline{\pi_\mu } \varepsilon_A $ \big(resp. $ (1-za^I)^{-1} \pi_\mu \varepsilon_A $ \big) is equal 
to the generating function of the number of 
$I$-chains  $\Gamma $  having right key ${\bf K\rm}(I,\mu) $ \big(resp. 
having right key less or equal to ${\bf K\rm}(I,\mu) $ \big) , i.e.

$$(1-za^I)^{-1}\ \overline {\pi_\mu } \ \varepsilon  \ = 
\ \sum_{\Gamma} \ z^{length\Gamma }
\  \Gamma  \  \varepsilon_A$$
sum on all $I$-chains $\Gamma$ having right key ${\bf K\rm}(I,\mu) $ .


\vskip 10mm
\noindent
\bf5. Avatars of standard bases.    \rm According to theorem
3.8, if $\mu$ and $\sigma_k $ 
are such that $\ell (\mu\sigma_k) > \ell (\mu) $, then for any partition 
$I$ , $ {\cal U}(\mu,I)\theta_k = {\cal U}(\mu\sigma_k,I) $ .
Thus the operators $\theta_k$ allow to connect the 
standard bases corresponding to diffferent 
permutations. Using the same induction $\mu \rightarrow \mu\sigma_k $, 
it is not too difficult, but we shall abstain from 
doing it, to check that standard bases can also be 
defined in the following two other manners 5.2 and 
5.8.

First, according to \bf[L-M-S]\rm, a tableau can be 
considered as an increasing chain of permutations 
(with repect to the Ehresmann order 2.13). One 
says that a chain of permutations  $ \mu^{(1)}  \leq \mu^{(2)} \leq \ldots 
 \leq \mu^{(r)}  $  \it lifts \rm a tableau $ t = v_1 \bullet \cdot\cdot\cdot \bullet v_r  $ 
if $  \widetilde v_1 ,\ldots , \widetilde v_r   $ 
are respective left factors of 
$ \mu^{(1)} , \ldots , \mu^{(r)} $ 
, where, for a word $ v = x_1\cdot\cdot\cdot x_m  $, the 
notation $ \widetilde v  $ stands for the reverse word $ x_m\cdot\cdot\cdot x_1 $ .

It is clear that given a tableau, there 
exists a unique minimal lift of it. Indeed, 
putting $\mu^{(0)}= identity $ and having found the minimal 
chain $\mu^{(0)} \leq \mu^{(1)} \leq \ldots \leq \mu^{(p-1)} $
 with respective left factors 
$ \widetilde v_1 , \ldots , \widetilde v_{p-1}  $ , 
given moreover $v_p = x_1\cdot\cdot\cdot x_m $,
 we see that the set of permutations $\mu$ 
such that $ \mu \geq \mu^{(p-1)} $ and $1\mu = x_m ,\ldots, m\mu = x_1  $ admits a 
unique minimal element $\mu^{(p)}$ . An induction on $p$ 
thus gives a lift $\mu^{(1)}(t) \leq \cdot\cdot\cdot \mu^{(r)}(t)  $ that we shall 
call the \it canonical lift of \rm$t$ . From the 
construction, for any other lift $\zeta^{(1)} \leq \cdot\cdot\cdot \leq \zeta^{(r)}  $, 
one has $\mu^{(1)} \leq \zeta^{(1)} ,\ldots , \mu^{(r)} \leq \zeta^{(r)} $ , i.e. the 
canonical lift is minimal with respect to the 
Ehresmann order.

For example, the canonical lift of the 
tableau $531 \ 62 \ 4 $ is 
$ \bf135 \rm\ 246 \leq \bf26 \rm\ 3145 \leq \bf4 \rm\ 62135 $. Let us illustrate on 
this example how to pass from $ \mu^{(p-1)} $ to $ \mu^{(p)} $, say 
for $p=2 $. The left reordered factors of $\mu^{(1)} $ are 
$1, 13, 135, 1235, 12345 \ ; \ 236 $ is the minimum word 
having subword $26 $ bigger than $135$, $1236$ is the 
minimum word containing $236 $ bigger than $1235$, and 
finally, $12346 $ is the minimum word containing $1235 $
bigger than $12345$. These minimum words are the 
left reoredered factors of $\mu^{(2)} = 263145 $ which 
therefore is the minimum permutation bigger than 
$\mu^{(1)}$ and beginning by $\bf26 \rm$.

\vskip 5mm
\noindent
\bf Definition 5.1.   \rm Given a partition $I$ and a 
permutation $\mu$ , the \it L-M-S standard basis \rm${\cal U}'(\mu,I) $
is the set of tableaux $t$  such that the last 
permutation of their canonical lift is equal to  $\mu$ .

\vskip 5mm
When $\mu = identity$, the set ${\cal U}(\mu,I) $ reduces to 
the tableau $(1I\cdot\cdot\cdot1)(2I\cdot\cdot\cdot1)\*\cdots(rI\cdot\cdot\cdot1) $ as well as 
${\cal U}(\mu,I) $; the induction $\mu\rightarrow \mu\sigma $ proves, as claimed 
in the beginning of this section, that ${\cal U}(\mu,I) $ is 
the sum of the tableaux belonging to ${\cal U}'(\mu,I)$. In 
other words, one has the following property 
showing that the L-M-S standard bases coincide 
with the one defined in 3.5 , up to the change of 
the alphabet {A} with $N$ .

\vskip 5mm
\noindent
\bf Proposition 5.2.       \rm A key ${\bf K\rm} = {\bf K\rm}(\mu,I) $ is the 
right key of a tableau $t$ iff $t$ has shape $I$ and $\mu$ 
is the last permutation in the canonical lift of $t$ .

\vskip 5mm
For example, the last permutation $462135 $ in 
the canonical lift of the tableau $t \ = \ 531 \ 62 \ 4 $
gives the key $642 \ 64 \ 4 $, which is the right key of 
$t$ as seen in 2.9.

One may favor horizontals rather than 
verticals.  Reading the succesive horizontals of a 
tableau $t$ , one gets a word which is a product of 
rows (as defined in sect.2) and which is congruent 
to $t$ ; we shall call this word the \it row-word \rm of $t$.

For example, the row-word of $\matrix{
5 \cr 3 &6 \cr 1 &2 &4 \cr }$  is $5 \ 36 \ 124 $.
 Row-words are characterized by their insertion 
tableau, as seen from property 2.5 :

\vskip 5mm
\noindent
\bf Lemma 5.3.
 \rm A word $w$ is the row-word of a tableau $t$ 
iff there exists a partition $J = 1J \geq 2J \geq \cdots \geq pJ $  
such that 
$\big[(pJ+...+2J+1)\cdot\cdot\cdot(pJ+...+1J)\big]\cdot\cdot\cdot\big[(pJ+1)\cdot\cdot\cdot(pJ+(p-1
)J)\big] \big[1\cdot\cdot\cdot pJ\big] $
is an insertion word for $w$ . In that case, $J$ is 
the partition conjugate to the shape of $t$ .

\vskip 5mm
For example, $(5 \ 36 \ 124){\bf@\rm} =\matrix{
4 \cr 2 &5\cr 1 &3 &6\cr }$, and this 
tableau is congruent to the word $[456] \ [23] \ [1] $.

Apart from the symmetry between rows and 
columns, which means taking instead of composition 
words their reverse,  the same property as 2.8.\it2 
\rm holds : in the class of any tableau t of shape 
conjugate to a partition $J = (1J,\ldots,pJ) $, for any 
permutation $H$ of $J$ , there exists a unique word $w$ 
congruent to $t$ , which admits 
$\big[(pH+...+2H+1)\cdot\cdot\cdot(pH+...+1H)\big] \cdots \big[1\cdot\cdot\cdot pH\big] $ as an 
insertion word. This forces $w$ to be a product 
$w_p\cdot\cdot\cdot w_1 $ of rows of respective degrees $pH , \ldots, 2H 
, 1H $ . For standard tableaux, transposition (i.e. 
exchange of the two axes of coordinates) commutes 
this construction with the one given in section 2 .
The hexagon generated by the action of the 
symmetric group on the row-word $5 \ 36 \ 124 $ is now 
$$ \matrix{  & &56 \ 3 \ 124  &\longrightarrow \ &56 \ 134 \ 2  \cr
&\nearrow & & & &\searrow \cr
5 \ 36 \ 124 & & & & & &156 \ 34 \ 2 \cr
&\searrow & & & &\nearrow \cr
& &5 \ 136 \ 24 &\longrightarrow \ &156 \ 3 \ 24 }$$


The corresponding insertion words are respectively  
$$ \matrix{  & &456 \ 3 \ 12  &\longrightarrow \ &6 \ 345 \ 12  \cr
&\nearrow & & & &\searrow \cr
456 \ 23 \ 1 & & & & & &6 \ 45 \ 123 \cr
&\searrow & & & &\nearrow \cr
& &56 \ 234 \ 1 &\longrightarrow \ &56 \ 4 \ 123 }$$


Given $H \in N^p $, let $T_H $ be the sum of words $w$ such 
that :

\vskip 5mm
\noindent
\bf(5.4)  \rm$w$ has the insertion word 
$$\varphi = \big[(pH+...+2H+1)\cdot\cdot\cdot(pH+...+1H)\big]\cdot\cdot\cdot \big[1\cdot\cdot\cdot pH\big]$$
\bf(5.5) \rm For the factorization $w = w_p\cdot\cdot\cdot w_1 $
corresponding to $\varphi$ , every $w_j $, $1 \leq j \leq p $, belongs to 
the monoid generated by $A_j = \{ a_1 ,\ldots ,a_j \} $, i.e.  
$w_1 \in A_1^* ,  w_2 \in A_2^*  , \ldots, w_p \in A_p^*  $. 

\vskip 5mm
Because of the explicit value of $\varphi$ , the 
above factorization is the row-factorization of $w$ 
, apart from \it void \rm factors that we must specify in 
order to fix the flag conditions 5.5 .

For example, $T_{1302} = (44 222 1 + 34 222 1 + 
44 122 1 + 34 122 1) + (44 112 1 + 34 112 1) + (24 
122 1) + (33 222 1 + 33 122 1) + (24 112 1) + (33 
112 1) + (23 122 1) + (23 112 1) $ is the sum of 
words $w = w_3w_2w_1 $such that $w{\bf@\rm} \ \equiv \ 6 \ 345 \ 12$ 
\big($w{\bf@\rm} =\matrix{
6 \cr 3 &4\cr 1 &2 &5\cr }$\big) and 
$w_1 \in \{ 1 \}^* , w_2 \in \{ 1,2 \}^* , w_3 \in \{ 1,2,3 \}^* $.

As we already said, the induction  $\mu\rightarrow \mu\sigma $, 
starting from the case $T_J $ with $J$ partition ($T_J $ is 
the single word $\cdots2^{2J} 1^{1J}$), allows to obtain the 
general case, summarized in the following 
proposition :

\vskip 5mm
\noindent
\bf Proposition 5.6.    \rm Let $J$ be a partition, $\mu$ a 
permutation, $H=J^\mu $ , $I$ the partition conjugate to 
$J$ . Then $T_H $ is congruent to 
$ \sum_{\nu \leq \mu }  {\cal U}(I,\mu) $.

\vskip 5mm
In the preceeding example, $J= 321$, $\mu=2413 $. 
One has $8$ permutations in the interval $[1234, 
2413] $. According to the proposition, $T_{1302} \ \equiv \ 
{\cal U}(321,2413) + {\cal U}(321,1423) + {\cal U}(321,2143) + 
{\cal U}(321,2314) + {\cal U}(321,1243) + {\cal U}(321,1324) + 
{\cal U}(321,2134) + {\cal U}(321,1234) \ = \ $

$ \{ 421422 + 321422 + 421412 + 321412 \} + \{ 421411 + 
321411\} + \{ 421212 \} + \{ 321322 + 321312 \} + \{ 421211\} 
+ \{ 321311 \} + \{ 321212 \} + \{ 321211 \} $. 

These tableaux are respectively congruent to 
the words enumerated in the same order above.

Flags of alphabets or of modules naturally 
occur in the study of Schubert polynomials \bf[L-S2] 
\rm or of Schubert subvarieties of a flag manifold.

One can restrict the sum $T_H $ to its component 
$T'_H $ congruent to ${\cal U}(\mu,I)$. Indeed, one has the 
following property, which is also proved through 
the induction  $\mu\rightarrow \mu\sigma  $:

\vskip 5mm
\noindent
\bf Lemma 5.7.     \rm Let $t$ be a tableau of shape $I$ 
conjugate to $J$ , ${\bf K\rm}={\bf K\rm}(\mu,I)$ its right key , $\zeta$ a 
permutation , $H = J^\zeta $. Then there exists a word in 
$T_H $ congruent to $t$ iff $\zeta \geq \mu $. 

\vskip 5mm
In other terms, for any word $w$ , the set of $H$ 
such that $w$ is congruent to a word in $T_H$ is either 
void or admits a unique minimum element (i.e. an $H 
= J^\mu $  such that $\mu$ is minimal for the Ehresmann 
order, $J$ being the partition conjugate to the 
shape of $w{\bf R\rm}$). One can now define $T'_H $ to be the 
restriction of $T_H $ to such words. For example, the 
tableau $4321 \ 321\ 31\ 41\ 3 $ is congruent to the words 
$3344 \ 11233\ 2\ 11 \ \in T_{2154} $, $ 3344\ 11233\ 12\ 1\ \in T_{1254} $
, $13344\ 1233\ 2\ 11\ \in T_{2145} $, $ 13344\ 1233\ 12\ 1\ \in 
T_{1245}  $ which correspond to all the permutations 
above $3412 $ ; it is also congruent to the words 
$3344\ 23\ 2\ 11113 $ , $ 34\ 12334\ 2\ 1113 $, $3344\ 3\ 11223 
\ 11 $, $4\ 13334\ 1223\ 11 $ but these words do not belong 
to respectively $T_{5124} , T_{4152} , T_{2514} , T_{2451} $ (which 
are just below in the Ehresmann order) because the 
flag condition 5.5 is violated. Thus $t$ is 
congruent to a word in $T'_{2154} $. Proposition 5.6 
can now be reformulated :

\vskip 5mm
\noindent
\bf Proposition 5.8.        \rm Let $J$ be a partition, $\mu$ a 
permutation, $H=J^\mu $ , $I$ the partition conjugate to $J$ 
. Then $T'_H $ is congruent ${\cal U}(I,\mu) $.

\vskip 5mm
The key of the preceeding tableau is $\matrix{
4 \cr 3 &4 \cr 2 &3 &4 &4 \cr 1 &1 &3 &3 &3 \cr} $ , 
i.e. is equal to ${\bf K\rm}(3412,5421) $, in accordance with 
the fact that  $(5421)^{3412} $ is equal to $2154 $.

\vskip 10mm
\noindent
\bf6. Appendix.   \rm Let $U$ , $\Xi$ be two sets 
, $\Xi^* $ the free monoid generated by $\Xi$ . 
An \it action \rm of $\Xi^* $ on $U$ is a \it function 
\rm(not everywhere defined ; we use the 
symbol $\emptyset$ for the points of indeterminacy) 
: $U \times \Xi^*  \rightarrow U \cup \{ \emptyset \}  $ such that 
$u(\xi\xi' ) = (u\xi )\xi' $ and  $ u\xi = \emptyset \Rightarrow u\xi\xi' = \emptyset  $ 
for any $u \in U , \xi , \xi'\in \Xi  $.

Let $\Xi$ be finite and totally ordered :
$ \Xi = \{ \xi_1 , \ldots, \xi_{p+1} \} $. Suppose 
that "Moore-Coxeter" relations hold, 
i.e. that for any pair $\xi_i = \sigma , \xi_j = \tau $
and any u in $U$ , one has identically :
\vskip 5mm
\noindent
\bf(6.1)  \rm\quad $ u\xi \neq \emptyset \ \Rightarrow \ u \xi\xi = u$

\noindent
\bf(6.2)  \rm\quad if $|i-j| \geq 2 \ , \   u\sigma\tau = u\tau\sigma $

\noindent
\bf(6.3)  \rm\quad if $ |i-j| = 1  \ , \  u\sigma\tau\sigma = u\tau\sigma\tau  $.
\vskip 5mm
\noindent
\bf Remark 6.4. \rm\it1) \rm Let $|i-j| = 1 $ and $u\sigma, u\tau, u\sigma\tau  \neq \emptyset $,
 then  $u\sigma\tau\sigma = u\tau\sigma\tau \neq \emptyset $.

            \it2) \rm Let $|i-j| \geq 2  $ and 
$u\sigma, u\tau \neq \emptyset  $. Then  $ u\sigma\tau = u\tau\sigma  \neq \emptyset  $.

\vskip 5mm
\noindent Proof of \it1) \rm: $u\tau \neq \emptyset  $ implies  $(u\tau)\tau = u  $
according to 6.1 ; the hypothesis 
becomes $(u\tau)\tau , (u\tau)\sigma\tau , (u\tau)\tau\sigma\tau  \neq \emptyset $ 
showing that $(u\tau)\sigma\tau\sigma = (u\tau)\tau\sigma\tau \neq \emptyset  $ by 6.3. 
Therefore, $\emptyset \neq (u\tau)\sigma\tau\sigma\sigma = 
(u\tau)\tau\sigma\tau\sigma = u\sigma\tau\sigma $ as required.

\noindent Proof of \it2) \rm: As above, we use 6.1 to write 
$u\sigma = (u\tau)\tau\sigma $ ; according to 6.2,
$(u\tau)\tau\sigma = (u\tau)\sigma\tau $ ; since 
$u\sigma \neq \emptyset $ , $u\tau\sigma\tau $ is different from $\emptyset$ as well as its 
factor $u\tau\sigma $ , and $u\sigma\tau $ by symmetry.\hfill      $Q.E.D.$

\vskip 5mm
Choose any $u = u_0  $ in $U$ . 
The three preceeding axioms allow to 
identify the orbit $\Omega = \{ u\xi : u\xi \neq \emptyset \} $ 
to a quotient (the $u\xi $ need not 
to be all 
different) of a subset of ${\cal S}(p+1) $ , $u$ 
being sent to the identity element of 
${S}(p+1)$. The following proposition 
gives a necessary and sufficient 
condition for the orbit to be a quotient of 
the full symmetric group.

\vskip 5mm
\noindent
\bf Proposition 6.5.   \rm Let $n,m \geq 1 $, 
$p=n+m $ and set $\rho = \xi_n , \Xi_1 = \{ \xi_1, \ldots ,\xi_{n-1} \} $, 
$ \Xi_2 = \{ \xi_{n+1}, \ldots, \xi_{p-1} \} $. 
Assume that both $u\Xi_1^* $ and $u\Xi_2^* $ do not 
contain $\emptyset$ and that 
$  \xi_1\in \Xi_1^* , \xi_2\in \Xi_2^*  \Rightarrow u \xi_1 \xi_2 \rho \neq \emptyset  $ .

Then $ u \Xi^* $ does not contain $\emptyset$ .

\vskip 5mm
Proof. We can suppose $n \leq m $ by symmetry,
 and deduce the general case from 
the case where all the points $\neq \emptyset $ 
in $u\Xi^* $ are different. Thus the orbit $\Omega$ is 
a subset of the symmetric group and we 
write its elements as permutations.
If $n=m=1 $, there is nothing to prove. 
Consider the case where $n=1 , m=2 $. 
Then $\Xi_1 $ is void , $\Xi_2 = \{ \xi_2 \} , \rho = \xi_1 $ .
 By hypothesis, $u = 123 , u\rho = 213 $, 
$u\xi_2 = 312 $ and $u\xi_2\rho = 312 $ are all 
different from $\emptyset$ . Thus taking $u' = 213 , 
\sigma=\rho , \xi_2=\tau $ in 6.3, we get that 
$u'\tau = u\rho\xi_2 = 231 \ , \ u'\tau\sigma = u\rho\xi_2\rho = 321 $ are 
different from $\emptyset$ ; this proves the proposition in this case. 

Let again $n=1$ and $m \geq 3 $. 
As above, $\rho=\xi_1 $ and $\Xi_1 $ is void. Using 
induction on $m$ , we have that $\Omega$ 
contains all the permutations such that their 
rightmost letter is $\neq 1 $. In particular, for any 
$i,j > 1 $, $\Omega$ contains all the 
permutations such that their restriction to the third 
righmost letters is 
$1ij , i1j, 1ji $ or $j1i $. 
Repeating the same argument with $\sigma = \xi_{p-2} $ and $\tau = 
\xi_{p-1} $, we conclude that $\Omega$ contains all the 
permutations such that their 
right factor of length $3$ is $ij1 $ or $ji1 $ ,
 concluding the proof of the 
proposition for $n =1 $.

Consider now the general case where $n \geq 2 , m \geq 1 $
 . For any $k \leq n $, we can 
find some $\xi$ in $\Xi_1^* $ such that the 
first (ie. left) letter of $u\xi $ is $k$ . 
Thus by induction on $n$, i.e. 
by considering the restriction of $u\xi $ to all 
its letters except the first, we have that 
$\Omega$ contains all the permutations 
such that their first letter is $h \leq k $. 
Considering now the first three 
letters on the left and applying the same 
argument as for the case of $n=1 $, 
we conclude that $\Omega$ is the full symmetric group.     
\hfill  $Q.E.D.$

\vskip 5mm
The action of "commutation" of columns seen in section 2 satisfy the 
axioms 6.1, 6.2 and 6.3 . Only 6.3 is not straightforward. Since it 
involves only triples of consecutive columns in a word, it needs to be 
checked only for 3-columns words. This we do just now.

\vskip 5mm
\noindent 
\bf Lemma 6.6. \rm Let $w$ be a 3-columns word, $\sigma$
 and $\tau$ be the two generators of 
${\cal S}(3) $. Then $\big\{ w\sigma , w\sigma\tau , w\sigma\tau\sigma \neq \emptyset \big\} \Rightarrow \big\{ w\tau , w\tau\sigma \neq \emptyset $
 \&  $ w\sigma\tau\sigma = w\tau\sigma\tau \big\} $.

\vskip 5mm
\noindent Proof. One of the four words 
$w$ , $w\sigma$ , $w\sigma\tau$ , $w\sigma\tau\sigma$ has its shape decreasing
or increasing. Let it be $w\sigma = v_1 \bullet v_2 \bullet v_3 $.
 Recall that a 2-columns word $w$ is 
a tableau or a contretableau iff $w^{\flat } \neq \emptyset $
, i.e. iff $w$ is frank, and that a 
word is a tableau (resp. a contretableau) if each factor made of two 
consecutive columns is such. 
The two factors $v_1v_2 $ and $v_2v_3 $ being frank, $w\sigma $ 
is a tableau or a contretableau. According to 2.6.\it3 \rm, the action of 
permutation of columns on a tableau or a contretableau generate the frank 
words in its class : thus $w, w\sigma, w\sigma\tau, w\sigma\tau\sigma=w\tau\sigma\tau, w\tau\sigma , w\tau $ 
are the frank words in the class of $w\sigma $.

Suppose now that this is $w = v_1 \bullet v_2 \bullet v_3  $ 
which has a decreasing shape 
$\Vert w\Vert = ijh $ , and let $t$ be the insertion tableau of 
$w$ and $\sigma$ be the first 
generator of ${\cal S}(3)$. Since $v_1v_2\sigma \neq \emptyset $,
 the word $v_1\bullet v_2  $ is a tableau and this 
determines  $t \cap \{ 1, \ldots,i+j \} $.
 Since $v_1\bullet v_2\bullet v_3 \sigma\tau \neq \emptyset $ , the digit $i+j+h $
cannot be in the first column of $t$ ; 
since $v_1\bullet v_2\bullet v_3 \sigma\tau\sigma \neq \emptyset $ , it cannot be 
either in the second column of $t$. 
It must be in the third, which means that $t$ is 
equal to $\big[i\cdot\cdot\cdot1\big]\big[(i+j)\cdot\cdot\cdot(i+1)\big]\*\big[(i+j+h)\cdot\cdot\cdot(i+j+1)\big] = ijh\bf M \rm$.
 Thus $w$ is a 
tableau and we conclude as before. This reasoning also applies to the case 
where $\Vert w\Vert $ is increasing, since then 
$\Vert w\sigma\tau\sigma\Vert $ is decreasing and we can 
exchange the r\^ole of $w$ and $w\sigma\tau\sigma $ .     \hfill  $ Q.E.D.$

\vskip 5mm

Pictorially, hypothesis 6.6 is that if the four consecutive words 
$w \rightarrow w\sigma \rightarrow w\sigma\tau \rightarrow w\sigma\tau\sigma $ are different from $\emptyset$ , 
then we can "close the hexagon " :

$$ \matrix{  & &w\sigma  &\longrightarrow \ &w\sigma\tau  \cr
&\nearrow & & & &\searrow \cr
w & & & & & &w\sigma\tau\sigma = w\tau\sigma\tau \cr
&\nwarrow & & & &\swarrow \cr
& &w\tau &\longleftarrow \ &w\tau\sigma }$$




Let us finish with an example of a word whose orbit (under commutation 
of columns) is not a quotient of the full symmetric group.

Let $w = 31\bullet 42\bullet 4\bullet 51 $, 
and $\sigma, \rho, \tau $ be the three generators of ${\cal S}(4) $ .
 We get four double points : $ w=w\sigma , w\rho = 31 \ 4 \ 42 \ 51 
= w\sigma\rho , w\rho\sigma = \omega\rho\sigma\rho = 
3\bullet 41\bullet 42\bullet 51 , w\tau = w\tau\sigma = 31\bullet 42\bullet 41\bullet 5 $.
 Since the words $42\bullet 41$ and $42\bullet 51$ are 
not frank, all the neighbours  $w\rho\tau, w\tau\rho , w\sigma\tau\rho , w\sigma\rho\tau, w\rho\sigma\tau $ 
and $w\sigma\rho\sigma\tau $ are $\emptyset$ 
and thus the orbit $\Omega$ of $w$ is restricted 
to the enumerated four double 
points. Indeed, condition 2.8.\it3 \rm to ensure that 
$w$ be frank is exactly that 
$42\bullet 4 $ (central factor of $w$) and 
$42\bullet 41$ (central factor of $w\sigma$ , $w\tau$ and 
$w\tau\sigma $) 
should be frank . Since this not the case for the last word, we already 
knew from th.2.8 that $\Omega$ could not be a 
quotient of the full symmetric group.

\vskip 10mm
\centerline{\bf REFERENCES} 
\vskip 5mm

\noindent \bf[B-G-G]  \rm Bernstein I.N., Gelfand I.M., 
Gelfand S.I. UMN.\bf28 \rm(1973)1-26 .

\noindent \bf[B-K]  \rm A.BENDER, D.E.KNUTH, 
Enumeration of plane partitions, J.Comb.Th. \bf A 
13 \rm(1972) 40-54.

\noindent\bf[B] \rm A.BJ�RNER , Ordering of Coxeter 
Groups, Contemp.M. \bf3\rm4 (1984) 175-195.

\noindent \bf[Bo] \rm N.BOURBAKI, El\'ements de 
Math\'ematiques modernes, Alg\`ebre ch.1, Paris, New 
York , C.C.L.S. (1971).

\noindent \bf[D1] \rm M.DEMAZURE, D\'esingularisation des 
vari\'et\'es de Schubert,
Ann.E.N.S. \bf6 \rm(1974) 163-172.

\noindent \bf[D2] \rm M.DEMAZURE, Une formule des 
caract\`eres, Bull.Sc.M. \bf98 \rm(1974)163-172. 

\noindent \bf[E] \rm C.EHRESMANN, Sur la topologie de 
certains espaces homog\`enes, Ann. M. (2)\bf35 
\rm(1934) 396-443 .

\noindent
\bf[Gr] \rm A.GROTHENDIECK, Sur quelques propri\'et\'es 
fondamentales en th\'eorie des intersections, 
S\'eminaire Chevalley, Paris (1958).

\noindent
\bf[K-L] \rm D.KAZHDAN and G.LUSZTIG, Representations 
of Coxeter Groups and Hecke Algebras, Invent. 
\bf53 \rm(1979) 165-184 .

\noindent
\bf[K] \rm D.E.KNUTH, Permutations matrices and 
generalized Young tableaux, 
Pac.J.Math. \bf34 \rm(1970) 709-727

\noindent
\bf[L-M-S] \rm V.LAKSHMIBAI, C.MUSILI and C.S.SESHADRI, 
Geometry of G/P IV, 
\it Proc. Indian Acad.Sc. \rm\bf88A \rm(1979) 280-362 .

\noindent
\bf[L-S1] \rm A.LASCOUX \& M.P.SCH\"UTZENBERGER, Le 
Monoide Plaxique, Atti del C.N.R., Roma,  
(1981)

\noindent
\bf[L-S2] \rm A.LASCOUX \& M.P.SCH\"UTZENBERGER , 
Symmetry and Flag Manifolds, Lect. Notes in Math. 
(1983) \bf996\rm.

\noindent
\bf[L-S3] \rm A.LASCOUX \& M.P.SCH\"UTZENBERGER,   
Symmetrization operators on po\-ly\-no\-mial rings, 
Funk. Anal. \bf21 \rm(1987) 77-78 .

\noindent
\bf[L-S4] \rm A.LASCOUX \& M.P.SCH\"UTZENBERGER, Tableaux 
and non commutative Schubert polynomials, to 
appear in FunK. Anal.

\noindent
\bf[L-S5]  \rm A.LASCOUX, Anneau de Grothendieck de la 
vari\'et\'e de dra\-peaux, \it submitted to the \rm Comit\'e 
d'\'e\-va\-lua\-tion des hom\-mages \`a Grothendieck (1988).

\noindent
\bf[L-S6] \rm A.LASCOUX \& M.P.SCH\"UTZENBERGER, Ar\^etes 
et tableaux , S\'eminaire Lotha\-rin\-gien de 
Combinatoire, Cagliari (1988).

\noindent
\bf[L-W] \rm V.LAKSHMIBAI, J.WEYMAN, Bases standards, 
C.R.Acad.Sc.Paris, (1988).

\noindent
\bf[M]  \rm I.G.MACDONALD, Symmetric Functions and Hall 
Polynomials, Oxford Mono., Oxford (1979).79).

\noindent
\bf[Mc] \rm Major P.MACMAHON, Combinatory Analysis, 
Chelsea reprints, New York (1960).

\noindent
\bf[Sche] \rm C.SCHENSTED, Longest increasing and 
decreasing sequences, Canad.J.Math. \bf13 \rm(1961) 
179-191.

\noindent
\bf[Schu] \rm M.P.SCH\"UTZENBERGER, Quelques remarques 
sur une construction de Schensted, Math.Scand. 
\bf12 \rm(1963) 117-128 .

\vskip 5mm
\it L.I.T.P., U.E.R.Maths Paris 7, 2 Place Jussieu, 
75251 PARIS Ced \rm05

\bye



