%%%%%%% This is LaTeX2e, compile twice %%%%%%%

\documentclass[12pt]{article}
\usepackage{amssymb,amstex}

\setlength{\topmargin}{0.0in} 
\setlength{\textheight}{23cm}
\setlength{\headsep}{0.1cm}
\setlength{\textwidth}{15.1cm}
\setlength{\parindent}{0.6cm} 
\setlength{\evensidemargin}{0.35in} 
\setlength{\oddsidemargin}{0.35in} 

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{conjecture}[theorem]{Conjecture}

\def\proof{\smallskip\noindent {\it Proof. \ }}
\def\proofof#1{\smallskip\noindent {\it Proof of #1. \ }}
\def\endproof{\hfill$\square$\medskip}

\def\bt{\bar{\theta}}
\def\C{\mathbb{C}}
\def\E{{\cal E}}
\def\H{{\rm H}} 
\def\O{\Omega} 
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\S{\mathfrak{S}}
\def\T{{\cal T}}
\def\Z{\mathbb{Z}}
\def\QH{{\rm QH}} 
\def\al{\alpha}
\def\b{\mathfrak{b}}
\def\be{\beta}
\def\g{\mathfrak{g}}
\def\l{\ell}
\def\pa{\partial}
\def\s{\sigma}
\def\t{\tau}
\def\wt{\widetilde}
\def\wh{\widehat}
\def\wnot{w_\mathrm{o}}
\def\<{\left<\kern-.04in\left<\kern.01in}
\def\>{\kern.01in\right>\kern-.04in\right>}

\title{On a Quantum Version of Pieri's Formula
\footnotetext[0]{%
\emph{Key words and phrases.} Flag manifold, Monk's formula, Pieri's formula, 
quantum cohomology.}}

\author{{\sc \normalsize Alexander Postnikov}\\[.1in]
             \normalsize Department of Mathematics, M.I.T., Cambridge, MA 02139\\
            {\normalsize E-mail address: \tt apost@@math.mit.edu}}
\date{\small March~23, 1997}


\begin{document}
\maketitle

\begin{abstract} We give an algebro-combinatorial proof of a general version
of Pieri's formula following the approach developed by Fomin and Kirillov in
the paper ``Quadratic algebras, Dunkl elements, and Schubert calculus.'' We
prove several conjectures posed in their paper.  As a consequence, a new proof
of classical Pieri's formula for cohomology of complex flag manifolds, and
that of its analogue for quantum cohomology is obtained in this paper.
\end{abstract}



\section{Introduction}

The purpose of this paper is to investigate several consequences and
generalizations of quantum Monk's formula from~\cite{FGP}.  In our approach we
follow Fomin and Kirillov~\cite{FK}, who constructed a certain quadratic
algebra~$\E_n$ equipped with a family of pairwise commuting ``Dunkl
elements,'' which generate a subalgebra canonically  isomorphic to the
cohomology ring of complex flag manifold.  They observed that Pieri's formula
for the cohomology of flag manifolds can be deduced from a certain identity,
which conjecturally holds in~$\E_n$.  In this paper a more general Pieri-type
formula is proved, which specializes to their conjecture in a particular
case.

A quantum deformation of the algebra~$\E_n$ was also given in~\cite{FK}, along
with the conjecture that its subalgebra generated by the Dunkl elements is
canonically isomorphic to the (small) quantum cohomology of the flag manifold.
This statement is also a special case of our result.

%No wonder that 
Pieri's formula for multiplication in the quantum cohomology ring 
of flag manifolds can
also be obtained from our formula (but the opposite is not true).  Its
classical counterpart is the rule that was formulated by Lascoux and
Sch\"utzenberger~\cite{ls} and proved geometrically by Sottile~\cite{sottile}
(see also~\cite{winkel} for a combinatorial proof).
Pieri's formula for the quantum cohomology was recently proved by
Ciocan-Fontanine~\cite{ciocan2}, using nontrivial algebro-geometric
techniques.  
%The advantage (or disadvantage?) of our approach is that 
By contrast, our proof is combinatorial, and does not rely upon geometry at
all---once (quantum) Monk's formula is given.  Our proof seems to be new even
in the classical case.


\bigskip
The rest of Introduction is devoted to a brief account of main notions and
results related to the classical as well as the quantum cohomology rings of
complex flag manifolds.  For a more complete story, see~\cite{BGG},
\cite{FGP}, \cite{fulton}, \cite{mac}, and bibliography therein.  Although
many of the constructions below can be carried out in a more general setup of
an arbitrary semisimple Lie group, only the case of type~$A_{n-1}$ is
considered in this paper.

Let $Fl_n$ denote the manifold of complete flags of subspaces in~$\C^n$.
According to classical Ehresmann's result~\cite{Ehr}, the Schubert
classes~$\s_w$, indexed by the elements~$w$ of the  symmetric group~$S_n\,$,
form an additive $\Z$-basis of the cohomology ring $\H^*(Fl_n,\Z)$ of the flag
manifold.  

Multiplicative structure of~$\H^*(Fl_n,\Z)$ can be recovered from Borel's
theorem~\cite{borel}.  Let $s_{ij}$ be the element of~$S_n$ that
transposes~$i$ and~$j$.   Also let $s_i=s_{i\,i+1}$, $1\leq i\leq n-1$, be
the Coxeter generators of~$S_n$.  Borel's theorem says that~$\H^*(Fl_n,\Z)$ is
canonically isomorphic, as a graded algebra, to the quotient
\begin{equation}
  \label{eq:factor}
  \Z[x_1,x_2,\dots,x_n]\,/\left<e_1,e_2,\dots,e_n\right>,
\end{equation}
where $e_k=e_k(x_1,x_2,\dots,x_n)$ denotes the $k$th elementary symmetric
polynomial, for $k=1,2,\dots,n$; and $\left<e_1,\dots,e_n\right>$ is the ideal
generated by the~$e_k$.  The isomorphism is given by explicitly specifying
\[
  x_1+x_2+\dots+x_m\longmapsto \s_{s_m}\,,\quad m=1,2,\dots,n-1\,.
\]

