%%%%    Hyderabad.tex change format -> HermesGroth.tex  04.04.05  
%  
%%%    Fichier Hermes.tex 
\magnification=1200
\voffset= -1cm
\hoffset=  1cm
\hsize  = 12cm   
\vsize  = 18.4cm
\parindent 12pt 
\parskip=3pt plus 2pt minus 1pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\font\tenpc=cmcsc10
\font\eightpc=cmr8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10       \font\tenbboard=msbm10
\font\eightgoth=eufm8      \font\eightbboard=msbm8
\font\sevengoth=eufm7      \font\sevenbboard=msbm7
\font\sixgoth=eufm6        \font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt \r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}\let\old=\oldstyle
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard 
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}\let\old=\oldstyle
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sixbboard
  \scriptscriptfont\bboardfam=\fivebboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \let\petcap=\eightpc
  \normalbaselines\rm}

\frenchspacing   \tenpoint

\let\bb=\bboard

%���������������������� dactylographie fran�aise �����������������

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

%__________________________________________________________________________

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \vskip 2pt
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000

%__________________________________________________________________________

\newtoks\auteurcourant \newtoks\titrecourant   \newbox\seroul

\auteurcourant={\hfil} \titrecourant={\hfil}  

\def\titleheadline{\hfil}

\newif\iftpage       \tpagetrue         

\def\coinshaut{\setbox\seroul=\line{\dimen\seroul=\hsize
\advance\dimen\seroul by 1cm
\hss\vrule height 0pt depth 5mm width .2pt%
\vrule height .2pt depth 0pt width 5mm
\kern\dimen\seroul
\vrule height .2pt depth 0pt width 5mm%
\vrule height 0pt depth 5mm width.2pt\hss}\ht\seroul=0pt\wd\seroul=0pt\box\seroul}

\def\coinsbas{\setbox\seroul=\line{\dimen\seroul=\hsize
\advance\dimen\seroul by 1cm
\hss\vrule height 5mm width .2pt%
\vrule height .2pt width 5mm
\kern\dimen\seroul
\vrule height .2pt width 5mm%
\vrule height 5mm width .2pt\hss}\ht\seroul=0pt\dp\seroul=0pt\box\seroul}


\def\plainoutput{\shipout\vbox{
\coinshaut
\kern 2pc
\makeheadline
\pagebody
%\makefootline
\kern 2pc
\coinsbas}
\ifnum\outputpenalty>-20000
\else\dosupereject\fi
\global\advancepageno}

\output{\plainoutput \global\tpagefalse}

\headline={%
\iftpage \titleheadline
\else   \ifodd\pageno\rightheadline
        \else\leftheadline
        \fi
\fi}

%\def\titlefootline{\hfil} \def\rightfootline{\hfil}    \def\leftfootline{\hfil}

%\footline={\iftpage\titlefootline\else
%  {\ifodd\pageno\rightfootline\else\leftfootline\fi}\fi}

\def\leftheadline{\line{\strut\rlap{\tenrm\folio}\kern10mm\eightit\the\auteurcourant\hfill}}

\def\rightheadline{\line{\strut\hfill\eightit\the\titrecourant\kern 10mm\llap{\tenrm\folio}}}

\def\titleheadline{%
\ifodd\pageno \line{\strut\hfill\tenrm\folio}%
\else         \line{\strut\tenrm\folio\hfill}%
\fi}

%__________________________________________________________________________


\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak\hskip 0em
  plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}

