% % A Monoid for the Universal k-Bruhat order % % Nantel Bergeron % Frank Sottile % % LaTeX version of \beta-release for MSRI preprint series % % 2 July 1997 % % \documentclass[12pt]{amsart} \usepackage{amssymb} \usepackage{epsf} \headheight=8pt \topmargin=0pt \textheight=624pt \textwidth=432pt \oddsidemargin=18pt \evensidemargin=18pt \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{definition}[thm]{Definition} \newtheorem{prob}[thm]{Problem} \newtheorem{rem}[thm]{Remark} \newenvironment{Remark}{\begin{rem}\sl}{\end{rem}} \newcommand{\abs}[1]{|#1|} \def\silentfootnote#1{{\let\thefootnote\relax\footnotetext{#1}}} \def\u#1{{\bf u}_{#1}} \def\hu#1{\hat{{\bf u}}_{#1}} \def\cu#1{{\scriptstyle \hu{#1}}\hfill} \def\hx{\hat{\bf x}} \def\hy{\hat{\bf y}} \def\hz{\hat{\bf z}} \def\Sym{{\mathcal S}} \def\Q{{\mathbb Q}} \def\C{{\mathbb C}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\Mon{{\mathcal M}} \def\Non{{\mathcal N}} \def\a{\alpha} \def\b{\beta} \def\c{\gamma} \def\d{\delta} \def\scr{\scriptstyle} \begin{document} \title[A Monoid for the universal $k$-Bruhat order]{A Monoid for the universal $k$-Bruhat order} \author{Nantel Bergeron \and Frank Sottile} \address{Department of Mathematics and Statistics\\ York University\\ North York, Ontario M3J 1P3\\ CANADA} \email[Nantel Bergeron]{bergeron@mathstat.yorku.ca} \address{Department of Mathematics\\ University of Toronto\\ 100 St.~George Street\\ Toronto, Ontario M5S 3G3\\ CANADA} \email[Frank Sottile]{sottile@math.toronto.edu} \date{2 July 1997} \thanks{Bergeron supported in part by CRM, MSRI, and NSERC} \thanks{Sottile supported in part by NSF grant DMS-9022140, NSERC grant OGP0170279, and CRM} \subjclass{05E15, 14M15, 05E05} \keywords{Bruhat order, nil-Coxeter monoid, flag manifold, Grassmannian} \begin{abstract} Structure constants for the multiplication of Schubert polynomials by Schur symmetric polynomials are known to be related to the enumeration of chains in a new partial order on $\Sym_\infty$, the universal $k$-Bruhat order. Here we present a monoid $\Mon$ for this order. We show that $\Mon$ is analogous to the nil-Coxeter monoid for the weak order on $\Sym_\infty$. For this, we develop the theory of reduced sequences for $\Mon$. We use these sequences to give a combinatorial description of the structure constants above. We also give a combinatorial proof of some of the symmetry relations satisfied by these constants. \end{abstract} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Let $\Sym_\infty$ denote the infinite symmetric group consisting of permutations of $\{1,2,\ldots\}$ which fix all but finitely many numbers. In their approach to the Schubert calculus for flag manifolds, Lascoux and Sch\"utzenberger~\cite{LS82a,LS82b,LS83,LS89} defined Schubert polynomials ${\mathfrak S}_u\in \Z[x_1,x_2,\ldots]$, a homogeneous basis indexed by permutations $u\in\Sym_\infty$. By construction, the degree of ${\mathfrak S}_u$ is the length, $\ell(u)$, of $u$. We refer the reader to \cite{Macdonald91} for an interesting detailed account of Schubert polynomials and double Schubert polynomials. This construction has been extended to quantum Schubert polynomials for the manifolds of complete flags~\cite{FGP,KM} and for manifolds of partial flags~\cite{C-F}. In~\cite{Fulton97}, W. Fulton generalizes all of these constructions. It is a famous open problem to understand the multiplicative structure constants for the Schubert polynomials and any of their generalizations. This would provide an understanding of some Gromov-Witten invariants. From algebraic geometry, the structure constants $c_{uv}^w$ defined by the identity $${\mathfrak S}_u{\mathfrak S}_v\ =\ \sum_{w\in \Sym_\infty} c_{uv}^w {\mathfrak S}_w$$ are known to be positive integers, and in some cases they reduce to the Littlewood-Richardson coefficients. A general combinatorial construction or bijective formula for the $c_{uv}^w$ is not known. It is believed that $c_{uv}^w$ counts the number of chains from $u$ to $w$ in the Bruhat order which satisfy conditions imposed by $v$ \cite{BS97a}. In particular, if $v$ is a Grassmannian permutation with descent in $k$, then one can restrict the chains to a suborder: the $k$-Bruhat order $\le_k$ on $\Sym_\infty$~\cite{LS83,Sottile96,BS97a}. In \cite{BS97a}, a study of $\le_k$ leads to a new partial order $\preceq$ on $\Sym_\infty$ which we call the {\sl universal $k$-Bruhat} order. This order is ranked and has the property that a nonempty interval $[u,w]_k$ in a $k$-Bruhat order is isomorphic to the interval $[1,wu^{-1}]_\preceq$ in the universal order (independent of $k$). Every interval in Young's lattice is an interval in this universal order. The first aim of this paper is to present a monoid $\Mon$ that describes the chain structure of the universal $k$-Bruhat order. The monoid $\Mon$ has a $0$ and generators $\u{\a\b}$ indexed by integers $0<\a<\b$, subject to the relations $$ %\begin{equation}\label{rel} \begin{array}{clrclll} (1)&&\u{\b\c}\u{\c\d}\u{\a\c}&\equiv&\u{\b\d}\u{\a\b}\u{\b\c},\hfill&& \hbox{if $\a<\b<\c<\d$},\hfill\\ (2)\hfill&& \hfill \u{\a\c}\u{\c\d}\u{\b\c}&\equiv& \u{\b\c}\u{\a\b}\u{\b\d},\hfill&& \hbox{if $\a<\b<\c<\d$},\hfill\\ (3)\hfill&& \hfill \u{\a\b}\u{\c\d}&\equiv&\u{\c\d}\u{\a\b}, \hfill&& \hbox{if $\b<\c$ or $\a<\c<\d<\b$},\hfill\\ (4)\hfill&& \hfill \u{\a\c}\u{\b\d}&\equiv& \u{\b\d}\u{\a\c}\ \equiv \ 0,\hfill&& \hbox{if $\a\le \b<\c\le\d$},\hfill\\ (5)\hfill&& \hfill \u{\b\c}\u{\a\b}\u{\b\c} &\equiv&\u{\a\b}\u{\b\c}\u{\a\b}\ \equiv\ 0,\hfill&& \hbox{if $\a<\b<\c$}. \end{array} \eqno{(1.1)} $$ %\end{equation} The relation between $\Mon$ and the order $\preceq$ on $\Sym_\infty$ is obtained via a faithful representation of $\Mon$ as linear operators on $\Q\Sym_\infty$. Let $\ell_{\u{}}$ denote the rank function of $\preceq$. Let $(\a\,\,\,\b)\in\Sym_\infty$ be the transposition that interchanges $\a$ and $\b$. We define linear operators $\hu{\a\b}$ by $$ %\begin{equation}\label{operat} \begin{array}{rcl} \hu{\a\b}\ \colon\ \Q\Sym_\infty&\longrightarrow& \quad\Q\Sym_\infty,\\ \zeta\quad&\longmapsto&\ \ \rule{0pt}{28pt} \left\{\begin{array}{ll} (\a\,\,\,\b)\zeta &\mbox{ if } \ell_{\u{}}\big((\a\,\,\,\b)\zeta)\big)=\ell_{\u{}}(\zeta)+1,\\ \mbox{ }\\ 0& \mbox{ otherwise.}\end{array}\right. \end{array} \eqno{(1.2)} $$ %\end{equation} The main results of Section 3 are summarized in the following theorem. \begin{thm}\label{Operators} \mbox{ } \begin{enumerate} \item[(a)] The map $\ell_{\u{}}\colon\Sym_\infty\to\N$ is well defined by $\ell_{\u{}}(\zeta)=\ell(\zeta u)-\ell(u)$ for any $u$ and $k$ such that $u\le_k\zeta u$. \item[(b)] The operators $\hu{\a\b}$ satisfy the relations (1.1), and a composition of operators is characterized by its value at the identity. That is $\hu{\a'_m\b'_m}\cdots\hu{\a'_1\b'_1}=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}$ if and only if \/$\hu{\a'_m\b'_m}\cdots\hu{\a'_1\b'_1}1=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}1$. \item[(c)] For ${\bf x}=\u{\a_n\b_n}\cdots\u{\a_2\b_2}\u{\a_1\b_1}\in\Mon$, the map ${\bf x}\mapsto \hx=\hu{\a_n\b_n}\cdots\hu{\a_2\b_2}\hu{\a_1\b_1}$ is a faithful representation of $\Mon$. \item[(d)] The following map is a well defined bijection: \begin{eqnarray*} \Mon&\longrightarrow& \Sym_\infty\cup\{0\},\\ {\bf x}&\longmapsto& \hx 1. \end{eqnarray*} \item[(e)] The universal $k$-Bruhat order $\preceq$ on $\Sym_\infty$ is ranked by $\ell_{\u{}}$. We have $\eta\preceq \zeta$ if and only if there exists ${\bf x}\in \Mon$ such that $\zeta=\hx \eta$. The order $\preceq$ satisfies the universal property: $[u,\zeta u]_k\cong [1,\zeta]_\preceq$ whenever $u\le_k \zeta u$. In particular $[\eta,\zeta]_\preceq\cong[1,\zeta\eta^{-1}]_\preceq$ whenever $\eta\preceq\zeta$. \item[(f)] The set $R_{\u{}}(\zeta)=\{\hx:\hx1=\zeta\}$ corresponds to the set of all maximal chains in $[1,\zeta]_\preceq$. \end{enumerate} \end{thm} We call the elements of $R_{\u{}}(\zeta)$ the $\u{}$-reduced sequences of $\zeta$. Parts (a) and (e) of Theorem \ref{Operators} are obtained in \S 3.2 of \cite{BS97a}. In Section 2, we relate Theorem \ref{Operators} to classical results on the weak order of $\Sym_\infty$ and the nil-Cotexer monoid. Recall \cite{Macdonald91} that the Schur polynomial $S_\lambda(x_1,x_2,\ldots,x_k) = {\mathfrak S}_{v(\lambda,k)}$ for a unique Grassmannian permutation $v(\lambda,k)$. In Theorem E of \cite{BS97a}, we have shown that if $c_{uv(\lambda,k)}^w\neq 0$, then $c_{uv(\lambda,k)}^w$ depends only on $\lambda$ and $\zeta=wu^{-1}$. We can thus define constants $c_\lambda^\zeta$ such that $c_{uv(\lambda,k)}^w=c_\lambda^{wu^{-1}}$ whenever $u\le_k w$. We note that ({\sl cf.} Proposition 1.1 \cite{BS97a}) $$ %\begin{equation}\label{celleq} \abs{R_{\u{}}(\zeta)} = \sum_\lambda f^\lambda c_\lambda^\zeta, \eqno{(1.3)} $$ %\end{equation} where $f^\lambda$ is the number of standard Young tableaux of shape $\lambda$. In Section 4 we give a combinatorial description of the constant $c_{uv(\lambda,k)}^w$ using elements of $R_{\u{}}(\zeta)$. We use this description to give a combinatorial proof of many of the symmetry relations given in \cite{BS97a}. In Section 5 we discuss open problems related to the monoid $\Mon$ and the constants $c_{uv(\lambda,k)}^w$. The interested reader may obtain by email from {\tt bergerna@mathstat.yorku.ca} or find at {\tt http://www.math.yorku.ca/Who/Faculty/Bergeron} two appendices. One describes a graphical representation of chains in $\preceq$ which greatly helps visualize the relations (1.1) and the arguments of \S 3. The other describes an insertion correspondence, giving a bijection between ${\mathcal H}_{n,1}(\zeta)$ and ${\mathcal H}_{1,n}(\zeta)$. This is related to one open problem described in Section 5. %%%%%%%%%%%%%%%%%%%%%%%%% \section{orders and monoids on $\Sym_\infty$} The weak order $\le_{weak}$ on $\Sym_\infty$ is the transitive closure of the following cover relation: for $u,w\in\Sym_\infty$, we say that $w$ covers $u$ in the weak order if $\ell(w)=\ell(u)+1$ and $wu^{-1}$ is a simple transposition $(\a\,\,\a\!+\!1)$. Maximal chains from the identity to $w\in\Sym_\infty$ correspond to reduced sequences for $w$. The nil-Coxeter monoid $\Non$ plays an important role~\cite{EG,LS82b,Macdonald91} in studying reduced sequences. The monoid $\Non$ has a $0$ and generators $\u{i}$ indexed by integers $i>0$, subject to the nil-Coxeter relations: $$ \begin{array}{rcl} \u{\a}\u{\a+1}\u{\a}&\equiv&\u{\a+1}\u{\a}\u{\a+1},\\ \u{\a}\u{\b}&\equiv&\u{\b}\u{\a}, \qquad\qquad\hbox{if $\abs{\a-\b}>1$},\\ \u{\a}\u{\a}&\equiv& 0. \end{array} \eqno{(2.1)} $$ There is a faithful representation of $\mathcal N$ as linear operators on the group algebra $\Q\Sym_\infty$. For this, let $$ \begin{array}{rcl} \hu{\a}\ \colon \ \Q\Sym_\infty&\longrightarrow& \quad\Q\Sym_\infty,\\ \zeta\quad&\longmapsto&\ \ \rule{0pt}{28pt} \left\{\begin{array}{lll} (\a\,\,\,\a\!+\!1)\zeta&\quad& \mbox{if }\ell\big((\a\,\,\,\a\!+\!1)\zeta\big)=\ell(\zeta)+1,\\ \\ 0&&\mbox{otherwise.} \end{array}\right.\end{array} $$ The following proposition is a reformulation of well known facts about reduced sequences of a permutation and the weak order. See \cite{Macdonald91} for a proof of most of them. \vfill \eject \begin{prop}\label{WeakOp}\mbox{ } \begin{enumerate} \item[(a)] The map $\ell\ \colon\ \Sym_\infty\to\N$ is well defined. \item[(b)] The operators $\hu{\a}$ satisfy the relations~(2.1), and a composition of operators is characterized by its value at the identity. That is $\hu{\a_n}\cdots\hu{\a_1}=\hu{\b_m}\cdots\hu{\b_1}$ if and only if $\hu{\a_n}\cdots\hu{\a_1}1=\hu{\b_m}\cdots\hu{\b_1}1$. \item[(c)] For ${\bf x}=\u{\a_n}\cdots\u{\a_2}\u{\a_1}\in\Non$, the map ${\bf x}\mapsto \hx=\hu{\a_n}\cdots\hu{\a_2}\hu{\a_1}$ is a faithful representation of $\Non$. \item[(d)] The following map is a well defined bijection: \begin{eqnarray*} \Non&\longrightarrow& \Sym_\infty\cup\{0\},\\ {\bf x}&\longmapsto& \hx 1. \end{eqnarray*} \item[(e)] The weak order $\le_{weak}$ on $\Sym_\infty$ is ranked by $\ell$. We have $u\le_{weak} w$ if and only if there exists ${\bf x}\in \Non$ such that $w=\hx u$. Also $[\eta,\zeta]_{weak}\cong[1,\zeta\eta^{-1}]_{weak}$ whenever $\eta \le_{weak}\zeta$. \item[(f)] The set $R(w)=\{\hx:\hx1=w\}$ corresponds to the set of all maximal chains in $[1,w]_{weak}$. The elements of $R(w)$ are the reduced sequences of $w$. \end{enumerate} \end{prop} At this point we note the striking resemblance between Theorem~\ref{Operators} and Proposition~\ref{WeakOp}. The proof of Proposition \ref{WeakOp} relies on the understanding of reduced sequences. For Theorem \ref{Operators}, the order $\preceq$ is new and its chains have not been studied previously. We develop the elementary theory of the analogue of reduced sequences for $\preceq$. We note that not all orders on $\Sym_\infty$ have such a simple monoid. In particular, the Bruhat order $\le$ on $\Sym_\infty$ has no known monoid. Recall that $w$ covers $u$ in the Bruhat order if $\ell(w)=\ell(u)+1$ and $wu^{-1}$ is a transposition $(\a\,\,\b)$. In fact, very little is known about the problem of chain enumeration for the Bruhat order. We believe that a monoid for the Bruhat order would not satisfy conditions as simple as those of Theorem \ref{Operators} and Proposition \ref{WeakOp}. The monoid structure for the weak order was a key factor in the following results. Under the nil-Coxeter-Knuth relations $$ \begin{array}{rcll} \qquad \u{\a}\u{\a+1}\u{\a}&\equiv&\u{\a+1}\u{\a}\u{\a+1},\\ \u{\b}\u{\c}\u{\a}&\equiv&\u{\b}\u{\a}\u{\c},&\qquad\hbox{if $\a<\b<\c$},\\ \u{\a}\u{\c}\u{\b}&\equiv&\u{\c}\u{\a}\u{\b},& \qquad\hbox{if $\a<\b<\c$},\\ \u{\a}\u{\a}&\equiv &0,\end{array} \eqno{(2.2)} $$ the set of all reduced sequences $R(w)$ for a permutation $w\in\Sym_\infty$ is refined into classes, called Coxeter-Knuth cells, indexed by some semi-standard tableaux. The cardinality of a cell is the number of standard tableaux of the same shape as the cell's index~\cite{EG,LS82b,Stanley84}. This decomposition suggests an action of the symmetric group on $R(w)$. The symmetric function corresponding to such an action is the function $F_w$ introduced by Stanley in~\cite{Stanley84}. Equation~(1.3) suggests the possibility of similar structure for the monoid $\Mon$ and relations (1.1). %%%%%%%%%%%%%%%%%%%%%%%%% \section{$k$-Bruhat orders and the monoid $\Mon$} The multiplicative structure of Schubert polynomials is determined by Monk's rule \cite{Macdonald91}: $$ {\mathfrak S}_u (x_1+x_2+\cdots+x_k) = \sum_{\stackrel{a\le k 0$. Equivalently, this is the partial order with covering relation given by the index of summation in Monk's rule. We call this suborder of the Bruhat order the {\sl $k$-Bruhat order}. Denote by $[u,w]_k$ the interval from $u$ to $w$ in the $k$-Bruhat order. Then $\gamma(u,w,k)$ is the number of maximal chains in $[u,w]_k$. These cover relations give some invariants of the $k$-Bruhat order. For example, consider the following maximal chain in the 3-Bruhat order: \silentfootnote{$^{\dag}$Notation: For every $w\in\Sym_\infty$ there exists infinitely many $n$ such that $w\in\Sym_n\subset\Sym_\infty$. For any such $n$ we write $(w(1),w(2),\ldots,w(n))$ to represent such a $w$.} $$ (3,1,5,2,6,4)\le_3 (3,1,6,2,5,4)\le_3(3,2,6,1,5,4) \le_3(3,5,6,1,2,4).^{\dag} $$ In this chain, the first three entries of the permutations do not decrease and the other entries do not increase. Also, the second and third entries remain in the same relative order for all permutations in the chain. This leads to a characterization of the $k$-Bruhat order based on such invariants. \vfill\eject \begin{prop}[Theorem A of \cite{BS97a}]\label{klength} For $u,w\in\Sym_\infty$, \ $u\le_k w$ if and only if \begin{enumerate} \item[(1)] $u(i)\le w(i)$ \qquad for $i\le k$, \item[(2)] $u(i)\ge w(i)$ \qquad for $i>k$, \item[(3)] $(u(i)\ell(u)+1$, let $a\le ku(a)\ge w(b)$ and $w(b)=\min\{w(j):j>k, u(j)>u(a)\ge w(j)\}$. \end{enumerate} Let $u_1=u(a\,b)$. The CM-chain of $[u,w]_k$ is $$u=u_0<_ku_1<_ku_2<_k\cdots<_ku_n=w,$$ where $u_1<_ku_2<_k\cdots<_ku_n$ is the CM-chain of $[u_1,w]_k$. \end{enumerate} \end{definition} It is not obvious that conditions {\bf I} and {\bf II} define unique integers $a\le kw(b)$ and $w(b)=\min\{w(j):j> k, u(j)>w(j)\}$, \item[\bf II$'$] $u(a)w(a_j)$, or $w(a_i)=w(a_j)$ and $w(b_i)w(b_j)$. \end{itemize} \noindent The inversion set $\mathcal I$ of a chain is the set of all its inversions. In the example above, the inversion set of the middle maximal chain is $\{(1,2),(1,3),(1,4),(2,3),(2,4)\}$. %%%%%%%%%%%%%%%%%%%%% % We define the {\sl descent} set $\mathcal D$ of a chain %to be the set $\{i: (i,i+1)\in{\mathcal I}\}$. In our example that is $\{1,2\}$. %In Section 6 %we give a usefull visualise of chains, inversions, and other related notions. \begin{lem}\label{canon} A maximal chain is the CM-chain if and only if it has no inversions. \end{lem} \noindent{\em Proof } The reverse implication is clear. Consider a maximal chain with an inversion $(i,j)$. It suffices to show there is an $i'$ such that $(i',i'+1)$ is also an inversion of the chain. If $(i,i+1)$ is an inversion then we are done. If $(i,i+1)$ is not an inversion then either \begin{enumerate} \item[(a)] $w(a_i)>w(a_{i+1})$ or \item[(b)] $w(a_i)=w(a_{i+1})$ and $w(b_i)w(b_i)> w(b_j)$. Thus $(i+1,j)$ is an inversion. By induction on $j-i$ we conclude that there is an $i\le i'j\}$. Proposition~\ref{Izeta} constructs a standard interval $[u,w]_k$ for any $\zeta$. Counting the inversions of $u$ and $w$, and rearranging the terms we deduce \begin{eqnarray*} \ell_{\u{}}(\zeta)&=& \abs{\big\{ (i,j)\in up(\zeta)\times dw(\zeta) : \,i>j\big\}}\\ &&-\abs{\big\{ (i,j)\in \zeta^{-1}(up(\zeta))\times \zeta^{-1}(dw(\zeta)):\,i>j\big\}}\\ &&-\abs{\big\{ (i,j)\in \left(\zeta^{-1}(up(\zeta))\right)^2:\,i\zeta(j) \big\}}\\ &&-\abs{\big\{ (i,j)\in \left(\zeta^{-1}(dw(\zeta))\right)^2:\,i\zeta(j) \big\}}. \end{eqnarray*} If $u\le_k \zeta u$ and $u'\le_{k'} \zeta u'$, then the isomorphism $[u,\zeta u]_k\cong [u',\zeta u']_{k'}$ is given by $\eta u\mapsto \eta u'$. We now introduce the universal $k$-Bruhat order $\preceq$ on $\Sym_\infty$. $$ \eta\preceq\zeta \quad\iff\quad\big(\hbox{There exists $u$, $k$ such that $u\le_k\eta u\le_k\zeta u$}\big). \eqno{(3.3)} $$ Using the permutation $u$ given by Proposition ~\ref{Izeta}, we see that $\eta\preceq \zeta$ if and only if \begin{enumerate} \item[(1)] $\eta(\a)\le \zeta(\a)$ \quad for $\a\in\zeta^{-1}\big(up(\zeta)\big)$, \item[(2)] $\eta(\a)\ge \zeta(\a)$ \quad for $\a\in\zeta^{-1}\big(dw(\zeta)\big)$, \item[(3)] $\big(\eta(\a)<\eta(\b)\implies \zeta(\a)<\zeta(\b)\big)$ for $\a<\b\in \zeta^{-1}(up(\zeta))$ or $\a<\b\in \zeta^{-1}(dw(\zeta))$. \end{enumerate} \noindent It follows from the definition that the order $\preceq$ is ranked by $\ell_{\u{}}$ and $[1,\zeta\eta^{-1}]_\preceq\cong[\eta,\zeta]_\preceq$ via the map $\xi\mapsto\xi\eta$. The operators $\hu{\a\b}$ in~(1.2) are defined so that $\hu{\a\b}\eta=\zeta$ if and only if $\zeta$ covers $\eta$ in $\preceq$. In particular, nonzero compositions $\hx=\hu{\a_n\b_n}\cdots\hu{\a_2\b_2}\hu{\a_1\b_1}$ such that $\hx\eta=\zeta$ correspond bijectively to maximal chains in $[\eta,\zeta]_\preceq$: $$ \eta\preceq \hu{\a_1\b_1}\eta\preceq \hu{\a_2\b_2}\hu{\a_1\b_1} \eta\preceq\cdots\preceq\hx\eta=\zeta $$ We note that the isomorphism $[1,\zeta\eta^{-1}]_\preceq\cong[\eta,\zeta]_\preceq$ implies $$ \hx \eta=\zeta\quad\iff\quad \hx 1=\zeta\eta^{-1}. \eqno{(3.4)} $$ The isomorphism $[1,wu^{-1}]_\preceq\cong[u,w]_k$ given by $\eta\mapsto \eta u$, induces an isomorphism on chains. Given a maximal chain $$ u=u_0<_k u_1 <_k u_2 <_k \cdots <_k u_n=w \eqno{(3.5)} $$ of $[u,w]_k$, we adopt the following conventions. \begin{itemize} \item Let $a_i\le k1$ and assume that the theorem holds for all intervals $[u',w']_{k'}$ such that $\ell(w')-\ell(u')w(a_1)$. We have two sub-cases to consider: \noindent Case 1a: $\{\a_1,\b_1\}\cap\{\a_2,\b_2\}=\emptyset$. We can use relation (3) of (1.1) and get $$ \hx\equiv \hu{\a_n\b_n}\cdots\hu{\a_1\b_1}\hu{\a_2\b_2}. \eqno{(3.8)} $$ The hypothesis on $\bf y$ and $w(a_2)>w(a_1)$ implies that $\hu{\a_2\b_2}$ is the first step of the CM-chain of $[u,w]_k$. We can use our induction hypothesis on $[\hu{\a_2\b_2}u,w]_k$ and get $\hx\equiv \hz\hu{\a_2\b_2}$, t he CM-chain of $[u,w]_k$. \noindent Case 1b: $\a_2<\b_2=\a_1<\b_1$. Since $\bf y$ is the CM-chain of $[u_1,w]_k$, we have $$ \b_2=\a_3<\b_3=\a_4<\cdots<\b_{m-1}=\a_m, $$ for $m\ge 3$, where $\b_m = w(a_2)>w(a_1)\ge\b_1$. Let $3\le s\le m$ be such that $\a_s<\b_1<\b_s$. We can apply the relations (1.1) and get \begin{eqnarray*} \hx&=&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_s\a_s}\ cdots\hu{\a_2\b_2}\hu{\a_1\b_1}\\ &\equiv&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_{s+1}\a_{s+1}} \hu{\a_s\b_1}\hu{\b_1\b_s}\hu{\a_2\b_1}\hu{\a_{s-1}\b_{s-1}} \cdots\hu{\a_3\b_3}\\ &\equiv&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_{s+1}\a_{s+1}} \hu{\a_s\b_1}\hu{\a_{s-1}\b_{s-1}}\cdots\hu{\a_3\b_3} \hu{\b_1\b_s}\hu{\a_2\b_1}\\ &\equiv&\hz\hu{\a_2\b_1}. \end{eqnarray*} where, by the induction hypothesis, $\hz$ is the CM-chain of $[\hu{\a_1\b_2}u,w]_k$. Here $\hu{\a_2\b_1}$ is the first step in the CM-chain of $[u,w]_k$. Hence $\hx\equiv \hz\hu{\a_2\b_1}$, the CM-chain of $[u,w]_k$. If condition {\bf I} holds but condition {\bf II} fails, then $w(b_1)$ is not minimal. In this case assume that $\bf y$ is the DCM-chain of $[u_1,w]$. Here, we must have that $w(b_2)\a_3=\b_4>\cdots>\a_{m-1}=\b_m,$$ for $m\ge 3$, where $\a_m = w(b_2)>w(b_1)\ge\a_1$. Let $3\le s\le m$ be such that $\b_s>\a_1>\a_s$. We can apply the relations~(1.1) and get $$ \begin{array}{rcl} \hx&=&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_s\a_s}\cdots \hu{\a_2\b_2}\hu{\a_1\b_1}\\ &\equiv&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_{s+1}\a_{s+1}} \hu{\a_1\b_s}\hu{\a_s\b_1}\hu{\a_1\b_2}\hu{\a_{s-1}\b_{s-1}} \cdots\hu{\a_3\b_3}\\ &\equiv&\hu{\a_n\b_n}\cdots \hu{\a_m\b_m}\cdots\hu{\a_{s+1}\a_{s+1}} \hu{\a_1\b_s}\hu{\a_{s-1}\b_{s-1}}\cdots\hu{\a_3\b_3} \hu{\a_s\b_1}\hu{\a_1\b_2}\\ &\equiv& \hz\hu{\a_1\b_2}, \end{array} \eqno{(3.10)} $$ where $\hz$ is the CM-chain of $[\hu{\a_1\b_2}u,w]_k$. If $\hu{\a_1\b_2}$ is the first step in the CM-chain of $[u,w]_k$, then we are done. If not, then condition {\bf I$'$} on $\hu{\a_1\b_2}$ implies that only the condition {\bf I} can fail in $\hz\hu{\a_2\b_2}$ and again we are back to cases 1a or 1b. \qed\medskip We now complete the characterization of compositions $\hx=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}$ which correspond to maximal chains for some $[u,w]_k$. If $\hx$ corresponds to a maximal chain in $[u,w]_k$, then $wu^{-1}=\hx$. Hence $w=\zeta u$ where $\zeta=\hx 1=wu^{-1}$. Conversely, Proposition~\ref{Izeta} shows that for any $\zeta\in\Sym_\infty$ we can find $u$ and $w$ such that $w=\zeta u$ and $[u,w]_k$ is nonempty for some $k$. In the following, we say that a composition $\hx=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}$ is $\u{}$-reduced if $\hx 1\neq 0$. Theorem~\ref{genere} gives us a way of generating all $\u{}$-reduced sequences for $\zeta\in\Sym_\infty$; they are all connected via the relations (1)-(3) of (1.1). To complete our study, we need to characterize the compositions $\hx$ such that $\hx =0$. \begin{thm}\label{reduced} Let $\hx=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}$ be a composition. If $\hx 1=0$, then $\hx\equiv 0$ modulo the relations (1.1). \end{thm} \noindent{\em Proof } We proceed by induction on $n$. When $n=2$, \ $\hx 1=0$ implies that relation (4) applies to $\hx$. Suppose $n\ge 3$ and the theorem holds for all compositions of length $\tau^{-1}(\c)$, then $\max\{w^{-1}(\a),w^{-1}(\c)\}\le k$ implies $w^{-1}(\a)\tau^{-1}(\b)$ then $k<\min\{w^{-1}(\b),w^{-1}(\c)\le k\}$ implies $w^{-1}(\c)\tau^{-1}(\gamma)$, or $\tau^{-1}(\gamma)>\tau^{-1}(\b_n)$. \end{enumerate} \noindent We complete the proof by showing that each case (a), (b), or (c) implies $\hu{\a_n\b_n}\hy\equiv 0$ modulo the relations (1.1). \noindent{\sl If (a) holds:} By Theorem~\ref{genere} we may assume that $\hy$ is any maximal chain. Let $\hy=\hz\hu{\a_1\b_1}$. Note that if $\a_n\in dw\big(\hz 1)$ then the induction hypothesis applies and we are done. We can thus assume that $\a_n=\a_1$. But this must be true for any maximal chain $\hy$. Since $\a_1=\min\big(dw(\tau)\big)$ for the DCM-chain, we have $\a_n=\min\big(dw(\tau)\big)$. Now let $\hy$ be the CM-chain, and consider its initial segment $\hu{\a_m\b_m}\cdots\hu{\a_1\b_1}$ where $\b_1=\a_2<\b_2=\a_3<\cdots<\b_{m-1}=\a_m$ and $\b_m =\max\big(up(\tau)\big)$. If $\big|up(\tau)\big|>1$, then $m\b_{n-1}$ then we apply relation (3) to obtain $\hu{\a_n\b_n}\hy\equiv \hu{\a_{n-1}\b_{n-1}}\hu{\a_n\b_n}\hu{\a_{n-2}\b_{n-2}}\cdots\hu{\a_1\b_1} \equiv \hu{\a_{n-1}\b_{n-1}}\hy'$, and $\hy'\equiv 0$ by the induction hypothesis. If $\b_n=\a_{n-1}$ then we may apply relation (2) to obtain $\hu{\a_n\b_n}\hx\equiv \hu{\a_{n-2}\b_{n-2}}\hu{\a_n\a_{n-2}} \hu{\a_{n-2}\b_{n-1}}\cdots\hu{\a_1\b_1}$, which is equivalent to $0$ as before. Finally if $\a_{n-1}<\b_n\le\b_{n-1}$ then $\hu{\a_n\b_n}\hu{\a_{n-1}\b_{n-1}}\equiv 0$ \noindent{\sl If (b) holds:} This case is similar to (a), the map $\Omega_n$ from Lemma~\ref{vsym} can be used to interchange the roles of conditions (a) and (b). \noindent{\sl If (c) holds:} Assume that $\tau^{-1}(\a_n)>\tau^{-1}(\c)$. The other case, $\tau^{-1}(\c)>\tau^{-1}(\b_n)$, is argued in a similar fashion using the map $\Omega_n$. We may also assume that (a) does not hold, hence we have $\tau^{-1}(\c)<\tau^{-1}(\a_n)\le \a_n<\c<\b_n$ and, in particular, $\c\in up(\tau)$. Let $\c$ be minimal with these properties. We may assume that $\hy$ is the CM-chain and we let $\hy=\hu{\a_{n-1}\b_{n-1}}\hz$ and $\hz 1=\sigma\in\Sym_\infty$. In this case $\b_{n-1}=\min\big(up(\tau)\big)\le\c$. If $\b_{n-1}<\c$ then the minimality of $\c$ implies $\b_{n-1}\le\a_n$. We have a four sub-cases to consider: \begin{enumerate} \item[(i)] If $\b_{n-1}=\c$ and $\a_{n-1}\le\a_n$, then $\hu{\a_n\b_n}\hu{\a_{n-1}\b_{n-1}}\equiv 0$ is an instance of relation (4) of (1.1). \item[(ii)] If $\b_{n-1}=\c$ and $\a_{n-1}>\a_n$, then $\hu{\a_n\b_n}\hy \equiv \hu{\a_{n-1}\b_{n-1}}\hu{\a_n\b_n}\hz.$ Since $\tau^{-1}(\c)<\a_n$ and $\bf x$ is the CM-chain, we must have $\b_{n-2}=\a_{n-1}$. So $\a_n<\a_{n-1}=\b_{n-2}<\c<\b_n$ and $\sigma^{-1}(\b_{n-2})=\tau^{-1}(\c)<\a_n$. By the induction hypothesis $\hu{\a_n\b_n}\hy\equiv 0$. \item[(iii)] If $\b_{n-1}<\a_n$, then $\hu{\a_n\b_n}\hy \equiv \hu{\a_{n-1}\b_{n-1}}\hu{\a_n\b_n}\hz$ where $\sigma^{-1}(\b_{n-2})=\tau^{-1}(\c)$. The induction hypothesis applies and again $\hu{\a_n\b_n}\hz\equiv 0$. \item[(iv)] If $\b_{n-1}=\a_n$, then since $\hy$ is the CM-chain, the minimality of $\c$ implies that $\b_m=\c<\b_n$ for some $1\le m\le n-2$, with $$\a_n=\b_{n-1}>\a_{n-1}=\b_{n-2}>\cdots>\a_{m+2}=\b_{m+1}>\a_{m+1}.$$ For some $1\le s\le m$ we also have $$\c=\b_{m}>\a_m=\b_{m-1}>\cdots>\a_{s+1}=\b_s,$$ where $\a_s=\tau^{-1}(\c)<\tau^{-1}(\a_n)=\a_{m+1}$. If $s>1$ we may appeal to the induction hypothesis and get $\hu{\a_n\b_n}\hy\equiv 0$. Thus we may assume that $s=1$. Also, since $\a_1<\a_{m+1}<\b_{m+1}\le\a_n<\c=\b_m$ we may apply relations (1)-(3) as in~(3.10) to obtain $$\hu{\a_{m+1}\b_{m+1}}\hu{\a_{m}\b_{m}}\cdots\hu{\a_1\b_1}\equiv \hu{\a'_{m}\b'_{m}}\cdots\hu{\a'_1\b'_1}\hu{\a_{m+1}\b_{m+1}},$$ where $\c=\b_m=\b'_m$, $\b'_{m-1}=\a'_m$, $\b'_{m-2}=\a'_{m-1}$, $\ldots$, $\b'_1=\a'_2$ and $\a'_1=\a_1$. Hence we can use the induction hypothesis on $\hu{\a_n\b_n}\cdots\hu{\a_{m+2}\b_{m+2}}\hu{\a'_{m}\b'_{m}}\cdots\hu{\a'_1\b'_1}$, to obtain $$\hu{\a_n\b_n}\cdots\hu{\a_{m+2}\b_{m+2}}\hu{\a'_{m}\b'_{m}}\cdots\hu{\a'_1\b'_1}\equiv 0,$$ and this concludes our proof. \end{enumerate} \qed\medskip \noindent{\em Proof } [of Theorem \ref{Operators}] \begin{enumerate} \item[(a)] This is a direct consequence of Proposition~\ref{indep} and Proposition~\ref{Izeta}. \item[(b)] Theorem~\ref{genere} and Theorem~\ref{reduced} imply that the operators $\hu{\a\b}$ satisfy the relations (1.1). Equation~(3.4) gives the characterization part. \item[(c)] This is a consequence of (b), Theorem~\ref{genere}, and Theorem~\ref{reduced}. \item[(d)] Injection is from part (b) and (c). Surjection is given by Proposition~\ref{Izeta}. \item[(e)] Follows from the definitions of $\preceq$ and $\hu{\a\b}$. \item[(f)] This is a direct consequence (a)-(f) above. \end{enumerate} \qed\medskip The universal $k$-Bruhat order is a very interesting object to study on its own. Numerous other results of \cite{BS97a} can be translated to the monoid $\Mon$ and on the universal $k$-Bruhat order. We consider a few in the next section. %%%%%%%%%%%%%%%%%%%%%%%%% \section{A Combinatorial description of $c_\lambda^\zeta$.} We give a combinatorial description of the constants $c_\lambda^\zeta$ appearing in Equation~(1.3) and combinatorial proofs of many of the identities of~\cite{BS97a}. Recall that the Schur polynomial $S_\lambda(x_1,x_2,\ldots,x_k)$ equals ${\mathfrak S}_{v(\lambda,k)}$ for a unique Grassmannian permutation $v(\lambda,k)$. We have $$ {\mathfrak S}_{u}{\mathfrak S}_{v(\lambda,k)}=\sum_{w} c_{u v(\lambda,k)}^w {\mathfrak S}_{w}. \eqno{(4.1)} $$ First we consider a special case of~(4.1). The Schubert polynomial ${\mathfrak S}_{v((n),k)}=$\break $h_n(x_1,x_2,\ldots,x_k)$ is the homogeneous symmetric polynomial on $k$ variables. Lascoux and Sch\"utzenberger~\cite{LS82a} formulated a Pieri-type formula for ${\mathfrak S}_u{\mathfrak S}_{v((n),k)}$. In~\cite{BB}, proven in~\cite{Sottile96}, we have reformulated this rule. Using Theorem \ref{Operators}, we can state it here as follows: $$ {\mathfrak S}_u{\mathfrak S}_{v((n),k)} = \sum_ {\stackrel{\mbox{\scriptsize $\hx=\hu{\a_n\b_n}\cdots \hu{\a_1\b_1}\not\equiv 0 $}} {\a_1<\a_2<\cdots <\a_n}} {\mathfrak S}_{(\hx 1)u}. \eqno{(4.2)} $$ There are now other proofs of~(4.2), some of them are combinatorial~\cite{Postnikov,Veigneau}. Let $p=(p_1,p_2,\ldots,p_r)$ be a sequence of $r$ integers such that $p_1+p_2+\cdots+p_r=n$. We say that a $\u{}$-composition $\hx=\hu{\a_n\b_n}\cdots\hu{\a_1\b_1}$ {\sl weakly fits} $p$ if $$ \begin{array}{r} \hfill\a_1<\a_2<\cdots<\a_{p_1},\\ \hfill\a_{p_1+1}<\a_{p_1+2}<\cdots<\a_{p_1+p_2},\\ \hfill\vdots\;\;\\ \hfill\a_{n-p_{r}+1}<\a_{n-p_{r}+2}<\cdots<\a_n, \end{array} $$ and for all $i$, we have $p_i\ge 0$. Let ${\mathcal H}_p(\zeta)= \{\hx\in R_{\u{}}(\zeta) : \zeta=\hx1\ \hbox{\sl and $\hx$ weakly fits }\,p\}$. Note that ${\mathcal H}_p(\zeta)=\emptyset$ if some $p_i<0$. \begin{Remark}\label{HPier} {}From~(4.2), ${\mathcal H}_p(wu^{-1})$ is the coefficient of ${\mathfrak S}_w$ in the product $$ {\mathfrak S}_u{\mathfrak S}_{v((p_1),k)}{\mathfrak S}_{v((p_2),k)}\cdots {\mathfrak S}_{v((p_r),k)} $$ when all $p_i>0$. \end{Remark} \noindent Now consider the Jacobi identity~\cite{Macdonald91}: for $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_r)$ a partition of $n$, $$ {\mathfrak S}_{v(\lambda,k)}=S_\lambda(x_1,x_2,\ldots,x_k)= \det\left(h_{\lambda_i+j-i}(x_1,x_2,\ldots,x_k) \right)_{1\le i,j\le r}, \eqno{(4.3)} $$ where $h_0(x_1,x_2,\ldots,x_k)=1$, $h_n(x_1,x_2,\ldots,x_k)={\mathfrak S}_{v((n),k)}$ for $n>0$, and $h_n=0$ for $n<0$. For $\sigma\in\Sym_r$, let $\lambda_\sigma=\big(\lambda_\sigma(1),\lambda_\sigma(2), \ldots,\lambda_\sigma(r)\big)$, where $\lambda_\sigma(i)=\lambda_{\sigma(i)}+i-\sigma(i)$. Denote by $\epsilon(\sigma)$ the sign of the permutation $\sigma\in\Sym_r$. Expanding the determinant~(4.3) in~(4.1), and using~(4.2), we get \begin{eqnarray*} {\mathfrak S}_u{\mathfrak S}_{v(\lambda,k)} &=& \sum_{\sigma\in\Sym_r} \epsilon(\sigma) {\mathfrak S}_u{\mathfrak S}_{v((\lambda_\sigma(1)),k)} {\mathfrak S}_{v((\lambda_\sigma(2)),k)}\cdots {\mathfrak S}_{v((\lambda_\sigma(r)),k)}\\ &=& \sum_{w\in\Sym_\infty}\left( \sum_{\sigma\in\Sym_r} \epsilon(\sigma)\left| {\mathcal H}_{\lambda_\sigma}(wu^{-1})\right|\right) {\mathfrak S}_w. \end{eqnarray*} Thus $$ c_{uv(\lambda,k)}^w=\sum_{\sigma\in\Sym_r} \epsilon(\sigma) \left| {\mathcal H}_{\lambda_\sigma}(wu^{-1})\right|. \eqno{(4.4)} $$ This is a consequence of Theorem \ref{Operators}. {}From this we deduce the following proposition. \begin{prop}\label{XX}\mbox{ } \begin{enumerate} \item[(1)] $c_{uv(\lambda,k)}^w=0$ if $u\not\le_k w$, and \item[(2)] if $u\le_k w$ then $c_{uv(\lambda,k)}^w$ depends only on $\lambda$ and $wu^{-1}$. \end{enumerate} \end{prop} \noindent Hence, we have that $c_\lambda^\zeta=c_{uv(\lambda,k)}^w$ is well defined for any $u\le_k w$ with $\zeta=wu^{-1}$. We have \begin{thm}\label{combiconst} $\displaystyle c_\lambda^\zeta=\sum_{\sigma\in\Sym_r} \epsilon(\sigma) \left| {\mathcal H}_{\lambda_\sigma}(\zeta)\right|$. \end{thm} Let us illustrate Theorem~\ref{combiconst} on an example. Let $\zeta=(2,5,4,1,6,3)$. Using Proposition~\ref{Izeta} we have $(3,1,2,5,6,4)=u \le_4 \zeta u = (4,2,5,6,3,1)$. In Figure 2, we have drawn the interval $[u,\zeta u]_4$ and we have labeled each covering edge in the interval by the index $\a$ of the corresponding $\hu{\a\b}$. Here we have removed the commas and parentheses to represent the permutations in a more compact form. Note that there are $14$ maximal chains in this interval. %%%%%%%%%%%%%%%%%%%%%%%%% %Figure 2 \begin{figure}[htb] $$ \epsfxsize=2.5in \epsfbox{Pos2.eps} $$ \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%% \noindent Theorem~\ref{combiconst} gives us that \begin{eqnarray*} c_{(2,2,1)}^\zeta&=&\left|{\mathcal H}_{(2,2,1)}(\zeta)\right| - \left|{\mathcal H}_{(1,3,1)}(\zeta)\right| - \left|{\mathcal H}_{(2,0,3)}(\zeta)\right| + \left|{\mathcal H}_{(1,0,4)}(\zeta)\right|\\ &&\qquad\qquad+ \left|{\mathcal H}_{(-1,3,3)}(\zeta)\right| - \left|{\mathcal H}_{(-1,2,4)}(\zeta)\right|. \end{eqnarray*} The sets ${\mathcal H}_{(-1,3,3)}(\zeta)$ and ${\mathcal H}_{(-1,2,4)}(\zeta)$ are both empty since the indices contains a negative component. Looking at Figure 2, we find $$ {\mathcal H}_{(2,2,1)}(\zeta)=\{\hu{12}\hu{35}\hu{23}\hu{56}\hu{34}, \hu{34}\hu{45}\hu{12}\hu{56}\hu{24}\} $$ and ${\mathcal H}_{(1,3,1)}(\zeta)={\mathcal H}_{(2,0,3)}(\zeta)=\emptyset$. Hence $c_{(2,2,1)}^\zeta=2$. Now for $\lambda=(2,1,1,1)$ and $\sigma\in\Sym_4$, the sequences $\lambda_\sigma$ that do not contains a negative component are $(2,1,1,1)$, $(2,1,0,2)$, $(2,0,2,1)$, $(2,0,0,3)$, $(0,3,1,1)$, $(0,3,0,2)$, $(0,0,4,1)$ and $(0,0,0,5)$. For our example, we have $\left|{\mathcal H}_{(2,1,1,1)}(\zeta)\right|=5$, $\left|{\mathcal H}_{(2,1,0,2)}(\zeta)\right|=2$, $\left|{\mathcal H}_{(2,0,2,1)}(\zeta)\right|=2$ and all the others are empty. Hence $c_{(2,1,1,1)}^\zeta=5-2-2=1$. Using (1.3) for this example, we get $c_\lambda^\zeta=0$ for the other $\lambda$, since $14=5*2+4*1$ is the total number of maximal chains. With Theorem~\ref{combiconst}, we are able to show combinatorialy many of the symmetries of the $c_\lambda^\zeta$ that were first shown using geometry in~\cite{BS97a}. Let us start with symmetries derived from algebraic structures in the cohomology of the flag manifolds. If $\zeta\in\Sym_n\subset\Sym_\infty$, let $\omega_0=(n,n-1,\ldots,3,2,1)$ be the longest element of $\Sym_n$. As in Lemma~\ref{vsym}, the vertical and horizontal symmetries of (1.1) imply the following lemmas. \begin{lem}\label{SymmV} The following map (vertical symmetry) is a bijection \begin{eqnarray*} \Psi_v\colon\ R_{\u{}}(\zeta)\!\!\qquad\ \qquad&\longrightarrow& R_{\u{}}(\omega_0 \zeta\omega_0)\\ \hu{\a_n\b_n}\cdots \hu{\a_1\b_1}\ &\longmapsto&\ \hu{\omega_0(\b_n)\omega_0(\a_n)}\cdots \hu{\omega_0(\b_1)\omega_0(\a_1)} \end{eqnarray*} \end{lem} \begin{lem}\label{SymmH} The following map (horizontal symmetry) is a bijection \begin{eqnarray*} \Psi_h\colon\ R_{\u{}}(\zeta)\!\!\qquad\ \qquad&\longrightarrow& R_{\u{}}(\zeta^{-1})\\ \hu{\a_n\b_n}\cdots \hu{\a_1\b_1}\ &\longmapsto& \hu{\a_1\b_1}\cdots \hu{\a_n\b_n} \end{eqnarray*} \end{lem} Given a non-degenerate hermitian form on $\C^n$, we get an involution on the flag manifold induced by taking orthogonal complements. On the Schubert basis, this corresponds to ${\mathfrak S}_w\mapsto{\mathfrak S}_{\omega_0 w\omega_0}$ and ${\mathfrak S}_{v(\lambda,k)}\mapsto{\mathfrak S}_{v(\lambda^t,n-k)}$, where $\lambda^t$ denotes the conjugate partition. Thus $c_\lambda^\zeta=c_{\lambda^t}^{\omega_0\zeta\omega_0}$. Also $c_{u v(\lambda,k)}^w$ is the coefficient of ${\mathfrak S}_{\omega_0}$ in ${\mathfrak S}_{\omega_0w}{\mathfrak S}_u{\mathfrak S}_{v(\lambda,k)}$. Interchanging the roles of $u$ and $w$ gives $c_\lambda^\zeta=c_{\lambda}^{\omega_0\zeta^{-1}\omega_0}$. Combining these, we get $c_\lambda^\zeta=c_{\lambda^t}^{\zeta^{-1}}$. Here we show these identities directly from Theorem~\ref{combiconst} and its dual version. \begin{cor}\label{SymA} $c_\lambda^\zeta=c_{\lambda^t}^{\zeta^{-1}}$. \end{cor} \noindent{\em Proof } We note that both~(4.2) and the Jacobi identity have dual versions. For this, let $1^n$ denote the partition conjugate to $(n)$, that is $(1,1,\ldots,1)$. From~\cite{Sottile96} or other formulations, the reader deduces that $$ {\mathfrak S}_u{\mathfrak S}_{v(1^n,k)} = \sum_ {\stackrel{\mbox{\scriptsize $\hx=\hu{\a_n\b_n}\cdots \hu{\a_1\b_1}\not\equiv 0$ }} {\a_1>\a_2>\cdots >\a_n}} {\mathfrak S}_{(\hx 1)u}. \eqno{(4.5)} $$ Here ${\mathfrak S}_{v(1^n,k)}=e_n(x_1,x_2,\ldots,x_k)$ is the $n$th elementary symmetric polynomial. On the other hand, we know from~\cite{Macdonald91} that $$ {\mathfrak S}_{v(\lambda^t,k)}=S_{\lambda^t}(x_1,x_2,\ldots,x_k)= \det\left(e_{\lambda_i+j-i}(x_1,x_2,\ldots,x_k) \right)_{1\le i,j\le r}. \eqno{(4.6)} $$ For $p\in\Z^r$, we define ${\mathcal E}_p(\zeta)=\emptyset$ if $p_i<0$ for some $i$, and set ${\mathcal E}_p(\zeta)$ to be $$ \big\{\hx\in R_{\u{}}(\zeta) : \a_1>\cdots>\a_{p_1};\a_{p_1+1}>\cdots>\a_{p_1+p_2}; \ldots;\a_{n-p_r+1}>\cdots>\a_{n}\big\}. $$ otherwise. With computations similar to~(4.4), using a different expansion for the determinant~(4.6), we deduce that $$ c_{\lambda^t}^\zeta=\sum_{\sigma\in\Sym_r}\epsilon(\sigma) \left|{\mathcal E}_{\overleftarrow{\lambda_\sigma}}(\zeta)\right|, \eqno{(4.7)} $$ where for $p=(p_1,p_2,\ldots,p_r)$ we define $\overleftarrow{p}=(p_r,\ldots,p_2,p_1)$. Now we note that $\Psi_h$ in Lemma~\ref{SymmH} maps ${\mathcal H}_{p}(\zeta)$ bijectively to ${\mathcal E}_{\overleftarrow{p}}(\zeta^{-1})$. Hence by Theorem~\ref{combiconst}, the equation~(4.7) is equal to $c_\lambda^\zeta$.\qed\medskip \begin{cor}\label{SymB} $c_\lambda^\zeta=c_{\lambda^t}^{\omega_0\zeta\omega_0}$. \end{cor} \noindent{\em Proof } We only sketch the proof here since it is very similar to that of Corollary~\ref{SymA}. First, we use a different version of~(4.5), see~\cite{Sottile96}: $${\mathfrak S}_u{\mathfrak S}_{v(1^n,k)} = \sum_ {\stackrel{\mbox{\scriptsize $\hx=\hu{\a_n\b_n}\cdots \hu{\a_1\b_1}\not\equiv 0 $}} {\b_1>\b_2>\cdots >\b_n}} {\mathfrak S}_{(\hx 1)u}. $$ From this we define ${\mathcal E}'_p(\zeta)$ to be $$ \big\{\hx\in R_{\u{}}(\zeta) : \b_1>\cdots>\b_{p_1};\b_{p_1+1}>\cdots>\b_{p_1+p_2}; \ldots;\b_{n-p_r+1}>\cdots>\b_{n}\big\} $$ for $p\in\N^r$. We deduce that $$ c_{\lambda^t}^\zeta=\sum_{\sigma\in\Sym_r} \epsilon(\sigma) \left|{\mathcal E}'_{\lambda_\sigma}(\zeta)\right|. \eqno{(4.8)} $$ Finally we note that $\Psi_v$ in Lemma~\ref{SymmV} maps ${\mathcal H}_p(\zeta)$ bijectively to ${\mathcal E}'_p(\zeta)$ and this concludes our proof. \qed For an integer $a$, let $\phi_a\colon\N\to\N$ be defined by $\phi_a(i)=i$ if $i