\PassOptionsToPackage{usenames,dvipsnames,svgnames,table}{xcolor} \documentclass[ALCO, Unicode]{cedram} \usepackage{mathtools} \usepackage{enumitem} \usepackage{hyperref} \frenchspacing \usepackage{tikz,ifthen,keyval} \usetikzlibrary{calc} \usetikzlibrary{backgrounds} \makeatletter \newcounter{valuediagram-height} \newcounter{valuediagram-xmin} \newcounter{valuediagram-xmax} \define@key{valuediagram}{classic color}{\def\valuediagram@classiccolor{#1}} \define@key{valuediagram}{quantum color}{\def\valuediagram@quantumcolor{#1}} \define@key{valuediagram}{fontsize}{\def\valuediagram@fontsize{#1}} \define@key{valuediagram}{xscale}{\def\valuediagram@xscale{#1}} \define@key{valuediagram}{yscale}{\def\valuediagram@yscale{#1}} \define@key{valuediagram}{scale}{\def\valuediagram@scale{#1}} \define@key{valuediagram}{critical windows}{\def\valuediagram@criticalwindows{#1}} \define@key{valuediagram}{critical window color}{\def\valuediagram@criticalwindowcolor{#1}} \define@key{valuediagram}{critical window padding}{\def\valuediagram@criticalwindowpadding{#1}} \define@key{valuediagram}{node size}{\def\valuediagram@nodesize{#1}} \define@key{valuediagram}{padding}{\def\valuediagram@padding{#1}} \define@key{valuediagram}{xmin}{\def\valuediagram@xmin{#1}} \define@key{valuediagram}{xmax}{\def\valuediagram@xmax{#1}} \define@key{valuediagram}{height}{\def\valuediagram@height{#1}} \define@key{valuediagram}{thickness}{\def\valuediagram@thickness{#1}} \define@key{valuediagram}{arrow}{\def\valuediagram@arrow{#1}} \define@key{valuediagram}{baseline}{\def\valuediagram@baseline{#1}} \define@key{valuediagram}{tikzpicture options}{\def\valuediagram@tikzpictureoptions{#1}} \makeatother \setkeys{valuediagram}{ classic color=DarkGreen, quantum color=DarkRed, fontsize=\tiny, xscale=0.5, yscale=0.25, scale=1, critical windows=None, critical window color=yellow!50, critical window padding=0.1, node size=3pt, padding=0.75, xmin=1, xmax=None, height=None, thickness={very thick}, arrow={-}, baseline=0pt, tikzpicture options={}, } \makeatletter \newcommand{\valuediagram}[2][]{ \def\arg{#2} \begingroup \setkeys{valuediagram}{#1} \begin{tikzpicture}[ every node/.style={font=\valuediagram@fontsize}, xscale=\valuediagram@scale*\valuediagram@xscale, yscale=\valuediagram@scale*\valuediagram@yscale, baseline=\valuediagram@baseline, \valuediagram@tikzpictureoptions] \tikzstyle{node}=[circle, minimum size=\valuediagram@nodesize, inner sep=0pt] \tikzstyle{classic-node}=[node, fill=\valuediagram@classiccolor, draw=\valuediagram@classiccolor] \tikzstyle{quantum-node}=[node, fill=\valuediagram@quantumcolor, draw=\valuediagram@quantumcolor] \tikzstyle{segment}=[\valuediagram@arrow, \valuediagram@thickness] \tikzstyle{classic-segment}=[segment, color=\valuediagram@classiccolor] \tikzstyle{quantum-segment}=[densely dotted, segment, color=\valuediagram@quantumcolor] \tikzstyle{grid style}=[dash pattern = on 1.5pt off 1.5pt, color=lightgray] \ifthenelse{\equal{\valuediagram@height}{None}}{ \setcounter{valuediagram-height}{-1} \foreach \ab in \arg { \stepcounter{valuediagram-height} } \def\height{\arabic{valuediagram-height}} }{ \def\height{\valuediagram@height} } \ifthenelse{\equal{\valuediagram@xmax}{None}}{ \setcounter{valuediagram-xmin}{1000} \setcounter{valuediagram-xmax}{-1000} \foreach \ab [count=\acnt] in \arg { \foreach \coord [count=\bcnt] in \ab { \ifthenelse{\coord > \arabic{valuediagram-xmax}}{\setcounter{valuediagram-xmax}{\coord}}{} \ifthenelse{\coord < \arabic{valuediagram-xmin}}{\setcounter{valuediagram-xmin}{\coord}}{} } } \def\valuediagram@xmin{\arabic{valuediagram-xmin}} \def\valuediagram@xmax{\arabic{valuediagram-xmax}} }{} \draw[color=lightgray, rounded corners] (\valuediagram@xmin - \valuediagram@padding, -\valuediagram@padding) rectangle (\valuediagram@xmax + \valuediagram@padding, \height + \valuediagram@padding); \foreach \x in {\valuediagram@xmin,...,\valuediagram@xmax} {\draw[grid style] (\x, -\valuediagram@padding) -- (\x, \height + \valuediagram@padding);} \foreach \ab [count=\y from 0] in \arg { \pgfmathtruncatemacro{\a}{{\ab}[0]} \pgfmathtruncatemacro{\b}{{\ab}[1]} \coordinate (a) at ($(\a, \y)$); \coordinate (b) at ($(\b, \y)$); \ifthenelse{\a < \b}{ \draw[classic-segment] (a) -- (b); \node at (a) [classic-node] {}; \node at (b) [classic-node] {}; }{ \draw[quantum-segment] (a) -- (b); \node at (a) [quantum-node] {}; \node at (b) [quantum-node] {}; } } \pgfonlayer{background} \ifthenelse{\equal{\valuediagram@criticalwindows}{None}}{}{ \foreach \ab in \valuediagram@criticalwindows { \pgfmathtruncatemacro{\a}{{\ab}[0]} \pgfmathtruncatemacro{\b}{{\ab}[1]} \draw[color=\valuediagram@criticalwindowcolor, fill] (\a + \valuediagram@criticalwindowpadding, -\valuediagram@padding) rectangle (\b - \valuediagram@criticalwindowpadding, \height + \valuediagram@padding); } } \endpgfonlayer \end{tikzpicture} \endgroup } \makeatother \setkeys{valuediagram}{ classic color=LimeGreen, quantum color=FireBrick, fontsize=\tiny, xscale=0.4, yscale=0.2, critical windows=None, critical window color=Yellow!50, critical window padding=0.1, node size=3pt, padding=0.5, xmin=1, xmax=None, height=None, thickness={very thick}, arrow={-}, baseline=0pt, tikzpicture options={}, } \newcommand{\Fl}{{\mathbb F}\ell} \newcommand{\Fln}{{\mathbb F}\ell_n} \newcommand{\CC}{{\mathbb C}} \newcommand{\NN}{{\mathbb N}} \newcommand{\ZZ}{{\mathbb Z}} \newcommand{\frakS}{{\mathfrak S}} \newcommand{\calF}{{\mathcal F}} \newcommand{\calL}{{\mathcal L}} \newcommand{\calM}{{\mathcal M}} \newcommand{\qu}{{\mathbf u}} \newcommand{\qv}{{\mathbf v}} \newcommand{\bzero}{{\mathbf 0}} \newcommand{\bx}{{\mathbf x}} \newcommand{\precdot}{{\prec\!\!\!\cdot\,}} \newcommand{\sg}{{\mbox{\rm sg}}} \newcommand{\ptsp}{\hspace{0.55pt}} \newcommand{\pb}{\raisebox{-1pt}{\ptsp\color{magenta}\rule{0.75pt}{11pt}}\ptsp} \newcommand{\p}{\raisebox{-0.5pt}{\ptsp\color{magenta}\rule{0.75pt}{9pt}}\ptsp} \newcommand{\pp}{\raisebox{-0.3pt}{\ptsp\color{magenta}\rule{0.75pt}{6pt}}\ptsp} \DeclareMathOperator{\het}{ht} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\nd}{end} \DeclareMathOperator{\Lab}{{\it Lab}} \DeclareMathOperator{\FK}{{\it FK}} \DeclareMathOperator{\qFK}{{\it qFK}} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\Span}{Span} \DeclareMathOperator{\kactionop}{{\scriptstyle \bullet}} \newcommand{\kaction}[1][k]{\kactionop_{#1}} \newcommand{\rc}[1]{{\color{red}#1}} \newcommand{\defcolor}[1]{{\color{RoyalBlue}#1}} \newcommand{\demph}[1]{\defcolor{{\sl #1}}} \newcommand{\ncycle}{\mathfrak o} \newcommand{\hookGamma}{\mathsf{\Gamma}} \def\R{\mathbf{R}} \def\C{\mathbf{C}} \def\F{\mathbf{F}} \def\T{\mathbf{T}} \title[Quantum Murnaghan--Nakayama rule]{A quantum Murnaghan--Nakayama rule\\ for the flag manifold} \author[\initial{C.} Benedetti Vel\'{a}squez]{\firstname{Carolina} \lastname{Benedetti Vel\'{a}squez}} \address{Carolina Benedetti\\ Universidad de Los Andes\\ Bogot\'a\\ Colombia} \email{c.benedetti@uniandes.edu.co} \thanks{Benedetti thanks Grant FAPA of the Faculty of Science of Universidad de Los Andes.} \author[\initial{N.} Bergeron]{\firstname{Nantel} \lastname{Bergeron}} \address{Nantel Bergeron\\ York University\\ Toronto, Ontario\\ Canada} \email{bergeron@yorku.ca} \thanks{Bergeron is partially supported by NSERC and the York Research Chair in Applied Algebra.} \author[\initial{L.} Colmenarejo]{\firstname{Laura}\nobreakauthor\lastname{Colmenarejo}} \address{Laura Colmenarejo\\ North Carolina State University\\ Raleigh, North Carolina\\ USA} \email{lcolmen@ncsu.edu} \thanks{Colmenarejo was partially supported by the AMS-Simons Travel grant.} \author[\initial{F.} Saliola]{\firstname{Franco} \lastname{Saliola}} \address{Franco Saliola\\ Universit\'e du Qu\'ebec \`a Montr\'eal\\ Montr\'eal, Qu\'ebec\\ Canada} \email{saliola.franco@uqam.ca} \thanks{Saliola is partially supported by NSERC} \author[\initial{F.} Sottile]{\firstname{Frank} \lastname{Sottile}} \address{Frank Sottile\\ Texas A\&M University\\ College Station, Texas\\ USA} \email{sottile@tamu.edu} \thanks{Sottile is partially supported by the Simons Foundation and the National Science Foundation through grant DMS-2201005.} \keywords{Murnaghan--Nakayama rule, Schubert calculus, Schubert polynomials, quantum cohomology} \subjclass{05E05, 14N15} \begin{document} \begin{abstract} In this paper, we give a rule for the multiplication of a Schubert class by a tautological class in the (small) quantum cohomology ring of the flag manifold. As an intermediate step, we establish a formula for the multiplication of a Schubert class by a quantum Schur polynomial indexed by a hook partition. This entails a detailed analysis of chains and intervals in the quantum Bruhat order. This analysis allows us to use results of Leung--Li and of Postnikov to reduce quantum products by hook Schur polynomials to the (known) classical product. \end{abstract} \maketitle \section{Introduction} The \demph{Murnaghan--Nakayama rule} is a method for computing values of the irreducible characters of symmetric groups \cite{Mu37,Na41a,Na41b}. Under the identification of the character ring with the ring of symmetric functions, it translates into a rule for the multiplication of a Schur symmetric function by a Newton power sum. As explained in~\cite[Sect.~2]{MorrisonSottile}, in the cohomology ring of a Grassmannian, the Murnaghan--Nakayama formula is a formula for the intersection product of a Schubert variety with a component of the Chern character of the tautological bundle (a tautological class), as these tautological classes are essentially Newton power sums. Consequently, any formula describing multiplication by a tautological class will also be called a Murnaghan--Nakayama rule. Murnaghan--Nakayama rules have been described for many different algebras that carry a notion of a Newton power sum. Fomin and Green gave a version for noncommutative symmetric functions, which led to formulas for characters of representations associated to stable Schubert and Grothendieck polynomials~\cite{FoGr98}. Assaf and McNamara gave a skew version~\cite{A-McN}, which Konvalinka generalized to a skew rule for multiplication by a `quantum' (perturbed by a parameter $q$) power sum function~\cite{Ko12}. Bandlow, \emph{et al.} gave a version in the cohomology of an affine Grassmannian~\cite{BSZ11}, and Lee gave a version in the cohomology of the affine flag manifold~\cite{Lee}. Tewari gave a version for noncommutative Schur functions~\cite{Tewari}, and Berg \emph{et al.} for the immaculate noncommutative symmetric functions \cite{BBSSZ}. Wildon gave a plethystic version~\cite{Wildon}. Ross gave a version for loop Schur functions~\cite{Ro14}, providing a fundamental step in the orbifold Gromov--Witten/Donaldson--Thomas correspondence~\cite{RoZo13}. Morrison and Sottile gave Murnaghan--Nakayama rules in the cohomology ring of a flag manifold and in the quantum cohomology of the Grassmannian~\cite{MorrisonSottile}. Khanh, \emph{et al.} gave a version in the Grothendieck ring of the Grassmannian~\cite{KHST}. Khanh also gave a version for $K$-$k$-Schur and $k$-Schur functions~\cite{Khanh}, generalizing~\cite{BSZ11}. Fan, \emph{et al.} gave a Murnaghan--Nakayama formula for Chern--Schwartz--MacPherson classes of Schubert cells in the flag variety~\cite{FGX}. We first derive a formula for the multiplication of a Schubert polynomial by a hook Schur polynomial and use this to give a new proof of the Murnaghan--Nakayama formula in the cohomology of a flag variety that was originally derived in~\cite{MorrisonSottile}. This hook multiplication formula is related to the formula of M{\'e}sz{\'a}ros et al.~\cite[Thm.~2]{MPP}, but it does not use the noncommutative Fomin--Kirillov algebra~\cite{FominKirillov}. Our main result (Corollary~\ref{C:quantumMN}) is a Murnaghan--Nakayama rule in the small quantum cohomology ring of the flag manifold, proving a formula conjectured by Morrison at FPSAC 2014~\cite{Morrison}. This follows from a formula (Theorem~\ref{thm:q_hook_product}) for multiplication by a quantum Schur polynomial indexed by a hook partition. M{\'e}sz{\'a}ros et al.~\cite[Thm.~15]{MPP} also gave a formula for multiplication by a hook quantum Schur polynomial, which would imply our formula. Unfortunately, their proof is not valid, as we explain in Section~\ref{SS:R_MPP}---this necessitates the arguments we give. Our arguments involve a detailed analysis of chains and intervals in the \demph{quantum Bruhat order}, a partial order relevant to multiplication in the quantum cohomology of a flag manifold. We also use the ``quantum-equals-classical'' result of Leung and Li \cite{LeungLi2012} as well as Postnikov's cyclic symmetry \cite{Postnikov_symmetry} to show that structure constants for quantum products by hook quantum Schur polynomials are equal to structure constants for the classical product from~\cite{So96}, and thereby deduce our results. In Section~\ref{sec:classic-mn-rule} we develop some background on the flag variety and Bruhat order, giving a new proof of the Murnaghan--Nakayama formula in the cohomology of the flag variety. Section~\ref{S:qCoh} develops background on the quantum cohomology ring of the flag variety, and gives a proof of the Murnaghan--Nakayama formula in this setting, which relies on results established in two subsequent sections. We extract some results of Leung and Li \cite{LeungLi2012} in Section~\ref{quantum-equals-classical}, including a version of their ``quantum-equals-classical'' result (Lemma~\ref{L:Quantum_is_Classical}). The final Section~\ref{left-operators} develops a detailed combinatorics of chains in the quantum Bruhat order to prove the second result used in our proof of the quantum Murnaghan--Nakayama rule (Theorem~\ref{Th:nonZero}). It is the technical heart of this paper. A theme in the paper~\cite{BS-Bruhat} is the relation between intervals in the $k$-Bruhat order~$\leq_k$ (a suborder of the Bruhat order on $S_n$) and Littlewood--Richardson coefficients $c^w_{u,v}$ when $v$ is a Grassmannian permutation. For example, the isomorphism type of an interval $[u,w]_k$ in the $k$-Bruhat order only depends upon $wu^{-1}$, and $c^w_{u,v}$ also only depends upon $wu^{-1}$ when $v$ is Grassmannian. Only substantially weaker versions of these and related results hold for quantum cohomology. While an interval $[u,q^\alpha w]_k^q$ in the quantum $k$-Bruhat order (see Section~\ref{quantum-k-bruhat-order}) is not determined by $wu^{-1}$, its isomorphism type is preserved by some operations including a cyclic shift (Corollary~\ref{C:equivalences}) that is related to Postnikov's cyclic shift and is distinct from the cyclic shift in~\cite{BS-Bruhat} (which does not preserve isomorphism type). When $v$ is Grassmannian, we show that the numerical part $N^{w,\alpha}_{u,v}$ of a quantum Littlewood--Richardson coefficient (see Section~\ref{quantum-equals-classical}) only depends upon $wu^{-1}$ (but $q^\alpha$ may change); this is Theorem~\ref{Th:quantumIndependence}. \begin{remark}\label{rem:fpsac} The results of this paper were announced in a published FPSAC conference abstract~\cite{FPSAC23}. Here, we provide all the proofs, clarify some definitions and statements, and correct typos. \end{remark} \section{A Murnaghan--Nakayama rule for (classic) cohomology} \label{sec:classic-mn-rule} We review combinatorial models for the cohomology ring of the flag manifold. We omit the precise definitions of the flag manifold and its cohomology as the combinatorial models will suffice for our purposes; the interested reader can consult~\cite{Fu97}. Then we deduce a formula for the product of a Schubert polynomial and a hook Schur function from which we deduce the Murnaghan--Nakayama rule in the cohomology of the flag manifold, resulting in a different proof from that given by Morrison and Sottile \cite{MorrisonSottile}. Our proof of the Murnaghan--Nakayama rule in quantum cohomology is analogous. \subsection{Cohomology of the flag manifold} \label{cohomology-ring-of-the-flag-manifold} Let $n\in\NN$ be a positive integer and write \defcolor{$\Fln$} for the manifold of complete flags in $\CC^n$. We let \defcolor{$H^*\Fln$} denote its cohomology ring with coefficients in $\ZZ$. This is a free $\ZZ$-module with a distinguished basis \defcolor{$\{\frakS_w\}_{w \in S_n}$} of \demph{Schubert classes} which are indexed by elements of the symmetric group~\defcolor{$S_n$}. Borel~\cite{Borel} described the ring structure of $H^*\Fln$ as a quotient of a polynomial ring, \begin{equation} \label{borel-presentation} H^* \Fln\ \simeq\ \ZZ[x_1,\dotsc,x_n] / I_n\,, \qquad I_n\ =\ \big\langle e_a(x_1,\dotsc,x_n)\mid a \in [n] \big\rangle\,, \end{equation} where $e_a$ is the $a$th elementary symmetric polynomial and $\defcolor{[n]}\vcentcolon=\{1,\dots,n\}$. Lascoux and Sch\"utzen\-ber\-ger~\cite{LaSch82} defined a set of polynomials in $\ZZ[x_1, \ldots, x_n]$ called \demph{Schubert polynomials} that correspond to the Schubert classes $\frakS_w$ under Borel's isomorphism. We write $\frakS_w(x)$ for the Schubert polynomial corresponding to $\frakS_w$ on the set of variables $x: = \{x_1, \ldots, x_n\}$. Every Schur polynomial $s_\lambda(x_1, \ldots, x_k)$ is a Schubert polynomial. Let $w\in S_n$ be a permutation with a unique descent at position $k$. Then the sequence $(w(k){-}k,\dotsc, w(2){-}2,w(1){-}1)$ is a partition contained in the \demph{rectangular partition $R_{k,n-k}$} of $k(n{-}k)$ into $k$ parts with each part of size $n{-}k$. This is a bijection and for $\lambda \subseteq R_{k, n-k}$ we write $\defcolor{v(\lambda,k)}\in S_n$ for the corresponding permutation. Then $\frakS_{v(\lambda, k)}(x) = s_\lambda(x_1, \ldots, x_k)$. For example, when $n=7$, \begin{equation} v((3,1,0),3)\ =\ 136\p2457 \qquad\mbox{and}\qquad v((1,0,0,0),4)\ =\ 1235\p467\ =\ (4,5)\,. \end{equation} Observe that we may write permutations using both one-line and cycle notation. The ``\,$\p$\,'' is written after the $k$-th position in a permutation in one-line notation. It remains an important open problem in Schubert calculus to find a manifestly positive combinatorial rule expressing $\frakS_u \cdot \frakS_v$ in terms of the basis $\{ \frakS_w \}_{w \in S_n}$ of $H^*\Fln$. That is, one seeks a combinatorial rule for the coefficients $\defcolor{c_{u,v}^{w}}\in\ZZ$ in the product \begin{equation} \label{eq:classical-coeffs} \frakS_u \cdot \frakS_v\ =\ \sum_{w} c_{u, v}^{w} \frakS_w\,. \end{equation} A remarkable property of Schubert polynomials is that this computation can be performed directly in the polynomial ring as the resulting coefficients $c_{u, v}^w$ are the same. Although this problem remains open in general, several special cases are known. \demph{Monk's Formula}~\cite{Monk} treats the case where $v$ is the simple transposition $(k, k{+}1)$. For any $u \in S_n$, \begin{equation} \label{classical-Monk-formula} \frakS_u(x) \cdot \frakS_{(k,k+1)}(x) \ =\ \sum_{\substack{1 \leq i \leq k < j \leq n \\ \ell(u) + 1 = \ell(u(i,j))}} \frakS_{u (i,j)}(x)\,, \end{equation} where $\defcolor{\ell(u)}\vcentcolon=\#\{iu(j)\}$ denotes the length of the permutation $u$. In this case, $\frakS_{(k, k+1)}(x) = s_{(1)}(x_1, \ldots, x_k)$. Proposition~\ref{pieri-formulas-version-2} below describes the special case of multiplying by $s_{(b, 1^{a-1})}(x_1, \ldots, x_k)$ in terms of the \emph{$k$-Bruhat order}, which we define next. Here, $(b,1^{a-1})$ is the \demph{hook partition} of $a{+}b{-}1$ into $a$ parts, the first of size $b$, and the remaining all of size $1$. \subsection{\texorpdfstring{$k$}{k}-Bruhat order} The terms appearing in Monk's Formula \eqref{classical-Monk-formula} define a partial order on $S_n$ graded by $\ell(u)$. Define the \demph{$k$-Bruhat order $\leq_k$} by the covering relation \[ {\defcolor{u\lessdot_k u (i,j)}} \qquad\text{if}\quad 1 \leq i\leq k\dotsb >l_a 3 = \#\supp(\zeta_2) - s(\zeta_2). \end{equation*} Related to minimality is the notion of crossing. Let $l_1 \calL(\eta) + \calL(\eta')$, which contradicts that $\zeta$ is minimal. This inequality is illustrated by $\zeta=(1,7,4)(3,6)$. We showed that $\calL(\zeta)=5$, but $\calL(1,7,4) = 2$ and $\calL(3,6)=1$. \end{proof} \begin{proposition}\label{P:peaklessChains} A permutation $\zeta\ne e$ is minimal if and only if the interval $[e,\zeta]_\preceq$ has a peakless chain. The number of peakless chains of height $a$ in $[e,\zeta]_\preceq$ is the binomial coefficient $\left(\begin{smallmatrix} s(\zeta)-1 \\ \het(\zeta)-a \end{smallmatrix}\right)$. \end{proposition} \begin{proof} We begin by showing that the first statement follows from the corresponding result for irreducible permutations. Let $\zeta=\zeta_1\dotsb \zeta_s$ be the unique factorization of $\zeta$ into a noncrossing product of irreducible permutations. By Lemma~\ref{L:properties-noncrossing-products}, $\zeta$ is minimal if and only if each $\zeta_i$ is minimal. Since $\zeta_i$ is irreducible, $\zeta$ is minimal if and only if each interval $[e, \zeta_i]_{\preceq}$ has a peakless chain. By Lemma~\ref{L:properties-noncrossing-products}, this holds if and only if $[e, \zeta]_{\preceq}$ has a peakless chain. We now prove the result for irreducible permutations. Suppose that $\zeta$ is minimal and irreducible. By Lemma~\ref{L:properties-noncrossing-products}, $\zeta$ is a single cycle. In~\cite[Lem.~6.7]{BS-iso} it is proved that if $\zeta$ is a minimal cycle, then there is a unique peakless chain in the interval $[e, \zeta]_\preceq$, which proves the forward direction. Conversely, suppose that $[e, \zeta]_\preceq$ has a peakless chain. Let \defcolor{$a$} be the height of that chain and set $\defcolor{b}\vcentcolon=\calL(\zeta){-}a{+}1$. Replacing $\zeta$ by a shape-equivalent permutation if necessary, we may assume that $\supp(\zeta)=[n]$ (so that~$\zeta\in S_n$) and thus $\calL(\zeta) \geq \#\supp(\zeta) - s(\zeta) = n-1$. Since $e \preceq \zeta$, there is a $k < n$ and $u \in S_n$ such that $u \leq_k \zeta u$ and $[e, \zeta]_\preceq \simeq [u, \zeta u]_k$. By~\cite[Thm.~3.1.5]{BS-Bruhat}, we have \begin{equation*} \{i \mid i < \zeta(i)\}\ \subseteq\ \{u^{-1}(1), \ldots, u^{-1}(k)\} \ \text{and}\ \{i \mid i > \zeta(i)\}\ \subseteq\ \{u^{-1}(k + 1), \ldots, u^{-1}(n)\} \end{equation*} so that \begin{equation*} \het(\zeta)\ =\ \#\{i \mid i < \zeta(i)\} \leq k \quad\text{and}\quad n - \het(\zeta)\ =\ \#\{i \mid i > \zeta(i)\} \leq n - k. \end{equation*} Together, these imply that $\het(\zeta) = k$. Since there is a peakless chain in $[e,\zeta]_\preceq$ and $[e,\zeta]_\preceq\simeq[u,\zeta u]_k$, it follows from Formula~\eqref{eq:schubert-times-hook-via-peakless-chains} below that the coefficient $c^{\zeta u}_{u, v((b,1^{a-1}),k)}$ is nonzero. This implies that~$v((b,1^{a-1}),k)\leq_k \zeta u$. As $\zeta u\in S_n$, we have $v((b,1^{a-1}),k)\in S_n$. Thus $a\leq k\ \dotsb\ >\ l_{a-1} \ >\ l_a\ <\ l_{a+1}\ <\ \dotsb\ <\ l_{a+b-1} \end{equation} into three subsets. Call $l_1> \dotsb>l_{a-1}$ the decreasing segment, $l_a$ the minimum, and $l_{a+1} <\dotsb0$, let $\defcolor{p_r(x_1,\dotsc,x_k)}\vcentcolon=x_1^r+\dotsb+x_k^r$ denote the $r$th power sum polynomial. Expanded in terms of Schur polynomials~\cite{Macdonald}, we have \begin{equation}\label{Eq:PowerSumHook} p_r(x_1, \ldots, x_k) = s_{(r)}(x_1, \ldots, x_k) - s_{(r-1,1)}(x_1, \ldots, x_k) + \cdots + (-1)^{r+1} s_{(1^r)}(x_1, \ldots, x_k). \end{equation} \begin{corollary}[Murnaghan--Nakayama rule for $H^*\Fln$] \label{C:classical-schubert-times-powersum} Let $u \in S_n$. Then \begin{equation*} \frakS_u(x) \cdot p_r(x_1,\dotsc,x_k)\ =\ \sum (-1)^{\het(\zeta)+1} \frakS_{\zeta u}(x)\,, \end{equation*} the sum over all minimal cycles $\zeta \in S_n$ such that $u\leq_k\zeta u$ and $\calL(\zeta)=r$. \end{corollary} \begin{proof} Expanding the product $\frakS_u(x) \cdot p_r(x_1,\dotsc,x_k)$ using Equations \eqref{Eq:Schubert-times-hook} and \eqref{Eq:PowerSumHook} shows that the coefficient of $\frakS_{\zeta u}$ for $u\leq_k\zeta u$ is zero unless $\calL(\zeta)=r$ and $\zeta$ is minimal. When $\zeta$ is the noncrossing product of $s(\zeta)$ minimal cycles, this coefficient is \begin{equation*} (-1)^{\het(\zeta)+1} \sum_{a=1}^{r} (-1)^{a-\het(\zeta)}\binom{s(\zeta)-1}{\het(\zeta)-a}\ =\ \begin{cases} 0, & \text{ if } s(\zeta)\neq 1,\\ (-1)^{\het(\zeta)+1},& \text{ if } s(\zeta)=1. \end{cases} \qedhere \end{equation*} \end{proof} This proof differs from that given in~\cite{Morrison, MorrisonSottile}. \section{A Murnaghan--Nakayama rule for quantum cohomology} \label{S:qCoh} The (small) quantum cohomology ring \defcolor{$qH^*\Fln$} of the flag manifold is a deformation of the ordinary cohomology ring $H^*\Fln$ whose product encodes the genus zero three-point Gromov--Witten invariants of $\Fln$. We describe this ring and extend the main objects from Section~\ref{sec:classic-mn-rule} to the quantum setting. \subsection{Quantum cohomology ring of the flag manifold} As a $\ZZ$-module, we have \begin{equation*} qH^*\Fln\ =\ \ZZ[q_1,\dotsc,q_{n-1}] \otimes_\ZZ H^*\Fln\,, \end{equation*} where $q_1,\dotsc,q_{n-1}$ are indeterminates. To simplify notation, write \defcolor{$\ZZ[q]$} for\break $\ZZ[q_1,\dotsc,q_{n-1}]$, and use multiindex notation, for $\alpha\in\NN^{n-1}$, we have $\defcolor{q^\alpha}\vcentcolon= q_1^{\alpha_1}\dotsb q_{n-1}^{\alpha_{n-1}}$. The Schubert classes $\{\frakS_w\}_{w \in S_n}$ in $H^*\Fln$ form a $\ZZ[q]$-basis of $qH^*\Fln$. We write $\defcolor{\frakS_u \ast \frakS_v}$ for the product of Schubert classes $\frakS_u$ and $\frakS_v$ in $qH^*\Fln$ to distinguish it from the product $\defcolor{\frakS_u \cdot \frakS_v}$ in $H^*\Fln$. The ring structure of $qH^*\Fln$ is determined by the \demph{quantum Monk formula}~\cite{FGP}. For every $u\in S_n$ and $1\leq k0$, the \demph{quantum power sum} is defined to be \begin{multline} \label{Eq:Q-powerSum} \qquad \defcolor{p^q_r(x_1,\dotsc,x_k)}\ \vcentcolon= \\ s^q_{(r)}(x_1,\dotsc,x_k) - s^q_{(r-1,1)}(x_1,\dotsc,x_k) + \dotsb + (-1)^{r+1} s^q_{(1^r)}(x_1,\dotsc,x_k)\,. \qquad \end{multline} \subsection{Quantum \texorpdfstring{$k$}{k}-Bruhat order} \label{quantum-k-bruhat-order} The terms appearing in the quantum Monk formula~\eqref{quantum-Monk-formula} define a ranked partial order on the (infinite) set \begin{equation*} \defcolor{S_n[q]}\ \vcentcolon=\ \big\{ q^\alpha u \mid u\in S_n \text{ and } \alpha\in\NN^{n-1}\big\}\,. \end{equation*} The \demph{quantum $k$-Bruhat order $\leq_k^q$} on $S_n[q]$ is defined by the following cover relations: \begin{enumerate} \item $\defcolor{u\lessdot_k^q u (i,j)}$ if $i\leq k u(j)$, and \\ for every $l$ such that $i < l < j$, we have $u(j) < u(l) < u(i)$. \end{enumerate} \end{proposition} \subsection{Minimal intervals} \label{sec:Qminim} As far as we know, there is no analog of the Grassmannian--Bruhat order related to the quantum $k$-Bruhat order, and so rather than speak of minimal permutations (as we did in the classical case; see Section~\ref{minimal-permutations}), we work instead with certain intervals in the quantum $k$-Bruhat order. This lack of an analog of the Grassmannian--Bruhat order necessitates the significant work we do in Section~\ref{left-operators}. Let $u, w \in S_n$ and suppose that $u \leq_k^q q^{\alpha}w$ in the quantum $k$-Bruhat order on~$S_n[q]$. We say that the interval $[u,q^\alpha w]_k^q$ is \demph{minimal} if its rank $\ell(q^{\alpha}w)-\ell(u)$ equals $\#\supp(wu^{-1}) - s(wu^{-1})$. When $q^\alpha=1$, the interval $[u, w]_k^q=[u,w]_k$ is minimal if and only if $wu^{-1}$ is a minimal permutation. In the proof of Theorem~\ref{thm:q_hook_product} we will show that if $[u,q^\alpha w]_k^q$ is minimal, then $wu^{-1}$ is a minimal permutation in the sense of Section~\ref{minimal-permutations}. The interval on the left in Figure~\ref{F:k-Bruhat} is a minimal interval in the quantum $5$-Bruhat order in $S_8$. Figure~\ref{F:more_minimal} displays two minimal intervals in quantum $k$-Bruhat order on~$S_5[q]$ for $k=2,3$. \begin{figure}[htb] \centering \begin{picture}(100,110)(-15,0) \put(13,0){\includegraphics{figures/q-int1.eps}} \put(25,100){\small$q_{1,5}q_{2,4}12\p354$} \put(-15, 75){\small$q_{2,5}52\p314$} \put(38, 75){\small$q_{1,5}15\p324$} \put(-15, 50){\small$q_{2,5}51\p324$} \put(38, 50){\small$q_{1,5}14\p325$} \put( 0, 25){\small$54\p321$} \put(38, 25){\small$q_{1,5}13\p425$} \put( 0, 0){\small$53\p421$} \end{picture} \qquad \begin{picture}(120,110)(-35,0) \put(-25,0){\includegraphics{figures/q-int2.eps}} \put(-10,100){\small$q_{3,5}521\p34$} \put(0, 75){\small$524\p31$} \put(35,75){\small$q_{3,5}421\p35$} \put(-35,50){\small$514\p32$} \put(0, 50){\small$523\p41$} \put(45,50){\small$425\p31$} \put(-35,25){\small$513\p42$} \put(0, 25){\small$423\p51$} \put(45,25){\small$415\p32$} \put(0, 0){\small$413\p52$} \end{picture} \caption{Two minimal quantum intervals. Note that $q_{1,5}q_{2,4}=q_{1,4}q_{2,5}=q_1q_2^2q_3^2q_4$.} \label{F:more_minimal} \end{figure} \subsection{The Murnaghan--Nakayama rule for \texorpdfstring{$qH^*\Fln$}{qH*Fln}} As for Corollary~\ref{C:classical-schubert-times-powersum}, we derive the quantum Murnaghan--Nakayama formula from an intermediate result describing the quantum product of a Schubert class $\frakS_u$ by a quantum hook Schur polynomial $s_{(b, 1^{a-1})}^q(x_1,\dotsc,x_k)$. \begin{theorem} \label{thm:q_hook_product} Let $u \in S_n$\,, $a \leq k$ and $b \leq n-k$. Then \begin{equation*} \frakS_u \ast s^q_{(b,1^{a-1})} (x_1, \dots, x_k) = \sum \left(\begin{smallmatrix} s(wu^{-1})-1 \\ \het(wu^{-1})-a \end{smallmatrix}\right) q^\alpha \frakS_{w}\,, \end{equation*} the sum over all minimal intervals $[u, q^{\alpha}w]_k^q$ such that $\ell(q^\alpha w) - \ell(u)= a{+}b{-}1$. \end{theorem} The proof depends on Theorem~\ref{Th:nonZero} and Lemma~\ref{L:Quantum_is_Classical}, which will be proved in subsequent sections. \begin{proof} For $u,w \in S_n$, a partition $\lambda$, $k \in \NN$ with $1\leq k$ and $\alpha\in \NN^{n-1}$, define quantum Littlewood--Richardson coefficients $C^{q^\alpha w}_{u,v(\lambda,k)}\in q^\alpha \NN$ by \begin{equation} \label{eq-definition-Cq} \frakS_u \ast s^q_\lambda(x_1, \ldots, x_k) \ =\ \sum_{q^\alpha w \in S_n[q]} C^{q^\alpha w}_{u,v(\lambda,k)} \frakS_w\,. \end{equation} We must prove that \begin{equation*} C^{q^\alpha w}_{u,v((b, 1^{a-1}),k)}\ =\ \begin{cases} q^\alpha \left(\begin{smallmatrix} s(wu^{-1})-1 \\ \het(wu^{-1})-a \end{smallmatrix}\right), & \begin{array}[t]{lr} \text{if $[u, q^{\alpha}w]_k^q$ is minimal and} \\[-0.5ex] \qquad\qquad\qquad \text{$\ell(q^\alpha w) - \ell(u) = a{+}b{-}1$,} \end{array} \\ 0, & \begin{array}[t]{lr} \text{otherwise.} \end{array} \end{cases} \end{equation*} Suppose that $[u, q^{\alpha}w]_k^q$ is a minimal interval with $\ell(q^\alpha w) - \ell(u) = a{+}b{-}1$. By Theorem~\ref{Th:nonZero}, there exists a hook partition $\gamma$ with $|\gamma| = \ell(q^\alpha w) - \ell(u)$ and $C^{q^\alpha w}_{u,v(\gamma,k)} \neq 0$. By Lemma~\ref{L:Quantum_is_Classical}, there exist permutations $y, z \in S_n$ satisfying \begin{equation} \label{properties-of-y-and-z} y\ \leq_k\ z, \quad \ell(z) - \ell(y)\ =\ \ell(q^\alpha w) - \ell(u) = a{+}b{-}1, \quad zy^{-1}\ =\ wu^{-1}, \end{equation} and such that \begin{equation} \label{eq-leung-li-reduction} C^{q^\alpha w}_{u,v(\mu,k)}\ =\ q^\alpha c^z_{y,v(\mu,k)} \quad \text{for all partitions $\mu$ with $|\mu| = a{+}b{-}1$\,.} \end{equation} This implies that $z y^{-1}$ is a minimal permutation, since \begin{align*} \ell(z) - \ell(y) = \ell(q^\alpha w) - \ell(u) = \#\supp(w u^{-1}) - s(w u^{-1}) = \#\supp(z y^{-1}) - s(z y^{-1}), \end{align*} where the middle equality follows from the assumption that $[u, q^{\alpha}w]_k^q$ is minimal. Then \begin{equation} C^{q^\alpha w}_{u,v((b, 1^{a-1}),k)} \ =\ q^\alpha c^z_{y,v((b, 1^{a-1}),k)} \ =\ q^\alpha \left(\begin{smallmatrix} s(zy^{-1})-1 \\ \het(zy^{-1})-a \end{smallmatrix}\right) \ =\ q^\alpha \left(\begin{smallmatrix} s(wu^{-1})-1 \\ \het(wu^{-1})-a \end{smallmatrix}\right), \end{equation} where the first equality follows from \eqref{eq-leung-li-reduction} and the second equality follows from Proposition~\ref{P:classical_hook} and that $z y^{-1}$ is a minimal permutation. Conversely, suppose $C^{q^\alpha w}_{u,v((b, 1^{a-1}), k)} \neq 0$. By Lemma~\ref{L:Quantum_is_Classical}, there exist $y, z \in S_n$ satisfying \eqref{properties-of-y-and-z} and \eqref{eq-leung-li-reduction}. Setting $\mu = (b, 1^{a-1})$ in \eqref{eq-leung-li-reduction} gives \begin{equation} C^{q^\alpha w}_{u,v((b, 1^{a-1}),k)} \ =\ q^\alpha c^z_{y,v((b, 1^{a-1}),k)}. \end{equation} Since the left hand side is assumed to be nonzero, we have that $c^z_{y,v((b, 1^{a-1}),k)}$ is nonzero. It now follows from Proposition~\ref{P:classical_hook} that $z y^{-1}$ is a minimal permutation so that \begin{equation*} \ell(q^\alpha w) - \ell(u) = \ell(z) - \ell(y) = \#\supp(z y^{-1}) - s(z y^{-1}) = \#\supp(w u^{-1}) - s(w u^{-1}), \end{equation*} where the first and last equalities follow from \eqref{properties-of-y-and-z}. Thus, $[u, q^\alpha w]_k^q$ is a minimal interval such that $\ell(q^\alpha w) - \ell(u) = a{+}b{-}1$. \end{proof} The following was conjectured in~\cite{Morrison}. It follows from Theorem~\ref{thm:q_hook_product} in the same way that Corollary~\ref{C:classical-schubert-times-powersum} follows from Proposition~\ref{P:classical_hook}, and is the signature result in this paper. \begin{corollary}[Quantum Murnaghan--Nakayama Formula] \label{C:quantumMN} Let $u \in S_n$. Then \begin{equation*} \frakS_u \ast p_r^q(x_1,\dotsc,x_k) = \sum (-1)^{\het(wu^{-1})+1} q^\alpha \frakS_{w} \end{equation*} the sum over all minimal intervals $[u, q^{\alpha}w]_k^q$ of rank $r$ such that $wu^{-1}$ is a single cycle. \end{corollary} \begin{example}\label{Ex:MN_example} In $qH^*\Fl_8$, if $u=68235741$, then the product $\frakS_{u}\ast p^q_4(x_1,\dotsc,x_5)$ is \begin{gather*} \frakS_{(2,3,5,7,4)u} + \frakS_{(2,4,3,5,7)u} + \frakS_{(3,5,6,7,4)u} - \frakS_{(2,3,5,6,7)u} + q_{5,7}\frakS_{(2,3,4,7,5)u} \\ + q_{5,7}\frakS_{(3,4,6,7,5)u} + \defcolor{q_{5,8}\frakS_{(1,6,7,3,5)u}} + q_{5,8}\frakS_{(1,7,2,3,5)u} - q_{5,8}\frakS_{(1,6,7,5,4)u} \\ - q_{5,8}\frakS_{(1,7,5,3,4)u} - q_{5,8}\frakS_{(1,7,4,3,5)u} - q_{2,6}\frakS_{(2,3,5,7,8)u} + q_{2,8}\frakS_{(1,7,3,5,8)u} \\ + q_{2,8}\frakS_{(1,8,2,3,4)u} + q_{2,8}\frakS_{(1,6,7,5,8)u} + q_{2,8}\frakS_{(1,7,5,6,8)u} -q_{2,8}q_{5,7}\frakS_{(1,7,5,4,8)u} \,. \end{gather*} Note that unlike in ordinary cohomology, this is not an identity among quantum Schubert polynomials $\frakS^q_w(x)$, but rather among their images in the quotient ring $\ZZ[q][x]/I^q_n$. \end{example} \subsection{Remarks regarding~\texorpdfstring{\cite[Thm.~15]{MPP}}{[25, Thm. 15]}}\label{SS:R_MPP} Proposition~\ref{P:classical_hook} may be deduced from a stronger result of M\'esz\'aros, Panova, and Postnikov~\cite[Thm.~8]{MPP}. There, they establish a formula for a `lift' of the Schur polynomial $s_{(b,1^{a-1})}(x_1,\dotsc,x_k)$ to the Fomin--Kirillov~\cite{FominKirillov} algebra ${\mathcal E}_n$, which is a subalgebra (generated by certain Dunkl elements~$\theta_i$) of the quotient of a free associative algebra with generators $x_{i,j}$ for $1\leq i0$. \item \emph{(\cite[Lemma 2.10]{LeungLi2012})} If $\varpi_i(\alpha)>0$ for a unique $i\in[n{-}1]$, then $\varpi_i(\alpha)\geq 2$. \end{enumerate} \end{proposition} If $N^{w,\alpha}_{u,v(\lambda,k)}\neq 0$ and $i\neq k$ in Proposition~\ref{P:LL_lemmas}(1), then $\varpi_i(\alpha)=1$ as $\varpi_i(\alpha)>1$ contradicts~\eqref{Eq:Grass_bound}, and this implies that $\sg_i(u)=1$ and $\sg_i(w)=0$. Theorem 1.2 in~\cite{LeungLi2012} is their ``quantum equals classical'' result. It states that if $N^{w, \alpha}_{u,v(\lambda,k)}\neq 0$, then there exist $w',u'\in S_n$ such that $N^{w, \alpha}_{u,v(\lambda,k)}=N^{w', {\bzero}}_{u',v(\lambda,k)}= c^{w'}_{u',v(\lambda,k)}$. A consequence of their proof is that $w u^{-1}=w'(u')^{-1}$, but we require more than that. We state and prove the result we will need; this is extracted from the proof of Theorem 1.2 in~\cite{LeungLi2012}. \begin{proposition}\label{P:LLThm1.2} Suppose that $u,w\in S_n$, $\lambda$ is a partition, $\alpha\in\NN^{n-1}$ is nonzero, and $N^{w,\alpha}_{u,v(\lambda,k)}\neq 0$. \begin{enumerate} \item There exists $i\in[n{-}1]$ such that $\sg_i(u)=1$, $\sg_i(w)=0$, and \[ \mbox{either }\ \varpi_i(\alpha) = 1\ \mbox{if }i\neq k \quad\mbox{or}\quad \varpi_i(\alpha) = 2\ \mbox{if }i= k \,. \] \item Let $\mu\neq 0$ be a partition with at most $k$ parts. With $i$ as in (1), we have $N^{w,\alpha}_{u,v(\mu,k)}=N^{ws_i, \alpha-e_i}_{us_i,v(\mu,k)}$. \end{enumerate} \end{proposition} As $N^{w,\alpha}_{u,v(\lambda,k)}\neq 0$, we must have $2|\alpha|+\ell(w)=\ell(u)+|\lambda|$. Since $\alpha\neq 0$, we have $\lambda\neq 0$. Consequently, any partition $\mu$ in Statement (2) with $N^{w,\alpha}_{u,v(\mu,k)}\neq 0$ must satisfy~$|\mu|=|\lambda|$. \begin{proof} We first prove statements (1) and (2) in the case when $\mu=\lambda$. By Proposition~\ref{P:LL_lemmas}(1), there is an $i\in[n{-}1]$ such that $\varpi_i(\alpha)>0$. Suppose that $i$ is not unique with this property. Then we may assume that $i\neq k$, from which it follows that $\sg_i(v(\lambda, k)) = 0$. As $N^{w,\alpha}_{u,v(\lambda,k)}\neq 0$, Equation~\eqref{Eq:Grass_bound} implies that $\sg_i(u)=1=\varpi_i(\alpha)$ and $\sg_i(w)=0$. Thus $\sg_i(ws_i)=1=\sg_i(v(\lambda,k)s_i)$, so that \[ \sg_i(ws_i)\ +\ \varpi_i(\alpha)\ =\ \sg_i(u)\ +\ \sg_i(v(\lambda,k) s_i)\ =\ 2\,. \] By Proposition~\ref{P:LL_Th1.1}(2) with $x=u$, $y=v(\lambda,k) s_i$, and $z=w s_i$, we have that \[ N^{ ws_i,\alpha}_{u, v(\lambda,k) s_i}\ =\ N^{ws_i, \alpha-e_i}_{u s_i, v(\lambda,k)}\ =\ N^{w,\alpha}_{u,v(\lambda,k)}\,. \] (As $s_i^2=1$ and $\sg_i(z)=\sg_i(ws_i)=1$). Now suppose that there is a unique $i$ with $\varpi_i(\alpha)>0$. Then by Proposition~\ref{P:LL_lemmas}(2), we have $\varpi_i(\alpha)\geq 2$. As $N^{w,\alpha}_{u,v(\lambda,k)}\neq 0$, Proposition~\ref{P:LL_Th1.1}(1) implies that \[ \sg_i(w)\ =\ 0\,,\ \ \ \varpi_i(\alpha)\ =\ 2\,,\ \ \mbox{and}\ \ \sg_i(u)\ =\ \sg_i(v(\lambda,k))\ = \ 1\,. \] Since $\sg_i(v(\lambda,k))=1$, we must have that $i=k$, as $v(\lambda,k)$ has a unique descent at~$k$. As $\sg_i(w)=0$, Proposition~\ref{P:LL_Th1.1}(2) with $x=v(\lambda,k)$, $y=u$, and $z=w$ implies that $N^{w,\alpha}_{v(\lambda,k), u}=N^{w s_i, \alpha-e_i}_{v(\lambda,k), u s_i}$. As commutativity implies that $N^{z,\alpha}_{x,y}=N^{z,\alpha}_{y,x}$, we have $N^{ws_i, \alpha-e_i}_{u s_i,v(\lambda,k)}=N^{w,\alpha}_{u,v(\lambda,k)}$. This proves statement (1) and statement (2), in the case when $\mu=\lambda$. As $\mu\neq 0$, we have that for all $i\in[n{-}1]$, $\sg_i(v(\lambda,k))=\sg_i(v(\mu,k))$, as $v(\mu,k)$ has a unique descent at $k$. The arguments we gave for $N^{w,\alpha}_{u,v(\lambda,k)}$ then also hold for $N^{w,\alpha}_{u,v(\mu,k)}$, which completes the proof. \end{proof} \begin{lemma} \label{L:Quantum_is_Classical} Suppose that $u,w\in S_n$, $\lambda$ is a partition, $\alpha\in\NN^{n-1}$, and $C^{q^\alpha w}_{u,v(\lambda,k)}\neq 0$. Then there exist $y,z\in S_n$ with $y\leq_k z$, $\ell(z)-\ell(y)=|\lambda|$, and $zy^{-1}=wu^{-1}$ such that for every partition $\mu$ with $|\mu|=|\lambda|$, we have $q^{-\alpha}C^{q^\alpha w}_{u,v(\mu,k)}=N^{w,\alpha}_{u,v(\mu,k)}=c^{z}_{y,v(\mu,k)}$. \end{lemma} \begin{proof} We use induction on $|\alpha|$. Let $\alpha\in\NN^{n-1}$. When $|\alpha|=0$, $\alpha={\bzero}$ and $C^{q^{\bf 0}w}_{u,v(\mu,k)}=c^w_{u,v(\mu,k)}$. Suppose that $\alpha\neq\bzero$. Let $i\in[n{-}1]$ be the index guaranteed by Proposition~\ref{P:LLThm1.2}(1). By Proposition~\ref{P:LLThm1.2}(2), if $\mu$ is a partition with $|\mu|=|\lambda|$, then $N^{w,\alpha}_{u,v(\mu,k)}=N^{ws_i, \alpha-e_i}_{us_i,v(\mu,k)}$. In particular, $wu^{-1}=ws_i(u s_i)^{-1}$ and $N^{ws_i, \alpha-e_i}_{us_i,v(\lambda,k)}\neq 0$, which implies that $us_i\leq_k^q q^{\alpha-e_i}w s_i$. This completes the proof. \end{proof} \begin{example}\label{Ex:q-minimal} We illustrate these results. In Example~\ref{Ex:MN_example}, the term $q_{5,8}\frakS_{(1,6,7,3,5)u}$ appears in the product $\frakS_{u}\ast p^q_4(x_1,\dotsc,x_5)$. As $78251\p346=(1,6,7,3,5)u$, by Equation~\eqref{Eq:Q-powerSum}, there is a hook partition $\lambda\subseteq R_{5,3}$ with $|\lambda|=4$ such that $N^{78251\pp346, q_{5,8}}_{68235\pp741, v(\lambda,5)}\neq 0$. Since $q_{5,8}=q^\alpha$ for $\alpha=(0,0,0,0,1,1,1)$, we have $\varpi_7(\alpha)=1$, so that by Proposition~\ref{P:LLThm1.2}(2), $N^{78251\pp3\rc{46}, q_{5,\rc{8}}}_{68235\pp7\rc{41}, v(\lambda,5)}= N^{78251\pp3\rc{64}, q_{5,\rc{7}}}_{68235\pp7\rc{14}, v(\lambda,5)}$, as $q^{\alpha-e_7}=q_{5,7}$. We may apply Proposition~\ref{P:LLThm1.2}(2) again as $\varpi_6(\alpha-e_7)=1$ to obtain that $N^{78251\pp\rc{36}4, q_{5,\rc{7}}}_{68235\pp\rc{71}4, v(\lambda,5)}= N^{78251\pp\rc{63}4, q_{5,6}}_{68235\pp\rc{17}4, v(\lambda,5)}$. If $\beta=\alpha-e_7-e_6$, so that $q^\beta=q_{5,6}=q_5$, then $i=5=k$ is the only index with $\varpi_i(\beta)>0$ and we have $\varpi_5(\beta)=2$. By Proposition~\ref{P:LLThm1.2}(2) again, $N^{7825\rc{1\pp6}34, q_5}_{6823\rc{5\pp1}74, v(\lambda,5)}= c^{7825\rc{6\pp1}34}_{6823\rc{1\pp5}74, v(\lambda,5)}$. Figure~\ref{F:qminimal} shows the interval $[68231\p574, 78256\p134]_5$, which has one peakless chain (the vertical one in blue, with labels $6,3,1,3$). \begin{figure}[htb] \centering \begin{picture}(145,122)(-50,-2) \put(-31,0){\includegraphics{figures/qminimal_2.eps}} \put(0,112){\small$78256\p134$} \put(-50, 84){\small$78236\p154$} \put(0, 84){\small$7825{\color{red}\underline{3}}\p164$} \put(-50, 56){\small$78235\p164$} \put(0, 56){\small$7825{\color{red}\underline{1}}\p364$} \put(50,56){\small$68253\p174$} \put(-50, 28){\small$68235\p174$} \put(0, 28){\small$782{\color{red}\underline{3}}1\p564$} \put(50,28){\small$68251\p374$} \put(0, 0){\small${\color{red}\underline{6}}8231\p574$} \end{picture} \qquad\qquad \begin{picture}(175,122)(-60,-2) \put(-41.5,0){\includegraphics{figures/qminimal_1.eps}} \put(-6,112){\small$q^\alpha78251\p346$} \put(-60, 84){\small$78256\p341$} \put(-6, 85){\small$q^\alpha78231\p546$} \put(54,84){\small$q^\alpha68251\p347$} \put(-60, 56){\small$78236\p541$} \put(-6, 56){\small$q^\alpha68231\p547$} \put(60,56){\small$68257\p341$} \put(-60, 28){\small$78235\p641$} \put( 0, 28){\small$68237\p541$} \put( 0, 0){\small$68235\p741$} \end{picture} \caption{Two minimal intervals in the quantum 5-Bruhat order on $S_8[q]$.} \label{F:qminimal} \end{figure} As this has height 3 (as does the minimal permutation $(1,6,7,3,5)$), we see that \newline $c^{7825\rc{6\pp1}34}_{6823\rc{1\pp5}74, v((2,1,1,0,0),5)}=1$, and thus all of the other coefficients considered above are~1. Using~\cite[Prop. 1.1.1]{BS-Bruhat} and solving for the partition $(2,2)$ also show that $c^{78256\pp134}_{68231\pp574, v((2,2,0,0,0),5)}=1$, and thus \begin{eqnarray*} 1\ =\ c^{78256\pp134}_{68231\pp574, v((2,2,0,0,0),5)} &=& N^{78251\pp634, q_{5,6}}_{68235\pp174, v((2,2,0,0,0),5)}\\ &=& N^{78251\pp364, q_{5,7}}_{68235\pp714, v((2,2,0,0,0),5)} \ =\ N^{78251\pp346, q_{5,8}}_{68235\pp741, v((2,2,0,0,0),5)}\,, \end{eqnarray*} by Lemma~\ref{L:Quantum_is_Classical}. For $\lambda\neq(2,1,1,0,0), (2,2,0,0,0)$ with $|\lambda|=4$, these coefficients vanish.\hfill$\diamond$ \end{example} Observe that the intervals may change when applying a reduction as in Proposition~\ref{P:LLThm1.2}(2), even though these reductions do not change $wu^{-1}$. Indeed, the two intervals in Figure~\ref{F:qminimal} demonstrate this. (In~\cite{BS-Bruhat}, it was shown that the classical interval $[u,w]_k$ depends only on $wu^{-1}$.) We show that the coefficient $N^{w,\alpha}_{u,v(\lambda,k)}$ depends only upon $wu^{-1}$. \begin{theorem}\label{Th:quantumIndependence} For a partition $\lambda$, permutations $w,u,\overline{w},\overline{u}$ in $S_n$, exponent vectors $\alpha,\overline{\alpha}\in\NN^{n-1}$ and indices $k,lb$ and $u\lessdot_k^q q_{i,j} (a,b) u$\,,\ \ ($u(i)=a$, $u(j)=b$)} \\[0.4ex] \bzero\,, & \text{otherwise\,,} \end{cases} \end{align} and extend to $S_n[q] \cup \{\bzero\}$ by setting $\defcolor{\qv_{ab} \kaction (q^\alpha u) \vcentcolon= q^\alpha \, (\qv_{ab} \kaction u)}$. Note that if \mbox{${\qv}_{ab} \kaction u\neq\bzero$}, then $u\lessdot_k^q{\qv}_{ab} \kaction u$ is a cover, and all covers in the quantum Bruhat order occur in this way. \begin{remark}\label{Rem:k-action} We make a few remarks and definitions about these operators. \begin{enumerate}[label=(\roman*)] \item The operators $\qv_{ab}$ with $ab$. \item \label{Rem:k-action:zero} A composition $\qv$ of operators \demph{is zero} ($\defcolor{\qv\equiv \bzero}$) if for every $u\in S_n$ and $1\leq kb_i$, then $q^{\alpha_i}=q_{s,t}q^{\alpha_{i-1}}$. Hence, the operator $\defcolor{\qv}\vcentcolon=\qv_{a_rb_r}\dotsb \qv_{a_1b_1}$ is such that $\qv\kaction u=q^\alpha w$. \item \label{Rem:k-action:subword} Finally, suppose that $\qv''\qv\qv'$ is a nonzero operator and $\qv''\qv\qv'\kaction u=q^\alpha w$. If we write $\qv'\kaction u=q^\beta x$ and $\qv\qv'\kaction u=q^\gamma y$, then $\qv\kaction x = q^{\gamma-\beta} y$. Suppose that $\qu$ is $(x,k)$-equivalent to $\qv$, so that $\qu\kaction x = q^{\gamma-\beta} y$. Then $\qv''\qv\qv'$ is $(u,k)$-equivalent to $\qv''\qu\qv'$. \end{enumerate} Items~\ref{Rem:k-action:zero_compose} and~\ref{Rem:k-action:subword} show that equivalence of operators may be induced by subwords.\hfill$\diamond$ \end{remark} A consequence of Remark~\ref{Rem:k-action} is the following generalization of Proposition~\ref{Prop:monoid}\eqref{Prop_3}. \begin{proposition}\label{Prop:chains_and_operators} Suppose that $u\leq_k^q q^\alpha w$. Then there is a bijection between saturated chains in the interval $[u,q^\alpha w]_k^q$ and nonzero operators $\qv$ such that $\qv\kaction u=q^\alpha w$, and this set of operators forms a single $(u,k)$-equivalence class of nonzero operators. \end{proposition} \subsection{Flattening and \texorpdfstring{$(u,k)$}{(u,k)}-equivalence} \label{SS:Shape-equivalence} Equivalence among classical operators,~\eqref{Eq:monoid-relations} and Proposition~\ref{Prop:monoid}, depends only upon the relative order of the indices, and not their actual values. We establish a version for quantum operators. We begin with some definitions. Let $a=(a_1,\dotsc,a_t)$ be a sequence of integers and set $m\vcentcolon=\#\{a_1,\dotsc,a_t\}$, the number of distinct integers in this sequence. The \demph{flattening} of $a$ is the sequence $(c_1,\dotsc,c_t)$ where each $c_i\in[m]$ and $c_i>c_j$ if and only if $a_i>a_j$. For example, the flattening of $(3,6,1,6,8,3,1)$ is $(2,3,1,3,4,2,1)$. Sequences are \demph{shape-equivalent} if they have the same flattening. The flattening of an operator $\qv_{a_r b_r}\dotsb\qv_{a_1 b_1}$ is $\qv_{c_r d_r}\dotsb\qv_{c_1 d_1}$, where $(c_r,d_r,\dotsc,c_1,d_1)$ is the flattening of $(a_r,b_r,\dotsc,a_1,b_1)$. Operators $\qv$ and $\qv'$ are \demph{shape-equivalent} if they have the same flattening. This extends the notion of shape-equivalence of permutations $\zeta$ from Section~\ref{SS:GBO}. The \demph{support} of an operator $\qv=\qv_{a_r b_r}\dotsb\qv_{a_1 b_1}$ is $\supp(\qv)\vcentcolon=\{a_r,b_r,\dotsc,a_1,b_1\}$. The operator $\qv$ is \demph{minimal} if the factorization of $\zeta=\zeta(\qv)=(a_r,b_r)\dotsb(a_1,b_1)$ into transpositions has minimal length in that $r=\#\supp(\zeta)-s(\zeta)$. As $r$ is the minimal possible number of transpositions whose product is $\zeta$, we have that $\supp(\zeta(\qv))=\{a_r,b_r,\dotsc,a_1,b_1\}=\supp(\qv)$. Furthermore, if $\qv\kaction u=q^\alpha w$, then as $\zeta(\qv)=wu^{-1}$, the interval $[u,q^\alpha w]_k^q$ is minimal in the sense of Section~\ref{sec:Qminim}. Later, in the proof of Theorem~\ref{Th:nonZero} in Section~\ref{sec:final}, we will show that the permutation $\zeta(\qv)$ is a minimal permutation in the sense of Section~\ref{minimal-permutations}. Shape-equivalence preserves equivalence to $\bzero$ and for minimal operators, $(u,k)$-equivalence. \begin{theorem}\label{Th:shape-equivalence} Let $\qv$ be an operator with flattening $\qv'$. Then $\qv\equiv\bzero$ if and only if $\qv'\equiv\bzero$. Suppose that $\qv$ is nonzero and minimal, and that $\qu$ is an operator that is $(u,k)$-equivalent to $\qv$ for some $u\in S_n$ and $ku^{-1}(a)$ for all $a\in\supp(\qv)$. Then for any $s\in[n{+}1]$, $\iota_s(\qv)\kactionop_{\iota_r(k)} \varepsilon_{r,s}(u) = q^{\varepsilon_{r,0}(\alpha)}\varepsilon_{r,s}(w)$. \end{enumerate} \end{lemma} \begin{proof} Both statements follow (by composition) from the case when $\qv=\qv_{ab}$ is a single operator. As $u\lessdot_k q^\alpha w=\qv_{ab}\kaction u$, we have $w=(a,b)u=u(i,j)$, where $i=u^{-1}(a)\leq k < u^{-1}(b)=j$ and either $q^\alpha=1$ when $ab$. The statements follow from the definitions of $\tau_s$, $\iota_s$, $/r$, $\varepsilon_{r,s}$, and the characterizations of covers in Propositions~\ref{nothing-in-between-is-in-between} and~\ref{prop:quantum-k-bruhat-covers}, in a case-by-case analysis depending upon the relative positions of $s$ with $a,b$ and $r$ with $i,j$. While we omit that analysis, we illustrate three cases in Example~\ref{Ex:three_cases} below. Note that when $au^{-1}(a)$ for all $a\in\supp(\qv)\cup\supp(\qv')$, we have that $\iota_s(\qv)$ and $\iota_s(\qv')$ are $(\varepsilon_{r,s}(u), \iota_r(k))$-equivalent. \end{enumerate} \end{enumerate} \end{corollary} \begin{proof} The third statement holds by Lemma~\ref{L:relative-labels}. This also proves the (contrapositive of) the implication $\Leftarrow$ in the first two statements. As in (1), $\qv=\iota_s(\tau_s(\qv))$ and in (2), $s\not\in\supp(\iota_s(\qv))$ and $\qv=\tau_s(\iota_s(\qv))$, the other directions also hold. \end{proof} \begin{proof}[Proof of Theorem~\ref{Th:shape-equivalence}] As flattening is induced by applying truncation operators, the first statement of Theorem~\ref{Th:shape-equivalence} follows from Corollary~\ref{C:single_equivalences}~\ref{C:SE_1}. Suppose that $\qv$ is nonzero and minimal. Let $\qu$ be an operator that is $(u,k)$-equivalent to $\qv$. Then there exist $w\in S_n$ and $\alpha\in\NN^{n-1}$ such that $\qv\kaction u=\qu\kaction u=q^\alpha w$. As $\zeta(\qv)=wu^{-1}$, $\zeta(\qu)=\zeta(\qv)$. As $(u,k)$-equivalence is ranked, both $\qv$ and $\qu$ involve the same number of elementary operators $\qv_{ab}$. This implies that $\qu$ is minimal and that $\supp(\qv)=\supp(\qu)$. Consequently, any sequence of truncation operators that flattens $\qv$ also flattens $\qu$. The existence of $x$ and $l$ in the final part of Theorem~\ref{Th:shape-equivalence} follows by applying Corollary~\ref{C:single_equivalences}~\ref{C:SE_3}~\ref{C:SE_3_i} along this same sequence of truncation operators. \end{proof} \subsection{Diagrammatic notation} \label{SS:diagrammatic-notation} We introduce a \defcolor{diagrammatic notation} for compositions of operators $\qv_{ab}$, which will facilitate our study of relations among them. Figure~\ref{fig:classical-relations} depicts the relations among classical operators in~\eqref{Eq:monoid-relations} using this notation. Depict a classical operator $\qv_{ab}$ with $ab$ by a dotted red line segment $[b,a]$, drawn in a window with the positions of $1,\dotsc,n$ indicated by vertical dashed lines as follows, \newcommand{\labelhack}{\begin{picture}(62,2) \put(0 ,-4){{\small 1}}\put(11.5,-4){{\small 2}} \put(23,-4){{\small 3}}\put(34.5,-4){{\small 4}} \put(46,-4){{\small 5}}\put(57.5,-4){{\small 6}}\end{picture}} \[ \begin{array}{c@{\qquad}c@{\qquad}c} \labelhack& \labelhack& \labelhack \\ \valuediagram[padding=1, xmin=1, xmax=6]{{2,4}} & \valuediagram[padding=1, xmin=1, xmax=6]{{1,5}} & \valuediagram[padding=1, xmin=1, xmax=6]{{6,3}} \\[1ex] \qv_{24} & \qv_{15} & \qv_{63} \end{array}\ . \] A composition of operators is depicted by stacking intervals. For example, \newcommand{\llabelhack}{\begin{picture}(85,2) \put(0 ,-4){{\small 1}}\put(11.5,-4){{\small 2}} \put(23,-4){{\small 3}}\put(34.5,-4){{\small 4}} \put(46,-4){{\small 5}}\put(57.5,-4){{\small 6}} \put(69,-4){{\small 7}}\put(80.5,-4){{\small 8}}\end{picture}} \[ \begin{array}{c@{\qquad}c} \raisebox{-1pt}{\llabelhack} & \raisebox{2pt}{\llabelhack} \\ \valuediagram[height=2, padding=1]{{1,2},{4,2},{6,8}} & \valuediagram[padding=1]{{1,4},{8,4},{5,7},{4,2}} \\[1ex] \qv_{68}\qv_{42}\qv_{12} & \qv_{42}\qv_{57}\qv_{84}\qv_{14} \end{array}\ . \] Since the operators act on the left, a composition acts by the rightmost operator first, which corresponds to reading the associated diagram from the bottom to the top. \begin{remark}\label{Rem:relative-labels} We may omit labeling the vertical dashed lines and dashed lines not in the support. For instance, the diagram $\valuediagram[height=.9, padding=.5]{{2,3},{3,1}}$ represents any composition of the form ${\qv}_{ca} {\qv}_{bc} $ with $aj$, set $q_{i,j}=q_{j,i}^{-1}$. For $u,w\in S_n$, define $\defcolor{q^{\ncycle(u,w)}}\vcentcolon=q_{w^{-1}(n),u^{-1}(n)}$, which keeps track of how the monomial $q^\alpha$ in elements of $S_n[q]$ is affected by the cyclic shift. Note that $q^{\ncycle(u,w)}=q_{1,u^{-1}(n)}\cdot q_{w^{-1}(n),1}$, which shows that it is multiplicative in that $q^{\ncycle(u,w)}=q^{\ncycle(u,v)}\cdot q^{\ncycle(v,w)}$, for any $u,v,w\in S_n$. Observe that for $u\in S_n$ and $i\ncycle u(j)=\ncycle(n)=1$ and if $i\ncycle u(l)>1=\ncycle u(j)$, which implies that $\ncycle u \lessdot^q_k q_{i,j} \ncycle w$. By~\eqref{Eq:qOcycle}, $q^{\ncycle(u,w)}=q_{i,j}$ and we again have that $\ncycle u \lessdot^q_k q^{\ncycle(u,w)} \ncycle w$. Thus when $q^\alpha=1$, (1) implies (2). Similar arguments show that (1) implies (2$'$), which is the statement~(2), but where we use $\ncycle^{-1}$ in place of $\ncycle$ and replace $q^{\ncycle(u,w)}$ by $q^{\ncycle(\ncycle^{-1}(w),\ncycle^{-1}(u))}$. Suppose now that $q^\alpha\neq 1$, so that $q^\alpha=q_{i,j}$ and $u\lessdot^q_k q_{i,j} w$. Then $a=u(i)>b=u(j)$ and if $iu(l)>b$. Multiplying by $w_0$ on the right shows that \[ w w_0\ \lessdot^q_{n-k}\ q_{n+1-j,n+1-i} w w_0 (n{+}1-j,n{+}1-i)\ =\ w_0(q_{i,j})\, u w_0\,, \] and further multiplying by $w_0$ on the left shows that \[ w_0uw_0\ \lessdot^q_{n-k}\ q_{n+1-j,n+1-i} w_0 u w_0 (n{+}1-j,n{+}1-i)\ =\ w_0(q_{i,j})\, w_0 w w_0\,. \] Thus (1) implies both (3) and (4) in this case. Let us now consider (2). If $a\neq n$, then as before, $\ncycle u \lessdot_k^q q_{i,j}\ncycle w=q^{\ncycle(u,w)} q_{i,j}\ncycle w$, as $q^{\ncycle(u,w)}=1$. If $a=n$, then $q^{\ncycle(u,w)}=q_{i,j}^{-1}$ by~\eqref{Eq:qOcycle}. If $iu(l)>b=u(j)$, and we have $n\geq u(l)+1 = \ncycle u(l)>\ncycle u(j)=b+1$. Thus $\ncycle u \lessdot_k \ncycle u(i,j)=\ncycle w= q^{\ncycle(u,w)} q_{i,j} \ncycle w$. Thus (1) implies (2). Similar arguments show that (1) implies (2$'$), which is the statement (2), but where we use $\ncycle^{-1}$ in place of $\ncycle$ and $q^{\ncycle(\ncycle^{-1}(w),\ncycle^{-1}(u))}$ in place of $q^{\ncycle(u,w)}$. These arguments show that if $u\lessdot^q_k q^\alpha u(i,j)=q^\alpha w$, then (1) implies each of (2), (2$'$), (3), and (4). The implications $(3)\Rightarrow(1)$ and $(4)\Rightarrow(1)$ follow as $u\mapsto u w_0$ and $u\mapsto w_0 u w_0$ are involutions. Similarly, $\ncycle^{-1}\ncycle u=u$ and $q^{\ncycle(u,w)}q^{\ncycle(w,u)}=1$, thus $(1)\Rightarrow(2')$ for $\ncycle u \lessdot^q_k q^{\ncycle(u,w)} q^\alpha\ncycle w$ is $(2)\Rightarrow(1)$. This completes the proof that the four statements are equivalent. \end{proof} We combine the equivalences of Corollary~\ref{C:symmetries-q-ops} with the interpretation of equivalent operators corresponding to different chains in intervals of Remark~\ref{Rem:k-action}~\ref{Rem:k-action:chains} and~\ref{Rem:k-action:uk_equiv}. \begin{lemma} \label{lemma:actions} The following statements are equivalent: \begin{enumerate}[label=(\alph*)] \item \label{l:actions:a} $\qv$ and $\qv'$ are $(u,k)$-equivalent with $\qv \kaction u = \qv' \kaction u = q^\alpha w$. \item \label{l:actions:b} $\ncycle \qv$ and $\ncycle \qv'$ are $(\ncycle u, k)$-equivalent, with $\ncycle\qv\kaction \ncycle u=\ncycle\qv'\kaction \ncycle u = q^{\ncycle(u,w)} q^\alpha \ncycle w$. \item \label{l:actions:c} $w_0 \qv$ and $w_0\qv'$ are $(w_0uw_0, n{-}k)$-equivalent with $w_0\qv\kactionop_{n-k} w_0uw_0=w_0\qv'\kactionop_{n-k} w_0 uw_0 = q^{w_0(\alpha)} w_0 w w_0$. \item \label{l:actions:d} $\rho \qv$ and $\rho \qv'$ are $(ww_0, n{-}k)$-equivalent with $\rho\qv\kactionop_{n-k} w w_0=\rho\qv'\kactionop_{n-k} ww_0 = q^{w_0(\alpha)} u w_0$. \end{enumerate} \end{lemma} Before proving the lemma, we observe that a composition being nonzero is preserved by $\ncycle$, $w_0$, and $\rho$, and the same for being zero. \begin{corollary}\label{C:symmetries_bzero} A composition $\qv$ is equivalent to zero if and only if one (and hence all) of $\ncycle\qv$, $w_0\qv$, and $\rho\qv$ is equivalent to zero. \end{corollary} \begin{proof}[Proof of Lemma~\ref{lemma:actions}] Let $u,w\in S_n$, $\alpha\in\NN^{n-1}$, and $\qv,\qv'$ be compositions of left operators such that $u<_k^q \qv\kaction u=\qv'\kaction u = q^\alpha w$. By Remark~\ref{Rem:k-action}\ref{Rem:k-action:chains}, $\qv$ and $\qv'$ each correspond to a chain in $[u,q^\alpha w]_k^q$. We apply the equivalences of Corollary~\ref{C:symmetries-q-ops} to each step of those chains. For~\ref{l:actions:c}, we have $w_0 uw_0 <_{n-k} w_0\qv\kactionop_{n-k} w_0uw_0 = w_0\qv'\kactionop_{n-k} w_0uw_0 = q^{w_0(\alpha)}w_0 ww_0$. For~\ref{l:actions:d}, note that the chain is reversed and this shows that $w w_0 <_{n-k} \rho\qv\kactionop_{n-k} w w_0 = \rho\qv'\kactionop_{n-k} w w_0 = q^{w_0(\alpha)}u w_0$. The argument for~\ref{l:actions:b} is slightly more involved as the action of $\ncycle$ on monomials depends upon the cover. Let $u<_k^q \qv u = q^{\alpha} w$ correspond to the saturated chain in $[u,q^\alpha w]_k^q$, \[ u\ =\ q^{\alpha_0}w_0\ \lessdot_k^q\ q^{\alpha_1}w_1\ \lessdot_k^q\ q^{\alpha_2}w_2 \ \lessdot_k^q\ \dotsb\ \lessdot_k^q\ q^{\alpha_r}w_r=q^\alpha w\,. \] By Lemma~\ref{L:symmetry_qkBO}(2), applying $\ncycle$ to $q^{\alpha_i}w_i\lessdot_k^q q^{\alpha_{i+1}}w_{i+1}$ gives $$q^{\alpha_i}\ncycle w_i\lessdot_k^q q^{\ncycle(w_i,w_{i+1})}q^{\alpha_{i+1}}\ncycle w_{i+1}.$$ If we set $\defcolor{q^{\beta_i}}\vcentcolon=q^{\ncycle(u,w_i)}q^{\alpha_i}$, then, as $q^{\ncycle(u,w_{i+1})}=q^{\ncycle(u,w_i)}q^{\ncycle(w_i,w_{i+1})}$, we obtain the saturated chain \[ \ncycle u\ =\ q^{\beta_0}\ncycle w_0\ \lessdot_k^q\ q^{\beta_1}\ncycle w_1\ \lessdot_k^q\ q^{\beta_2}\ncycle w_2 \ \lessdot_k^q\ \dotsb\ \lessdot_k^q\ q^{\beta_r}\ncycle w_r=q^{\ncycle(u,w)}q^\alpha \ncycle w\, \] in the interval $[\ncycle u,q^{\ncycle(u,w)} q^\alpha \ncycle w]_k^q$, which completes the proof. \end{proof} We have the following corollary. Here $\textit{op}$ applied to a poset gives the opposite poset, reversing all inequalities. \begin{corollary}\label{C:equivalences} Let $u,w\in S_n$ and $\alpha\in\NN^{n-1}$ be such that $u <_k^q q^\alpha w$. Then we have the following isomorphisms of posets, \begin{align*} [u,q^\alpha w]_k^q &\ \simeq\ [\ncycle u, q^{\ncycle(u,w)} q^\alpha \ncycle w]_k^q \ \simeq\ [w_0 uw_0,q^{w_0(\alpha)} w_0 w w_0]_{n-k}^q\\ &\ \simeq\ \textit{op}\left([ww_0,q^{w_0(\alpha)} u w_0]_{n-k}^q\right)\,. \end{align*} \end{corollary} \begin{example} Figure~\ref{F:three_ops} illustrates Corollary~\ref{C:equivalences} on the rightmost interval of Figure~\ref{F:more_minimal}. \begin{figure}[htb] \centering \begin{picture}(140,110)(-60,0) \put(-35,0){\includegraphics{figures/q-int3.eps}} \put(-13,100){\small$q_{1,5}q_3132\p45$} \put(-10, 75){\small$q_{1,4}135\p42$} \put(42,75){\small$q_3532\p41$} \put(-60,50){\small$q_{1,4}125\p43$} \put(-10, 50){\small$q_{1,4}134\p52$} \put(42,50){\small$q_3531\p42$} \put(-60,25){\small$q_{1,4}124\p53$} \put(0, 25){\small$534\p12$} \put(42,25){\small$q_3521\p43$} \put(0, 0){\small$524\p13$} \end{picture} \quad \begin{picture}(115,110)(-35,0) \put(-25,0){\includegraphics{figures/q-int2.eps}} \put(-10,100){\small$q_{1,3}23\p541$} \put(0, 75){\small$53\p241$} \put(35,75){\small$q_{1,3}13\p542$} \put(-35,50){\small$43\p251$} \put(0, 50){\small$52\p341$} \put(45,50){\small$53\p142$} \put(-35,25){\small$42\p351$} \put(0, 25){\small$51\p342$} \put(45,25){\small$43\p152$} \put(0, 0){\small$41\p352$} \end{picture} \quad \begin{picture}(145,110)(-50,0) \put(-25,0){\includegraphics{figures/q-int4.eps}} \put( 0,100){\small$q_{1,3}25\p314$} \put(-50,75){\small$q_{1,3}24\p315$} \put( 0, 75){\small$q_{1,3}15\p324$} \put(50,75){\small$q_{1,3}23\p514$} \put(-50,50){\small$q_{1,3}23\p415$} \put( 0, 50){\small$q_{1,3}14\p325$} \put(50,50){\small$q_{1,3}13\p524$} \put( 0, 25){\small$q_{1,3}13\p425$} \put(60,25){\small$53\p124$} \put(10, 0){\small$43\p125$} \end{picture} \caption{Actions of $\ncycle$, $\omega_0$, and $\rho$ on the rightmost interval of Figure~\ref{F:more_minimal}.} \label{F:three_ops} \end{figure} \begin{figure}[htb] \centering $\begin{array}{rccccccccc} &\valuediagram[padding=.75]{{4,1},{1,2},{3,4},{4,5}}&\ &\valuediagram[padding=1]{{4,1},{3,4},{1,2},{4,5}}&\ & \valuediagram[padding=.75]{{4,1},{3,4},{4,5},{1,2}}&\ &\valuediagram[padding=1]{{4,5},{5,1},{3,5},{1,2}}&\ & \valuediagram[padding=.75]{{4,5},{5,1},{1,2},{3,5}}\\ \\ \raisebox{5pt}{$\ncycle$} &\valuediagram[padding=.75]{{5,2},{2,3},{4,5},{5,1}}&\ &\valuediagram[padding=1]{{5,2},{4,5},{2,3},{5,1}}&\ & \valuediagram[padding=.75]{{5,2},{4,5},{5,1},{2,3}}&\ &\valuediagram[padding=1]{{5,1},{1,2},{4,1},{2,3}}&\ & \valuediagram[padding=.75]{{5,1},{1,2},{2,3},{4,1}}\\ \\ \raisebox{5pt}{$\omega_0$} &\valuediagram[padding=.75]{{5,2},{4,5},{2,3},{1,2}}&\ &\valuediagram[padding=1]{{5,2},{2,3},{4,5},{1,2}}&\ & \valuediagram[padding=.75]{{5,2},{2,3},{1,2},{4,5}}&\ &\valuediagram[padding=1]{{1,2},{5,1},{1,3},{4,5}}&\ & \valuediagram[padding=.75]{{1,2},{5,1},{4,5},{1,3}}\\ \\ \raisebox{5pt}{$\rho$} &\valuediagram[padding=.75]{{4,5},{3,4},{1,2},{4,1}}&\ &\valuediagram[padding=1]{{4,5},{1,2},{3,4},{4,1}}&\ & \valuediagram[padding=.75]{{1,2},{4,5},{3,4},{4,1}}&\ &\valuediagram[padding=1]{{1,2},{3,5},{5,1},{4,5}}&\ & \valuediagram[padding=.75]{{3,5},{1,2},{5,1},{4,5}} \end{array}$ \caption{Actions of $\ncycle$, $\omega_0$, and $\rho$ on chains from the rightmost interval of Figure~\ref{F:more_minimal}.} \label{F:symmetry-chains} \end{figure} These operators act on each chain in the respective orders. Each row in Figure~\ref{F:symmetry-chains} shows the diagrams for all five chains in one of the four intervals, with the first row from the rightmost interval of Figure~\ref{F:more_minimal} and subsequent rows for the indicated interval in Figure~\ref{F:three_ops}.\hfill$\diamond$ \end{example} As mentioned in Section~\ref{quantum-equals-classical}, we are often able to reduce to the classical (no quantum operators) case, which is the origin of our interest in these operators $\ncycle$, $\omega_0$ and $\rho$. \subsection{Degree two relations} \label{S:degreeTwo} Given a composition $\qv$ involving quantum operators, in Section~\ref{SS:monoid} we developed the notions of equivalence to zero ($\qv\equiv\bzero$), of $\qv$ being nonzero ($\qv\not\equiv\bzero$), and the notion of $(u,k)$-equivalence for nonzero compositions $\qv$. We do not however have a notion of equivalence of operators similar to the stronger one of~\cite{BS-Monoid} for classical operators. By Theorem~\ref{Th:shape-equivalence}, a composition $\qv$ being equivalent to $\bzero$ only depends upon its shape-equivalence class. Furthermore, if $\qv$ is minimal and $\qv\kaction u=q^\alpha w$, then $(u,k)$-equivalence to $\qv$ only depends on shape-equivalence (and not specifically on $u$ or $k$). Consequently, we will simply write $\equiv$ for equivalence to $\bzero$ and $(u,k)$-equivalence of minimal compositions. A composition $\qv_{ab}\qv_{cd}$ is minimal when $\{a,b\}\neq\{c,d\}$. We identify all relations among minimal compositions that preserve equivalence. These relations are depicted in Figures~\ref{fig:crossing-operators}, ~\ref{fig:degree-2-nonzero-relations}, ~\ref{fig:more-degree-2-zero-relations}, and ~\ref{fig:touching-orbit}. This uses the notion of crossing and noncrossing sets from Section~\ref{sec:classic-mn-rule}. \begin{lemma}\label{Lem:Rel} The following describe all relations among minimal compositions of two left operators; those not of the form $\qv_{ab} \qv_{ba}$ or $\qv_{ab} \qv_{ab}$. \begin{enumerate} \item If $\{a,b\}\cap\{c,d\}=\emptyset$, then the operators commute, ${\qv}_{ab}{\qv}_{cd} \equiv {\qv}_{cd}{\qv}_{ab}$. \begin{enumerate}[itemsep=1ex, topsep=1ex, label=(\roman*)] \item \label{Rel:1:i} If $\{a,b\}$ and $\{c,d\}$ are crossing, then $\qv_{ab}\qv_{cd} \equiv \bzero$. \item \label{Rel:1:ii} If $ab>c>d$, then $\qv_{cd}\qv_{ab}$ and $\qv_{ab}\qv_{cd}$ are both zero, \[ \valuediagram[scale=1.1]{{1,4},{3,2}}\equiv \valuediagram[scale=1.1]{{2,1},{4,3}}\equiv \valuediagram[scale=1.1]{{3,2},{1,4}}\equiv \valuediagram[scale=1.1]{{4,3},{2,1}}\equiv \bzero\,. \] \item \label{Rel:1:iii} In all other cases when $\{a,b\}$ and $\{c,d\}$ are noncrossing, $\qv_{ab}\qv_{cd}\equiv\qv_{cd}\qv_{ab}$, and both are nonzero. \end{enumerate} \item If $\#(\{a,b\}\cap\{c,d\})=1$, then the operators $\qv_{ab}$ and $\qv_{cd}$ do not commute. \begin{enumerate}[itemsep=1ex, topsep=1ex, label=(\roman*)] \item \label{Rel:2:i} For $ab$ follows from this by cyclic shift (applying $\ncycle$) and Corollary~\ref{C:symmetries_bzero}. The composition $\qv_{ab}\qv_{ba}$ is nonzero and $\qv_{ab}\qv_{ba}\not\equiv \qv_{ba}\qv_{ab}$. If $ab$, then $\qv_{ab}\qv_{ba}\kaction u$ equals $q_k u$ if $u(k)=a$ and $u(k{+}1)=b$ and is $\bzero$ otherwise.\hfill$\diamond$ \end{remark} \begin{proof}[Proof of Lemma~\ref{Lem:Rel}] Consider compositions $\qv_{ab}\qv_{cd}$ with $\{a,b\}\cap\{c,d\}=\emptyset$. Then $\{a,b\}$ and $\{c,d\}$ form an ordered partition of the four-element set $\{a,b,c,d\}$. There are $6=\binom{4}{2}$ such. Each operator may be either quantum or classical, there are 24 choices in all. For (1)\ref{Rel:1:i}, the eight compositions $\qv_{ab}\qv_{cd}$ with $\{a,b\}$ and $\{c,d\}$ crossing are shown in Figure~\ref{fig:crossing-operators}. \begin{figure}[htpb] \centering \begin{equation*} \begin{array}{l@{\hskip1.25em}l@{\hskip1.25em}l@{\hskip1.25em}l} \valuediagram[padding=.75]{{1,3},{2,4}} & \valuediagram[padding=.75]{{2,4},{3,1}} & \valuediagram[padding=.75]{{3,1},{4,2}} & \valuediagram[padding=.75]{{4,2},{1,3}} \\ \\ \valuediagram[padding=.75]{{2,4},{1,3}} & \valuediagram[padding=.75]{{3,1},{2,4}} & \valuediagram[padding=.75]{{4,2},{3,1}} & \valuediagram[padding=.75]{{1,3},{4,2}} \end{array} \end{equation*} \caption{Crossing compositions of (1)(i). They all are equivalent to $\bzero$.} \label{fig:crossing-operators} \end{figure} They form a single orbit under the joint action of $\ncycle$ and $\rho$. Both classical compositions (in the first column) are zero by~\eqref{Eq:monoid-relations}({\it ii}). Corollary~\ref{C:symmetries_bzero} implies the rest are zero. The four compositions in (1)\ref{Rel:1:ii} form a single orbit under $\ncycle$ by Lemma~\ref{lemma:actions}, and it suffices to show that one is equivalent to $\bzero$. As in Section~\ref{cohomology-ring-of-the-flag-manifold}, write permutations in one-line notation, placing ``\,$\p$\,'' just after the $k$th position. Thus $52\pb 6134\in S_6$ has $k=2$, and $(\dotsc a\dotsc \pb b \dotsc)$ is a permutation $w$ with $w^{-1}(a)\leq k$ and $w(k{+}1)=b$. Let $a\dotsb>a_r$}. A \demph{column} is a composition that can be cyclically shifted to a classical column as in Figure~\ref{fig:column-vs-classical-column}. A connected column is an instance of a path. Note that if $\qv$ is a column, then $\rho(\qv)$ is a row. \begin{figure}[htpb] \centering \begin{equation*} \begin{array}{c} \valuediagram[ critical windows={(6,7)}]{{2,3},{1,2},{9,1},{8,9},{5,6},{4,5},{7,4}} \end{array} \xrightarrow{~~\ncycle^3~} \begin{array}{c} \valuediagram{{5,6},{4,5},{3,4},{2,3},{8,9},{7,8},{1,7}} \end{array} \equiv \begin{array}{c} \valuediagram{{8,9},{7,8},{5,6},{4,5},{3,4},{2,3},{1,7}} \end{array} \end{equation*} \caption{The operator on the right is a \emph{classical column} as it is the product of two noncrossing \emph{connected classical columns}. The operator on the left is a \emph{column} as it can be cyclically shifted to the classical column.} \label{fig:column-vs-classical-column} \end{figure} \begin{theorem} \label{thm:quantum_path} Every path is either a row or a column and a path contains at most one quantum operator. Paths can be cyclically shifted to a classical row or to a classical column. The only path that can be shifted to both consists of a single operator. \end{theorem} \begin{proof} We split the proof into four parts. Let $\qv$ be a path, which is nonzero.\smallskip \noindent\textit{(1) Paths consisting only of classical operators.} Suppose the path $\qv = \qv_{a_r b_r}\dotsb\qv_{a_1 b_1}$ is a composition of classical operators (for all $i$, $a_id$. Set $a=d$ and $b=c$ so that $\qv_{cd}=\qv_{ba}$ with $a