A way to relate these two descriptions of the cohomology ring~$\H^*(Fl_n,\Z)$
was found by Bernstein, Gelfand, and Gelfand~\cite{BGG} and
Demazure~\cite{Dem}.  Lascoux and Sch\"utzenberger~\cite{ls} then constructed
the Schubert polynomials,  whose images in the
quotient~(\ref{eq:factor}) represent the Schubert classes~$\s_w$.

Recently attention has been drawn to the (small) quantum cohomology ring
$\QH^*(Fl_n,\Z)$ of the flag manifold.  We will not give here the definition
of quantum cohomology (see e.g.~\cite{fulton}), but we
mention that structure constants of quantum cohomology are $3$-point
Gromov-Witten invariants, which count the numbers of certain rational curves
and play a role in enumerative algebraic geometry.

As a vector space, the quantum cohomology of~$Fl_n$ is essentially the same as
the usual cohomology.  More precisely,
\[
  \QH^*(Fl_n,\Z)\cong \H^*(Fl_n,\Z)\otimes \Z[q_1,\dots,q_{n-1}].
\]
However, the multiplicative structure in~$\QH^*(Fl_n,\Z)$ is different.

A quantum analogue of Borel's theorem was suggested by Givental and
Kim~\cite{giv-kim}, and then justified by Kim~\cite{Kim} and
Ciocan-Fontanine~\cite{ciocan}.  Let
$E_1,E_2,\dots,E_n\in\Z[x_1,\dots,x_n;q_1,\dots,q_{n-1}]$ be the nonidentity
coefficients of the characteristic polynomial of the matrix
\begin{equation} 
\label{eq:matrix}
  \label{eq:G_n} 
  \left( 
    \begin{array}{ccccc} 
      x_1    & q_1    & 0      & \cdots  & 0      \\
      -1     & x_2    & q_2    & \cdots  & 0      \\
      0      & -1     & x_3    & \cdots  & 0      \\
      \vdots & \vdots & \vdots & \ddots  & \vdots \\
      0      & 0      & 0      & \cdots  & x_n 
    \end{array} 
  \right)\,. 
\end{equation} 
The $E_k$ are certain $q$-deformations of the elementary symmetric
polynomials~$e_k$.  If $q_1=\dots=q_{n-1}=0$ then $E_k$ specializes to~$e_k$.

Givental, Kim, and Ciocan-Fontanine showed that the quantum cohomology
ring~$\QH^*(Fl_n,\Z)$ is canonically isomorphic to the quotient
\begin{equation}
  \label{eq:q-factor}
  \Z[x_1,\dots,x_n;q_1,\dots,q_{n-1}]\,/\left<E_1,E_2,\dots,E_n\right>.
\end{equation}
Just as in the classical case, the isomorphism is given by specifying
\begin{equation}
  \label{eq:q-isom}
  x_1+x_2+\dots+x_m\longmapsto \s_{s_m}\,,\quad m=1,2,\dots,n-1\,.
\end{equation}

An important problem is to find the expansion of the quantum product
$\s_u\,{*}\,\s_w$ of two Schubert classes in the basis of Schubert classes,  where
``$*$'' denotes the multiplication in the quantum cohomology ring.

This problem was solved, or at least reduced to combinatorics, in~\cite{FGP}.
In that paper we gave a quantum analogue of the Bernstein-Gelfand-Gelfand
theorem and the corresponding deformation of Schubert polynomials of Lascoux
and Sch\"utzenberger.  We also proved there a quantum Monk's formula, which
generalizes the classical Monk's result~\cite{monk}.

Let us denote $q_{ij}=q_i q_{i+1}\cdots q_{j-1}$, for $i<j$.

