\magnification 1200 
\overfullrule 0mm
\input ../../a4new
\voffset -1cm

\ctitre 
Polyn\^omes de Kazhdan-Lusztig pour les vari\'et\'es de Schubert
vexillaires 
\endctitre

\smallskip
\centerline{Alain Lascoux}

\vskip 3mm
\eightpoint{\bf R\'esum\'e}\pointir Nous donnons, dans le cas du 
groupe 
sym\'etrique, les polyn\^omes de Kazhdan-Lusztig$P_\mu(\nu)$ pour toutes 
les permutations vexillaires $\mu$ et pour $\nu$ quelconque. 
Nous utilisons pour ce faire 
la description de l'ordre de Bruhat \`a l'aide du  treillis 
enveloppant du groupe sym\'etrique.

\smallskip\ctitre Kazhdan-Lusztig polynomials for vexillary Schubert 
varieties\endctitre

{\bf Abstract}\pointir  We give Kazhdan-Lusztig polynomials 
$P_\mu(\nu)$ for all 
vexillary permutations $\mu$ (i.e. $\mu$ does not contain any substring 
$jikh$, $i<j<h<k$), and all $\nu$. We use the embedding of the symmetric 
group into its envelopping lattice, and the characterization of a permutation 
by the set of bigrassmannian ones which are below it with respect to the
Ehressmann-Bruhat order.

\vskip 5mm

\tenpoint

Zelevinsky [14] a d\'ecrit une r\'esolution des 
singularit\'es des sous-vari\'et\'es
de Schubert des Grassmanniennes, qui explicite dans ce cas les polyn\^omes 
de Kazhdan-Lusztig [5] comme polyn\^omes de Poincar\'e [6].

Cette famille de vari\'et\'es est incluse dans celle des sous-vari\'et\'es de
Schubert {\it vexillaires} (i.e. d'indice une permutation vexillaire) 
de la vari\'et\'e de drapeaux pour $Gl({\bb{C}}^n)$. Les classes correspondantes
dans l'anneau de cohomologie [10],  [12], [13], ou de Grothendieck [8],
 poss\`edent
nombre des propri\'et\'es combinatoires des classes dans le cas des 
vari\'et\'es de Grassmann.

Les permutations vexillaires interviennent aussi dans le crit\`ere de
non-singularit\'e de Lakshmibai et Sandhya :

\th TH\'EOR\`EME  [7]
\enonce  La vari\'et\'e de Schubert $X_\mu$, $\mu\in{\goth{S}}(n)$, est non singuli\`ere
\`a l'origine, et donc est lisse, ssi pour toute projection
$p : {\goth{S}}(n) \rightarrow {\goth{S}}(4)$, alors  


\qquad $p(\mu) \neq 2143 $ \ ( i.e. $\mu$ est vexillaire ) \qquad {\rm et} 
\qquad  $p(\mu) \neq 1324 $.
\endth

\smallskip
En d'autres termes, il n'existe pas de quadruple d'entiers
$1\leq i<j<h<k\leq n$ tel que 
$\mu(j) < \mu(i) < \mu(k) <\mu(h) $ ou 
$\mu(i)< \mu(h) < \mu(j) < \mu(k) $.

\smallskip
Nous avons choisi l'indexation des vari\'et\'es de Schubert pour laquelle
la vari\'et\'e de drapeau correspond \`a l'identit\'e, et la vari\'et\'e de Schubert
de dimension 0, \`a la permutation maximum $\omega = n\ldots 1$ de ${\goth{S}}(n)$.
Nous noterons en cons\'equence $P_\mu(\nu)$ les polyn\^omes de Kazhdan-Lusztig
que leurs d\'ecouvreurs [4] d\'esignaient quant \`a eux par 
$P_{\nu\omega,\, \mu\omega}(q)$.  En outre, nous consid\`ererons les permutations
comme appartenant au groupe sym\'etrique infini ${\goth{S}}(\infty) = lim {\goth{S}}(n)$,
${\goth{S}}(n)$ \'etant plong\'e dans ${\goth{S}}(n+1)$ par adjonction d'un point fixe 
$n+1$.

\smallskip
Les polyn\^omes de Kazhdan-Lusztig sont intimement li\'es aux propri\'et\'es 
de l'ordre de Bruhat sur le groupe sym\'etrique [1], [2].
En vertu de [11], nous plongeons le groupe sym\'etrique dans son 
treillis {\it enveloppant}, l'ordre de Bruhat \'etant l'ordre induit
par celui du treillis. Ce dernier est distributif, ses g\'en\'erateurs
\'etant les permutations {\it bigrassmanniennes}, qui ne sont autres
que les permutations ( que l'on notera $[r_0,r_1,r_2,r_3]$) 
 du type
$$(1\ldots r_0,  r_0+r_2+1, \ldots r_0+r_2+r_1,
r_0+1,\ldots r_0+r_2, r_0+r_2+r_1+1, \ldots  r_0+r_1+r_2+r_3 ) \ ,  $$
o\`u $r_0, r_3\geq0 $, $r_1,r_2 \geq1$ et $r_0+r_1+r_2+r_3 =n$.
Ces permutations sont obtenues en coupant $1,\ldots, n$ en 4 blocs,
et en permutant les deux blocs centraux.

D'apr\`es [11], une permutation $\mu$ est d\'etermin\'ee par 
l'ensemble $B(\mu)$ des bigrassmanniennes plus petites 
(au sens de l'ordre d'Ehresmann-Bruhat) qu'elle, et 
$\mu\geq\nu$ ssi $B(\mu) \supseteq B(\nu)$. Les \'el\'ements maximaux de $B(\mu)$
sont appel\'es les {\it rectrices } de $\mu$, et correspondent bijectivement
aux points essentiels de Fulton [4].

\smallskip
Soit $b= [r_0,r_1r_2,r_3]$ une bigrassmannienne, et 
 $\nu\in{\goth{S}}(n) $ telle que $b\leq\nu$. La 
 {\it  distance} $d\in{\bb{N}}$ de $\nu$ \`a $b$ 
 est le plus grand entier $d$
tel que $[r_0-d,\,  r_1+d,\,  r_2+d,\, r_3-d] \, \leq \nu$.

Enfin, on appelera {\it niveau} d'une permutation $\nu$ par rapport
\`a une autre $\mu$, lorsque $\mu\leq\nu$, 
 le vecteur $v[\mu\rightarrow \nu]$ des distances
de $\nu$ aux rectrices de $\mu$. 

Moyennant ces d\'efinitions, et les formules donn\'ees dans [9],
 on peut d\'ecrire les polyn\^omes 
$P_\mu(\nu)$ pour les permutations vexillaires:

\th TH\'EOR\`EME
\enonce A toute partition $I$ dont le diagramme a $k$
coins est associ\'ee une fonction 
$f_I : {\bb{N}}^k \rightarrow {\bb{N}}[q]$ dans 
l'ensemble des polyn\^omes en $q$
\`a coefficients positifs.

Soit $\mu$ une permutation vexillaire, $I$ la partition obtenue en r\'eordonnant
son code. Alors pour toute permutation $\nu\geq\mu$, on a
$$P_\mu(\nu) = f_I ( v[\mu\rightarrow \nu] ) \ ,$$
o\`u $v[\mu\rightarrow \nu]$ est le niveau de $\nu$ au dessus de $\mu$.

En particulier, la fonction $f_I$ est d\'etermin\'ee 
par le cas des permutations grassmanniennes de code $0\cdots 0 \, I \, 0\cdots$
d\'ecrit en [9].
\endth

\smallskip
La partie combinatoire de la preuve, trop longue pour \^etre donn\'ee dans
le cadre d'une note, repose sur le fait que les r\'ecurrences
ci-dessous suffisent \`a d\'eterminer de proche en proche
les polyn\^omes cherch\'es.

On veut montrer que la fonction inconnue ne d\'epend que de 
la partition obtenue en r\'eordonnant le code de $\mu$. 
On consid\`ere donc simultan\'ement toutes 
les permutations correspondant \`a la m\^eme partition 
( c'est une classe vexillaire, au sens donn\'e dans [12]).
On a une induction entre classes vexillaires, qui correspond \`a 
l'accroissement de la plus grande part de la partition. 
Enfin, on utilise les r\'ecurrences 
suivantes (cf. [9]) d\'eduites de celles de
 de Kazhdan-Lusztig, mais n'impliquant pas
les  ar\^etes difficiles \`a calculer du graphe de Kazhdan-Lusztig.
Ces relations portent sur des couples de permutations dont on modifie
un triple de valeurs adjacentes situ\'ees \`a la m\^eme place,
le triple \'etant not\'e $\{a<b<c \}$ pour  les $\nu$ et
$\{1<2<3\}$ pour les $\mu$:

$$\kern -7mm P_{\ldots 213\ldots}(\ldots cab \ldots ) 
- P_{\ldots 213\ldots  } (\ldots bac \ldots)  =
q\bigl(P_{\ldots 231\ldots}(\ldots acb \ldots )  
-P_{\ldots 231\ldots}(\ldots abc \ldots ) \bigr)
 $$
$$\kern -7mm P_{\ldots 132\ldots}(\ldots bca \ldots ) 
- P_{\ldots 132\ldots  } (\ldots acb \ldots)  =
q\bigl(P_{\ldots 312\ldots}(\ldots bac \ldots )  
-P_{\ldots 312\ldots}(\ldots abc \ldots ) \bigr)
 $$
$$\kern-7mm P_{\ldots 213\ldots}(\ldots bac \ldots ) 
- P_{\ldots 213\ldots  } (\ldots abc \ldots)  =
P_{\ldots 231\ldots}(\ldots bca \ldots )  
-P_{\ldots 231\ldots}(\ldots acb \ldots ) 
 $$
$$\kern-7mm P_{\ldots 132\ldots}(\ldots acb \ldots ) 
- P_{\ldots 132\ldots  } (\ldots abc \ldots)  =
P_{\ldots 312\ldots}(\ldots cab \ldots )  
-P_{\ldots 312\ldots}(\ldots bac \ldots ) 
 $$


\smallskip

\setbox2=\hbox{$\mid$}
\setbox3=\hbox{$\bullet$}
\setbox4=\hbox{$\mid$}
\setbox11=\vbox{\box2\nointerlineskip\box3\nointerlineskip\box4}
\setbox21=\hbox{\box11}

\setbox2=\hbox{$\mid$}
\setbox3=\hbox{$\bullet$}
\setbox4=\hbox{$\mid$}
\setbox5=\hbox{$\bullet$}
\setbox6=\hbox{$\mid$}
\setbox11=\vbox{\box2\nointerlineskip\box3\nointerlineskip\box4
\nointerlineskip\box5\nointerlineskip\box6}
\setbox41=\hbox{\box11}

\setbox5=\hbox{\kern 3pt$\mid$}
\setbox6=\hbox{$\bigwedge$}
\setbox12=\vbox{\box5\nointerlineskip\box6}
\setbox22=\hbox{\box12}

\setbox8=\hbox{$\kern 4pt \wedge$}
\setbox7=\hbox{$\bigwedge$}
\setbox13=\vbox{\box7 \nointerlineskip\box8}
\setbox23=\hbox{\box13}
Les fonctions $f_I$ ne d\'ependent pas des partitions $I$, mais seulement
des arbres associ\'es \`a ces partitions (cf. [9]). Ainsi, pour 
${\goth{S}}(6)$, les arbres irr\'eductibles sont 

\qquad \raise 9pt \hbox{$\mid$} \qquad \raise 3pt \hbox{\unhbox21} \qquad \unhbox41\qquad 
\raise 8pt \hbox{\unhcopy22\ ,}  


de fonctions correspondantes ( avec $[x] = 1 +q\cdots + q^{x-1}$) 

\smallskip
$f_1(x) = [x+1]$, 
$f_{22}(x) = [x+1][x+2]/[2]$,

 
$f_{333}(x) = [x+1][x+2][x+3]/[2][3]$, 


$f_{233}(y,z) =  [y+1][z+1] + q^3[y][z] + q^6 [y-1][z-1] +
q^9 [y-2][z-2] +\cdots $.

\smallskip
Ces quatre fonctions permettent d'exprimer tous les polyn\^omes de 
Kazhdan-Lusztig $P_\mu(\nu)$, pour toutes les permutations $\mu$
image d'une permutation vexillaire de ${\goth{S}}(6)$ par le
plongement ${\goth{S}}(6) \hookrightarrow {\goth{S}}(1)\times \cdots {\goth{S}}(1)\times
{\goth{S}}(6)\times{\goth{S}}(1)\times\cdots  $

\smallskip
Par exemple, 
 $\mu = 15764238$ a pour code $(03432000)$; par r\'eordonnement, on trouve
la partition  $2334$ qui donne l'arbre 
 \quad  \unhbox23 .  Cet arbre d\'ecompose en les deux arbres
\ $\mid$ \ et \  \unhbox22 \ , et donc
$$f_{2334}(x,y,z) = f_1(x) f_{233}(y,z)  \ . $$

\smallskip
La permutation $\omega=87654321$ est au niveau $[1,1,1]$ au dessus de
$\mu$, puisque $[0440]$, $[0530]$ et $[1250]$ sont les bigrassmanniennes
maximales appartenant \`a 
${\goth{S}}(8)$ d\'eduites des trois rectrices de $\mu$ : 
$[1331]$, $[1421]$, $[2141]$.

Ceci implique que les param\`etres $x,y,z$ sont 0 ou 1, et donc qu'il n'y a
que $2^3$ polyn\^omes de Kazhdan-Lusztig $P_\mu(\nu)$ possibles (pour $\nu$ 
variable), \`a savoir :

\smallskip
\noindent
$f_{2334}(000)=1$, 

\noindent $f_{2334}(010)=f_{2334}(001)= 1+q$ 
($\nu=56781234$, $\nu=45678123$)

\noindent $f_{2334}(011)=1+2q+q^2+q^3$ ($\nu=56784123$), 

\noindent 
$f_{2334}(100)=1+q$ ($\nu=17854236$) 

\noindent $f_{2334}(110)= f_{2334}(101)= (1+q)^2$
($\nu=57861234$, $\nu=47856123$), 

\noindent $ f_{2334}(111)= (1+q)(1+2q+q^3+q^4)$ ( $\nu=57864123$),

\smallskip
ce qui co\"\i ncide bien avec les valeurs fournies par 
Fokko du Cloux [3].



\vskip 3mm
Les 513 permutations vexillaires
de ${\goth{S}}(6)$ se distribuent en 15 classes suivant l'arbre associ\'e.
 Nous donnons le cardinal de chaque classe, ainsi que
la premi\`ere permutation de la classe (pour l'ordre lexicographique), et son
code :

$f_{333} $: 456123 (333000),  card 6

$f_{2344} $: 564312 (4432),  card 2

$f_{233} $:  156423 (033200),  card 23

$f_{233} f_1 $: 465312 (343200),  card 3

$f_{22} $:   125634 (002200),  card 40

$f_{22}^2 $: 563412 (442200),   card 2

$f_{1} f_{22} $:  146523 (023200),  card 27

$f_{1}^2 f_{22} $: 365412 (243200),  card 41

$f_{1} f_{233} $: 564132 (443010), card 80

$f_{1} f_{22}f_1 $: 465132 (343010),  card 9

$f_1^2 $:  123654 (000210),  card 205

$f_1^2 f_{22} $: 561432 (440210),  card 14

$f_1^3 $:  126543 (003210),  card 208

$f_1^4 $:  165432 (043210),  card 46

$f_1^5 $:  654321 (543210), card 1



\vskip 3mm

\centerline{\bf  Bibliographie}

\parindent 0mm
\vskip 3mm

[1] \ F. BRENTI,  A combinatorial formula for Kazhdan-Lusztig 
polynomials, {\it Invent. M. }, 118, 1994,  p. 371-394.


\smallskip
[2] \ F. BRENTI,  Kazhdan-Lusztig and R-polynomials from
a combinatorial point of view,  {\it pr\'epublication} , 1994.

\smallskip
[3] \ FOKKO DU CLOUX,  A transducer approach to
Coxeter groups, {\it pr\'epublication}, 1995.

\smallskip
[4]\ W. FULTON,  Flags, Schubert polynomials, degeneraci loci, 
{\it Duke Math.}, { 65} , 1992, p.  381-420.


\smallskip
[5]\ D. KAZDHAN, G. LUSZTIG,  Representations of Coxeter groups
and Hecke algebras, {\it Invent. M.},  53, 1979, p.  165-184.

\smallskip
[6]\ D.  D. KAZDHAN, G. LUSZTIG,
 Schubert varieties and Poincar\'e duality
{\it Proc. Symp. Pure M.},  34, A.M.S. , 1980, p.  185-203.

\smallskip
[7] \ V. LAKSHMIBAI, B. SANDHYA, 
  Criterion for smoothness of
Schubert varieties,  {\it Proc.Indian Acad. Sc. M.},  100, 1990,  p. 45-52.

\smallskip
[8]\ A. LASCOUX,  Anneau de Grothendieck de la vari\'et\'e de 
drapeaux, in  {\it The Grothendieck Festtchrift, vol III}, 
Birkha\"user , 1990,  p. 1-34.

\smallskip
[9]\ A. LASCOUX, M.P. SCH\"UTZENBERGER,  Polyn\^omes de
Kazdhan-Lusztig pour les grassmanniennes,  {\it Ast\'erisque },  87-88,
 1981, p.  249-266.

\smallskip
[10]\ A. LASCOUX, M.P. SCH\"UTZENBERGER,  Polyn\^omes de
Schubert,
{\it C.R. Acad. Sc. Paris},  294 , 1982,  p. 447-450.

\smallskip
[11]\ A. LASCOUX, M.P. SCH\"UTZENBERGER, 
Treillis et bases des groupes de Coxeter,
{\it pr\'epublication }, 1995.

\smallskip
[12]\ A. LASCOUX, M.P. SCH\"UTZENBERGER,  Schubert polynomials
and the Littlewood-Richardson rule, {\it  Letters in Math. Phys. },  10,
 1985, p.  111-124.


\smallskip
[13] \ I.G. MACDONALD,  Notes on Schubert Polynomials,
Pub. LACIM, UQAM, Montr\'eal , 1991.  

\smallskip
[14]\ A. ZELEVINSKY,  Small resolutions of singularities of
Schubert varieties, {\it  Funct. Anal. Pry.},  17 , 1983, p. 142-144.
\bye