\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip .5cm plus .1cm minus .1cm\penalty -100
              \noindent{\bf #1}
              \vskip 5pt
              \penalty 1000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                 {\it #1}\pointir}

%les differents retraits, voir aussi \item

\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}

% pour les titres en deux lignes et les sections sans point-tiret :

\def\titrea#1|#2|%
{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -100
  \leftline{\bf #1}
  \leftline{\bf #2}
  \vskip 5pt
  \penalty 1000 }

\def\sectiona#1|%
{\par\vskip .3cm
  {\bf #1.}
  \par\penalty 1000\vskip 3pt }

\def\ssectiona#1|%
{\par\vskip .2cm
  {\it #1.}
  \par\penalty 1000\vskip 2pt }

\long\def\th#1|#2\finth{\par\vskip 5pt
              {\petcap #1\pointir}{\it #2}\par\vskip 3pt}

\long\def\tha#1|#2\fintha{\par\vskip 5pt
                    {\petcap #1.}\par\penalty 1000{\it #2}\par\vskip 3pt}
\def\cf{{\it cf}}

\def\rem#1|{\par\vskip 5pt
                 {{\it #1}\pointir}}

\def\rema#1|{\par\vskip 5pt
                 {{\it #1.}\par\penalty 1000}}

%__________________________________________________________________________

\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|%
{{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, t.\penalty 1000\ {\bf #5}, {\oldstyle #6},
     p.\penalty 1000\ #7.\filbreak}}

%reference pour un livre :
\def\livre#1|#2|#3|#4|%
{{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\filbreak}}

%reference complementaire :
\def\divers#1|#2|#3|%
{{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\filbreak}}

\mathchardef\conj="0365

\def\dem{\par{\it D\'emonstration}\pointir}

\def\proof{\par{\it Proof}\pointir}

\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

%\quad\hbox{\hskip 1pt\vrule width 4pt height 6pt
%depth 1.5pt\hskip 1pt}}

\def\cqfd{\penalty 500 \hbox{\qed}\par\vskip 3pt}
\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}

\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

\def\dleqno#1|{\hfil\kern-\displaywidth\rlap{$#1$}\kern\displaywidth
  \hfilneg}

\def\@lign{\tabskip\z@skip\everycr={}}

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}

\catcode`\@=12

%pour les restrictions des fonctions en mode centre et dans le texte

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}%
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen2=\ht1
            \advance\dimen2 by\dp1
            \divide \dimen2 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen2{}\right.$}}

\def\pv{\kern 2pt\string;\ }

\def\\#1{{\cal#1}}



%����������������������������������������������������������
% ��������������� pour qu'il la ferme ������������������� �
%����������������������������������������������������������

\showboxbreadth=-1  \showboxdepth=-1
%%%%%%%%%%%%%%%%   FIN DE FICHIER HERMES
%%%%%%%%                    AJOUT    %%%%%%%%%%%%%%%%%%%%%%%%%%
% petits tableaux ~E deux ou quatre lignes
\def\tabl#1|#2|{ {}_{#2}^{#1} }

\def\ttabl#1|#2|#3|#4|{%
\vbox{\hbox{$\tabl#1|#2|$} \hbox{$\tabl#3|#4|$} } }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Cyclic Permutations on words, Tableaux and Harmonic 
Polynomials}


\vskip 3mm

\centerline{Alain Lascoux }


\vskip 3mm

\hfill {\it mars 1990}


\vskip 3mm

\abstract{ 
The compatibility of tableaux with cyclic permutations provides 
a rank poset structure on the set of tableaux with a given 
evaluation, allowing the embedding of different sets of tableaux 
into each other. There results a decomposition of these sets
into smaller sets, the cardinals of which are multiplicities 
of isotypic components (for the symmetric group action) 
either in cohomology rings of flag manifolds or equivalently 
in spaces of harmonic polynomials. }


\titre 1. Introduction |

It has been known since the work of Young that tableaux provide a way
of explicitly describing the irreducible representations of the 
symmetric group over ${\bb{C}}$. It was soon realized by Littlewood,
Robinson, Weyl and others that irreducible characters (that is to
say {\it Schur functions}) are also given by tableaux ; we 
prefer to express this by lifting a Schur function into the sum 
of all tableaux of a given shape inside the free algebra (Th.2.3).


Tableaux are now special words in the free algebra. Cyclic permutations 
on words induce an operation on tableaux that we call \lq\lq cyclage" and 
give a rank-poset structure 
 on the set of tableaux with a given evaluation, the rank being an 
important invariant called the {\it cocharge} .
Cyclage connects any tableau to a row tableau which can be identified with 
a monomial in commuting variables (Prop.3.1). Inverting the cyclage lifts 
computations in the ring of polynomials to the level of tableaux, 
e.g. it lifts the permutation action of the symmetric group 
(lemma 4.1). 
 From this one can 
imbed canonically each of the sets of tableaux 
with a given evaluation into the set of {\it 
standard } tableaux, obtaining a partition of the set of standard 
tableaux into disjoint sets that we call {\it atoms} (Th.4.2 and 4.4).

The cocharge gives also the {\it Kostka-Foulkes polynomials} 
which are the coefficients in the expansion of Hall-Littlewood 
polynomials in the basis of Schur functions (Th.5.1)
. An interesting consequence 
of the construction is that the matrix of Kostka-Foulkes polynomials 
is the product of the incidence matrix (of the lattice of partitions )
 by a positive matrix, the entries of which 
correspond to the atoms (Cor.5.2).

Young introduced tableaux to obtain idempotents in the group algebra of the 
symmetric group, obtaining also multiplicities and bases of representations  
with the help of standard tableaux of a given shape. 
By identifying instead the regular representation with the cohomology ring 
of the flag manifold, one can further decompose the regular representation, 
with the elementary components corresponding to the atoms (Th.6.5).
 Tableaux furthermore provide explicit bases (as free modules) of the 
cohomology spaces of different flag manifolds (Prop.6.11).

Instead of cohomology rings, following Specht we may take 
spaces of harmonic polynomials. Cocharge and atoms provide 
multiplicities of representations 
for the action of the affine symmetric group (Th.7.4), and provide bases, 
notably Verma's basis (section 8).

Section 9 gives additional properties of atoms and shows how to generate 
them from two-rows tableaux.

The combinatorics of tableaux is a joint work with M.P.
Sch\" utzenberger and constitutes the more substantial part of this paper, 
 to which I have added a translation into geometrical terms.



\titre 2 . The plactic algebra |

Let ${\bb{A}}^*$ be the free monoid generated by the alphabet 
${\bb{A}} = \{ a_1<a_2<\cdots \} $ and  ${\bb{Z}}[{\bb{A}}^*]$ the free algebra
 of ${\bb{A}}$.
The elements of ${\bb{A}}^*$ are {\it words}. The degree of a word 
$w$ is denoted $|w|$, and its degree in a letter $a $ is 
denoted $|w|_a$. 
The image in the ring of polynomials 
${\bb{Z}}[{\bb{A}}] $ of a word $w$
 is called its {\it evaluation} and noted  $ev(w)$. 
We shall also use the exponent notation $ev(w) = e^I$, 
with $I = (|w|_{a_1}\, , \, |w|_{a_2}
\, , \, |w|_{a_3}\, , \ldots ) $. 
A word $w $ is {\it standard} iff 
there exists an integer $k $ such that  $ ev(w) = a_1 a_2 
\cdots a_k $.

A word is a {\it row} iff it is weakly increasing : 
$ w=x_1x_2x_3 \cdots $, $x_1\leq x_2\leq x_3\leq \cdots $, 
$x_i \in {\bb{A}} $.
The ring ${\bb{Z}}[{\bb{A}}]$ can be imbedded into the free algebra as the free
 
${\bb{Z}}$-module generated by rows (writing monomials as increasing words).
  A row $w= x_1 x_2 x_3\cdots $ {\it dominates} another
$w'= x'_1 x'_2 x'_3\cdots $ 
if $|w| \leq |w'|$ and 
$x_1 > x'_1 \ , x_2 > x'_2 \, \ldots $.

Every word admits a unique
factorization, called its {\it row-factorization}, as a product of
 a minimal number of rows $w = v_k \cdots v_2 v_1$. 
The shape $\Vert w\Vert $ of $w$ is the sequence of degrees 
$|v_k| , \ldots ,|v_1| $ of its rows.
A word is a {\it tableau } iff for its row-factorization 
$w = v_k \cdots v_2 v_1$, one has
\setbox3=\hbox{is weakly increasing}
\setbox4=\hbox{dominates}
\setbox5=\hbox{dominates}
$$\left\{\eqalign{ \ \Vert w\Vert \ \box3 &  \cr
v_k \ \box4 \ v_{k-1 }, \, \ldots \ ,\,
 &v_2 \ \box5 \ v_1 \cr } \right. $$

In other terms, a word is a tableau iff it is obtained by reading 
in the appropriate/French way a usual planar Young tableau.
Thus the word ${bcd\, aabd}$ is a tableau that one can planarly display as 
${}_{aabd }^{bcd}\ .$

The {\it Schur function} $S_I$ of index a partition $I$ is the 
sum of all tableaux of shape $I$ in the free algebra .

We can see that the product $S_1 \cdot S_2$
is equal to the sum $ S_{12}+ S_3$ , but that it is 
 different from $S_2 \cdot S_1$. For, after 
deleting the words in common, we have on the left 
$\sum_{x<y} (yxx +yxy) + \sum_{x<y<z }(yxz +zxy )$, 
 and on the right 
$\sum_{x<y} (xyx +yyx) + \sum_{x<y<z }(yzx +xzy) $.

To force equality, one of the principal 
methods is the following set 
of elementary relations 
(due to Knuth), for $x<y<z$ in ${\bb{A}}$ :
$$\leqalignno{ yxx \equiv xyx \quad &; \quad  yxy \equiv yyx  &(2.1) \cr
yxz \equiv yzx \quad &; \quad zxy \equiv xzy &(2.2)  \cr } $$

These relations generate a congruence 
which is called the
{\it plactic congruence} and denoted $\equiv$~. This is the same as 
the algebraic formalization of \lq\lq 
Schensted's construction" which produces, for any word, 
the only tableau which is congruent to it.
The {\it plactic monoid} ${\bb{A}}^* / \equiv $  is the associated 
quotient of ${\bb{A}}^*$ and its algebra, the {\it plactic ring}  
${\bb{Z}}[{\bb{A}}^* / \equiv]$. 

The ring of symmetric polynomials in ${\bb{A}}$, 
${\bb{Z}}[{\bb{A}}]^{\goth{S}} $ , 
is canonically imbedded into the plactic algebra, according
to the following theorem (see [L\& S1] ) :

\def\hfl#1{{\buildrel{#1}\over
             {\hbox to 12mm{\rightarrowfill}}}}
\def\vfl#1#2{\llap{$\scriptstyle #1$}\left\uparrow
\vbox to 4mm{}\right.\rlap{$\scriptstyle #2$}}
\def\diagram#1{\def\normalbaselines{\baselineskip=2pt
\lineskip=6pt\lineskiplimit=1pt} \matrix{#1}}

\setbox13=\hbox{$\scriptstyle{\ Free\, module}$}
\setbox14=\hbox{$\scriptstyle{generated \, by \, the \, S_I}$}
\setbox15=\vbox{\box13  \box14}
\setbox16=\hbox{$\left\{\raise -2mm \box15\right\}$ }
\setbox17=\hbox{$ {\bb{Z}}[{\bb{A}}]^{\goth{S}}    $}
\setbox18=\hbox{$ {\bb{Z}}[{\bb{A}}]^{\goth{S}}    $}
\th  Theorem 2.3 |  The submodule of
${\bb{Z}}[{\bb{A}}^* /\equiv]$ generated by the images of the $S_I$ is 
a commutative 
algebra isomorphic to ${\bb{Z}}[{\bb{A}}]^{\goth{S}}$. In other 
words, one has the following diagram :
$$\diagram{
{\bb{Z}}[{\bb{A}}^*] &\hfl{}{} &{\bb{Z}}[{\bb{A}}^*/\equiv] &\hfl{}{} &{\bb{Z}}
[{\bb{A}}] \cr   
\vfl{}{} &&\vfl{}{} &&\vfl{}{}\cr
\box16 &\hfl{}{} &\box17&\hfl{\sim}{} &\box18 \cr }$$
  \finth




\titre 3 . Cyclic permutations |

Let $t = xw $ be a tableau, $x$ being its initial letter. The word 
$wx$ is congruent to another tableau $t'\equiv wx$. If $t$ has at least two 
rows, then $t \rightarrow t'$ is called a {\it cyclage} ; the inverse of a 
cyclage, when it exists, is called a {\it cocyclage}. From 
the Schensted construction it is clear that if $t_1 \rightarrow t'$ and 
$t_2 \rightarrow t'$ are two cyclages leading to the same tableau, then 
the shapes of $t_1$ and $t_2$ are different. Thus, shape is sufficient to 
differentiate between all the cocyclages of a given tableau. 
In section 9 , we describe a more general cyclage and show how 
its properties are related to the Pieri decomposition of the product 
of a Schur function by an elementary symmetric function.

We need there only the following property, which is proved 
in [L\& S1]:

\th Proposition 3.1  |The cyclage induces a rank-poset
structure on the set of tableaux with a given evaluation $u $ ;
the row $u$ is the unique minimal element. \finth

We shall note the above poset ${\cal{T}}(u)$, or ${\cal{T}}(I)$, for 
$u = a_1^{I_1}a_2^{I_2 } \cdots $.
Let us call the rank of a tableau $t$ for 
this structure the {\it cocharge} $\nu(t)$, putting 
$\nu(u) = 0$. An algorithm for computing directly the cocharge 
is given in [Mac, p.129] (in fact, what is given there is the {\it 
charge} which is the complement of the cocharge).

\noindent
\it Example \rm3.2 \pointir  The poset ${\cal{T}} (321)$, for the alphabet 
$\{ a,b,c \}$, is

\setbox3=\hbox{\ttabl {}|c|bb|aaa| }
\setbox4=\hbox{\ttabl |c|b|aaab|}
$$\matrix{ Charge \quad &
& & Poset  & & &\quad Cocharge\cr 
\noalign{\vskip 2pt}
0& & &\box3  & & &4\cr 
&&&\big\downarrow\cr
1&\box4 & &{ }_{aaac }^{bb }& &{ }_{aaa }^{bbc }&3\cr
&\big\downarrow & &\big\downarrow & \swarrow \cr
2&{}_{aaabc}^b & &{}_{aaab}^{bc} & & &2\cr
& &\searrow  &\big\downarrow \cr
3& & &{}_{aaabb}^c &&&1 \cr
& & &\big\downarrow \cr
4 & & &{}_{aaabbc}&&&0  \cr }$$

\titre 4. Canonical embeddings of tableaux |


There are many linear operations on ${\bb{Z}}[{\bb{A}}]$ which can be extended 
to the plactic or free algebra,
thanks to the cyclage connecting any tableau to a row (prop.3.1).

For example, the symmetric group ${\goth{S}}({\bb{A}})$ acts by permutation 
on ${\bb{Z}}[{\bb{A}}]$ : 
$ a,b, \ldots \longrightarrow a\mu, b\mu, \ldots $ for $\mu \in {\goth{S}}
({\bb{A}})$ induces 
 $a^{I_a}b^{I_b }\cdots \longrightarrow a^{I_a\mu}b^{I_b\mu }\cdots $ for 
$I \in {\bb{N}}^{\bb{A}}$.

We have defined more generally in [L \& S1] an action of ${\goth{S}}({\bb{A}})$ 
on the free algebra : 
$$(w \in {\bb{A}}^* , \mu\in {\goth{S}}({\bb{A}}) ) \rightarrow w^\mu \in 
{\bb{A}}^* \quad .$$

This action is compatible with the plactic 
congruence and with the cyclage, as stated in the following lemma 
(\it cf. \rm[L \&S1, th.4.6]) :
\th Lemma 4.1 | Let $v, w $ be two words, $\mu $ be a permutation.
Then 

i) \quad $v \equiv w \quad \Rightarrow \quad v^\mu \equiv w^\mu\quad ,$

ii) $w$ is a tableau $\Leftrightarrow w^\mu$ is a tableau ; moreovoer, 
the shapes of 
$w$ and $w^\mu$ are identical,

iii)\quad $w =xw' , w^\mu = y w'' $, with $x,y \in {\bb{A}}$ 
$\Rightarrow (w' x)^\mu = w''y \quad .$
\finth

Given a tableau $t$ and a permutation $\mu$, the tableau 
$t^\mu$ is determined by the above lemma. For cycle the tableau 
 to the row : 
$t= t_0 \rightarrow t_1 \rightarrow \cdots \rightarrow t_k = ev(t)$. 
We obtain $t^\mu$ by cocyclage, 
starting from the row $\big(ev(t)\big)^\mu$ :
$t^\mu \leftarrow t_1^\mu \leftarrow \cdots \leftarrow t_k^\mu$ ; 
knowing $t_{j+1}^\mu$, we determine $t_j^\mu$ among the different tableaux 
which cycle to $t_{j+1}^\mu$ by the condition that its shape equals that 
of $t_j$.

For example, the symmetric group ${\goth{S}}(a,b,c)$ exchanges the following 
6 chains of cyclages :
\setbox3=\hbox{\ttabl |c|bb|aaa|}
\setbox4=\hbox{\ttabl |c|bb|aab|}
\setbox6=\hbox{\ttabl |c|bc|aac|}
\setbox8=\hbox{\ttabl |c|bc|abc|}
\setbox7=\hbox{\ttabl |c|bc|abb|}
\setbox5=\hbox{\ttabl |c|bc|aaa|}
$$\eqalign{
 \box3 \rightarrow {}_{aaac}^{bb} \rightarrow {}_{aaab}^{bc} 
\rightarrow {}_{aaabb}^{c} \rightarrow {}_{aaabbc} \ &; \ 
\box4 \rightarrow {}_{aaac}^{bb} \rightarrow {}_{aaab}^{bc} 
\rightarrow {}_{aabbb}^{c} \rightarrow {}_{aabbbc} \ ; \cr 
 \box5 \rightarrow {}_{aaac}^{bc} \rightarrow {}_{aaab}^{cc} 
\rightarrow {}_{aaabc}^{c} \rightarrow {}_{aaabcc} \ &; \ 
\box6 \rightarrow {}_{aacc}^{bc} \rightarrow {}_{aabc}^{cc} 
\rightarrow {}_{aabcc}^{c} \rightarrow {}_{aabccc} \ ; \cr 
 \box7 \ \rightarrow \ {}_{abbc}^{bc} \rightarrow {}_{abbb}^{cc} 
\rightarrow {}_{abbbc}^{c} \rightarrow {}_{abbbcc} \ &; \ 
\box8 \rightarrow {}_{abcc}^{bc} \rightarrow {}_{abbc}^{cc} 
\rightarrow {}_{abbcc}^{c} \rightarrow {}_{abbccc} \ . \cr }$$ 




Consider the following transformation $\varphi$ on words :

\quad 
\lq\lq change the letter $a$ which is furthest to the right into 
a $b$ ; if there are no $a $' s, send the word to 0 " \ . 

Let moreover $I \in {\bb{N}}^{\bb{A}}$ be such that $I_a = m > I_b = n $. 
It is clear that in this case $\varphi$ transforms a tableau of evaluation 
$I$ into a tableau of evaluation $I_a -1 , I_b +1 , I_c , \ldots$ 
of the same shape, 
and that $\varphi$ is compatible with the cyclage. In other words, 
$\varphi$ induces an embedding, still denoted $\varphi$, of the rank poset
 ${\cal{T}}(I_a I_b I_c \ldots)$ into the rank poset 
 ${\cal{T}}(I_a -1 \  I_b+1 \  I_c \ldots)$, and the image of a cyclage 
is a cyclage. Combining $\varphi$ with the action of the symmetric 
group, we obtain :

\th Theorem 4.2  |Let $I, J $ be two partitions : 
$I \leq J $ ; $\check I \in {\bb{N}}^{\bb{A}} $ a permutation of $I$, 
$\check J \in {\bb{N}}^{\bb{A}} $ a permutation of $J$. Then there exists 
a canonical embedding of the rank poset 
${\cal{T}}(\check I)$ into the rank poset ${\cal{T}}(\check J)$. 
\finth

The embedding of ${\cal{T}}(\check I)$ into ${\cal{T}}(1 \ldots 1)$ is 
called the {\it standardization } and is denoted $\theta$.
It should be noticed that $\theta$ does not co\"\i ncide 
with the standardization mentionned by 
[Sche, th.4] obtained by numbering the successive occurrences of 
$a$ from left to right, then of $b$, etc. 
To obtain the theorem, we just need to observe that 
the order on partitions (decreasing from left to right) 
is generated by the vector addition
$I \rightarrow
 I + (0 \ldots 0\,  -\! 1 \ 0 \ldots 0\ 1 \ 0 \ldots)$. \hfil\break
Therefore there exists at least one sequence of permutations 
$\mu, \eta, \ldots , \zeta$ which provides the required embedding 
by the composite \hfill\break 
$ {\cal{T}} (\check I) 
{\buildrel \mu \over\longrightarrow } {\cal{T}}(\check I^\mu) 
{\buildrel \varphi\over \hookrightarrow} {\cal{T}}(H) 
{\buildrel \eta \over\longrightarrow } {\cal{T}}(\check H^\eta) 
{\buildrel \varphi\over \hookrightarrow} 
\ldots \quad 
{\buildrel \varphi\over \hookrightarrow} 
{\cal{T}}(\check J^{\zeta^{-1}}) 
{\buildrel \zeta \over\longrightarrow } {\cal{T}}(\check J)  \quad . $

The fact that the embedding is canonical is provided by the 
compatibility with the cyclage of $\varphi $ and of the action of 
${\goth{S}}({\bb{A}}) $ : given $t \in 
{\cal{T}}(\check I)$, we cycle it to the row $ev(t)$; now the image of $t$ 
in ${\cal{T}}(\check J)$ is obtained by the corresponding cocylages, 
starting from the row in 
${\cal{T}}(\check J)$ \quad \qed

For example, the poset ${\cal{T}}(321)$ described in 3.2 is isomorphic to 
${\cal{T}}(312)$. Its image by $\varphi$ is a subposet of ${\cal{T}}(222)$:


\setbox11=\hbox to 35mm{\upbracefill}
\setbox12=\hbox{\kern 12mm ${\cal{T}}(312)$}
\setbox10=\vbox{\box11 \box12}
\setbox21=\hbox to 35mm{\upbracefill}
\setbox22=\hbox{\kern 12mm ${\cal{T}}(222)$}
\setbox20=\vbox{\box21 \box22}
\setbox23=\hbox{\box10 \kern 22mm \box20  }

\setbox3=\hbox{\ttabl |c|bc|aaa|}
\setbox4=\hbox{\ttabl |c|b|aaac|}
\setbox5=\hbox{\ttabl |cc|bb|aa|}
\setbox6=\hbox{\ttabl |c|bb|aac| }
\setbox7=\hbox{\ttabl |c|bc|aab|}
\setbox8=\hbox{\ttabl |c|b|aabc|}
$$\matrix{
& & & & &\quad & & & & &\box5 \cr
& & & & &      & & & & &\big\downarrow \cr
& & & & &      & & & & &\box6 \cr
& & & & &      & & & & &\big\downarrow \cr
& &\box3 & & & & & &\box7 & &{ }_{aacc }^{bb }  \cr 
&&\big\downarrow & & & & & &\big\downarrow &\swarrow \cr
\box4 & &{ }_{aaac }^{bc }& &{ }_{aaa }^{bcc }
& &\box8 & &{ }_{aabc }^{bc }& &{ }_{aab }^{bcc }\cr
\big\downarrow & &\big\downarrow & \swarrow 
& & &\big\downarrow & &\big\downarrow &\swarrow \cr
{}_{aaacc}^b & &{}_{aaab}^{cc} & & & &
{ }_{aabcc }^{b} & &{ }_{aabb }^{cc }\cr
&\searrow  &\big\downarrow & & & & &\searrow &\big\downarrow\cr
& &{}_{aaabc}^c & & & & & &{ }_{aabbc}^c \cr
& &\big\downarrow & & & & & &\big\downarrow \cr
& &{}_{aaabcc} & & & & & &{ }_{aabbcc } \cr
\noalign{\vskip 3mm}
\noalign{\box23} }$$

\noindent
\it Definition \rm4.3 \pointir Given a partition $J$, the {\it atom } 
${\cal{A}}(J)$ is the poset of standard tableaux 
$$ {\cal{A}}(J) := \, \theta\big({\cal{T}}(J)\big) \setminus \cup_{I<J} \, 
\theta\big({\cal{T}}(I)\big) \quad , $$
{\it i.e.} is the poset of standard tableaux which are images 
of tableaux of evaluation 
$e^J$, but not images of tableaux of evaluation $e^I$ with 
$I <J$.

The atomic decomposition of the set of standard tableaux 
${\cal{T}}(1 \ldots 1)$ pulls back to all the other sets 
of tableaux and gives :

\th Theorem 4.4  | For any partition $J $, the standardization 
$\theta $ is a bijection between the set ${\cal{T}}(J)$ and the disjoint 
union (on all partitions $I\leq J$) of the atoms ${\cal{A}}(I)$. 
The set $\theta^{-1}\big({\cal{A}}(J) \big) $ is the complement of the 
canonical images of all the ${\cal{T}}(I)$, $I<J$, in ${\cal{T}}(J)$.
\finth

For example, the 26 standard tableaux of degree 5 are distributed among 
the following 7 atoms (with the alphabet $\{1,\ldots, 5 \}$):

\setbox33=\hbox{\ttabl |32145|54213 |52413|}
\setbox3=\hbox{$\left\{ \raise -1mm\box33 \right. $}
\setbox43=\hbox{\ttabl |42513| 42135| 24135|}
\setbox4=\hbox{$\left\{ \raise -1mm\box43 \right. $}
\setbox51=\hbox{\kern 36mm Atoms}
\setbox52=\hbox to 8 cm{\downbracefill}
\setbox53=\vbox{\box51  \box52}
\setbox54=\hbox{Cocharge}
\setbox5=\hbox{\kern -1cm\box54 \kern 1cm \box53}

$$\matrix{
\noalign{\box5}
\noalign{\vskip 2pt}
10 &{ }_{54321 }\cr 
\noalign{\vskip 2pt}
9 &{}_{43215} \cr
\noalign{\vskip 4pt}
8 &\left\{ {}_{32514}^{53214}\right. \cr
\noalign{\vskip 4pt}
7 &\box3 \cr
\noalign{\vskip 4pt}
6 &\box4  & {}^{54312} \cr
\noalign{\vskip 4pt}
5 &\left\{ {}_{25134}^{52134}\right. 
&\left\{ {}_{43512}^{43125}\right. \cr
\noalign{\vskip 4pt}
4 &{}_{21345} &\left\{ {}_{35124}^{53124}\right. &{}_{53412} \cr
\noalign{\vskip 4pt}
3 & & {}^{31245} &{}^{34125}  &{}^{54123} \cr
\noalign{\vskip 2pt}
2 & &                      & &{}^{41235} &{}^{45123} \cr
\noalign{\vskip 2pt}
1 & &  & & & &{}^{51234} \cr
\noalign{\vskip 2pt}
0 & & &  & & &  &{}^{12345} \cr
\noalign{\vskip 2pt}
 &{\cal{A}}(11111) &{\cal{A}}(1112) &{\cal{A}}(122) &{\cal{A}}(113) 
&{\cal{A}}(23) &{\cal{A}}(14) &{\cal{A}}(5) \cr
}$$



\titre 5 . Kostka-Foulkes polynomials |

Given a tableau $t$, we have called cocharge of $t$ the number
 of cyclages needed to obtain from it the row of the same evaluation.
Any set of tableaux ${\cal{T}}$ gives rise to a cocharge polynomial 
$ \sum_{t\in{\cal{T}}} q^{\nu(t)}$. In particular,
 for any  $H \in {\bb{N}}^{\bb{A}}$, and any partition $J$, the 
{\it Kostka-Foulkes polynomial} ${\cal{K}}(H,J)$ is the sum 
$ \sum q^{\nu(t)}$ taken over all tableaux of evaluation $e^H $
and shape $J$ , \it cf \rm[Mac, p.126].
  Kostka-Foulkes polynomials are special 
Kazhdan-Lusztig polynomials, see [Lus].

The above construction induces a decomposition of 
Kostka-Foulkes polynomials.
For let us denote ${\cal{R}}(I,J)$  the cocharge polynomial 
corresponding to the subset 
of tableaux of shape $J$ in the atom ${\cal{A}}(I)$. The following 
property is a direct corollary of theorem(4.4) :

\th Theorem 5.1 | Let $H \in {\bb{N}}^{\bb{A}}$, let $I$ be the partition 
obtained by reordering $H $ and $J$ 
be another partition. Then the Kostka-Foulkes polynomial decompose into the 
following sum of smaller positive polynomials : 
$${\cal{K}}(H,J) = {\cal{K}}(I,J) \,  = \, 
\sum_{H \leq I}\,  {\cal{R}}(H,J) $$
  \finth

\th Corollary 5.2 | \quad i) Given any triple of partitions 
$I , I', J \ : \ I \leq I'$, then 
$\sum_H \mu(H) {\cal{K}}(H,J)$, where $H $ runs over the entire interval 
$[I, I']$ and $\mu$ is the M\"obius function of the interval,
 is a polynomial with positive integral coefficients.

ii) The product of the Kostka matrix by the M\"obius matrix 
is the matrix $\big[ {\cal{R}}(I,J) \big]_{I,J}$ \ .
  \finth

For example, for the shape 1223 and all possible evaluations, 
we have the following ${\cal{K}}(*, 1223)$ 
and ${\cal{R}}(*, 1223)$ polynomials 
(writing only their coefficients, $122\cdots  $ means 
$1+ 2q +2q^2 + \cdots $ ) :

\setbox3=\hbox{$\scriptstyle 1 2 3 4 6 7 8 8 8 7 6 4 3 2 1 $ }
\setbox4=\hbox{$\scriptstyle 0 0 0 0 1 2 4 5 6 6 6 4 3 2 1$ }
\setbox5=\hbox{$\scriptstyle 1 2 3 4 5 5 4 3 2 1 $  }
\setbox6=\hbox{$\scriptstyle 0 0 0 1 2 4 4 3 2 1  $  }
\setbox11=\hbox to 23mm{\downbracefill}
\setbox12=\hbox{\kern 4mm $Evaluation$}
\setbox10=\vbox{\box12\kern -2mm \box11}
\setbox21=\hbox to 27mm{\downbracefill}
\setbox22=\hbox{\kern 5mm ${\cal{K}}(*,1223)$}
\setbox20=\vbox{\box22 \kern -2mm\box21}
\setbox31=\hbox to 27mm{\downbracefill}
\setbox32=\hbox{\kern 5mm ${\cal{R}}(*,1223)$}
\setbox30=\vbox{\box32 \kern -2mm\box31}
\setbox7=\hbox{\box10 \kern 10mm \box20 \kern 11mm \box30 }

$$\matrix{
\noalign{\box7}
\noalign{\vskip 2pt}
1^8 & & & \box3 &&& \box4 \cr
\downarrow  & & & \downarrow & & & \downarrow \cr
1^6 2  &&& \box5 &&& \box6 \cr
\downarrow  & & & \downarrow & & & \downarrow \cr
1^422       & & & 123331     & & & 000121     \cr
\downarrow  &\kern -2mm \searrow & & \downarrow &\kern -1cm \searrow & 
& \downarrow & \kern -1cm \searrow \cr
11222 & &\kern -5mm 1^5 3 \quad & 1221 & &\kern -5mm 11111  &0011 & &\kern 
-5mm  00111 \cr
\downarrow  &\kern -2mm \searrow &\kern -5mm\downarrow\quad  & \downarrow &
\kern -1cm \searrow &\kern -5mm \downarrow 
 & \downarrow & \kern -1cm \searrow & \kern -5mm\downarrow \cr
2222 & &\kern -5mm 11123\quad &111 & &\kern -5mm 11 &011 & &\kern -5mm 01 \cr
 &\kern -2mm \searrow &\kern -5mm\downarrow \quad & & \kern -1cm \searrow 
&\kern -5mm\downarrow  & &\kern -1cm \searrow &\kern -5mm\downarrow \cr
& & \kern -5mm 1223\quad  & & & \kern -5mm 1 & & & \kern -5mm 1 \cr
}$$


For all partitions of weight 6, the matrix 
of Kostka-Foulkes polynomials 
can be found in [Mac, p.127] (with charge instead 
of cocharge). Its product by the M\" obius matrix is 
the following, 
 writing $\cdot$ for 0 entries 
(lexicographic order on decreasing partitions) :

$$\matrix{1 &\cdot &\cdot &\cdot &\cdot &\cdot &\cdot &\cdot &\cdot &\cdot 
&\cdot   \cr
\cdot&q &\cdot &q^2 &\cdot  &\cdot  &q^3 &\cdot  &\cdot  &{\scriptstyle q^4} 
&{\scriptstyle q^5 }\cr 
\cdot&\cdot   &q^2 &\cdot &\cdot &q^3 &q^4 &q^4 &\cdot &{\scriptstyle 
q^6+q^5} &{\scriptstyle
 q^8+q^7+q^6}\cr
\cdot&\cdot  &\cdot  &q^3 &\cdot  &\cdot  &q^5+q^4 &\cdot  &\cdot  
&{\scriptstyle q^7+q^6+q^5} &{\scriptstyle q^9+q^8+q^7+q^6 }\cr 
\cdot&\cdot   &\cdot  &\cdot  &q^3 &\cdot  &\cdot  &\cdot  &q^5 
&{\scriptstyle 
q^6} &{\scriptstyle q^9+q^7 }\cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &q^4 &q^5 &q^5 &q^6 &{\scriptstyle 
q^8+2q^7+q^6} &{\scriptstyle q^{11}+
2q^{10}+2q^9+2q^8+q^7} \cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &q^6 &\cdot &\cdot &{\scriptstyle 
q^9+q^8+q^7} &{\scriptstyle
 q^{11}+q^{10}+2q^9+q^8+q^7} \cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &q^6 &\cdot  
&{\scriptstyle q^8} &{\scriptstyle q^{12}+q^{10}+q^9 }\cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot   
&q^7 &{\scriptstyle q^9+q^8} &{\scriptstyle
 q^{13}+q^{12}+2q^{11}+q^{10}+q^9 }\cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  
&{\scriptstyle q^{10}} &{\scriptstyle
 q^{14}+q^{13}+q^{12}+q^{11}} \cr
\cdot&\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot  &\cdot    
     &{\scriptstyle q^{15}}\cr }$$


In [L \& S2], we gave result 5.2 \it i) \rm only for intervals of length 2, but
 in fact, the same proof applies to any interval.



\titre 6 . Flag varieties |

The ring ${\bb{Z}}[{\bb{A}}]$ is a free ${\bb{Z}}[{\bb{A}}]^{\goth{S}}$-module.
 The natural scalar product on 
it is, for any pair $P,Q$ of polynomials in ${\bb{Z}}[{\bb{A}}]$,
$$ (P \, , \, Q)\  :=\,  
\sum_\mu \ [PQ\, /\, \Delta]^\mu \leqno (6.1)$$
where $\Delta$ is the Vandermonde $\prod_{i<j} (a_i-a_j) \quad .$

Many bases of ${\bb{Z}}[{\bb{A}}]$ as a free module are known ; for example, the 
embedding ${\goth{S}}(n-1) \hookrightarrow {\goth{S}}(n)$ easily gives the basis 
$\{ e^I , I\leq \rho \} $ with $\rho = n-1 \cdots 2 \, 1 \, 0$ and 
$n = card({\bb{A}})$ (\it cf\rm. [Gro]).

Schubert polynomials are another basis, which has the advantage of 
being self-adjoint with respect to the scalar product 6.1 
(\it cf. \rm[L\& S1). Schubert polynomials correspond to the classes of 
Schubert varieties when one interprets ${\bb{Z}}[{\bb{A}}]$ as follows :

\th Lemma 6.2  | Let $n$ be a positive integer, 
${\cal{F}} ({\bb{C}}^n)$ the flag variety for $Gl(n)$, ${\bb{A}}$ an alphabet 
of cardinal $n$. Then the cohomology ring ${\cal{H}}({\cal{F}})$ 
of ${\cal{F}}({\bb{C}}^n)$ is isomorphic, as a graded ${\goth{S}}(n)$-ring, to 
the quotient 
of ${\bb{Z}} [{\bb{A}}]$ by the ideal generated by symmetric polynomials 
in ${\bb{A}}$ without constant terms.
  \finth

The scalar product 6.1 induces a scalar product $<\cdot\, |\, \cdot>$ 
on ${\cal{H}}({\cal{F}})$ : for any $\overline{P}, 
\overline{Q} $ of elements of ${\cal{H}}({\cal{F}}) $, let $P$ and $Q$ be any 
lifts of $\overline{P}, \overline{Q} $ in ${\bb{Z}}[{\bb{A}}]$. Then
$$ < \overline{P} \bigm| \overline{Q}> \ := 
\ (P,Q)^{\xi_0}   $$

\noindent i.e. the scalar product of 
$\overline{P}, \overline{Q} $ is equal to the image of 
$(P,Q)$ by the specialization $\xi_0
: {\bb{A}} \rightarrow \{0, \ldots, 0 \} $.

More generally, given any partition $I$ of weight $n$ 
and a corresponding unipotent ${\goth{u}}$ of $Gl(n)$, 
one can consider the subvariety ${\cal{F}}_{\goth{u}} $ of ${\cal{F}} 
({\bb{C}}^n)$ of 
flags fixed by ${\goth{u}}$. One has the following theorem due to 
De Concini \& Procesi [DeC-Pro]; see proposition 6.11 below 
for an explicit ${\bb{Z}} $-basis and 9.10 for generators of the ideal.

\th Theorem 6.3  |The integral cohomology ring of 
${\cal{F}}_{\goth{u}}  $   is ${\goth{S}}(n)$-isomorphic to the quotient 
${\cal{H}}_I$ of ${\bb{Z}}[{\bb{A}} ]$ by a certain explicit ideal depending
 only on the partition $I$ corresponding to ${\goth{u}}$. Moreover, 
 ${\cal{H}}_I$ is a free ${\bb{Z}}$-module.
\finth

The ring ${\cal{H}}_I$ inherits from ${\bb{Z}}[{\bb{A}}]$ a grading. 
For any partition $J$, the isotypic 
component corresponding to $J$ is also graded, and using a 
formal indeterminate $q$, one can represent its multiplicity 
by the polynomial $\sum d_r(I,J) \, q^r$ , where $d_r(I,J)$ is the 
multiplicity of the irreducible character corresponding to 
$J$ in the homogeneous component of degree $r$ of 
${\cal{H}}({\cal{F}}_{\goth{u}} ) \simeq {\cal{H}}_I$. The full ring
 corresponds to the maximal partition $I = 1 \ldots 1$.

Macdonald [Mac, II p.92 and III ex.9] states that 

\th Theorem 6.4  | Given any pair of partitions $I,J$, 
the multiplicity of the character corresponding to $J$ 
in the cohomology ring ${\cal{H}}_I$ is equal to the 
Kostka-Foulkes polynomial ${\cal{K}}(I,J)$.
  \finth

To the natural order on partitions correspond canonical 
${\goth{S}}(n)$-surjections :
$$ I \geq I' \quad \Rightarrow \quad {\cal{H}}_I \mapsto {\cal{H}}_{I'} $$
\noindent
(see [Hot-Spr] , [DeC-Pro]).

Translating theorem (5.1) , we get the more precise result :

\th  Theorem 6.5  | Let $I $ be a partition and 
$\check {\cal{H}}_I$ the intersection of the kernels 
of all the canonical surjections 
${\cal{H}}_I \mapsto {\cal{H}}_{I'}$ , $I >I'$. Then the multiplicity 
in $\check {\cal{H}}_I$ of 
the character of ${\goth{S}}(n)$ corresponding to a partition 
$J$ is equal to the polynomial ${\cal{R}}(I,J)$.
\finth

\noindent
\it Example \rm 6.6 \pointir The atom ${\cal{A}}(1122)$ contains the tableaux 
$653412$ (coch. 7), $534126$ (coch. 6) , $346125$ (coch.5) and thus 
$\check {\cal{H}} (1122)$ is concentrated in degrees 7,6,5, being an 
irreducible 
representation of ${\goth{S}}(6)$ in each of these degrees (of respective 
dimensions 9, 16, 5, corresponding to the partitions 1122, 
123, 33 which are the shapes of the three tableaux).

Tableaux provide not only multiplicities, but explicit bases as well of 
the free modules ${\cal{H}}_J$, for the following reason.

Given a partition $J$, let ${\cal{Y}}(J)$ be the set of all words 
(called {\it Yamanouchi} words) congruent to the tableau 
$\cdots 2^{J_2} 1^{J_1} 0^{J_0}$ (we have taken the Arabic alphabet 
$\{ 0, 1, 2, \ldots \} $ ). Let furthermore ${\cal{E}}(J)$ be the set of words 
which 
are smaller (componentwise) than at least one word in ${\cal{Y}}(J)$.

\noindent
\it Example \rm6.7 \pointir  ${\cal{Y}}(122) = \{21100, 12100, 21010, 
12010, 10210 \} $ and\hfill\break
${\cal{E}}(122) \setminus {\cal{Y}}(122)
= \{ 20100, 02100, 11100, 20010, 21000, 
02010, 11010, 12000, $\break 
$00210, 10110, 10200 ; 01100, 20000,  01010, 02000, 11000, 
00110, 00200, 10100, $ \break 
$10010 ; 10000, 01000, 00100, 00010 ;
00000 \} $.

Yamanouchi words in ${\cal{Y}}(J)$ are bijectively associated to standard 
tableaux 
of shape $J$: taking the successive levels of $1,2,3, \ldots$ in a tableau 
$t$, we get a word (which has to be written from right to left) and every 
Yamanouchi word is obtained in this way, \it e.g. 
\rm\setbox3=\hbox{${}_5$}  \setbox4=\hbox{${}_{1246}^{37} $}
\setbox5=\vbox{\box3 \box4}
$ \box5 \leftrightarrow 1020100 $ \ (because $1,2,4,6$ are on the 
bottom row, $3,7$ on the middle one, and $5$ on the top row).

\th Lemma 6.8 | i) For any pair of partitions $I,J: I \leq J$, 
${\cal{E}}(I) \subseteq {\cal{E}}(J)$.

ii) For any integer $k\geq0$, and for any $I$, let ${\cal{E}}(I,k)$ be the 
subset of words in ${\cal{E}}(I)$ beginning with $k$. Let $I^{\sharp k}$ be 
the partition obtained by reordering, if necessary,  the sequence 
$\ldots I_{k+1}\, I_k -1 \, I_{k-1} \ldots I_0$. Then 
${\cal{E}}(I^{\sharp k})$ is identical with the set obtained 
by erasing the first letter of each word in ${\cal{E}}(I,k)$.
\finth

\noindent
\it Proof. i) \rm It is sufficient to compare ${\cal{E}}(I)$ and ${\cal{E}}(J)$
 for a pair 
of the type $$\matrix{ I &= &(\ldots& m& n& \ldots& n& n+1& \ldots)\cr
 J &= &(\ldots& m+1& n& \ldots & n& n+1& \ldots)\cr
{}_{the \, right}^{Places \, from}
& &&\uparrow\scriptstyle{h} & & & &\uparrow\scriptstyle{k}& \cr }$$
with $m<n$, because such pairs generate the natural order on partitions.
A word $w$ is a Yamanouchi word iff for every factorization 
$w= w' w''$, $|w''|_0 \geq |w''|_1 \geq |w''|_2 \geq \cdots$
 ({\it cf.} [L\& S1, prop.3.7]). 
One sees that, given a word $w\in {\cal{Y}}(I)$, changing the 
leftmost occurrence of 
\lq\lq {$h-1$}" into \lq\lq {$h$}", the leftmost occurrence of 
\lq\lq {$h-2$}" into \lq\lq {$h-1$}", $\ldots$, the leftmost occurrence 
of \lq\lq {$k$}" into \lq\lq {$k+1$}", produces a word $v >w$ which is 
still a Yamanouchi word. Thus ${\cal{Y}}(I) \subset {\cal{E}}(J)$, which
 implies that ${\cal{E}}(I) \subseteq {\cal{E}}(J)$.

\setbox3=\hbox{{\it ii)} Let}
$\matrix{\box3& I& =& (\ldots& m& n& \ldots& n& n& \ldots) &\quad ,
\quad {\rm with} \ m<n\, . \cr
\noalign{\vskip -2pt}
& & &  &\uparrow\scriptstyle{h} & & & &\uparrow\scriptstyle{k}& \cr }
 $\hfill\break 
 Then 
$ I^{\sharp k}= I^{\sharp h} =
(\ldots\,  m\  n-1 \, \ldots \, n\, n\, \ldots)$. 
Let $w\in {\cal{E}}(I^{\sharp h})$ and $v$ be any Yamanouchi word in 
${\cal{E}}(I^{\sharp h})$ such that $w \leq v$. Then the word $hv$ is 
Yamanouchi, 
and thus belongs to ${\cal{Y}}(I)$; therefore the words $hw$ and $kw$ belong 
to ${\cal{E}}(I)$. Conversely, let $kw$ be a word in ${\cal{E}}(I)$, $hv$ any 
Yamanouchi word in ${\cal{Y}}(I)$. Then $v$ belongs to 
${\cal{Y}}(I^{\sharp h})$ and thus $w$ belongs to 
${\cal{E}}(I^{\sharp h})$         \quad \qed

Thus, looking back at example 6.6, one has to decompose ${\cal{E}}(122)$ into 
subsets of words beginning by 2, 1, 0 respectively. Erasing then this first 
letter, one obtains 
${\cal{E}}(122^{\sharp 2}) = \{ 1100, 1010, 0100, 0010, 0000\} =
{\cal{E}}(022)$; ${\cal{E}}(122^{\sharp 1}) = \{ 2100,2010, 0210, 
2000, 0200,  1100, 1010, 0110, 1000, 0100, 0010, 0000 \} $ \break
$= {\cal{E}}(112) = {\cal{E}}(122^{\sharp 0})$.

Let ${\cal{M}}(I)$ be the free module generated by the 
$\{ e^\beta , \beta\in {\cal{E}}(I) \} $. Translating lemma 6.8 in terms
 of modules, 
and remembering that $e^{ijh\ldots} $ means $a^i b^j c^h \cdots$, 
we obtain 

\th Corollary 6.9 |
Let $k\geq0$ be an integer, $I$ be a partition. Then 
$$ a^k {\cal{M}}(I) / a^{k+1} {\cal{M}}(I) \simeq {\cal{M}}(I^{\sharp k}) $$
\finth

Now geometry provides an induction between the flags in 
${\cal{F}}({\bb{C}}^{n-1})$ and ${\cal{F}}({\bb{C}}^n)$. More precisely, 
one has the following 
property which is the key technical point in DeConcini-Procesi's 
description of the cohomology of flag varieties ([DeC-Pro, lemma 4.5]):

\th Lemma 6.10 | Let $k\geq0$ be an integer, $I$ a partition. Then 
$$ a^k {\cal{H}}_I / a^{k+1} {\cal{H}}_I \simeq {\cal{H}}_{I^{\sharp k}} $$
\finth

Therefore the spaces ${\cal{H}}_I$ satisfy the same induction as the 
modules ${\cal{M}}(I)$ and ${\cal{H}}_I \simeq {\cal{M}}(I)$ (as free ${\bb{Z}}
$-modules) because this is 
true for the starting point $I= 0\cdots 0$. Combining this with th.6.5, one 
obtains the following refinement of De Concini-Procesi's theorem : 

\th Proposition 6.11 |
Let $J$ be a partition. Then ${\cal{H}}_J$ is a free ${\bb{Z}}$-module 
with basis 
$\{ e^\beta , \beta\in {\cal{E}}(J) \} $ ; $\check{{\cal{H}}}_J$ is a 
free module with basis 
$\{ e^\beta , \beta\in {\cal{E}}(J)\setminus \cup_{I<J} {\cal{E}}(I) \} $.
\finth

From the explicit basis of ${\cal{H}}_J$, one could recover 6.2, 6.3 and 
6.4 and give a basis of the ideal mentionned in 6.3. For example, 
since the set ${\cal{Y}}(1\cdots 1)$ contains only the word 
$\rho = n-1 \, \cdots 1\, 0$, we recover that 
${\cal{H}}_{1\cdots 1}= {\cal{H}}({\cal{F}})$ is generated as a free 
${\bb{Z}} $-module by the 
monomials $\{ e^\beta , \beta\leq \rho \} $. 

We can now develop example 6.6 : proposition 6.11 asserts that 
$\check {\cal{H}}_{1122}$ admits the basis 
${\cal{E}}(1122) \setminus \{ {\cal{E}}(222) \cup {\cal{E}}(1113)\}$. In degree
 7, this basis 
co\"\i ncide with ${\cal{Y}}(1122)= \{ 103210, 130210, 310210, 
132010, 312010, 132100, 321010, 312100,$ \break $ 321100 \} $ ; 
in degree 6, we have the 16 words which are not Yamanouchi : \break 
$\{ 102210, 120210, 122010, 122100, 103110, 130110, 310110, 311010, 
131010,$ \break
$ 131100, 311100, 103200, 130200, 310200, 312000, 132000
\} . $ \break 
Finally, in degree 5, there 
are only 5 words which are not dominated by a word in 
${\cal{E}}(222) \cup {\cal{E}}(1113)$ : 
$\{ 131000, 130100, 130010,  103100, 103010 \} $.

As concerns geometry, we mention that [DeC-Pro] have given 
another interpretation of the ring ${\cal{H}}_I$, proving a conjecture of [Kra] 
and showing that ${\cal{H}}_I$ is isomorphic to the coordinate ring of the 
scheme intersection of the closure of a nilpotent orbit with a maximal 
torus. A simpler description of the ideal defining ${\cal{H}}_I$, due to 
[Tan], is given in proposition 9.10. A stronger result has been obtained by 
[Wey] who dealt directly with the ideal of a nilpotent conjugacy class.



\titre 7 . Harmonic polynomials |

A harmonic polynomial in ${\bb{Q}} [{\bb{A}}]$ is a polynomial which is 
annihilated by all symmetric derivations 
(\it i.e. \rm any symmetric polynomial in the partial derivatives 
$\partial_a , a \in {\bb{A}} $) without constant term.

Since partial derivatives commute, 
any derivative of a harmonic polynomial is still a 
harmonic polynomial. Using Taylor's formula, one can also see 
that any element $(\mu , I)$ of the affine symmetric group :
$\mu \in {\goth{S}}({\bb{A}}), I \in {\bb{Z}}^{\bb{A}}$, acting by 
$$ \{a, b, \ldots \} \longrightarrow \{a^\mu + I_a \, , b^\mu + I_b , \ldots \}
 $$
preserves the set of harmonic polynomials. 

Let ${\cal{V}}({\bb{A}})$ be the ${\bb{Z}}$-module of harmonic polynomials. 
The composite morphism 
$$ {\bb{Q}} \otimes {\cal{V}}({\bb{A}}) \hookrightarrow {\bb{Q}}[{\bb{A}}] 
\longrightarrow {\bb{Q}} \otimes {\cal{H}}({\cal{F}} ) $$
is an isomorphism ({\it cf.} [Bor]). The product of two harmonic 
polynomials is not harmonic in general, but it is congruent to one and only 
one harmonic polynomial modulo the ideal generated by symmetric polynomials 
without constant term.

There are several canonical surjections 
${\bb{Z}}[{\bb{A}}] \longrightarrow {\cal{V}}({\bb{A}})$. We shall only give
 two of them, one related to 
cohomology, the other to the Grothendieck ring.


For any finite ordered set ${\bb{X}} = \{x_1, x_2, \ldots \}$ of 
elements of ${\bb{Z}}[ {\bb{A}}]$, let us write $\Delta({\bb{X}})$ for the 
Vandermonde $\prod_{i<j} (x_i - x_j )$.


For any $I \in {\bb{N}}^{\bb{A}}$, 
denote by $\partial^I$ the product of partial 
derivatives $ \partial^I = \partial_a^{I_a} \partial_b^{I_b }\cdots$ 
and by $\Delta^I$ the image of ${1 \over \Delta(\rho)}\Delta({\bb{A}})$ 
under $\partial^I$, with $\rho = (n-1, \ldots, 1, 0) $ as above 
(and thus, $\Delta(\rho)$ is the number $n\! -\! 1 !\ n\! -\! 2 ! \cdots 
1 ! \, 0! $).

\th Lemma 7.1 | The morphism $\phi : {\bb{Z}}[{\bb{A}}] \longrightarrow 
{\cal{V}}({\bb{A}})$ 
defined by $\phi(e^I) = \Delta^I$ factorizes through ${\cal{H}} ({\cal{F}})$ 
and it induces an isomorphism ${\cal{H}} ({\cal{F}}) \simeq {\cal{V}}({\bb{A}})
$. The induced scalar product $\ll \phi(P) , \phi(Q) \gg 
\, := <P \bigm| Q> $, with $P,Q$ in ${\cal{H}} ({\cal{F}})$ is such that 
$\ll \hbar , \Delta^I \gg \, = \partial^I(\hbar) (0, \ldots , 0)$ for 
any $\hbar$ in ${\cal{V}}({\bb{A}})$ and is such that the $\partial^I$ are self
-adjoint.
\finth

\noindent
{\it Proof}. We shall assume that 
$\Delta({\bb{A}})/ \Delta(\rho)$ and that its derivatives generate 
${\cal{V}}({\bb{A}})$. Thus $\phi$
 is surjective. The action of the ring of differential operators 
${\bb{Z}} [\partial_a , \partial_b , \ldots ]$ on ${\cal{V}}({\bb{A}})$ 
factorizes through the 
quotient of this ring by the ideal generated by symmetric 
operators without constant term ; therefore $\phi$ factorizes 
through ${\cal{H}} ({\cal{F}})$ and ${\cal{V}}({\bb{A}})$ is generated by the 
$\{ \Delta^I \, :  0\leq I\leq\rho\}$. Given any homogeneous polynomial $P $ 
whose image 
in ${\cal{H}} ({\cal{F}})$ is non-zero, there exists at least one 
monomial $e^I$ such that in ${\cal{H}} ({\cal{F}}) $, $e^I P 
\equiv c e^\rho$ with $c \neq 0$. Hence the harmonic polynomial 
$\phi(p)$ cannot be zero, since its image by 
$\partial^I$ is $c \phi(e^\rho) \neq 0$.

The operator $\partial^I$ is the image of the operator 
\lq\lq {\sl multiplication by} $e^I \, $" which is clearly 
self-adjoint since for any $P,Q$ in 
${\cal{H}} ({\cal{F}})$, we have \hfill\break 
\centerline{$<P\bigm| Q> \, = \, <PQ\bigm| 1>$.}

Finally, since $\ll \hbar , \Delta^I \gg \, = \ll \partial^I (\hbar), 
\Delta^{0\cdots 0} \gg$, it 
only remains to compute the scalar products of $\Delta^{0\cdots 0}$ 
with a basis, {\it e.g.} $\{ \Delta^I \ : \ 0\leq I \leq \rho \}$. But 
$\ll \Delta^I, \Delta^{0\cdots 0}\gg \, = 
< e^I \bigm| 1 > = 0$, except 
$\ll 1, \Delta^{0\cdots 0}\gg \, = \, < e^\rho \bigm| e^{0\cdots 0}>\, = 1$. 
This implies by linearity 
$\ll \hbar, \Delta^{0\cdots 0}\gg \, = \hbar(0, \ldots, 0)$ 
\quad \qed

The images of the different natural bases of ${\bb{Z}}[{\bb{A}}]$ are 
bases of harmonic polynomials, and pairs of adjoint bases 
give explicit decompositions in ${\cal{V}}({\bb{A}})$:

\th Corollary 7.2 | Let $\{P_I \}$, $\{Q_I \}$ be 
adjoint bases of ${\bb{Z}}[{\bb{A}}]$ as a free 
${\bb{Z}}[{\bb{A}}]^{{\goth{S}}}$-module. Then every harmonic polynomial 
$\hbar$ admits the following decomposition :
$$ \hbar = \sum \, \ll \hbar \, , \, \phi(P_I) \gg \, \phi(Q_I ) \quad . $$
\finth

For example, in the case of ${\goth{S}}(3)$, the basis of Schubert 
polynomials is 
$\{e^{000}, e^{100}, e^{100}+ e^{010}, 
e^{110}, e^{200}, e^{210} \}$ ; its adjoint is 
$\{ -e^{012}, e^{002}, e^{011}, - e^{010}-e^{001},
-e^{001}, e^{000} \}$ ({\it i.e.}, it is self-adjoint up to sign and 
reversal of the alphabet, {\it cf.} [L\& S3]
). Corollary 7.2 implies the following 
decomposition, writing $\hbar^I$ for the value of 
$\partial^I (\hbar)$ at the point $0, 0, 0$: 
$$ \displaylines{\rlap{(7.3)}\hfill 
\hbar \ = \ -\hbar^{000} \Delta^{012} + \hbar^{100}\Delta^{002}  
+( \hbar^{100}+ \hbar^{010}) \Delta^{011}\  - \hfill \cr
\hfill \hbar^{110} (\Delta^{010}+ \Delta^{001}) - \hbar^{200}\Delta^{001}  +
 \hbar^{210} \Delta^{000} \quad .\quad \cr} $$

One could also have obtained 7.3 from Taylor formula, 
using relations between derivatives of an harmonic polynomial 
(i.e. computing modulo the ideal generated by symmetric differential 
operators without constant term).

Let us denote $\check \phi: {\cal{H}} ({\cal{F}}) \longrightarrow 
{\cal{V}}({\bb{A}}) $ the isomorphism 
defined by $\check \phi (e^I) = \Delta^{\rho -I}, 0\leq I\leq\rho$. 
Let $I$ be a partition of weight $n$
, $J= J_1 \geq J_2 \geq\cdots \geq J_k $ 
its conjugate and $H \in {\bb{N}}^n $ the vector 
$$ \underbrace{\mathstrut (J_1 + \cdots 
J_{k-1})\cdots (J_1 + \cdots J_{k-1})}
_{J_k} \ \ldots \ 
\underbrace{\mathstrut (J_1 +J_2)\cdots (J_1+J_2)}_{J_3} \ 
\underbrace{\mathstrut J_1 \cdots J_1}_{J_2}
\ \underbrace{\mathstrut 0\cdots 0}_{J_1} $$

The polynomial $\hbar_I = \Delta^H$ is a product of Vandermonde determinants.
For example, $I = 5221$ leads to $J= 43111$ and 
$H = (4+3+1+1\, , \,  4+3+1\, , \, 4+3 \, , \, 4,4,4,0,0,0,0 )$. 
Therefore, $\hbar_{5221}= \, {1 \over \Delta(\rho)}\, 
 \partial_{a_1}^9 \, \partial_{a_2}^8 
\, \partial_{a_3}^7 \, (\partial_{a_4} \partial_{a_5} \partial_{a_6} )^4 \, 
\big( \Delta \big)\,  =\, 
{1 \over \Delta(210)}\Delta( a_4, a_5 , a_6) \cdot 
{1 \over \Delta(3210)} \Delta (a_7, a_8 , a_9 , a_{10})   $.


The orbit of $\hbar_I$ under the symmetric group (resp. affine symmetric 
group) generates an irreducible (resp. reducible) 
${\bb{C}} $-representation of ${\goth{S}} $ called 
{\it Specht module} (resp. {\it affine Specht module}, denoted 
${\cal{V}}_I$, {\it cf.} [Jam-Ker]). 
Since $\hbar_I = \check \phi( e^H )$, and since the 
space $ {\cal{H}}_I$ is generated by the action of the affine 
symmetric group on the element $e^H$ according to proposition 
6.11, the two spaces $ {\cal{H}}_I$ and ${\cal{V}}_I$ are isomorphic
 under $\check \phi$. This allows to translate theorems 6.3 and 
6.4 in terms of harmonic polynomials :


\th Theorem 7.4  | Let $I,J$ be two partitions. Then

i) The multiplicity in the affine Specht module 
${\cal{V}}_I $ of the character of the symmetric group 
corresponding to $J$ 
is equal to the Kostka-Foulkes polynomial ${\cal{K}}(I,J)$.

ii) The multiplicity of the character $J$ in the quotient space 
 ${\cal{V}}_I \, / \, \cup_{I'<I}{\cal{V}}_{I'}$ is 
${\cal{R}}(I,J)$.
  \finth

For example, for ${\goth{S}}(6)$, the atom ${\cal{A}}(1113)$ contains only 
the tableaux $6\, 5 \, 4 \, 123$, $5 \, 46 \, 123$, 
$5\, 4\, 1236$, $6\, 4\, 1235$, $46\, 1235$ and 
$4\, 12356$, the respective co\-char\-ges of which are 
6, 5, 5, 4, 4, 3. Thus the space ${\cal{V}}_{1113}\, / \, 
\{ {\cal{V}}_{123 }\cup {\cal{V}}_{114 }\}$ is of dimension 10 in degree 6, of 
dimension 16+10 in degree 5, dimension 10+9 in degree 4 and 
dimension 5 in degree 3. 



\titre 8 . Verma Bases |

Let ${\bb{Z}}[ {\bb{A}}, {\bb{A}}\,\check{} \, ]$ be the ring of Laurent 
polynomials 
in an alphabet ${\bb{A}}$ of cardinal $n$, ${\bb{X}}$ a second alphabet 
of the same cardinal  and 
$\psi: {\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ] \longrightarrow 
{\cal{V}}({\bb{X}}) $ the morphism defined by 
$\psi(e^I) = {1 \over \Delta(\rho)} \Delta({\bb{X}} + I) := 
{1 \over \Delta(\rho)} \prod_{h<k} \big( (x_h + I_h) - (x_k + I_k) \big)  $ 
(we shall denote this polynomial $\Delta_I$).
Let moreover $\varepsilon_1$ be the specialisation 
${\bb{A}} \longrightarrow \{1, \ldots, 1 \}$ and ${\cal{K}}({\bb{A}})$ be 
the quotient of 
${\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ]$ by the ideal generated by the 
$\{ (P -P^{\varepsilon_1}, P \in {\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \,
 ]^{{\goth{S}}} \}$. The ring 
${\cal{K}}({\bb{A}})$ can be interpreted as the Grothendieck ring of the flag 
manifold ${\cal{F}}( {\bb{C}}^n)$.

The morphism $\psi$ satisfies the same type of properties as 
 $\phi$ (we shall not repeat the proof):

\th Lemma 8.1 | 1) $\psi$ is a surjection which factorizes 
through ${\cal{K}} [{\bb{A}}]$ and induces an isomorphism 
${\cal{K}} [{\bb{A}}] \simeq {\cal{V}}({\bb{X}})$.

\quad 2) The induced scalar product $\prec \, ,\, \succ$ defined by 
$\prec \psi(P) , \psi(Q) \succ\ = (P,Q)^{\varepsilon_1}$ is such that the 
translation 
${\bb{X}} \rightarrow {\bb{X}} + I$ is self-adjoint, and such that 
$\prec \hbar , \Delta_I \succ \ = \hbar(I) \, , \, I\in {\bb{Z}}^n$.
\finth

Adjoint bases of ${\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ]$ (as a free 
${\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ]^{{\goth{S}}}$-
module) furnish explicit decompositions of harmonic polynomials.
For example in the case of ${\goth{S}}(3)$ as in 7.3, Schubert polynomials 
give :
$$\displaylines{\rlap{(8.2)}\hfill 
 \hbar \ = \ -\hbar(000) \Delta_{012} + \hbar(100)\Delta_{002}  
+\big( \hbar(100)+ \hbar(010)\big) \Delta_{011}\ - \hfill \cr 
\hfill \hbar(110) \big(\Delta_{010}+ \Delta_{001}\big) - \hbar(200)\Delta_{001}
  +
 \hbar(210) \Delta_{000} \quad .\quad \cr } $$

Verma [Ver] has introduced another basis which is 
related to the cyclage structure discussed in section 3. 

Given a permutation $\mu \in {\goth{S}}({\bb{A}})$, considered as the word 
$a_1^\mu \, a_2^\mu \cdots a_n^\mu$ in ${\bb{A}}^*$, the 
{\it cocharge vector} $\mu C$ is defined inductively as 
follows ({\it cf.} [Mac], p.129) :
attach to $a_1$ the index $0$ ; if $k$ is attached to
$a_j$, then attach $k$ (resp. $k+1$) to $a_{j+1}$ 
if $\mu$ has the subword $a_j a_{j+1}$ (resp. 
$a_{j+1}a_j $). The cocharge vector is the vector of 
the preceeding indices. For example, indexing 
$\mu = a_3 a_5 a_1 a_7 a_2 a_6 a_4$, one obtains 
$(a_3)_1  (a_5)_2  (a_1)_0  (a_7)_3
 (a_2)_0 (a_6)_2 (a_4)_1\, $, and thus 
$\mu C = (1203021)$. The sum of the components of 
$\mu C$ is in fact equal to the cocharge of the tableau 
congruent to the word $\mu$ ({\it cf.} [L\& S1] ). 
In the present case, the tableau is 
$ a_7 \, a_3 a_5 a_6 \, a_1 a_2 a_4$ 
 and its cocharge is $1+2+0+3+0+2+1 = 9$.

Verma conjectured (this was proved by Husulkar) that the constant 
$1$ could be expressed as an integral sum of 
polynomials $\Delta_{\mu C} := {1 \over \Delta(\rho)} \Delta({\bb{X}} + \mu C)$
.

More precisely, one has ({\it cf.} [Hus]) :

\th Theorem 8.3 | The set $\{\Delta_{\mu C}, \mu \in{\goth{S}} \}$ is a 
${\bb{Z}}$-basis 
of ${\cal{V}}$. There exist harmonic polynomials 
$\{\hbar_\mu , \mu \in{\goth{S}} \}$ such that $\hbar_\mu (\eta C) = 0$, 
$\eta \neq \mu$, and  $\hbar_\mu (\mu C) = 1\, .$
\finth

The scalar product $\prec \, , \, \succ$ allows us to interpret 
the polynomials $\hbar_\mu$. For any $I \in {\bb{Z}}^n $, write $I\omega$ for 
the reverse vector $(I_n , \ldots , I_1)$. It is easy to 
check that the matrix of scalar products 
$(e^{\mu C}, e^{\eta C\omega})$ is triangular, with $\pm 1$ on the diagonal
 ({\it cf.} [Hus] for the appropriate order on ${\goth{S}}$). Thus 
the set $\{ e^{\mu C} \}$ is a ${\bb{Z}}$-basis of 
${\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ]$ as a free ${\bb{Z}}[{\bb{A}}, 
{\bb{A}}\,\check{} \, ]^{{\goth{S}}}$-
module ; it has a certain adjoint basis $\{P_\mu , \mu \in {\goth{S}} \}$.

\th Corollary 8.4 | i) Husulkar's harmonic polynomials 
$\hbar_\mu$ are the image under $\psi$ of the polynomials 
$P_\mu$.

\hskip 1cm ii) \hskip 2cm $1 \, = \, 
\sum_{\mu\in {\goth{S}}}\, (P_\mu)^{\varepsilon_1}\, \Delta_{\mu C} $
\finth

\noindent
{\it Proof}. The condition $\hbar_\mu(\eta C) = 1$ or $0$ means precisely 
that $\{ \hbar_\mu \}$ is adjoint to $\{ \Delta_{\mu C} \}$ with 
respect to $\prec , \succ$. This follows from the fact that 
the scalar product is the image of the natural one on 
${\bb{Z}}[{\bb{A}}, {\bb{A}}\,\check{} \, ]$; assertion {\it i)} follows.

In particular, $1 = \sum \prec 1, \hbar_\mu \succ \Delta_{\mu C}$. However, 
for any $I$ in ${\bb{Z}}^n$, one has 
$\prec 1 , \Delta_I \succ = 1 = (e^I)^{\varepsilon_1}$. Therefore, 
$\prec 1, \hbar_\mu \succ = (P_\mu)^{\varepsilon_1}$    \quad \qed

Property {\it ii)} explicits  Verma's footnote [Ver, p.669] 
that the integers \break 
$\prec 1, \hbar_\mu \succ$ are the degrees of 
certain $T$(orus)-modules. Verma writes $ch(e^I)$ for the scalar product 
$(e^I,1)$ and calls \lq\lq trace " the specialisation morphism 
$\varepsilon_1$. His starting point was that the polynomial that calls 
\lq\lq Weyl polynomial" : 
$I \longrightarrow \Delta(I)/\Delta(\rho)$ (considered as a function of $I_1,
 \ldots ,I_n$)) gives the dimension of the irreducible representation 
(of $Gl({\bb{C}}^n)$) of highest weight $I -\rho$ whenever 
$I$ is regular (i.e. $I_1 > I_2 > \cdots > I_n \geq 0$).

For ${\goth{S}}(3)$, the matrix $(e^{\mu C} , e^{\eta C})$ is 

\def\TraitHorizontal{\noalign{\hrule}}
\def\tv{\vrule height 10pt depth 5pt}
$$\vbox{\offinterlineskip\halign{
\tv\hfill\quad#\quad\hfill &
\tv\quad#\quad\hfill &\hfill\quad#\quad &
\hfill\quad#\quad & \hfill\quad#\quad &
\hfill\quad#\quad & \hfill\quad#\quad &
\tv#             \cr
\TraitHorizontal
$e^{012}$ &-1 &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$& \cr
$e^{011}$ &$\cdot$ &1 &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$ & \cr
$e^{001} $&$\cdot$ &$\cdot$ &1 &$\cdot$ &$\cdot$ &$\cdot$ & \cr
$e^{101}$ &$\cdot$ &$\cdot$ &$\cdot$ &-1 &$\cdot$ &$\cdot$& \cr
$e^{010}$ &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$ &-1 &$\cdot$& \cr
$e^{000}$ &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$ &$\cdot$ &1 & \cr
\TraitHorizontal
 &$e^{000}$ &$e^{010}$ &$e^{101}$ &$e^{100}$ &$e^{110}$ &$e^{210} $& \cr
\TraitHorizontal    } } $$


Therefore, any harmonic polynomial $\hbar$ decomposes as follows :
$$\displaylines{\rlap{(8.5)} \hfill 
 \hbar \ = \ \hbar(000) \Delta_{210} - \hbar(010)\Delta_{110}  
- \hbar(101)\Delta_{100} + \hbar(001) \Delta_{101} + \hfill \cr 
\hfill   \hbar(011)\Delta_{010}  -
 \hbar(012) \Delta_{000} \qquad . \cr } $$

For ${\goth{S}}(4)$, apart from the diagonal, there are only 
$4 \times 2$ non-zero entries in the matrix of scalar products :
$ (e^{0101}, e^{1201}) = -1 $ , 
$(e^{0210}, e^{0102}) = 1 $ , 
$(e^{3210}, e^{1021}) = - e^{1111}\, 
\Rightarrow \, \prec \Delta_{3210} ,  \Delta_{1021} \succ \, = -1 $ , 
\hfill\break 
\hglue 4cm {$(e^{2120},  e^{2012}) =  e^{1111} 
\, \Rightarrow \, \prec \Delta_{2120} , \Delta_{2012} \succ \, = 1 $ .}

Hence the adjoint basis of the polynomials \hfill\break 
$ \{ \Delta_{0000}, \Delta_{0010}, \Delta_{0100}, \Delta_{1000}, 
\Delta_{1100}, \Delta_{0110}, \Delta_{1001}, \Delta_{1010}, 
\Delta_{0101}, \Delta_{1011}, \Delta_{1101}$, \break 
$\Delta_{1110},\Delta_{0210}, \Delta_{2010}, \Delta_{2100}, \Delta_{2110},
\Delta_{1201}, \Delta_{1210}, \Delta_{2101}, \Delta_{1021},
\Delta_{2102}, \Delta_{2120}$, \break 
$\Delta_{2210}, \Delta_{3210} \}$ \quad is \hfill\break 
 $ \{ (\Delta_{0123} - \Delta_{0101}), - \Delta_{0122}, (\Delta_{0212}+ 
 \Delta_{0001}), 
( \Delta_{0010}- \Delta_{2012}) , (\Delta_{1201}- \Delta_{0112})$,\break
$ \Delta_{0121}, \Delta_{1012}, -( \Delta_{1021}+ \Delta_{0000}),
- \Delta_{0112}, -\Delta_{0012}, (\Delta_{0102}+ \Delta_{0111}),$ \break 
$ (\Delta_{1011}- \Delta_{0120}),- \Delta_{0111}, \Delta_{1011}, - 
\Delta_{1101} , 
-( \Delta_{1010}+ \Delta_{0011}) ,- \Delta_{0101},$ \hfill \break 
$ \Delta_{0110}, \Delta_{1001}, 
 \Delta_{0011}, - \Delta_{0001} , \Delta_{0010} , - \Delta_{0100} , 
 \Delta_{0000} \} $. 

\titre 9. Some properties of atoms |

More general cyclic permutations than those used in section 3 
(we shall nevertheless keep the same word {\it cyclage}) furnish a 
richer structure on the set of tableaux with a given evaluation. This 
structure is in fact closely related to the Pieri formulae which 
characterize the ring of symmetric polynomials by giving 
 the product of a Schur function by a complete function. Through the 
embedding given by theorem 2.3 of ${\bb{Z}}[{\bb{A}}]^{\goth{S}}$ into 
the plactic algebra, 
Pieri formulae become the following lemma (
lemma (3) of Schensted [Sche] and [Sch\"u1]).

 Given a positive integer $n$ and a partition $I$, 
we denote the set of partitions obtained from the diagram 
of $I$ by adding (resp. deleting) 
$n$ boxes, with no two in the same column, by 
$\{ n \otimes I\}$ (resp. $\{I/n \}$. This set is a distributive lattice and we
 shall show elsewhere that its properties provide in particular a 
combinatorial description of the multiplication of Hall-Littlewood 
polynomials.

\th Lemma 9.1 | For any integer $n$ and any partition $I$, we have 
$$  S_n\cdot S_I \equiv 
\sum_{J \in \{ n\otimes I\} }   S_J  \quad {\rm and }
\quad  S_I\cdot S_n \equiv \sum_{J \in \{ n\otimes I\} }   S_J $$
  \finth

Let $t$ be a tableau of shape $J$, $I$ another partition such that 
$J/I$ is a single box. Then, according to 9.1, there exist two unique 
pairs $(x,w)$, $(w',x')$, such that $x,x' \in {\bb{A}}$, 
that $w,w'$ are tableaux of shape $I$ and that 
$t \equiv xw \, , \ t \equiv w'x'$.

\noindent
{\it Definition} 9.2  \pointir  Let $t$ be a tableau, $xw$ and 
$vy$, $x,y \in {\bb{A}}$, two words congruent to $t$, and let 
$t', t''$ be the tableaux $t' \equiv wx$ , $t''\equiv yv$. 
Let $\mu$ be any permutation such that 
$|t^\mu|_{a_1} \geq |t^\mu|_{a_i}$ for any $i$. Then 
$t \rightarrow t'$ (resp. $t \rightarrow t''$) is an $I$-{\it cyclage} 
(resp. $I$-{\it cocyclage}) iff 
$\check x \neq a_1$ (resp. $\check y \neq a_1$) with 
$\check x$ the initial letter of $(xw)^\mu$, 
$\check y$ the final letter of $(vy )^\mu$, and 
$I$ the shape of the tableau congruent to 
$w$ (resp. $v$). 

\setbox3=\hbox{\ttabl |c|bc|abc|}
In other  words, if $a_1$ is the most frequent letter in 
$t$ (so that we can take $\mu$= {\sl identity}), then any cyclic 
permutation on the words congruent to $t$ is acceptable as long as the 
letter which moves is different from $a_1$. 
For example, let $t$ be the tableau \raise -1mm\box3 on the alphabet 
${\bb{A}} = \{ a,b,c \}$ ; consider the three words congruent to it :
$$t = \underbrace{c}_{x_1}\,  \underbrace{bcabc}_{w_1} 
\equiv \underbrace{c}_{x_2}\,  \underbrace{cbcabc}_{w_2} 
\equiv \underbrace{c}_{x_3}\,  \underbrace{cbcab}_{w_3} $$
and their images by the permutation 
$\mu : \{ a,b,c \}\rightarrow \{ c,b,a \}$ : 
$$ (x_1 w_1)^\mu = c\, bbaaa \equiv (x_2 w_2)^\mu = b\, cbaaa 
\equiv (x_3 w_3)^\mu = a\, cbbaa \ . $$
Thus, the cyclic permutations $c\, bcabc \rightarrow bcabc\, c$ and 
$c\, cbabc \rightarrow cbabc\, c$ are two cyclages, but not 
$c\, cbcab \rightarrow cbcab\, c$ since the word 
$(ccbcab)^\mu$ begins by $a$.


Proposition 3.1 and theorem 4.2 extend to this more general cyclage 
({\it cf.} {[L\& S1]} ) : 

\th Theorem 9.3 | 
i) Let $I $ be a partition. The cyclage induces a rank-poset
structure on the set of tableaux with evaluation $e^I $ 
(this set is still denoted ${\cal{T}}(I)$) ;
the row $e^I$ is the unique minimal element. 

ii) Let $I, J $ be two partitions : 
$I \leq J $ ; $\check I \in {\bb{N}}^{\bb{A}} $ a permutation of $I$, 
$\check J \in {\bb{N}}^{\bb{A}} $ a permutation of $J$. Then there exists 
a canonical embedding of the rank poset 
${\cal{T}}(\check I)$ into the rank poset ${\cal{T}}(\check J)$. 
\finth

\setbox3=\hbox{\ttabl |c|bb|aaa|}
\setbox4=\hbox{\ttabl |c|b|aaab|}
For the example 3.2, one has only to complete the poset with the extra cyclage 

$\raise -1mm\box3 \longrightarrow \raise -1mm\box4$\ .


We need moreover the special composition of cyclages 
$ t = w u \longrightarrow u w \equiv t' $, with $u$ the bottom row of $t$.
We denote by $K(t)$ the tableau $t' $ congruent to 
$u w $ and call {\it katabolism} 
the morphisme $t \rightarrow K(t)$. Katabolism provide an invariant of 
tableaux. For applying repeatedly Pieri formulae 9.1 
(which imply that katabolism is a bijection), one 
obtains : 

\th Theorem 9.4  |
i) The sequence  of shapes $ \{ \Vert K^i(t)\Vert \, , i\geq0 \}$
characterizes $t$ among all the tableaux of the same evaluation.

ii) For any $t $, the tableau $\theta(t)$ is the unique 
standard tableau $s$ with identical sequence 
$ \{ \Vert K^i(s)\Vert \, , i\geq0 \} =  \{ \Vert K^i(t)\Vert \, , i\geq0\}$.
\finth

\noindent
{\it Example} 9.5  \pointir The image by $\theta$
of the sequence of katabolisms
$$ {}_{abbcdde}^{ce} \longrightarrow {}_{abbcddee}^{d}
\longrightarrow {}_{abbcddde}^{e} \longrightarrow {}_{abbcdddee} $$
is the sequence (taking now as alphabet $\{1, 2, \ldots \}$) 
$$ {}_{1234568}^{79} \longrightarrow {}_{12345679}^{8}
\longrightarrow {}_{12345678}^{9} \longrightarrow {}_{123456789} $$


Another invariant can also be read on the sequence 
$K^i (t)$. We shall consider here only the case of standard 
tableaux. The bottom row of a standard tableau $s$ contains 
a maximal subword of consecutive integers starting with 1, 
the degree of which is denoted $f(s)$.

\th Lemma 9.6  |For any standard tableau $s $, the sequence
$f(s), f(K(s) - f(s), f(K^2(s) - f(K(s), \ldots$
 is a decreasing partition $I $. 
Furthermore  $s $ belongs to the atom ${\cal{A}}(I)$.
 \finth

Going back to example 9.5, we obtain for the standard tableau 
$ 79 \ {1234568}$ the sequence $6, 7-6, 8-7, 9-8, 9-9, \ldots$ , 
\it i\rm.\it e. \rm the partition  $6 1 1 1$. Therefore this tableau belongs 
to ${\cal{A}}(6111)$.


We can also characterize the tableaux $t$
in ${\cal{T}} (I)$, $I $ a partition, 
such that $\theta(t)$ belongs to the atom ${\cal{A}}(I)$
 \big( $a,b$ are the first two letters of ${\bb{A}}$ and 
${\bb{A}}_p$ is the alphabet of the first $p$ letters\big) :

\th Lemma 9.7  |
i) Let $t \in{\cal{T}}(I) $. Then $\theta(t) \in{\cal{A}}(I)$ iff for every 
permutation $\mu$, the restriction of $t^\mu$ to 
$\{a,b \}^*$ is congruent to $b^{I_{b\mu}}a^{I_{a\mu} }$.

ii) Let $I$ be a partition, $J$ a permutation of $I$, 
$p$ an integer, $I'$ the partition obtained by reordering 
$(J_1, \ldots , J_p)$. Let $t$ be a tableau in 
${\cal{T}} (J)$, $t'$ its restriction to ${\bb{A}}_p^*$. Then 
$\theta(t) \in {\cal{A}}(I)$ implies that 
$\theta(t') \in {\cal{A}}(I')$.

iii) The set of tableaux $t \in{\cal{T}}(I)$ such that $\theta(t) 
\in{\cal{A}}(I)$ is closed by cocyclage.

iv) The minimum elements in ${\cal{A}}(I)$ are two-row tableaux.
\finth

Proof. {\it i)} According to 4.2,  $t$ is such that 
$\theta(t) \in {\cal{A}}(I)$ iff there exists no partition 
$J < I$ such that $t$ belongs to the image of 
${\cal{T}}(J)$ in ${\cal{T}}(I)$. But from the description of the canonical 
embedding in terms of the morphism $\varphi$ in 4.2, 
$t$ belongs to some ${\cal{T}}(J)$ iff there exists a permutation 
$\mu$ such that $|t^\mu|_a \geq |t^\mu|_b$ and the tableau 
$t^\mu$ has some occurrence of $b$ in its bottom row. 
This settles the case where $|t^\mu|_a \geq |t^\mu|_b$ ; otherwise, we 
take the product of $\mu$ by the transposition $\sigma$ of $a,b$ and 
notice that the image by $\sigma $ 
of the word $b^j a^i$, $j\geq i$ is the word 
$a^{j-i} \, b^i \, a^i \, \equiv b^i \, a^j$.

{\it ii)} Follows from {\it i)}, since we have to use only those 
permutations $\mu$ which preserve globally ${\bb{A}}_p$.

{\it iii)} Let $t \rightarrow t'$ be an $H$-cyclage of tableaux in 
${\cal{T}}(I)$. Let $\mu$ be any permutation such that 
$|t^\mu|_a \geq |t^\mu|_b$.
Then $t^\mu \rightarrow t'^\mu$ is an $H$-cyclage : $t^\mu \equiv xw$, 
$t'^\mu \equiv wx$, where $w$ is a tableau of shape $I$ 
and $x \neq a$. Thus if 
$t'^\mu$ has no $b$ in its bottom row, then $x\neq b$ and the restriction 
of $t^\mu$ and ${t'}^\mu$ to $\{a,b \}^*$ are identical. According to 
criterium {\it i)}, this ensures that $\theta(t) \in{\cal{A}}(I)$ if 
$\theta(t') \in{\cal{A}}(I)$.

{\it iv)} Let $t$ be a tableau of shape $J$ and 
$t \rightarrow t'$ be an $H-cyclage$ such that $J_2 = H_2$. Then for 
any $\mu$, $t^\mu = xw \rightarrow wx \equiv t'^\mu$ is such that $ x\neq a,b$.
 Therefore
 the restrictions of $t^\mu$ and ${t'}^\mu$ to $\{a,b \}^*$ co\"\i ncide 
and thus $\theta(t) \in{\cal{A}}(I)$ implies $\theta(t') \in{\cal{A}}(I)$. If $
t $ is a two-row 
tableau of shape $J$, then $t$ admits only the 
$(J_2 -1,J_1)$-cyclage ; if $t =b^m u a^n v$, $m>0$, then 
the cyclage $t\rightarrow t' \equiv b^{m-1}u a^n v b$ is such that $t'$ as a 
$b$ in its bottom row, and thus $\theta(t) \in{\cal{A}}(I) \Rightarrow
\theta(t') \notin {\cal{A}}(I)$     \qed

Property {\it iii)} shows that to describe atoms, we need 
only to enumerate the two-row tableaux. Moreover, given a partition 
$I$, if we start from the maximal tableau 
$t = \cdots w_3 w_2 w_1$ with $w_k = 
(I_1 + I_2 + \cdots I_{k-1 }+1) \cdots 
(I_1 + I_2 + \cdots I_k)$ and cycle the left letter of each 
successive tableau till we get a two-row tableau, 
then this final tableau (which we shall call \it canonical\rm) is
$w_2 w_4 \cdots w_{2k}\ w_1 w_3 \cdots$.
 
The following further simplification shows that we can restrict ourselves to 
the case of partitions with no parts repeated more than twice, and that in 
the case that no part is repeated, the atom has only one two-row tableau.

\th Lemma 9.8 |
i) Let $I$ be a partition, $I = 1^{m_1}2^{m_2} \cdots k^{m_k} $.
Let $\varepsilon_i = inf(2,m_i), \ n_i = m_i -\varepsilon_i , \forall i\geq1 $ 
and 
$I' = 0^{p-q }1^{\varepsilon_1}2^{\varepsilon_2} \cdots k^{\varepsilon_k}  $, 
with$p = |I'| = \varepsilon_1 + 2 \varepsilon_2 + \cdots + k \varepsilon_k $, 
$q= \varepsilon_1 + \cdots + \varepsilon_k$. Let moreover 
$J= 1^{n_1}2^{n_2} \cdots k^{n_k}\, J_p \cdots J_1 $, 
with $J_p + \cdots J_1 = p$.
 Let finally $t\in{\cal{T}} (J)$. Then 
$\theta(t) \in{\cal{A}}(I)$ iff $\theta(t') \in {\cal{A}}(I')$,
where $t'$ denotes the restriction of $t$ to the first 
$p$ letters of ${\bb{A}}$.

ii) if no part of $I$ is repeated, then ${\cal{A}}(I)$ has only one two-row 
tableau, namely its canonical tableau.
\finth

\noindent
{\it Proof}.\quad {\it i)} Let $t \in{\cal{T}}(J)$ be such that $\theta(t') 
\in{\cal{A}}(I')$. Then $t'$ is the image of a tableau $t'_1 \in{\cal{T}}(I')$; 
denote by $t_1$ the tableau obtained from $t$ by changing 
the subtableau $t'$ into $t'_1$. According to 9.7{\it i)} , to determine to 
which atom $\theta(t_1)$ belongs, we have to test the restriction to 
$\{a,b \}^*$ of all ${t_1}^\mu , \mu\in{\goth{S}}({\bb{A}})$. In fact we need 
only to test a subfamily of permutations $\eta$ such that each pair of 
parts of $I$ occurs at least once in the set 
$\{ \big( |t_1^\eta|_a , |t_1^\eta|_b \big) \} $. Because of the definition 
of the multiplicities $m_i$, we can suppose that $\eta$ fixes the 
letters outside ${\bb{A}}_p $ 
. In other words, $\eta$ acts only on the subtableau 
$t'_1$, the restriction of $t_1^\eta $ and ${t'}_1^\eta$ to 
$\{a,b \}^*$ co\"\i ncide and $\theta(t'_1) \in {\cal{A}}(I')$ implies that 
$\theta(t_1) \in {\cal{A}}(I)$. 

Conversely, property 9.7{\it ii)} shows that $\theta(t) \in {\cal{A}}(I)$ 
implies that $\theta(t') \in{\cal{A}}(I') $.

{\it ii)} \quad Let $t \in{\cal{T}}(I)$ be a two-row tableau such that 
$\theta(t) \in{\cal{A}}(I)$. We know from proposition 9.7 that for any $k$ the 

restriction $t'$ of $t$ to ${\bb{A}}_k$ is such that 
$\theta(t') \in {\cal{A}}(I')$, with $I'= (I_1,\ldots , I_k)$. Let 
$k$ be the smallest integer such that $\theta(t')$ is not canonical. 
It is equivalent to require that there is at least one occurrence of 
$a_k$ on the bottom (resp. top) row when $k$ is even (resp. odd).
 Since $|t|_{a_k}< |t|_{a_{k-1} }$, there is also one misplaced 
$a_k$ in the tableau $K(t')$. Therefore 
$\theta\big( K(t') \big)$ also is not canonical. Since it belongs to the atom 
${\cal{A}}(I'')$, with $I'' = (I_1\! +\! I_2 , I_3 , \ldots , I_k) $, the 
assertion follows by induction on the number of parts
\quad          \qed


To sum up, atoms are totally characterized by the enumeration 
of all the non-canonical two-row tableaux for partitions 
having no part repeated more than twice.


\vfill\eject

\centerline{\bf Compact table of all atoms for ${\goth{S}}(n)$, $n\leq12$}
\centerline{$\scriptstyle alphabet \ \{ 1,\ldots, 9, 0, \flat , \natural  
\}$ }
\setbox2\hbox{${\cal{A}}(1223)$}
\setbox3\hbox{$\kern 12mm {}_{123678}^{45}   $}
\setbox6=\hbox{${\cal{A}}(1224)$}
\setbox7=\hbox{$\kern 12mm{}_{1234789}^{56}$}
\setbox10=\hbox{${\cal{A}}(1225)$}
\setbox11=\hbox{$\kern 12mm{}_{12345890}^{67}$}
\setbox14=\hbox{${\cal{A}}(1334)$}
\setbox15=\hbox{$\kern 12mm{}_{1234890\flat }^{567}$}
\setbox18=\hbox{${\cal{A}}(1226)$}
\setbox19=\hbox{$\kern 12mm{}_{12345690\flat }^{78}$}
\setbox22=\hbox{${\cal{A}}(12234)$}
\setbox23=\hbox{$\kern 12mm{}_{123489}^{5670\flat \natural }$}
\setbox26=\hbox{${\cal{A}}(2334)$}
\setbox27=\hbox{$\kern 12mm{}_{1234890\flat }^{567\natural }$}
\setbox28=\hbox{$\kern 12mm { }_{1234890\flat \natural }^{567}$}
\setbox30=\hbox{${\cal{A}}(1335)$}
\setbox31=\hbox{$\kern 12mm{}_{1234590\flat \natural }^{678}$}
\setbox34=\hbox{${\cal{A}}(1227)$}
\setbox35=\hbox{$\kern 12mm{}_{12345670\flat \natural }^{89}$}
\setbox40=\hbox{$\scriptstyle Atom$}
\setbox41=\hbox{$\scriptstyle Non-canonical \ Tableaux$}
\setbox42=\hbox{\kern 2mm $\scriptstyle Cocharge$}
\def\TraitHorizontal{\noalign{\hrule}}
\def\tv{\vrule height 15pt depth 10pt}
$$\vbox{\offinterlineskip\halign{
\tv\hfill\quad#\quad\hfill &
\tv\quad#\quad\hfill &
\tv\hfill\quad#\qquad &
\tv#             \cr
\TraitHorizontal
\box40 &\box41 &\box42 &\cr
\TraitHorizontal
\box2 &\box3 &5 &\cr
\TraitHorizontal
\box6 &\box7 &5 &\cr
\TraitHorizontal
\box10 &\box11 &5 &\cr
\TraitHorizontal
\box14 &\box15 &7 &\cr
\TraitHorizontal
\box18 &\box19 &5 &\cr
\TraitHorizontal
\box22 &\box23 &11 &\cr 
\TraitHorizontal
\box26 &\box27 &9 &\cr
     &\box28 &8 &\cr
\TraitHorizontal
\box30 &\box31 &7 &\cr
\TraitHorizontal
\box34 &\box35 &5 &\cr
\TraitHorizontal    } } $$

Let us see how to use the table by a concrete example. Take 
$I= 11333$; reducing the multiplicities of parts to 2 at most, 
we obtain the partition $1133$ which is not in the table. 
Thus ${\cal{A}}(1133)$ has only one two-row tableau, namely
$456\, 8\, 123\, 7$. Cocycling, we obtain that ${\cal{A}}(1133)$ 
is equal to 

\setbox2=\hbox{\ttabl |7|456|1238|}
\setbox3=\hbox{\ttabl 8|7|456|123|}

$$ {}_{1237}^{4568}\ \longleftarrow \ \box2 \ \longleftarrow \ \box3 \quad .$$



Now according to 9.8, the pull-back of ${\cal{A}}(11333)$ in 
${\cal{T}}(3\, 1^8)$ is exactly the set of all tableaux obtained from 
the three preceeding ones by shuffling three occurrences of 9.
We give below each of these tableaux (written as words) together with 
their respective images by $\theta$,  and their cocharges,
 taking as alphabet $\{ 1, \ldots, 9, 0, \natural  \} $ : 
\setbox3=\hbox{${}_{\ \ tableau \quad \longrightarrow}^
{image \, by \, \theta\quad  \longrightarrow } $}
\setbox4=\hbox{$ {}_{98799456123  }^
{\natural  0789456123} $}
\setbox5=\hbox to 9cm{\box3 \kern 2cm \box4}

\hfill Cocharge 

\vskip -4mm
$$ \kern -1cm\box5
\eqno (16) $$ 

\vskip -4mm
$$ {}_{87994561239}^{0789456123\natural } \qquad
{}_{98794561239}^{\natural 0894561237} \eqno (15) $$

\vskip -4mm
$$ {}_{79945691238}^{789456\natural 1230} \quad
{}_{97945691238}^{089456\natural 1237} \quad
{}_{87945612399}^{0894561237\natural } \quad
{}_{97994561238}^{089\natural 4561237}\quad
{}_{98745612399}^{\natural 0945612378}   \eqno (14) $$

\vskip -4mm
$$\hskip -1cm {}_{99945681237}^{89\natural 45601237} \ 
{}_{79456912389}^{89456\natural 12370}\ 
{}_{97456912389}^{09456\natural 12378}\ 
{}_{97945612389}^{09\natural 45612378}    \ 
{}_{79945612389}^{89\natural 45612370}\ 
{}_{87456123999}^{0945612378\natural } \eqno (13)$$

\vskip -4mm
$${}_{99456812379}^{9\natural 456012378} \quad
{}_{74569123899}^{9456\natural 123780}\quad
{}_{79456123899}^{9\natural 456123780}\quad
{}_{97456123899}^{\natural 9456123780} \eqno (12) $$

\vskip -4mm
$${}_{94568123799}^{\natural 4560123789} \qquad
{}_{74561238999}^{9456123780\natural } \eqno (11) $$

\vskip -4mm
$${}_{45681237999}^{4560123789\natural } \eqno (10) $$

We shall now give a property which allows us to generate atoms 
by induction on the size of the alphabet.

Let $I= (I_1\geq I_2 \geq \cdots ) $ be a partition and $r$ an integer 
such that $r \leq I$, let $k$ be the integer such that 
$I_k \geq r >I_{k+1}$ and denote by $I\setminus r$ the partition 
$(I_1, \ldots , I_{k-1} ,\,  I_k + I_{k+1} -r \, , I_{k+2}\, , 
\ldots ) $. 

\th Proposition 9.9 | Let $I$ be a partition, $r,n$ two integers, 
$t$ a tableau such that $\theta(t) \in {\cal{A}}(I)$ and such that 
$|ev(t)|_{a_m} =0$ for $m>n$, $|ev(t)|_{a_n} = r$. 
Then the tableau $t'$ obtained from $t$ by erasing 
all occurrences of $a_n$ is such that $\theta(t')$ belongs to the atom 
${\cal{A}}(I \setminus r)$.
\finth

We will not give the proof, which reduces by cyclage to a detailed study of 
two-row tableaux. Note however that in the case where $r$ is 
a part of $I$, this property is a corollary of lemma 9.7.

\setbox3=\hbox{\ttabl 7|67|45|1237|}
\setbox4=\hbox{\ttabl 7|6|45|12377|}
\setbox5=\hbox{\ttabl |67|45|12377|}
\setbox6=\hbox{\ttabl |6|45|123777|}
\setbox7=\hbox{\ttabl |77|457|1236|}
\setbox8=\hbox{\ttabl |77|45|12367|}
\setbox9=\hbox{\ttabl |7|457|12367|}
\setbox10=\hbox{\ttabl |7|45|123677|}
\setbox11=\hbox{$\tabl 457|123677|$}
\setbox12=\hbox{$\tabl 45|1236777|$}
\setbox13=\hbox{\ttabl |6|45|123|}
\setbox14=\hbox{$\tabl 45|1236|$}
\setbox15=\hbox{$\raise -1mm\box3 \, ,
\raise -1mm \box4 \, ,\raise -1mm \box5 \, , \raise -1mm \box6 \, 
, \raise -1mm \box7 \, , \raise -1mm\box8 ,
 \raise -1mm\box9 \, , \raise -1mm\box10 \, , \raise -1mm\box11 \, , 
\raise -1mm\box12$}
For example, the pull-back of ${\cal{A}}(4221)$ in 
${\cal{T}}(1^6 3)$ is the set 
$$\left\{ \raise -1mm\box15 \right\} $$

Erasing the \lq\lq 7" , we get the two tableaux 
$\raise -1mm\box13 \ , \ \raise -1mm\box 14$ \ which belong to the atom 
${\cal{A}}(321)$, in accordance with the fact that 
$4221 \setminus 3 = (4\! +\! 2\! -\! 3)\ 2\, 1 = 3 2 1$.

In section 6 we saw that tableaux provide multiplicities of 
representations, as well as bases, in the cohomology ring 
${\cal{H}}_I$ of the space of flags corresponding to a partition $I$.

Generators of the ideal defining ${\cal{H}}_I$ can also be read from 
tableaux.

For a triple of integers $k,r,n \, : \, k\geq r, k+r\leq n $, let 
$\tau_{k\, r\, n}$ be the tableau 
 ${\tabl k+1 \cdots k+r | 1\ \cdots \ k \ \ k+r+1 \cdots\  n |}$ .
 Using criterium 9.6, we see that $\tau_{k\, r\, n}$ 
belongs to the atom ${\cal{A}}\big( P(\tau_{k\, r\, n})\big)$, where 
$P(\tau_{k\, r\, n})$ is the following partition of $n$: 
$P(\tau_{k\, r\, n}):= \big(k, r, \ldots, r, n-k-[{n-k \over r}] \big)$ 
and $[{n-k \over r}]$ is the integral part of $(n-k)/r$.
Moreover $\tau_{k\, r\, n}$ has cocharge $n-k$.

To the tableau $\tau_{k\, r\, n}$ we associate the complete function 
$S(\tau_{k\, r\, n}):= S_{n-k}({\bb{A}}_r) $, with 
${\bb{A}}_r = \{a_1 , \ldots, a_r \}$ as before. Given a partition 
$I$ of $n$, let ${\goth{T}}{\goth{a}}{\goth{b}} (I)$ be the set of tableaux 
$\tau_{k\, r\, n}$ such that 
$P\big(\tau_{k\, r\, n}\big)\not\leq I$, and let 
${\goth Ideal} (I)$ be the ideal of ${\bb{Z}}[{\bb{A}}]$ generated 
(as a ${\goth{S}}({\bb{A}})-$ideal) by the 
$\{S(\tau) , \tau \in {\goth{T}}{\goth{a}}{\goth{b}} (I) \}$. 
Recall that the order on partitions is defined by the componentwise 
order on the associated vectors : $I \rightarrow {conjugate\ partition}\, 
J= (J_1 \geq J_2 \geq \cdots) \rightarrow 
J^\Sigma := (J_1, J_1 +J_2 -1, J_1+J_2+J_3 -2,\ldots  ) $.

On the other hand, given an integral vector 
$H = (H_1, \ldots , H_p )$, let ${\goth{T}}{\goth{a}}{\goth{n}} (H)$ 
(due to Tanisaki [Tan]) be the 
${\goth{S}}({\bb{A}})-$ideal in ${\bb{Z}}[{\bb{A}}]$ generated by 
$\{S_{k_1}({\bb{A}}_1) , S{k_2}({\bb{A}}_2) , 
\ldots, S_{k_p}({\bb{A}}_p) \, , \, k_1 \geq H_1 , \ldots, k_p \geq H_p\}$.


\th Proposition 9.10 | Let $I$ and $J$ be conjugate partitions.
 Then the two ideals 
${\goth Ideal} (I)$ and ${\goth{T}}{\goth{a}}{\goth{n}} (J^\Sigma)$ 
co\"\i ncide.\finth

\noindent
{\it Proof}.\quad  Since order is defined by the vectors 
$J^\Sigma$, it is clear that ${\goth Ideal} (I)$ 
can be described by the components of $J^\Sigma$ rather than 
by the partitions  $P\big(\tau_{k\, r\, n}\big)$. We shall just check by an 
example that the two sets of generators co\"\i ncide.

Let $I = 8 6 4 4 2 1$ and thus $J=  65442211 \, , 
\, J^\Sigma = 6\ 10 \ 13\ 16\ 17\ 18\ 18\ 18$. 
The tableau  $\tau_{12,3,25}$ has cocharge 13 and belongs to the atom 
${\cal{A}}(12 \ 3\, 3\, 3\, 3\, 1)$ ; the conjugate of this last partition 
is $6\, 5\, 5\, 1^9$ which gives the vector 
$6\, 11\, 14\, 14 \ldots$ not comparable to $J^\Sigma$.
 Thus, $P\big(\tau_{12,3,25}\big) \not\leq I$. On the other hand, the tableau 
$\tau_{13,3,25}$ has cocharge 12 and belongs to the atom 
${\cal{A}}(13 \ 3\, 3\, 3\, 3)$; the corresponding conjugate partition is 
$ 5\, 5\, 5\, 1^{10}$ giving the vector 
$5\, 9\, 13\, 13\, 13\,\ldots $ which is less than $J^\Sigma$.
 Therefore,  ${\goth Ideal}(I)$ contains 
$S_{13}({\bb{A}}_3)$, but not $S_{12}({\bb{A}}_3)$, in accordance with 
the fact that the third component of $J^\Sigma$ is 13 \quad \qed

Tanisaki [Tan] uses elementary symmetric functions $e_j$ as generators of 
the ideal, but since $e_j ({\bb{A}}\setminus {\bb{B}}) = 
e_j({\bb{A}}) -S_1 ({\bb{B}}) e_{j-1} + S_2({\bb{B}}) e_{j-2}- \cdots + (-1)^j 
S_j({\bb{B}}) $ 
for any subalphabet ${\bb{B}}$ of ${\bb{A}}$,  one has 
$e_j(a_1 , \ldots, a_p) \equiv 
(-1)^j S_j (a_{p+1}, \ldots, a_n )$
modulo the ideal generated by symmetric polynomials in 
$\{a_1, \ldots, a_n \}$ without constant terms : elementary symmetric 
functions and complete functions are interchangeable.


\vskip 1cm
\centerline{ \bf References }

\article Bor |A.\pd BOREL | Cohomologie des espaces fibr\'es principaux |
Annals of Math. |57 |1953 |115-207 | 

\article DeC-Pro | C. \pd DE \pd CONCINI \& C.\pd PROCESI | Symmetric 
functions, conjugacy classes and the flag variety| Invent.Math.|  64|
1981|203-230|

\divers Gro |A.\pd GROTHENDIECK |Sur quelques propri\'et\'es fondamentales en 
th\'eorie des intersections, {\it S\'eminaire Chevalley}
 \pointir Paris, {\oldstyle 1958} | 

\article Hot-Spr|  R.\pd HOTTA \& T.A.\pd SPRINGER | A specialization theorem 
for certain Weyl group representations| Invent.Math.| 41|
1977|113-127|

\article Hus | S.G.\pd HUSULKAR |Proof of Verma's conjecture on 
Weyl's dimension polynomial|  Invent.Math.| 27|1974|45-52 |

\livre Jam-Ker|G.\pd JAMES \& A. \pd KERBER | The representation theory of 
the symmetric group | Addison-Wesley, {\oldstyle 1981}|

\article Kos| B.\pd KOSTANT | Lie group representations on polynomial 
rings | Amer. J. M. | 85 |1979|327-404|

\divers Kra|  H.\pd KRAFT | Conjugacy classes and Weyl group 
representations 
{\it \lq\lq Tableaux de Young et foncteurs de Schur, 
Ast\'erisque},  {\bf 87-88}, {\oldstyle 1981}, p.191-205|

\article L\& S1| A.\pd LASCOUX \& M.P.
\pd SCH\"{U}TZENBERGER |Le mono\"\i de plaxique |
 Quaderni della Ricerca scientifica | 109 |1981|129-156|

\article L\& S2| A.\pd LASCOUX \& M.P.
\pd SCH\"{U}TZENBERGER | Croissance des 
polyn\^omes de Foulkes/Green | C.R.Acad.Sc.Paris | 288|1979|95|

\article L\& S3| A.\pd LASCOUX \& M.P.\pd SCH\"{U}TZNBERGER | 
Polyn\^omes de Schubert|
C.R. Acad. Sc. Paris | 294 |1982|447|

\divers L\& S4| A.\pd LASCOUX \& M.P.
\pd SCH\"{U}TZENBERGER | Alg\`ebre des diff\'erences 
divis\'ees, {\it  pr\'epublication, Universit\'e 
Paris 7}, {\oldstyle 1989} |

\article Lus| G.\pd LUSZTIG | Green polynomials and singularities of
unipotent classes| Adv. in M. | 42 |1981|169-178|

\livre Mac|  I.G.\pd MACDONALD | Symmetric functions and Hall 
polynomials | Oxford Math. Mono, {\oldstyle 1979}|

\article Sche| C.\pd SCHENSTED | Longest increasing and decreasing 
subsequences| Canad. J.M. | 13 |1961|179-191|

\article Sch\"u1| M.P.\pd SCH\"{U}TZENBERGER | Quelques remarques sur une 
construction de Schensted | Math. Scand. | 12 |1963|117-128|

\divers Sch\"u2|  M.P.\pd SCH\"{U}TZENBERGER | La correspondance de 
Robinson
 {\it  in Combinatoire et repr\'esentation du groupe sym\'etrique} \pointir 
Strasbourg 1976, {\it Springer L.N.}, {\bf 579}, {\oldstyle 1977}, 
p.59-113|

\article Tan| T.\pd TANISAKI | Defining ideals of the closures of conjugacy 
classes and representations of the Weyl groups
| Tohoku Math.| 34 |1982|575-585|

\divers Ver| D.-N.\pd VERMA | The r\^ole of affine Weyl groups in the 
representation theory of algebra\" ic Chevalley groups, 
{\it in Lie Groups and their representations}, Budapest \pointir 
Akad. Kiado, {\oldstyle 1972}|

\article Wey| J.\pd WEYMAN | The equations of conjugacy classes of nilpotent 
matrices| Inv.Math.|98|1989|229-245|