\begin{theorem} {\rm (Quantum Monk's formula)~\cite[Theorem~1.3]{FGP}} \
  \label{th:monk}
   For $w\in S_n$ and $1\leq m<n$, the quantum product of Schubert classes
   $\s_{s_m}$ and $\s_w$ is given by
   \begin{equation}
      \label{eq:monk}
      \s_{s_m}*\s_w = \sum \s_{ws_{ab}} + \sum q_{cd}\,\s_{ws_{cd}}\,,
  \end{equation}
  where the first sum is over all transpositions $s_{ab}$ such that
  $a\leq m<b$ and $\l(ws_{ab})=\l(w)+1$, and the second sum is over 
  all transpositions $s_{cd}$ such that $c\leq r<d$ and $\l(ws_{cd})
    =\l(w)-\l(s_{cd})=\l(w)-2(d-c)+1$.
\end{theorem}

The formula~(\ref{eq:monk})  unambiguously determines the multiplicative
structure of the quantum cohomology ring~$\QH^*(Fl_n,\Z)$ with respect to the
basis of Schubert classes, since this ring is generated by the $2$-dimensional
classes~$\s_{s_r}$.  

As an example, we deduce a rule for the quantum product of any class~$\s_w$
with the class $\s_{c(k,m)}$, where $c(k,m)=s_{m-k+1}s_{m-k+2}\cdots s_m$
(Corollary~\ref{cor:pieri-QH}).   The main result of our paper is even more
general statement (Theorem~\ref{th:pieri}) that we call ``quantum Pieri's
formula.''  It is formulated in the language of the construction for the
cohomology of $Fl_n$ highlighted by Fomin and Kirillov.  We were able to
extend some of their results and provide a proof to the following conjectures
from~\cite{FK}: Conjecture~11.1, Conjecture~13.4, and Conjecture~15.1.


\bigskip
\textsc{Acknowledgments}.  
I am grateful to Sergey Fomin for introducing me to his paper with Anatol
Kirillov~\cite{FK}.



\section{Definitions}

Let us recall the definition of the quadratic algebra~$\E_n^p$ given by Fomin
and Kirillov~\cite[Section~15]{FK}.  (Their notation is slightly different
from ours.) The algebra $\E_n^p$ is generated over $\Z$ by the
elements~$\t_{ij}$ and $p_{ij}$, $i,j\in\{1,2,\dots,n\}$, subject to the
following relations:
\begin{align}
  \label{eq:en1}
  &\t_{ij}=-\t_{ji}\,, \quad \t_{ii} = 0\,,\\[.1in]
  \label{eq:en2}
  &\t_{ij}^2=p_{ij}\,,\\[.1in]
  \label{eq:en3}
  &\t_{ij}\t_{jk}+\t_{jk}\t_{ki}+\t_{ki}\t_{ij}=0\,,\\[.1in]
  \label{eq:en4}
  &[p_{ij},p_{kl}] = [p_{ij},\t_{kl}]=0\,,\quad\textrm{for any }
  i,j,k,\textrm{ and }l\,,\\[.1in]
  \label{eq:en5}
  &[\t_{ij},\t_{kl}]=0\,, \quad\textrm{for any distinct }
  i,j,k,\textrm{ and }l\,.
\end{align}
Here  $[a,b]=ab-ba$ is the usual commutator.
Remark that the generator $\t_{ij}$ was denoted by $[ij]$ in~\cite{FK}.
It follows from~(\ref{eq:en1}) and~(\ref{eq:en2}) that 
$p_{ij}=p_{ji}$ and $p_{ii}=0$.

The commuting elements~$p_{ij}$ can be viewed as formal parameters.  The
quotient~$\E_n$ of the algebra~$\E_n^p$ modulo the ideal generated by
the~$p_{ij}$ was the main object of study in~\cite{FK}.
Also an algebra~$\E_n^q$ was introduced in that paper.  It can be defined
as the quotient of~$\E_n^p$ by the ideal generated by the~$p_{ij}$ with
$|i-j|\geq 2$.  The image of $p_{i\,i+1}$ in~$\E_n^q$ is denoted~$q_i$. 

Following~\cite[Section~5]{FK}, define the \emph{``Dunkl elements''} $\theta_i$,
$i=1,\dots,n$, in the algebra~$\E_n^p$ by
\begin{equation}
  \label{eq:dunkl}
  \theta_i = \sum_{j=1}^n \t_{ij}.
\end{equation}

The following important property of these elements is not hard to deduce from
the relations~(\ref{eq:en1})--(\ref{eq:en5}).
\begin{lemma} {\rm \cite[Corollary~5.2 and Section~15]{FK}} \
  \label{lem:commute}
  The elements~$\theta_1,\theta_2,\dots,\theta_n$ commute pairwise.
\end{lemma}

Let $x_1,x_2,\dots,x_n$ be a set of commuting variables, and let~$p$ be a
shorthand for the collection of $p_{ij}$'s.  For a subset
$I=\{i_1,\dots,i_m\}$ in $\{1,2\dots,n\}$, we denote by $x_I$ the collection
of variables $x_{i_1},\dots,x_{i_m}$.  Define the \emph{quantum elementary
symmetric polynomial} (cf.~\cite[Section~3.2]{FGP} or
\cite[Section~15]{FK})
\begin{equation}
  \label{eq:elementary}
  E_k(x_I;p)=E_k(x_{i_1},x_{i_2},\dots,x_{i_m};p)
\end{equation}
by the following recursive formulas:
\begin{align}
  \label{eq:E1}
  E_0(x_{i_1},x_{i_2}&,\dots,x_{i_m};p)=1\,,\\[.1in]
  \notag
  E_k(x_{i_1},x_{i_2}&,\dots,x_{i_m};p)=
  E_k(x_{i_1},x_{i_2},\dots,x_{i_{m-1}};p)\\[.1in]
  \label{eq:E2}
  &+ \ E_{k-1}(x_{i_1},x_{i_2},\dots,x_{i_{m-1}};p)\,x_{i_m}\\%[.1in]
  \notag
  &+ \ \sum_{r=1}^{m-1}
  E_{k-2}(x_{i_1},\dots,\wh{x_{i_r}},\dots,x_{i_{m-1}};p)\, 
  p_{i_r\,i_{m}}\,,
\end{align}
where the notation $\wh{x_{i_r}}$ means that the corresponding term is
omitted.

The polynomial~$E_k(x_I;p)$ is symmetric in the sense that it is 
invariant under the simultaneous action of~$S_m$ on the variables 
$x_{i_a}$ and the $p_{i_a\,i_b}$.
One can directly verify from~(\ref{eq:E1}) and~(\ref{eq:E2}) that
\begin{align*}
  &E_1(x_{i_1},x_{i_2},\dots,x_{i_m};p)=x_{i_1}+x_{i_2}+\cdots+x_{i_m}
  \,,\\[.1in]
  &E_2(x_{i_1},x_{i_2},\dots,x_{i_m};p)=\sum_{1\leq a<b\leq m}
  (x_{i_a}x_{i_b}+p_{i_a\,i_b})\,.
\end{align*}

The polynomials~$E_k(x_I;p)$ have the following elementary monomer-dimer
interpretation~(cf.~\cite[Section~3.2]{FGP}).  A \emph{partial matching}
on the vertex set $I$ is a unordered collection of ``dimers'' $\{a_1,b_1\},
\{a_2,b_2\}, \dots$
%$a_1,b_1,a_2,b_2,\dots\in I$, 
and  ``monomers'' $\{c_1\},\{c_2\},\dots$ such that all $a_i, b_j, c_k$ are
distinct elements in~$I$. The \emph{weight} of a matching is the product
$p_{a_1\,b_1} p_{a_2\,b_2} \cdots x_{c_1} x_{c_2}\cdots $.  Then $E_k(x_I;p)$
is the sum of weights of all matchings which cover exactly~$k$ vertices
of~$I$.

For example, we have
\[
\begin{aligned}
E_3(x_1,x_2,x_3,x_4&;p)= x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4\\
&+  p_{12}\,(x_3 + x_4) + p_{13}\,(x_2 + x_4) + p_{14}\,(x_2 + x_3)\\
&+  p_{23}\,(x_1 + x_4) + p_{24}\,(x_1 + x_3) + p_{34}\,(x_1 + x_2)\,.
\end{aligned}
\]

Specializing $p_{ij}=0$, one obtains $E_k(x_I;0)=e_k(x_I)$, the 
usual elementary symmetric polynomial.
Assume that $p_{i\,i+1}=q_i$, $i=1,2,\dots,n-1$, and $p_{ij}=0$, for $|i-j|\geq 2$. 
Then the polynomial $E_k(x_1,\dots,x_n;q)$ is 
the quantum elementary polynomial~$E_k$, which is a coefficient
of the characteristic polynomial of the matrix~(\ref{eq:matrix}).
Here and below the letter~$q$ stands for the collection of $q_1,q_2,\dots,q_{n-1}$.



\section{Main result}

For a subset~$I=\{i_1,\dots,i_m\}$ in $\{1,2,\dots,n\}$, let $\theta_I$ denote
the collection of the elements $\theta_{i_1},\dots,\theta_{i_m}$, and
let $E_k(\theta_I;p)=E_k(\theta_{i_1},\dots,\theta_{i_m};p)$ denote the result
of substituting the Dunkl elements~(\ref{eq:dunkl})
in place of the corresponding~$x_i$ in~(\ref{eq:elementary}).
This substitution is well defined, due to Lemma~\ref{lem:commute}.
Our main result can be stated as follows:

\begin{theorem} {\rm (Quantum Pieri's formula)} \
\label{th:pieri}
Let $I$ be a subset in $\{1,2,\dots,n\}$, and
let $J=\{1,2,\dots,n\}\setminus I$.  Then, for $k\geq 1$, we have
in the algebra~$\E_n^p$:
\begin{equation}
  \label{eq:pieri}
  E_k(\theta_I;p) = \sum \t_{a_1\,b_1}\t_{a_2\,b_2}\cdots\t_{a_k b_k},
\end{equation}
where the sum is over all sequences $a_1,\dots,a_k,b_1,\dots,b_k$ 
such that {\rm ({i})} $a_j\in I,$ $b_j\in J$, for $j=1,\dots,k$; 
{\rm ({i}{i})} the $a_1,\dots,a_k$ are distinct; 
{\rm ({i}{i}{i})}  $b_1\leq \cdots\leq b_k$.
\end{theorem}

The proof of Theorem~\ref{th:pieri} will be given in~Section~\ref{sec:proof}.
In the rest of this section we summarize several corollaries of
Theorem~\ref{th:pieri}.

First of all, let us note that specializing $p_{ij}=0$ in
Theorem~\ref{th:pieri} results in Conjecture~11.1 from~\cite{FK}.

\begin{corollary} {\rm \cite[Conjecture~15.1]{FK}} \
\label{cor:relations-Ep}
For $k=1,2,\dots,n$, the following relation in the algebra~$\E_n^p$ holds
\[
  E_k(\theta_1,\theta_2,\dots,\theta_n;p)=0\,.
\]
\end{corollary}

\proof In this case, the sum
in~(\ref{eq:pieri}) is over the empty set.
\endproof

Define a $\Z[p]$-linear homomorphism~$\pi$ by
\[
  \begin{array}{c}
  \pi:\,\Z[x_1,x_2,\dots,x_n;p]\longrightarrow \E_n^p\\[.1in]
  \pi:\, x_i\longmapsto \theta_i\,.
  \end{array}
\]

\begin{corollary}
\label{cor:Ep}
The kernel of~$\pi$ is generated over $\Z[p]$ by
\begin{equation}
  \label{eq:Ek}
  E_k(x_1,x_2,\dots,x_n;p)\,,\quad k=1,2,\dots,n\,.
\end{equation}
\end{corollary}

\proof
All elements~(\ref{eq:Ek}) map to zero, due to Corollary~\ref{cor:relations-Ep}.
The statement now follows from dimension argument (cf.~\cite[Section~7]{FK}).
\endproof


In particular, we can define a homomorphism~$\bar{\pi}$ by
\[
  \begin{array}{c}
  \bar{\pi}:\,\Z[x_1,\dots,x_n]\longrightarrow
  \E_n\,,\\[.1in]
  \bar{\pi}:\,x_i\longmapsto \bt_i\,,
  \end{array}
\]
where~$\bt_i$ is the image in~$\E_n$ of the element~$\theta_i$.

\begin{corollary} {\rm \cite[Theorem~7.1]{FK}} \
The kernel of~$\bar{\pi}$ is generated by the elementary symmetric 
polynomials
\[
  e_k(x_1,x_2,\dots,x_n)\,,\quad k=1,2,\dots,n\,.
\]
Thus the subalgebra in~$\E_n$ generated by the~$\bt_i$
is canonically isomorphic to the cohomology of $Fl_n$,
which is isomorphic to the quotient~{\rm (\ref{eq:factor})\/}.
\end{corollary}

Likewise, let $\hat{\theta}_i$ be the image in~$\E_n^q$ of the
element~$\theta_i$, and let $\hat{\pi}$ be the $\Z[q]$-linear homomorphism
defined by
\[
  \begin{array}{c}
  \hat{\pi}:\,\Z[x_1,\dots,x_n;q]\longrightarrow \E_n^q\,,\\[.1in]
  \hat{\pi}:\,x_i\longmapsto \hat{\theta}_i\,.
  \end{array}
\]

\begin{corollary} {\rm \cite[Conjecture~13.4]{FK}} \
\label{cor:kernel-q}
The kernel of the homomorphism~$\hat{\pi}$ is generated 
over $\Z[q]$ by 
\begin{equation*}
E_k(x_1,x_2,\dots,x_n;q)\,,\quad k=1,2,\dots,n\,.  
\end{equation*}
Thus the subalgebra in~$\E_n^q$ generated over $\Z[q]$ by
the~$\hat{\theta}_i$ is canonically isomorphic to the quantum cohomology of
$Fl_n$, the latter being isomorphic to the quotient~{\rm (\ref{eq:q-factor})\/}.  
\end{corollary}



\section{Action on the quantum cohomology}

Recall that $s_{ij}$ is the transposition of~$i$ and~$j$ in~$S_n$,
$s_i=s_{i\,i+1}$ is a Coxeter generator,
and $q_{ij}=q_i q_{i+1}\cdots q_{j-1}$, for $i<j$.

Let us define the $\Z[q]$-linear operators $t_{ij}$, $1\leq
i<j \leq n$, acting on the quantum cohomology ring $\QH^*(Fl_n,\Z)$ by 
\begin{equation}
\label{eq:tij}
  t_{ij}(\s_w) =
  \left\{ 
    \begin{array}{ll}
      \s_{w s_{ij}} & \textrm{if } \l(w s_{ij})=\l(w)+1\,,\\[.05in]
      q_{ij}\, \s_{w s_{ij}} & \textrm{if } \l(w s_{ij})= \l(w) -2(j-i)+1
           \,,\\[.05in]
      0   & \textrm{otherwise.}
    \end{array}
  \right.
\end{equation}
By convention, $t_{ij}=-t_{ji}$, for $i>j$, and  $t_{ii}=0$.

Quantum Monk's formula (Theorem~\ref{th:monk}) can be stated as 
saying that the quantum product of~$\s_{s_m}$ 
and~$\s_w$ is equal to
\[
  \s_{s_m}*\s_w=\sum_{a\leq m<b} t_{ab}(\s_w)\,.
\]

The relation between the algebra~$\E_n^q$ and quantum cohomology 
of~$Fl_n$
is justified by the following lemma, 
which is proved by a direct verification.
\begin{lemma} {\rm \cite[Proposition~12.3]{FK}} \
The operators $t_{ij}$ given by~{\rm (\ref{eq:tij})} satisfy the
relations~{\rm (\ref{eq:en1})--(\ref{eq:en5})} %in the algebra~$\E_n^p$ 
with $\t_{ij}$ replaced by $t_{ij}$, $p_{i\,i+1}=q_i$,
and $p_{ij}=0$, for $|i-j|\geq 2$,
\end{lemma}

Thus the algebra~$\E_n^q$ acts on~$\QH^*(Fl_n,\Z)$ by 
$\Z[q]$-linear transformations
\[
  \t_{ij}:\,\s_w\longmapsto t_{ij}(\s_w)\,.
\]

Monk's formula is also equivalent to the claim that the Dunkl element
$\hat{\theta}_i$ acts on the quantum cohomology of~$Fl_n$ as the operator of
multiplication by~$x_i$,  the latter is defined via the
isomorphism~(\ref{eq:q-isom}).

Let us denote $c(k,m)=s_{m-k+1}s_{m-k+2}\cdots s_m$ 
and $r(k,m)=s_{m+k-1}s_{m+k-1}\cdots s_m$.
These are two cyclic permutations such that 
$c(k,m)=(m-k+1,m-k+2,\dots,m+1)$ and $r(k,m)=(m+k,m+k-1,\dots,m)$.

The following statement was geometrically proved in~\cite{ciocan}
(cf.\ also~\cite{FGP}).  For the reader's convenience and for 
consistency we show how to deduce it directly from Monk's formula.

\begin{lemma}
The coset of the polynomial $E_k(x_1,\dots,x_m;q)$ 
in the quotient ring~{\rm (\ref{eq:q-factor})} corresponds to the
Schubert class~$\s_{c(k,m)}$ under the isomorphism~{\rm (\ref{eq:q-isom}).}
Analogously, the coset of the polynomial~$E_k(x_{m+1},x_{m+2},\dots,x_n)$
corresponds to the class~$\s_{r(k,m)}$.
\end{lemma}

\proof  By~(\ref{eq:q-isom}) and~(\ref{eq:E2}), it is enough to check that
\[
  \s_{c(k,m+1)}=\s_{c(k,m)}+(\s_{s_{m+1}}-\s_{s_m})*\s_{c(k-1,m)}
  + q_m \s_{c(k-2,m-1)}.
\]
This identity immediately follows from Monk's formula:
\[
  (\s_{s_{m+1}}-\s_{s_m})*\s_{c(k-1,m)} = 
  (\sum_{b>m+1} t_{m+1\,b} - \sum_{a<m} t_{am})(\s_{c(k-1,m)})\,.
\]
The claim about~$\s_{r(k,m)}$ can be proved using a symmetric argument.
\endproof

It is clear now that Theorem~\ref{th:pieri} implies the following statement.  
This statement, though in a different form, was proved in~\cite{ciocan2}.
\begin{corollary} 
\label{cor:pieri-QH}
{\rm (Quantum Pieri's formulas: $\QH^*$ version)} \  
  For $w\in S_n$ and $0\leq k\leq m<n$, the product of Schubert 
  classes~$\s_{c(k,m)}$ 
  and~$\s_w$ in the quantum cohomology ring~$\QH^*(Fl_n,\Z)$
  is given by the formula
  \begin{equation}
    \s_{c(k,m)}*\s_w = \sum t_{a_1\,b_1}t_{a_2\,b_2}\cdots t_{a_k\,b_m}(\s_w),
  \end{equation}
  where the sum is over $a_1,\dots,a_k,b_1,\dots,b_k$ such that
  {\rm ({i})} $1\leq a_j\leq m< b_j<n$ for $j=1,\dots,k$; 
  {\rm ({i}{i})} the $a_1,\dots,a_k$ are distinct;  
  {\rm ({i}{i}{i})} $b_1\leq \cdots \leq b_k $. 

  Likewise, the quantum product of Schubert classes~$\s_{r(k,m)}$ and~$\s_w$ 
  is given by the formula
  \begin{equation}
    \s_{r(k,m)}*\s_w = \sum t_{c_1\,d_1}t_{c_2\,d_2}\cdots t_{c_k\,d_k}(\s_w),
  \end{equation}
  where the sum is over $c_1,\dots,c_k,b_1,\dots,d_k$ such that
  {\rm ({i})} $1\leq c_j\leq m< d_j<n$ for $j=1,\dots,k$; 
  {\rm ({i}{i})} $c_1\leq \cdots \leq c_k $; {\rm ({i}{i}{i})} the $d_1,\dots,d_k$ are
  distinct.  
\end{corollary}

Note that Corollary~\ref{cor:pieri-QH} does not imply Theorem~\ref{th:pieri}
(or even its weaker form for~$\E_n^q$), since the representation
$\t_{ij}\mapsto t_{ij}$ of $\E_n^q$ in the quantum cohomology is not exact.



\section{Proof of Theorem~\ref{th:pieri}}
\label{sec:proof}

For a subset $I$ in $\{1,2,\dots,n\}$, let $\wt{E}_k(I)$ denote the expression
in the right-hand side of~(\ref{eq:pieri}).  By convention, $\wt{E}_0(I)=1$.
For $k=1$, Theorem~\ref{th:pieri} says that 
\[ 
  \wt{E}_1(I)=\sum_{i\in I}\sum_{j\not\in I}\t_{ij}= 
  \sum_{i\in I}\sum_{j=1}^n \t_{ij}=E_1(\theta_I;p)\,,  
\] 
which is obvious by~(\ref{eq:en1}).

It suffices to verify that the $\wt{E}_k(I)$ satisfy the 
defining relation~(\ref{eq:E2}).  Then the claim
$E_k(\theta_I;p)=\wt{E}_k(I)$ will follow by induction on~$k$.
Specifically, we have to demonstrate that
\begin{equation}
  \label{eq:wtE}
  \wt{E}_k(I\cup\{j\})=\wt{E}_k(I) + \wt{E}_{k-1}(I)\,\theta_j 
     +\sum_{i\in I} \wt{E}_{k-2}(I\setminus\{i\})\,p_{ij}\,,
\end{equation}
where $I\subset\{1,2,\dots,n\}$ and $j\not\in I$.  To do this  
we need some extra notation.  For a subset $L=\{l_1,l_2,\dots,l_m\}$ 
and $r\not\in L$, denote
\[
  \<L\mid r\> = \sum \t_{u_1\,r}\t_{u_2\,r}\cdots\t_{u_m\,r},
\]
where the sum is over all permutations~$u_1,u_2,\dots,u_m$
of $l_1,l_2,\dots,l_m$.    

For~$I$ and~$j$ as in~(\ref{eq:wtE}),
let $J=\{1,2,\dots,n\}\setminus I=\{j_1,j_2,\dots,j_d\}$
with $j_1=j$. 
Then the first term in the right-hand side 
of~(\ref{eq:wtE}) can be written in the form
\begin{equation}
  \label{eq:<>}
  \wt{E}_k(I)= \sum_{I_1\dots I_d{\subset_{k}}I} 
  \<I_1\mid j_1\>\,\<I_2\mid j_2\>\cdots\<I_d\mid j_d\>,
\end{equation}
where the notation~$I_1\dots I_d{\subset_{k}}I$ means
that the sum is over all pairwise disjoint (possibly empty) subsets 
$I_1,I_2,\dots,I_d$ of~$I$ such that $\sum_s |I_s|=k$.
Let 
\begin{equation}
  \label{eq:proofA}
  \wt{E}_k(I)=A_1+A_2\,,
\end{equation}
where~$A_1$ is the sum of terms in~(\ref{eq:<>}) with $I_1=\emptyset$
and~$A_2$ is the sum of terms with $I_1\ne\emptyset$. 
Likewise, we can split the left-hand side of~(\ref{eq:wtE}) into
two parts:
\begin{equation}
  \label{eq:proofB}
  \begin{split}
  \wt{E}_k(I\cup\{j\}) &= \sum_{I'_2\cdots I'_{d}\subset_k I\cup\{j\}}
  \<I'_2\mid j_2\>\,\<I'_3\mid j_3\>\cdots\<I'_d\mid j_d\>  \\[.1in]
  & =B_1+B_2\,,
  \end{split}
\end{equation}
where~$B_1$ is the sum of the terms such that $j\not\in I'_2\cup\cdots\cup I'_{d}$,
and~$B_2$ is the sum of terms with~$j\in I'_2\cup\cdots\cup I'_{d}$.
We also
split the second term in the right-hand side of~(\ref{eq:wtE}) into
$3$ summands:
\begin{equation}
  \label{eq:proofC}
  \begin{split}
  \wt{E}_{k-1}(I)\,\theta_j &=\sum_{I''_1\dots I''_d\subset_{k-1}I}
  \<I''_1\mid j_1\>\cdots\<I''_d\mid j_d\> \,\sum_{s\ne j} \t_{js}  \\[.1in]
  &=C_1+C_2+C_3\,,
  \end{split}
\end{equation}
where $C_1$ is the sum of terms with $s\in 
I\setminus(I''_1\cup I''_2\cup\cdots\cup I''_d)$; 
$C_2$ is the sum of terms with $s\in I''_2\cup I''_3\cup\cdots\cup I''_d\cup J$; 
and $C_3$ is the sum of terms with $s\in I''_1$.

It is immediate from the definitions that $A_1=B_1$.
It is also not hard to verify that $A_2+C_1=0$, since 
for $I_1\ne\emptyset$
\[
  \<I_1\mid j_1\>=\sum_{i\in I_1}\< I_1\setminus\{i\}\mid j_1\>\, \t_{i\,j_1}\,.
\] 
To prove the identity~(\ref{eq:wtE}), it thus suffice to demonstrate that
\begin{align}
  \label{eq:abc3}
  &B_2=C_2\,,\\[.1in]
  \label{eq:abc4}
  &C_3+\sum_{i\in I}\wt{E}_{k-2}(I\setminus\{i\})\,p_{ij}=0\,.
\end{align}

The following lemma implies the formula~(\ref{eq:abc3}).
\begin{lemma}
\label{lem:kjl}
For any subset~$K$ in $\{1,2,\dots,n\}$ and $j,\,l\not\in K$, we have
\begin{equation}
  \label{eq:kjl}
  \<K \cup \{j\}\mid l\> =\sum_{L\subset K} \<L\mid l\>\,\<K\setminus L\mid j\>
                \sum_{s\in L\cup\{l\}}\t_{js} \,.
\end{equation}
\end{lemma}

Indeed, let $T=\<I_2'\mid j_2\>\cdots\<I_d'\mid j_d\>$ be a term of~$B_2$.
Then $j\in J'_r$ for some~$r$.  By Lemma~\ref{lem:kjl}, $T$ is equal the sum
of all terms $\<I_1''\mid j_1\>\cdots \<I_d''\mid j_d\>\,\t_{js}$ in~$C_2$
with fixed $I_u''=I_u'$ for all $u\ne r$ such that $s\in I_r''\cup\{j_r\}$
and the subsets $I_1''\cup I_r''=I'_r\setminus\{j\}$.  Thus $B_2=C_2$.

\proofof{Lemma~\ref{lem:kjl}}
Induction on $|K|$.  For $K=\emptyset$, the both sides
of~(\ref{eq:kjl}) are equal to~$\t_{jl}$.
For $|K|\geq 1$, the right-hand side of~(\ref{eq:kjl}) is equal
\begin{align*}
  &\sum_{L\subset K}\<L\mid l\>\,\<K\setminus L\mid j\>
             \sum_{s\in L\cup\{l\}}\t_{js}\\
  &=\sum_{L\varsubsetneqq K}\left( \sum_{i\in K\setminus L}
   \<L\mid l\>\,\t_{ij}\, \<K\setminus L\setminus\{i\}\mid  j\>
   \sum_{s\in L\cup\{l\}} \t_{js}\right)
     + \<K\mid l\>\sum_{s\in K\cup \{l\}} \t_{js}\\[.1in]
  &=\sum_{i\in K} \t_{ij}\,\<(K\setminus\{i\})\cup\{j\}\mid  l\> 
     + \<K\mid l\>\sum_{s\in K\cup\{l\}} \t_{js}\\
  &=\<K\cup\{j\}\mid l\>.
\end{align*}
The second equality is valid by induction hypothesis; the
remaining equalities follow from~(\ref{eq:en3}) and~(\ref{eq:en5}).  \endproof

Using a similar argument to the one after Lemma~\ref{lem:kjl}, one can
derive the formula~(\ref{eq:abc4}) from the  following lemma:
\begin{lemma}
For any subset~$K$ in $\{1,2,\dots,n\}$ and $j\not\in K$, we have
\begin{equation*}
  \sum_{s\in K}\left(\<K\mid j\>\,\t_{js} + \sum_{L\subset K\setminus\{s\}}
   \<L\mid s\>\,\<K\setminus L\setminus \{s\}\mid j\> p_{js}\right)=0\,.
\end{equation*}
\end{lemma}
 
This statement, in turn, is obtained from the following 
``quantum analogue'' of Lemma~7.2 from~\cite{FK}. Its proof is 
a straightforward extension.
\begin{lemma}
For $i,u_1,u_2,\dots,u_m\in\{1,\dots,n\}$, we have in the algebra~$\E_n^p$
\begin{equation}
\label{eq:cyc}
\begin{split}
  &\sum_{r=1}^m \t_{i\, u_r}\t_{i\,u_{r+1}}\cdots\t_{i\,u_m}
  \t_{i\,u_1}\t_{i\,u_2}\cdots \t_{i\,u_r}   \\%[.1in]
  &=\ \sum_{r=1}^m p_{i\,u_r}\, \t_{u_r\,u_{r+1}}\t_{u_r\,u_{r+2}} \cdots
  \t_{u_r\,u_m}\t_{u_r\,u_1}\t_{u_r\,u_2} \cdots
  \t_{u_{r}\,u_{r-1}}\,,
\end{split}
\end{equation}
where, by convention, the index~$u_{m+1}$ is identified with~$u_1$.
\end{lemma}

\proof 
Induction on~$m$.  The base of induction, for $m=1$, is easily 
established by~(\ref{eq:en2}):
$\t_{i\,u_1}\t_{i\,u_1}=p_{i\,u_1}$.
Assume that $m>1$. Applying~(\ref{eq:en3}) and~(\ref{eq:en5})
to the left-hand side
of~(\ref{eq:cyc}), we obtain:
\begin{align*}
  &\ \sum_{r=1}^m \t_{i\, u_r}\t_{i\,u_{r+1}}\cdots\t_{i\,u_{m-1}}\,(\t_{i\,u_m}
     \t_{i\,u_1})\,\t_{i\,i_2}\cdots \t_{i\,u_r}\\%[.2in]
  &=\ \sum_{r=1}^m \t_{i\, u_r}\t_{i\,u_{r+1}}\cdots\t_{i\,u_{m-1}}
    \,(\t_{i\,u_1}\t_{u_1\,u_m}+\t_{u_m\,u_1}\t_{i\,u_m})\,
  \t_{i\,u_2}\cdots \t_{i\,u_r}\\%[.2in]
  &=\ \left(\sum_{r=1}^{m-1} \t_{i\, u_r}\t_{i\,u_{r+1}}\cdots\t_{i\,u_{m-1}}
    \t_{i\,u_1}\t_{i\,u_2}\cdots \t_{i\,u_r}\right)\,\t_{u_1\,u_m}\\%[.2in]
  &\quad +\ \t_{u_m\,u_1}\,\left(\sum_{r=2}^m \t_{i\, u_r}\t_{i\,u_{r+1}}\cdots
    \t_{i\,u_m}\t_{i\,u_2}\t_{i\,i_3}\cdots \t_{i\,u_r}\right)\,.
\end{align*}
By induction hypothesis, this expression is equal to
\begin{align*}
  &\left(\sum_{r=1}^{m-1} p_{i\,u_r}\, \t_{u_r\,u_{r+1}}
          \t_{u_r\,u_{r+2}} \cdots
          \t_{u_r\,u_{m-1}}\t_{u_r\,u_1}\t_{u_r\,u_2} \cdots
          \t_{u_{r}\,u_{r-1}}\right)\,\t_{u_1\,u_m}\\%[.2in]
  &\quad+\ \t_{u_m\,u_1}\,\left(\sum_{r=2}^{m} p_{i\,u_r}\, \t_{u_r\,u_{r+1}}
          \t_{u_r\,u_{r+2}} \cdots
          \t_{u_r\,u_{m}}\t_{u_r\,u_2}\t_{u_r\,u_3} \cdots
          \t_{u_{r}\,u_{r-1}}\right)\\%[.2in]
  &=\ p_{i\,u_1}\, \t_{u_1\,u_2}\t_{u_1\,u_3} \cdots \t_{u_1\,u_m} 
   + p_{i\,u_m}\, \t_{u_m\,u_1}\t_{u_m\,u_2} \cdots \t_{u_m\,u_{m-1}}\\%[.1in]
  &\quad+\ \sum_{r=2}^{m-1}  p_{i\,u_r}\, \t_{u_r\,u_{r+1}} \cdots
          \t_{u_r\,u_{m-1}}\,(\t_{u_r\,u_1}\t_{u_1\,u_m}+
          \t_{u_m\,u_1}\t_{u_r\,u_m})\,
          \t_{u_r\,u_2} \cdots \t_{u_{r}\,u_{r-1}}\,.
\end{align*}
%By~(\ref{eq:en3}), 
The latter expression coincides with the right-hand side
of~(\ref{eq:cyc}).  \endproof
\medskip

This completes the proof of Theorem~\ref{th:pieri}.



\newpage
\begin{thebibliography}{BGG}
  
%\bibitem{BS} N.~Bergeron and F.~Sottile,  Schubert polynomials, the Bruhat
%order, and the geometry of flag manifolds, preprint dated December 4, 1996.

\bibitem[BGG]{BGG} I.~N.~Bernstein, I.~M.~Gelfand, and S.~I.~Gelfand, Schubert
cells and cohomology of the space~$G/P$, {\it Russian Math.\ Surveys\/ \bf 28}
(1973), 1--26.

%\bibitem{bertram} A.~Bertram, Quantum Schubert calculus, to appear in {\it
%Adv.\ Math.}

\bibitem[B]{borel} A.~Borel, Sur la cohomologie de espaces fibr\'es principaux et
des espaces homog\'enes des groupes de Lie compacts, {\it Ann.\ of Math.\ \rm
(2) \bf 57} (1953), 115--207.

\bibitem[C1]{ciocan} I.~Ciocan-Fontanine, Quantum cohomology of flag varieties,
{\it Intern.\ Math.\ Research Notes\/} (1995), No.~6, 263--277.

\bibitem[C2]{ciocan2} I.~Ciocan-Fontanine, On quantum cohomology rings or partial
flag varieties, preprint dated February 9, 1997.

\bibitem[D]{Dem} M.~Demazure, D\'esingularization des vari\'et\'es de Schubert
g\'en\'eralis\'ees, {\it Ann.\ Scient.\ Ecole Normale Sup.\ \rm (4) \bf 7}
(1974), 53--88.

\bibitem[E]{Ehr} C.~Ehresmann, Sur la topologie de certains espaces homog\`enes,
{\it Ann.\ Math.\ \bf 35} (1934), 396--443.

\bibitem[FGP]{FGP} S.~Fomin, S.~Gelfand, and A.~Postnikov, Quantum Schubert
polynomials, 
%AMS electronic preprint \#199605-14-008, April 1996;
to appear in {\it J.\ Amer.\ Math.\ Soc.}

\bibitem[FK]{FK} S.~Fomin and A.~N.~Kirillov,  Quadratic algebras, Dunkl elements,
and Schubert calculus, preprint AMSPPS \#199703-05-001.
%preprint dated March 12, 1997.

% \bibitem{fulton-yt} W.~Fulton, {\it Young tableaux with applications
% to representation theory and geometry},
% Cambridge University Press, 1996.

\bibitem[FP]{fulton} W.~Fulton and R.~Pandharipande, Notes on stable maps and
quantum cohomology, preprint alg-geom/9608011.

\bibitem[GK]{giv-kim} A.~Givental and B.~Kim, Quantum cohomology of flag manifolds
and Toda lattices, {\it Comm.\ Math.\ Phys.\ \bf 168} (1995), 609--641.

\bibitem[K]{Kim} B.~Kim, Quantum cohomology of flag manifolds $G/B$ and quantum
Toda lattices, preprint alg-geom/9607001.

%\bibitem{k-m} M.~Kontsevich and Yu.~Manin, Gromov-Witten classes, quantum
%cohomology, and enumerative geometry, {\it Comm.\ Math.\ Phys.\ \bf 164}
%(1994), 525-562.

%\bibitem{kostant} B.~Kostant, Flag manifold quantum cohomology, the Toda
%lattice, and the representation with highest weight~$\rho$, {\it Selecta
%Math.\ (N.S.)\/ \bf 2} (1996), % no.~1, 43-91.

\bibitem[LS]{ls} A.~Lascoux and M.~P.~Sch\"utzenberger, Polyn\^omes de Schubert,
{\it C.~R.\ Ac.~Sci.\ \bf 294} (1982), 447-450.

% \bibitem{ls2} A.~Lascoux and M.~P.~Sch\"utzenberger, Fonctorialit\'e de
% polyn\^omes de Schubert, {\it Contemp.\ Math.\ \bf 88} (1989), 585-598.

\bibitem[Ma]{mac} I.~G.~Macdonald, {\it Notes on Schubert polynomials},
Publications du LACIM, Montr\'eal, 1991.

\bibitem[Mo]{monk} D.~Monk, The geometry of flag manifolds, {\it Proc.\ London
Math.\ Soc.\ \bf (3) 9} (1959), 253--286.

\bibitem[S]{sottile} F.~Sottile, Pieri's formula for flag manifolds and Schubert
polynomials, {\it Annales de l'Institut Fourier} {\bf 46} (1996), 89-110.

\bibitem[W]{winkel} R.~Winkel, On the multiplication of Schubert polynomials,
preprint dated January 1997.

\end{thebibliography}
\end{document}