%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% A Little bijection for affine Stanley symmetric functions %%%%%%%%%%% %%%% Thomas Lam and Mark Shimozono %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% January 2006 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{amsart} \usepackage{verbatim} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amssymb} \textwidth14.5cm \hoffset-1.2cm \def\0{{\bf0}} \def\1{{\bf1}} \def\2{{\bf2}} \def\3{{\bf3}} \def\SS{\tilde{\mathfrak{S}}} \def\tF{\tilde{F}} \def\W{\tilde{S}_n} \def\tS{\tilde{S}} \def\Z{\mathbb{Z}} \def\a{\alpha} \def\G{{\mathcal G}} \def\B{{\mathcal B}} \newtheorem{thm}{Theorem} \newtheorem{cor}[thm]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \theoremstyle{definition} \newtheorem{algorithm}[thm]{Algorithm} \newtheorem{example}[thm]{Example} \newtheorem{question}[thm]{Question} \newtheorem{remark}[thm]{Remark} \newtheorem{defi}[thm]{Definition} \newcommand{\remind}[1]{$$\texttt{*** #1 ***}$$} \date{} \begin{document} \author{Thomas Lam and Mark Shimozono} \email{tfylam@math.harvard.edu} \email{mshimo@vt.edu} \title{A Little bijection for affine Stanley symmetric functions} \thanks{M.S. was supported in part by NSF DMS-0401012.} \thanks{T.L. was supported in part by NSF DMS-0502858 and NSF DMS-0600677.} \begin{abstract} Little [{\it Adv.\ Math.} \textbf{174} (2003), 236--253] developed a combinatorial algorithm to study the Schur-positivity of Stanley symmetric functions and the Lascoux--Sch\"{u}tzenberger tree. We generalize this algorithm to affine Stanley symmetric functions, which were introduced recently in [T.~Lam: ``Affine Stanley symmetric functions," {\it Amer.\ J. Math.}, to appear]. \end{abstract} \maketitle %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 54A \rms (2006), Article~B54Ai\hfill} \def\thepage{} % % \section{Introduction} A new family of symmetric functions, called {\it affine Stanley symmetric functions} were recently introduced in~\cite{Lam}. These symmetric functions $\tF_w$, indexed by affine permutations $w \in \tS_n$, are an affine analogue of the Stanley symmetric functions $F_w$ which Stanley~\cite{Sta} introduced to enumerate the reduced decompositions of a permutation $w \in S_n$. Stanley symmetric functions were later shown to be stable limits of the {\it Schubert polynomials} ${\mathfrak S}_w$~\cite{LS,BJS}. In the case that $w$ is a {\it Grassmannian permutation} the Stanley symmetric function is equal to a Schur function. Shimozono conjectured and Lam~\cite{Lam2} recently showed that the symmetric functions $\tF_w$ also have a geometric interpretation. When $w$ is {\it affine Grassmannian} then $\tF_w$ represents a Schubert class in the cohomology $H^*({\mathcal G}/{\mathcal P})$ of the affine Grassmannian and $\tF_w$ is called an {\it affine Schur function}. Affine Schur functions were introduced by Lapointe and Morse in~\cite{LM}, where they were called {\it dual $k$-Schur functions}. A key property of the Stanley symmetric function $F_w$ is that its expansion in terms of the Schur functions $s_\lambda$ involves non-negative coefficients. This was proved by Edelman and Greene~\cite{EG} using an insertion algorithm and separately by Lascoux and Sch\"{u}tzenberger~\cite{LS} via {\it transition formulae} for Schubert polynomials. These transition formulae lead to a combinatorial object known as the {\it Lascoux--Sch\"{u}tzenberger tree} which allows one to write a Stanley symmetric function $F_w$ in terms of other Stanley symmetric functions $F_v$ labeled by permutations ``closer to Grassmannian''. Answering a question of Garsia, Little~\cite{Lit} recently gave a combinatorial proof of the identity \[ \sum_{\substack{u = v\cdot t_{r,s} \\ l(u)=l(v)+1}} F_u(X) = \sum_{\substack{w = v \cdot t_{s',r} \\ l(w)=l(v)+1}} F_w(X), \] from which the Lascoux--Sch\"{u}tzenberger tree can be deduced. Here $v \in S_n$ is any permutation, $t_{r,s}$ denotes a transposition, and the summations are over $s > r$ and $s' < r$ respectively. The aim of this article is to generalize Little's bijection and to prove an affine analogue of the above identity for the affine Stanley symmetric functions $\tF_w$. Our techniques are mainly combinatorial and the resulting bijection appears to be interesting in itself -- for example, it seems to be closely related to the affine Chevalley formula. Unfortunately, we have been unable to use our affine Little bijection to prove that an arbitrary affine Stanley symmetric function expands positively in terms of affine Schur functions. This positivity follows from the results of Lam~\cite{Lam2} combined with unpublished work of Peterson~\cite{Pet}. %{\bf Acknowledgements.} \section{Affine Stanley symmetric functions} \subsection{Affine symmetric group} Let $\W$ be the affine symmetric group. It is a Coxeter group with simple reflections $\{s_i \mid i \in \Z/n\Z\}$ and relations $s_i^2=1$ for all $i$, $(s_is_{i+1})^3=1$ for all $i$, and $(s_is_j)^2=1$ for $i \neq j \pm 1$ not adjacent mod $n$. One may realize $\W$ as the set of all bijections $w:\Z\rightarrow\Z$ such that $w(i+n)=w(i)+n$ for all $i$ and $\sum_{i=1}^n w(i) = \sum_{i=1}^n i$. In this realization, to specify an element it suffices to give the ``window" $[w(1),w(2),\dotsc,w(n)]$. %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL THOMAS LAM AND MARK SHIMOZONO}{\SMALL A LITTLE BIJECTION FOR AFFINE STANLEY SYMMETRIC FUNCTIONS} % % Given integers $r$ and $s$ such that $s\not\equiv r \mod n$, there is a unique element $t_{r,s}\in \W$ such that, in the function notation, $t_{r,s}(r)=s$ and $t_{r,s}(s)=r$, and $t_{r,s}(i)=i$ for all $i$ such that $i \not\equiv r \mod n$ and $i\not\equiv s\mod n$. We note that $t_{r,s}=t_{r',s'}$ if and only if there is an integer $k$ such that $\{r,s\}=\{r'+kn,s'+kn\}$ as sets. In this notation $s_i=t_{i,i+1}$ for all $i$. For $a_i\in \Z/n\Z$ we call $a=a_1\dotsm a_l$ a reduced word for $w\in \W$ and write $a\in R(w)$ if $w=s_{a_1}\dotsm s_{a_l}$ such that $l$ is minimum. We call $l = \ell(w)$ the length of $w$. Let $v \lessdot w$ denote the covering relation of the \textit{strong Bruhat order} $\le$ on $\W$. By definition $v\lessdot w$ if and only if there is a reflection $t_{r,s}\in \W$ such that $w=vt_{r,s}$ and $\ell(w)=\ell(v)+1$. Say that $w\in \W$ is a \textit{right $r$-cover} of $v\in \W$ if $v\lessdot w$ with $w=v t_{r,s}$ for $r0$, are $w_1=[2,5,0,3]$ and $w_2=[2,4,-1,5]$. Now $w_1 = v t_{2,4}$ and $2$ occurs once mod 4 in $\{2,3\}$, and $w_2=vt_{2,7}$ and $2$ occurs twice mod 4 in $\{2,3,4,5,6\}$. Therefore $\tF_{s_2} \tF_v = \tF_{w_1}+2\tF_{w_2}$. \end{example} \subsection{Affine Garsia--Little Formula} The following, our main result, is an affine analogue of an identity for Stanley functions observed by Garsia~\cite{Gar}, for which David Little~\cite{Lit} found a combinatorial proof. \begin{thm} \label{t:affLittle} For any $r\in\Z$ and $v\in \W$, \begin{equation} \label{e:afflittle} \sum_{u\in \Psi_r^-(v)} \tF_u = \sum_{w\in \Psi_r^+(v)} \tF_w. \end{equation} \end{thm} \begin{example}\label{e:positivity} Let $n=4$ and $v=[-1,1,4,6]=s_3s_1s_0$. For $r=1$ we have $\Psi^+_1(v)=\{[1,-1,4,6]\}$ and $\Psi^-_1(v)=\{[-3,3,4,6],[-2,1,4,7]\}$ and all the Chevalley coefficients are 1: \begin{equation*} \tF_{[1,-1,4,6]}= \tF_{[-3,3,4,6]}+\tF_{[-2,1,4,7]}. \end{equation*} With the same $n$ and $v$ but $r=2$, we have $\Psi^+_2(v)=\{[-1,4,1,6],[-3,3,4,6]\}$ and $\Psi^-_2(v)=\{[1,-1,4,6],[-1,0,5,6]\}$ and all the Chevalley coefficients are 1: \begin{equation*} \tF_{[-1,4,1,6]}+\tF_{[-3,3,4,6]}= \tF_{[1,-1,4,6]}+\tF_{[-1,0,5,6]}. \end{equation*} Using these equations together one may find the equation \begin{equation*} \tF_{[-1,4,1,6]} = \tF_{[-2,1,4,7]}+\tF_{[-1,0,5,6]} \end{equation*} The latter two are the affine Schur functions indexed by the partitions $(2,1,1)$ and $(2,2)$ respectively (see~\cite{Lam}). \end{example} \begin{remark} Theorem~\ref{t:affLittle} is a consequence of Conjecture \ref{c:Chevalley}. Note that $\tF_{s_r}$ is the Schur function $s_1$ for all $r$. Subtracting \eqref{e:tFChevalley} for $\tF_{s_r} \tF_v$ and $\tF_{s_{r+1}} \tF_v$ one obtains \eqref{e:afflittle}. \end{remark} \subsection{Garsia--Little Formula and the Lascoux--Sch\"{u}tzenberger Tree} Theorem~\ref{t:affLittle} holds, with a slight modification in a special case (explained below), with all the affine objects (affine permutations, affine transpositions, affine Stanley symmetric functions) replaced by their usual $S_n$-counterparts. The resulting {\it Garsia--Little formula} implies that a Stanley symmetric function $F_w$ is Schur-positive, as follows. Let $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n \in S_n$ be a permutation. We set \begin{eqnarray*} r &=& \max(i \mid \sigma_i > \sigma_{i+1}), \\ s &=& \max(i > r \mid \sigma_i < \sigma_r), \\ I &=& \{i < r \mid \sigma_i < \sigma_s \,\text{and for all $j \in (i,r)$ we have $\sigma_j \notin (\sigma_i,\sigma_s)$}\}. \end{eqnarray*} Now let $\pi = \sigma \cdot t_{r,s}$. One can check that we have $\Psi^+_r(\pi) = \{ \sigma \}$ and $\Psi^-_r(\pi) = \{\pi \cdot t_{i,r} \mid i \in I\}$. If $I \neq \emptyset$ then Theorem~\ref{t:affLittle} reads \[ F_\sigma = \sum_{i \in I} F_{\pi \cdot t_{i,r}}. \] The permutations $\pi \cdot t_{i,r}$ are the children of $\sigma$ in the Lascoux--Sch\"{u}tzenberger tree. When $I = \emptyset$, the corresponding equation fails to hold, but we declare $\sigma$ to have a single child $1 \otimes \sigma = (1,\sigma_1+1,\sigma_2+1, \dotsc, \sigma_n+1) \in S_{n+1}$ and we note that $F_\sigma = F_{1 \otimes \sigma}$. It can be shown that the process of (repeatedly) taking children eventually results in permutations which are Grassmannian, which are the leaves of the Lascoux--Sch\"{u}tzenberger tree. Since the Stanley symmetric function indexed by $\sigma$ is equal to the sum of those indexed by the children of $\sigma$ we conclude that it is also the sum of those indexed by the leaves which are descendents of $\sigma$. A Stanley symmetric function indexed by a Grassmannian permutation is a Schur function, so in particular every Stanley symmetric function is Schur positive. Unfortunately, a similar attempt to produce an ``affine Lascoux--Sch\"{u}tzenberger tree'' fails because for an affine permutation $w \in \tS_n$ there may be no permutation $v$ and index $r$ so that Theorem~7 involves only $\tF_w$ on one side. However, by solving simultaneous equations obtained from Theorem~7, we have so far always been able to express an affine Stanley symmetric function in terms of affine Schur functions, as demonstrated in Example~\ref{e:positivity}. It is our hope that the methods of this paper will eventually lead to a combinatorial interpretation of the coefficients $a_w^\lambda$ in the expansion $\tF_w = \sum_\lambda a_w^\lambda \tF_\lambda$ of affine Stanley symmetric functions in terms of affine Schur functions. These coefficients contain, for example, the 3-point, genus zero, Gromov--Witten invariants of the Grassmannian, which are important numbers in combinatorics, geometry, and representation theory; see~\cite{LM,Lam}. The numbers $a_w^\lambda$ also include as a special case the structure constants for the multiplication of the homology of the affine Grassmannian in the Schubert basis; see~\cite{Lam2,Pet}. \section{Affine Little Bijection} %We change notation for reduced words. From now on, $s_i\in\W$ always %denotes the simple reflection $t_{i,i+1}$. A \textit{$v$-marked word} is a pair $(a,i)$ where $a=a_1\dotsm a_l$ is a word with letters in $\{0,1,\dotsc,n-1\}$ and $i\in[1,l]$ is the index of a distinguished letter in $a$ such that $a_1\dotsm \hat{a_i}\dotsm a_l\in R(v)$ where the hatted letter is omitted. We now define the \textit{affine Little graph}. It is a directed graph whose vertices are the $v$-marked words. Given a $v$-marked word $(a,i)$ with $a=a_1\dotsm a_l$, there is a unique directed edge $(a,i)\rightarrow (a',j)$ leaving $(a,i)$, where $a'$ is the word obtained from $a$ by replacing the letter $a_i$ by $a_i-1$ (mod $n$) and the index $j$ is equal to $i$ if $a'$ is reduced and is otherwise the unique index $j\not=i$ such that $a_1\dotsm \hat{a_j} \dotsm a_l\in R(v)$, whose existence and uniqueness follows by Lemma~\ref{l:insert} (see Section~\ref{sec:coxeter}). It is not hard to see that each vertex $(a,i)$ has a unique incoming edge $(b,k)\rightarrow (a,i)$: if $a$ is reduced then $k=i$, and otherwise, $k\not=i$ is the unique index such that $a_1\dotsm \hat{a_k}\dotsm a_l\in R(v)$, and in either case, $b$ is obtained from $a$ by replacing $a_k$ by $a_k+1$. Since there are finitely many $v$-marked words, the connected components of the affine Little graph are finite directed cycles. It is clear from the definition that none of these cycles is a loop, that is, it is never the case that $(a,i)\rightarrow (a,i)$. Say that the $v$-marked word $(a,i)$ is \textit{reduced} if $a$ is a reduced word for some $w\in \W$. Given a reduced $v$-marked word $(a,i)$, write $\phi^v(a,i)=(b,j)$ where $(b,j)$ is the first reduced $v$-marked word following $(a,i)$ on the cycle of the affine Little graph containing $(a,i)$. The map $\phi^v$ defines a bijection from the set of reduced $v$-marked words to itself. We call an application of $\phi^v$ the \textit{affine Little algorithm}. Let $w\gtrdot v$, $w=vt_{r,s}$ and $a=a_1\dotsm a_l\in R(w)$. By Proposition~\ref{p:SEC} there exists a unique $i \in [1,l]$ so that $a_1 \dotsm \hat{a_i} \dotsm a_l\in R(v)$ and $(a,i)$ is $v$-marked. Therefore the set of reduced $v$-marked words is in bijection with $\bigcup_{w\gtrdot v} R(w)$, and $\phi^v$ can be regarded as a bijection from this set to itself. \begin{example} Let $n=5$, $3410321042\in R(v)$, $r=2$, and $b=3410\underline{2}321042\in \Psi^+_r(v)$ where the distinguished reflection (the $j$-th) is underlined. The computation of $\phi^v(b,j)$ is shown in Figure~\ref{f:Little}. The indices $p(a,i)$ and $q(a,i)$ are those that appear in the proof of Theorem~\ref{t:bijection}. $\phi^v(b,j)$ is given by the last row. In Figure~\ref{f:Little} the edges of the affine Little graph for $v$ go from each $v$-marked word to the one in the next row. We give some additional data used in the proof of Theorem~\ref{t:bijection} with $r=2$. We note that for the last row, literally $p(a,i)=-1$ and $q(a,i)=7$. However $-6<2$ and $t_{-1,7}=t_{-6,2}$. In other words, one should identify the pairs $(p,q)$ and $(p',q')$ if there is a $k$ such that $ p'=kn+p$ and $q'=kn+q$. \begin{figure} \begin{equation*} \begin{array}{|c|c|c|} \hline % (a,i) & p(a,i) & q(a,i) \\ \hline % 3410\underline{2}321042 & 2 & 5 \\ \hline % 3410132104\underline{2} & 2 & 3 \\ \hline % 34\underline{1}01321041 & 2 & 1 \\ \hline % 340\underline{0}1321041 & 2 & 3 \\ \hline % 340\underline{4}1321041 & -6 & 2 \\ \hline % \end{array} \end{equation*} \caption{\label{f:Little} Computation of $\phi^v$.} \end{figure} \end{example} \begin{thm} \label{t:bijection} The map $\phi^v$ restricts to a bijection \[\phi^v_r: R(\Psi^+_r(v)) \longrightarrow R(\Psi^-_r(v)).\] \end{thm} \begin{proof} Due to the symmetry of left and right $r$-covers and the bijectivity of $\phi^v$, it suffices to show that $\phi^v$ maps $\Psi^+_r(v)$ into $\Psi^-_r(v)$. Given a $v$-marked word $(a,i)$ with $a=a_1\dotsm a_l$, let $x$ and $y$ be the elements of $\W$ with reduced words $a_1\dotsm a_{i-1}$ and $a_{i+1}\dotsm a_l$ respectively. Let $w=s_{a_1}\dotsm s_{a_l}$ and $t=a_i$. Then $w=xs_t y = xy (y^{-1}s_ty)=v t_{p,q}$ where $y(p)=t$ and $y(q)=t+1$. Note also that if $s_t y > y$ (which occurs if $a$ is reduced), then $pq$. We shall use the notation $p=p(a,i)$ and $q=q(a,i)$ to emphasize the dependence on $(a,i)$. Let $b\in R(\Psi^+_r(v))$ and $(b,j)$ the corresponding $v$-marked word. Let $\phi^v(b,j)=(c,k)$ where $c\in R(u)$. It is enough to show that $q(c,k)=r$, for if so, then since $c$ is reduced, $p(c,k)y$. It follows that $q'i$. Then $s_{t'}y'>y'$ and $s_{t-1}yy$ and $s\ell(w)$. Then there are indices $ix$ or $s_iy>y$. Without loss of generality we assume that $xs_i>x$; one may reduce to this case by reversing the reduced words and replacing elements of $W$ by their inverses. By assumption $xs_i=s_1\dotsm s_i$ is reduced. Let $j$ be the minimum index such that $i+1\le j\le l$ and $s_1\dotsm s_j$ is not reduced. Then $s_1\dotsm s_{j-1} \gtrdot s_1\dotsm \hat{s_i} \dotsm s_{j-1}$ since both words are reduced. Suppose that $s_1\dotsm\hat{s_i}\dotsm s_j \ne s_1\dotsm s_{j-1}$. By Lemma~\ref{l:strong}, $s_1\dotsm s_j \gtrdot s_1\dotsm \hat{s_i}\dotsm s_j$. Since $s_1\dotsm\hat{s_i}\dotsm s_j$ is reduced it follows that $s_1\dotsm s_j$ is also, contradicting our choice of $j$. Therefore $s_1\dotsm\hat{s_i}\dotsm s_j = s_1\dotsm s_{j-1}$. Right multiplying by $s_{j+1}\dotsm s_r$ we have $v=s_1\dotsm\hat{s_i}\dotsm s_r = s_1\dotsm \hat{s_j}\dotsm s_r$. But $s_1\dotsm \hat{s_i}\dotsm s_r$ is reduced and $s_1\dotsm \hat{s_j}\dotsm s_l$ has the same number of reflections, so it too must be reduced. For uniqueness, suppose there is a $k$ distinct from $i$ and $j$ such that $v=s_1\dotsm \hat{s_k}\dotsm s_r$ is reduced. We now treat the three indices $i,j,k$ interchangeably and suppose without loss of generality that $i