Une base sym�trique de l'alg�bre\\ des coinvariants quasi-sym�triques
Fr�d�ric Chapoton
On d�crit une nouvelle base de l'alg�bre des coinvariants quasi-sym�triques, qui est stable par l'involution naturelle et index�e par les triangulations d'un polygone r�gulier.
quasisym.tex
\documentclass[a4paper,10pt]{article}
\usepackage{amsmath,amssymb}
\usepackage[frenchb]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{graphicx}

\newcommand{\x}{\mathsf{x}}
\newcommand{\BB}{\mathsf{B}}
\newcommand{\racine}{\#}
\newcommand{\extr}{\operatorname{Ext}(T)}

\newtheorem{theorem}{Th�or�me}[section] 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{corollary}[theorem]{Corollaire} 
\newtheorem{lemma}[theorem]{Lemme} 
\newtheorem{definition}{Definition}
 
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{example}[theorem]{Example} 
\newtheorem{problem}[theorem]{Problem} 
\newtheorem{algorithm}[theorem]{Algorithm} 

\newenvironment{proof}{\begin{trivlist}\item{\bf{Preuve.}}}
  {\hfill\rule{2mm}{2mm}\end{trivlist}}

\title{Une base sym�trique de l'alg�bre\\ des coinvariants quasi-sym�triques}
\author{Fr�d�ric Chapoton}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
  On d�crit une nouvelle base de l'alg�bre des coinvariants
  quasi-sym�triques, qui est stable par l'involution naturelle et
  index�e par les triangulations d'un polygone r�gulier.
\end{abstract}

\setcounter{section}{-1}

\section{Introduction}

L'alg�bre des coinvariants est un objet classique associ� � chaque
groupe de Coxeter fini $W$ \cite{steinberg}. Cette alg�bre est d�finie
comme le quotient de l'alg�bre des polyn�mes sur l'espace vectoriel
sur lequel $W$ agit par r�flexions, par l'id�al homog�ne engendr� par
les polyn�mes invariants homog�nes non constants. Le quotient est une
alg�bre gradu�e de dimension finie donn�e par l'ordre de $W$.

Dans le cas du groupe sym�trique sur $n+1$ lettres, on peut expliciter
cette construction comme le quotient de l'alg�bre des polyn�mes en
$\x_1,\dots,\x_{n+1}$ par l'id�al homog�ne engendr� par les fonctions
sym�triques �l�mentaires. Plus r�cemment, une notion plus faible que
celle de polyn�me sym�trique est apparue \cite{gessel}. Un polyn�me
est dit quasi-sym�trique si, pour toute suite d'exposants
$(m_1,\dots,m_k)$ fix�e, tous les mon�mes $\x_{i_1}^{m_1}\dots
\x_{i_k}^{m_k}$ pour une suite \emph{croissante} d'indices
$i_1<i_2<\dots<i_k$ ont le m�me coefficient. En particulier, les
polyn�mes sym�triques sont aussi quasi-sym�triques.

Dans \cite{ba,bba}, la notion d'alg�bre coinvariante quasi-sym�trique
a �t� introduite et �tudi�e. Elle est d�finie comme le quotient de
l'alg�bre des polyn�mes en $\x_1,\dots,\x_{n+1}$ par l'id�al homog�ne
engendr� par les polyn�mes quasi-sym�triques homog�nes non constants.
C'est une alg�bre gradu�e. Il est d�montr� dans \cite{bba} que cette
alg�bre est de dimension finie, donn�e par le nombre de Catalan
$c_{n+1}$. La preuve est la construction explicite d'un ensemble de
mon�mes index�s par les chemins de Dyck de longueur $2n+2$, dont les
images dans le quotient forment une base de l'alg�bre des coinvariants
quasi-sym�triques.

Dans le cas des coinvariants usuels, le groupe de Coxeter $W$ agit par
automorphismes sur le quotient et on obtient une d�composition
int�ressante du module r�gulier. Dans le cas des coinvariants
quasi-sym�triques, le seul automorphisme de la situation est le
renversement qui envoie $\x_i$ sur $\x_{n+2-i}$. Cette involution
pr�serve l'id�al des fonctions quasi-sym�triques sans terme constant
et passe donc au quotient.

La motivation initiale de cet article est le fait que l'action de
cette involution semble difficile � d�crire dans la base des mon�mes
associ�s aux chemins de Dyck. On construit donc une nouvelle base,
dans laquelle l'involution agit par permutation. Cette base est form�e
de polyn�mes dont le terme dominant pour l'ordre naturel sur les
variables $\x_1,\dots,\x_{n+1}$ redonne les mon�mes associ�s aux
chemins de Dyck.

Il appara�t que l'ensemble naturel d'indexation de cette nouvelle base
est non pas l'ensemble des chemins de Dyck, mais celui des
triangulations d'un polygone r�gulier. Cet ensemble joue un r�le
primordial dans la th�orie des alg�bres � grappes de Fomin et
Zelevinsky \cite{cluster2}. Cet article donne donc un premier
rapprochement entre les alg�bres � grappes et les fonctions
quasi-sym�triques. Il se trouve que la construction de la base index�e
par les triangulations passe par le choix d'une triangulation de base
en forme d'�ventail. Dans le cadre de la th�orie des alg�bres �
grappes, ce choix correspond au carquois �qui-orient� de type $A_n$,
voir par exemple \cite{CCS}.

L'article est organis� comme suit. On commence par d�finir une
bijection \textit{ad hoc} entre triangulations et chemins de Dyck.
Ensuite on montre que, par cette bijection, le mon�me dominant du
polyn�me associ� � une triangulation est le mon�me associ� au chemin
de Dyck correspondant, ce qui entra�ne imm�diatement le r�sultat
principal.
 
\section{Bijection}

Soit $n$ un entier positif ou nul. On d�finit dans cette section une
bijection entre
\begin{enumerate}
\item les triangulations d'un polygone r�gulier � $n+3$ cot�s,
\item les chemins de Dyck de longueur $2n+2$. 
\end{enumerate}
Il est bien connu que ces deux ensembles ont pour cardinal le nombre
de Catalan 
\begin{equation}
  c_{n+1}=\frac{1}{n+2}\binom{2n+2}{n+1}.
\end{equation}
Par d�finition, un chemin de Dyck est une suite de pas verticaux
(``mont�es'') et horizontaux (``descentes'') qui reste au dessus de la
diagonale, voir la partie droite de la figure \ref{fig:bijection}.

La bijection est illustr�e par un exemple dans la figure
\ref{fig:bijection}.

Avant toute chose, on fixe une triangulation de base en forme
d'�ventail, c'est-�-dire form�e par toutes les diagonales contenant un
sommet choisi, not� $\racine$. On dessine cette triangulation avec le
sommet commun � toutes les diagonales plac� en bas. Les diagonales de
cette triangulation de base seront dites ``n�gatives'' et num�rot�es
de $1$ � $n$ de gauche � droite. Les diagonales qui n'interviennent
pas dans la triangulation de base sont dites ``positives''. On
num�rote aussi de $1$ � $n$ les sommets aux extr�mit�s des diagonales
n�gatives.

\smallskip

On associe alors un chemin de Dyck $D(T)$ � chaque triangulation $T$,
par r�currence sur $n$. Pour $n=0$, � la seule triangulation du
polygone � trois cot�s est associ�e le seul chemin de Dyck de longueur
$2$.

Si $n$ est non nul, on regarde le sommet $*$ du polygone plac� �
droite du sommet $\racine$ dans le sens trigonom�trique. On distingue
deux cas.

Si le sommet $*$ participe � un seul triangle de la triangulation $T$
\textit{i.e.} n'est contenu dans aucune diagonale de $T$, on lui
associe le chemin de Dyck obtenu en encadrant par une mont�e et une
descente le chemin de Dyck $D(T')$ associ� � la triangulation $T'$ du
polygone � $n+2$ cot�s qui est d�finie comme $T$ moins le triangle
adjacent � $*$. Le sommet distingu� $\racine$ de $T'$ est celui de
$T$.

Si le sommet $*$ participe � plusieurs triangles, on d�coupe la
triangulation en autant de morceaux (le long des diagonales contenant
$*$), voir la figure \ref{fig:morceaux}. Le sommet $*$ donne un sommet
dans chacun de ces morceaux. On prend dans chacun des morceaux le
sommet � gauche de $*$ comme sommet distingu� $\racine$. Par
r�currence, on associe un chemin de Dyck � chacun des morceaux et on
les concat�ne dans l'ordre des morceaux induit par l'ordre
de gauche � droite au voisinage du sommet $*$ dans $T$, voir les
figures \ref{fig:bijection} et \ref{fig:morceaux}.

C'est clairement une bijection. La bijection inverse est aussi d�finie
par r�currence sur $n$. On d�compose un chemin de Dyck r�ductible pour
la concat�nation en ses composantes irr�ductibles et on recompose une
triangulation par juxtaposition. Pour les chemins de Dyck
irr�ductibles, on enl�ve une mont�e et une descente, on obtient une
triangulation par r�currence et on rajoute un triangle.

\begin{figure}
  \begin{center}
    \includegraphics[width=8cm]{bijections.eps}
  \end{center}
  \caption{Exemple pour la bijection}
  \label{fig:bijection}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[width=10cm]{morceaux.eps}
  \end{center}
  \caption{D�composition en morceaux}
  \label{fig:morceaux}
\end{figure}

\begin{lemma}
  \label{premierspas}
  Le nombre de pas verticaux initiaux du chemin de Dyck $D(T)$ est le
  nombre de diagonales n�gatives dans $T$ plus $1$.
\end{lemma}

\begin{proof}
  La preuve se fait par r�currence. L'�nonc� est vrai pour $n=0$. On
  distingue deux cas comme dans la d�finition de la bijection. Dans le
  cas o� $*$ est dans une seule diagonale, les deux quantit�s
  augmentent de $1$. Dans l'autre cas, les deux quantit�s sont inchang�es.
\end{proof}

\section{Polyn�mes}

On associe � chaque diagonale un polyn�me en les variables
$\{\x_1,\dots,\x_{n+1}\}$ comme suit. On associe la constante $1$ aux
diagonales n�gatives. Chaque diagonale positive coupe un ensemble de
diagonales n�gatives cons�cutives de $i$ � $j$. En fait, ceci donne
une bijection entre les diagonales positives et les segments de
$\{1,\dots,n\}$. On peut donc parler de la diagonale positive $(i,j)$,
� qui on associe alors la somme des $\x_{k}-\x_{k+1}$ pour
$k=i,\dots,j$ soit $\x_{i}-\x_{j+1}$.

On associe alors � chaque triangulation $T$ le produit $\BB_T$ des
polyn�mes associ�s � ses diagonales. Dans l'exemple de la figure
\ref{fig:bijection}, on obtient
\begin{equation}
  \BB_T=(\x_1-\x_2)(1)(\x_3-\x_4)(\x_3-\x_6)(\x_5-\x_6).
\end{equation}

\smallskip

Par ailleurs, comme dans \cite{bba,ba}, on associe un mon�me $M_D$ en
$\{\x_1,\dots,\x_n\}$ � chaque chemin de Dyck $D$. On repr�sente un
chemin de Dyck par une suite de pas d'une unit� vers le haut
(``mont�e'') ou vers la droite (``descente'') dans une grille. On
num�rote les colonnes internes de la grille de $1$ � $n$, voir la
partie droite de la figure \ref{fig:bijection}. On convient que chaque
pas vertical d'indice $i$ correspond � la variable $\x_{i}$. Le mon�me
$M_D$ est alors le produit des contributions des pas verticaux.  Dans
l'exemple de la figure \ref{fig:bijection}, on obtient
\begin{equation}
  M_{D(T)}=\x_1\x_3\x_3\x_5.  
\end{equation}

On d�finit un ordre sur les mon�mes en ordonnant les variables par
\begin{equation}
  \x_1 \ggg \x_2 \ggg \dots \ggg \x_{n+1}.
\end{equation}

Le mon�me dominant d'un polyn�me pour cet ordre est celui o�
intervient la plus grande puissance de $\x_1$, puis en cas d'ambigu�t�
la plus grand puissance de $\x_2$ et ainsi de suite.

\begin{proposition}
  \label{correspond}
  Le mon�me dominant du polyn�me $\BB_T$ associ� � une triangulation
  $T$ est le mon�me $M_{D(T)}$ associ� au chemin de Dyck $D(T)$
  correspondant � $T$ via la bijection ci-dessus.
\end{proposition}

\begin{proof}
  Par r�currence sur $n$. La proposition est vraie pour $n=0$.
  Soit donc $n$ non nul. On distingue deux cas.

  Supposons d'abord que le sommet $*$ participe � un seul triangle de
  la triangulation $T$. Alors la triangulation $T$ contient la
  diagonale n�gative $n$. Le polyn�me $\BB_T$ ne fait donc pas
  intervenir $\x_{n+1}$ et est �gal au polyn�me $\BB_{T'}$ associ� �
  la triangulation raccourcie en $*$. De m�me, le chemin de Dyck
  $D(T)$ est obtenu par concat�nation d'une mont�e, du chemin de Dyck
  $D(T')$ et d'une descente. Donc le mon�me associ� � $D(T)$ est le
  m�me que celui associ� au chemin $D(T')$. On conclut par hypoth�se
  de r�currence que le mon�me dominant de $\BB_T$ est $M_{D(T)}$.

  Supposons maintenant que le sommet $*$ participe � plusieurs
  triangles de $T$. Soit $\extr$ l'ensemble des nombres $k$ dans
  $\{1,\dots,n\}$ tels que la diagonale n�gative $k$ partage un sommet
  avec un diagonale de $T$ contenant $*$. On va num�roter les
  diagonales de $T$ contenant $*$ par les �l�ments de $\extr$.

  Dans la d�finition de $\BB_T$ comme produit sur les diagonales de
  $T$, on peut s�parer les contributions des diagonales strictement
  contenues dans les diff�rents morceaux et la contribution des
  diagonales de $T$ s�parant les morceaux. On va traiter s�par�ment le
  morceau le plus � gauche et les autres morceaux. Ces autres morceaux
  sont num�rot�s par l'�l�ment de $\extr$ qui les borde sur leur
  gauche.

  La contribution des diagonales entre les morceaux est 
  \begin{equation}
    \prod_{k \in \extr} \left( \x_{k+1}-\x_{n+1} \right).
  \end{equation}
  
  Consid�rons le premier morceau et soit $k_{\min}$ le plus petit
  �l�ment de $\extr$. La contribution du premier morceau est
  \begin{equation}
    \prod_{{1\leq i\leq j< k_{\min}}\atop{(i,j) \in T}} 
    \left(\x_{i}-\x_{j+1}\right).
  \end{equation}

  Consid�rons maintenant $k\in \extr$ et le morceau correspondant,
  situ� � droite de $k$. Soit $k'$ l'�l�ment suivant de $\extr$ ou
  bien posons $k'=n+1$ si $k$ est le plus grand �l�ment de $\extr$. La
  contribution du morceau $k$ est alors
  \begin{equation}
    \prod_{{k+1\leq i < k'}\atop{(k+1,i) \in T}} \left(\x_{k+1}-\x_{i+1}\right)
    \prod_{{k+1< i\leq j< k'}\atop{(i,j) \in T}} \left(\x_{i}-\x_{j+1}\right),
  \end{equation}
  o� le premier facteur est associ� aux diagonales du morceau $k$ qui
  contiennent le sommet $k$.

  On a donc montr� que $\BB_T$ est le produit de facteurs associ�s �
  chaque morceau : pour le premier morceau,
  \begin{equation}
    \prod_{{1\leq i\leq j< k_{\min}}\atop{(i,j) \in T}} \left(\x_{i}-\x_{j+1}\right)
  \end{equation}
  et, pour le morceau � droite de $k$ dans $\extr$,
  \begin{equation}
    \left(\x_{k+1}-\x_{n+1} \right)
    \prod_{{k+1\leq i < k'}\atop{(k+1,i) \in T}} \left(\x_{k+1}-\x_{i+1}\right)
    \prod_{{k+1< i\leq j< k'}\atop{(i,j) \in T}} \left(\x_{i}-\x_{j+1}\right).
  \end{equation}

  Regardons maintenant l'image $D(T)$ de $T$ par la bijection. C'est
  la concat�nation des images des morceaux de $T$. Par d�finition du
  mon�me associ�, celui-ci est le produit des contributions de chaque
  morceau avec un d�calage des indices convenable et des contributions
  des pas verticaux initiaux des morceaux (sauf le premier).

  Par hypoth�se de r�currence, la contribution du premier morceau est
  \begin{equation}
    \prod_{{1\leq i\leq j< k_{\min}}\atop{(i,j) \in T}} \x_{i}.
  \end{equation}

  La contribution du morceau entre $k\in \extr$ et l'�l�ment suivant
  $k'$ de $\extr$ est donn�e, par hypoth�se de r�currence, par
  \begin{equation}
    \x_{k+1}^{\ell_k}    
    \prod_{{k+1< i\leq j< k'}\atop{(i,j) \in T}} \x_{i},
  \end{equation}
  o� $\ell_k$ est le nombre de pas verticaux initiaux du morceau $k$.

  Par le lemme \ref{premierspas} appliqu� au morceau $k$, on sait que
  le nombre $\ell_k$ de pas verticaux initiaux dans le morceau $k$ de
  $D(T)$ est �gal � $1$ plus le nombre de diagonales dans le morceau
  $k$ de $T$ qui contiennent le sommet $k$. La contribution du morceau
  $k$ au mon�me $M_{D(T)}$ est donc
  \begin{equation}
    \x_{k+1}\prod_{{k+1\leq i < k'}\atop{(k+1,i) \in T}} \x_{k+1}     
    \prod_{{k+1< i\leq j< k'}\atop{(i,j) \in T}} \x_{i}.
  \end{equation}
  
  On v�rifie que le terme dominant de la contribution de chaque
  morceau � $\BB_T$ est bien �gal � la contribution de chaque morceau
  � $M_{D(T)}$. En prenant le produit des contributions des morceaux,
  on obtient l'�galit� voulue.
\end{proof}

\begin{theorem}
  \label{principal}
  Les polyn�mes $\BB_T$ associ�s aux triangulations forment une base
  de l'alg�bre des coinvariants quasi-sym�triques. Cette base est
  stable par le renversement des variables $\x_{i} \mapsto
  \x_{n+2-i}$. Les deux choix naturels d'ordre total sur les variables
  donnent deux bases monomiales, en prenant les mon�mes dominants des
  polyn�mes $\BB_T$.
\end{theorem}

\begin{proof}
  Dans \cite{bba}, il est d�montr� que les classes des mon�mes $M_D$
  associ�s aux chemins de Dyck forment une base de l'anneau des
  coinvariants quasi-sym�triques. On d�duit alors de la proposition
  \ref{correspond} que les classes des polyn�mes $\BB_T$ forment aussi
  une base. Le fait que cette base soit stable par le renversement est
  imm�diat : l'image de $\BB_T$ est $\BB_{T'}$ o� la triangulation
  $T'$ est obtenue par renversement de $T$. Enfin la derni�re
  assertion est juste une reformulation de la proposition
  \ref{correspond} et son image par le renversement.
\end{proof}

\bibliographystyle{plain}
\bibliography{quasisym}

\end{document}

quasisym.bbl
\begin{thebibliography}{1}

\bibitem{bba}
J.-C. Aval, F.~Bergeron, and N.~Bergeron.
\newblock Ideals of quasi-symmetric functions and super-covariant polynomials
  for {$S\sb n$}.
\newblock {\em Adv. Math.}, 181(2):353--367, 2004.

\bibitem{ba}
J.-C. Aval and N.~Bergeron.
\newblock Catalan paths and quasi-symmetric functions.
\newblock {\em Proc. Amer. Math. Soc.}, 131(4):1053--1062 (electronic), 2003.

\bibitem{CCS}
P.~Caldero, F.~Chapoton, and R.~Schiffler.
\newblock Quivers with relations arising from clusters ({$A\sb n$} case).
\newblock {\em T.A.M.S.}, 2005.

\bibitem{cluster2}
S.~Fomin and A.~Zelevinsky.
\newblock Cluster algebras. {II}. {F}inite type classification.
\newblock {\em Invent. Math.}, 154(1):63--121, 2003.

\bibitem{gessel}
Ira~M. Gessel.
\newblock Multipartite {$P$}-partitions and inner products of skew {S}chur
  functions.
\newblock In {\em Combinatorics and algebra (Boulder, Colo., 1983)}, volume~34
  of {\em Contemp. Math.}, pages 289--317. Amer. Math. Soc., Providence, RI,
  1984.

\bibitem{steinberg}
R.~Steinberg.
\newblock Differential equations invariant under finite reflection groups.
\newblock {\em Trans. Amer. Math. Soc.}, 112:392--400, 1964.

\end{thebibliography}
