%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{67}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{fancyhdr}
\usepackage{enumitem} % Better Lists
\newlist{condenum}{enumerate}{1}
\usepackage{xcolor} % Better colors
\usepackage{graphicx} % Better layout control
\usepackage{hyperref} % Better \refs and \cites
\allowdisplaybreaks
\usepackage{mathtools}
\usepackage{mathabx}
\usepackage{bbm}
\usepackage{shuffle}
\usepackage[mathscr]{eucal}
\usepackage{stmaryrd} % Includes \mapsfrom
\usepackage{makecell}
\usepackage{tikz}
\usetikzlibrary{patterns, arrows, matrix, positioning, calc}
\usepackage{tikz-cd}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%     Fancy Comments    %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}
\usepackage[colorinlistoftodos]{todonotes}
\newcommand{\lucas}[1]{\todo[size=\tiny,color=green!5!red!30!yellow!80]{#1 \\  --- Lucas}}
\newcommand{\Lucas}[1]{\todo[size=\tiny,inline,color=green!5!red!30!yellow!80]{#1 \\ \hfill --- Lucas}}
\newcommand{\nantel}[1]{\todo[size=\tiny,color=blue!30]{#1 \\ \hfill --- Nantel}}
\newcommand{\Nantel}[1]{\todo[size=\tiny,inline,color=blue!30]{#1 \\ \hfill --- Nantel}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%     Macros - General     %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%
% Theorem Environments
%%%%%%%%%%%
\newtheorem{thm}[equation]{Theorem}
\newtheorem{conj}[equation]{Conjecture}
\newtheorem{openproblem}[equation]{Open Problem}
\newtheorem{question}[equation]{Question}
\newtheorem{prop}[equation]{Proposition}
\newtheorem{lem}[equation]{Lemma}
\newtheorem{cor}[equation]{Corollary}
\theoremstyle{definition}
\newtheorem{ex}[equation]{Example}
\newtheorem{definition}[equation]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[equation]{Remark}
\newtheorem{rems}[equation]{Remarks}
%
\numberwithin{equation}{section}
%
%%%%%%%%%%%
\newenvironment{introthm}[1]{
  \renewcommand\theequation{#1}
  \thm
}{\endthm}
%%%%%%%%%%%
\newenvironment{introcor}[1]{
  \renewcommand\theequation{#1}
  \cor
}{\endcor}
%%%%%%%%%%%



%%%%%%%%%%%
% Letter Macros
%%%%%%%%%%%
% Blackboard Letters
\newcommand{\FF}{\mathbb{F}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\KK}{\mathbb{K}}
% Calligraphic - Triple Capital Letters
\def\mydefb#1{\expandafter\def\csname #1#1#1\endcsname{\mathcal{#1}}}
\def\mydefallb#1{\ifx#1\mydefallb\else\mydefb#1\expandafter\mydefallb\fi}
\mydefallb ABCDEFGHIJKLMNOPQRSTUVWXYZ\mydefallb

%%%%%%%%%%%
% Nicening Macros
%%%%%%%%%%%
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\spanning}{\operatorname{-span}}
\renewcommand{\hom}{\operatorname{Hom}}
\renewcommand{\setminus}{-}

\usepackage{lipsum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%     Macros - Paper     %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\TL}{\mathsf{TL}}

\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\QSym}{\mathrm{QSym}}
\newcommand{\QSV}{\mathrm{QSV}}
\newcommand{\NCP}{\mathrm{NCP}}

\newcommand{\EP}{E_{pos}}
\newcommand{\EV}{E_{val}}

%%%%%Tikz Paper Macros
%% Black edge
\newcommand{\edge}[2]{\tikz[scale = 0.75, baseline = -0.2cm]{
\draw (0.1, 0) node[inner sep = 0ex] (a) {};
\node[left, xshift = 0.1cm, yshift = -0.1cm] at (a) {$\scriptstyle #1$};
\draw (0.9, 0)  node[inner sep = 0ex] (b) {};
\node[right, xshift = -0.1cm, yshift = -0.1cm] at (b) {$\scriptstyle #2$};
\draw[thick] (a) to[out = 35, in = 145] (b);}}


%% define your title in the usual way
\title[Excedance quotients, Quasisymmetric Varieties, and $\mathsf{TL}_{n}(2)$]{Excedance quotients, Quasisymmetric Varieties, and Temperley--Lieb algebras}


%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Nantel Bergeron\thanks{\href{mailto:bergeron@yorku.ca}{bergeron@yorku.ca}}\addressmark{1} \and Lucas Gagnon\thanks{\href{mailto:lgagnon@yorku.ca}{lgagnon@yorku.ca}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Dept. of Math. and Stat., York  University,  Toronto, Ontario M3J 1P3,  CANADA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Let $R_n=\mathbb{Q}[x_1,x_2,\ldots,x_n]$ be the ring of polynomials in $n$ variables and consider the ideal $\langle \mathrm{QSym}_{n}^{+}\rangle\subseteq R_n$ generated by quasisymmetric polynomials without constant term. 
It was shown by Aval--Bergeron--Bergeron that $\dim\big(R_n\big/\langle \mathrm{QSym}_{n}^{+} \rangle\big)=C_n$ the $n$th Catalan number. 
We explain here this phenomenon by defining a set of permutations $\mathrm{QSV}_{n}$ with the following properties: first, $\mathrm{QSV}_{n}$ is a basis of the Temperley--Lieb algebra $\mathsf{TL}_{n}(2)$, and second, when considering $\mathrm{QSV}_{n}$ as a collection of points in $\mathbb{Q}^{n}$, the top-degree homogeneous component of the vanishing ideal $\mathbf{I}(\mathrm{QSV}_{n})$ is $\langle \mathrm{QSym}_{n}^{+}\rangle$. Our construction has a few byproducts which are independently noteworthy.  
}

%% put your French abstract here, or comment this out if you don't have one
\resume{Soit $R_n=\mathbb{Q}[x_1,x_2,\ldots,x_n]$ l'anneau des polynômes en $n$ variables, et considérez l'idéal $\langle \mathrm{QSym}_{n}^{+}\rangle\subseteq R_n$ engendré par les polynômes quasisymétriques sans terme constant.
Il a été démontré par Ava--Bergeron--Bergeron que $\dim\big(R_n\big/\langle \mathrm{QSym}_{n}^{+} \rangle\big)=C_n$ le $n$-ième nombre de Catalan.
Nous expliquons ici ce phénomène en construisant un ensemble de permutations $\mathrm{QSV}_{n}$ ayant les propriétés suivantes: premièrement, $\mathrm{QSV}_{n}$ est une base de l'algèbre de Temperley--Lieb $\mathsf{TL}_{n}(2)$, et deuxièmement, en considérant $\mathrm{QSV}_{n}$ comme une collection de points dans $\mathbb{Q}^{n}$, la composante homogène de degré supérieur de l'idéal $\mathbf{I}(\mathrm{QSV}_{n})$ est $\langle \mathrm{QSym}_{n}^{+}\rangle$. Notre construction a quelques sous-produits qui sont indépendamment dignes d'intérêt.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Noncrossing partitions, Quasisymmetric polynomials, Varieties of points}
\keywords{Quasisymmetric Polynomials, Bruhat order, Excedance, Temperley--Lieb} 

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text
%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{QSV.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\begin{document}

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Quasisymmetric functions originate in the work of Stanley~\cite{S72}, where they appear as enumeration series for $P$-partitions.  
Later, Gessel~\cite{Gessel} gave a more algebraic treatment of the ring $\QSym$ spanned by all quasisymmetric functions, establishing a beautiful analogy with the classical ring of symmetric functions $\Sym$. 
The importance of $\QSym$ has continued to increase:~\cite{ABS} established $\QSym$ as a universal setting for enumerative combinatorial invariants, and in recent years quasisymmetric functions have been at the center of a number of research programs (many examples can be found in~\cite{Grinberg,LMvW, Mason} and references therein).

In this abstract, based on the paper~\cite{BG}, we explore the striking similarity between quasisymmetric functions and the invariant theory of finite reflection groups.  
Chevalley's theorem states that each finite reflection group $W$ acts naturally on a polynomial ring $R$, and the quotient of $R$ by the ideal $\langle R_{+}^{W} \rangle$ generated by positive degree invariants is isomorphic to the regular module of $W$; see~\cite[Chapter 3]{Humphrey}.  
Hivert~\cite{Hivert} shows that the quasisymmetric polynomials $\QSym_{n}$ in $R_{n} = \QQ[x_{1}, \ldots, x_{n}]$ are likewise the invariants of an action of the Temperley--Lieb algebra $\TL_{n}(2)$ on $R_{n}$.
Writing $\langle \QSym_{n}^{+} \rangle$
for the ideal generated by the positive degree quasisymmetric polynomials,~\cite{ABB, AB} show that the dimension of the coinvariant space $R_{n}\big/\langle \QSym_{n}^{+} \rangle$ and $\TL_{n}(2)$ agree: both are the $n$th Catalan number $C_{n}$.  
Since $\TL_{n}(2)$ shares many nice properties with reflection groups, one might expect a Chevalley-type theorem from this coincidence, but there is no obvious $\TL_{n}(2)$-action on $R_{n}\big/\langle \QSym_{n}^{+} \rangle$:  Hivert's action is not multiplicative and $\langle \QSym_{n}^{+} \rangle$ is not a $\TL_{n}(2)$-submodule.  

Motivated by the discussion above, we revisit two modules which afford the left regular representation of the symmetric group $S_{n}$:
\begin{enumerate}[itemsep = -.5ex, label = (\arabic*)]
\item the quotient $R_{n}\big/\langle \Sym_{n}^{+} \rangle$ of the polynomial ring $R_{n} = \QQ[x_{1}, \ldots, x_{n}]$ by the ideal generated by positive-degree symmetric polynomials $\Sym_{n}^{+}$, and

\item the coordinate ring $R_{n} \big/ \mathbf{I}(S_{n})$ for the vertices of the regular permutohedron $S_{n}$ in $\QQ^{n}$, which are the points $(\sigma_{1}, \ldots, \sigma_{n})$ for each permutation $\sigma$ on $n$ letters.

\end{enumerate}
Module (1) is a famous case of Chevalley's theorem: the $S_{n}$-invariants of $R_{n}$ are the symmetric polynomials, and $R_{n}\big/\langle \Sym_{n}^{+} \rangle$ is the $S_{n}$ coinvariant ring.  
On the other hand, module (2) comes from the left multiplicative action of $S_{n}$ on the permutohedron realized on the coordinate ring $R_{n} \big/ \mathbf{I}(S_{n})$  where $\mathbf{I}(S_{n})$ is the vanishing ideal. 
However, as seen in the work of Garsia and Procesi~\cite{GP} and reference therein, a careful inspection reveals that these modules determine one another!  
Consider the ideal
\[
I_{n} = \langle f(x_{1}, \ldots, x_{n}) - f(1, \ldots, n) \;|\; f \in \Sym_{n}^{+} \rangle \subseteq \mathbf{I}(S_{n}).
\]
For each $f \in R_{n}$, let $\mathsf{h}(f)$ denote the top-degree homogeneous component of $f$, and for any ideal $I$ in $R_{n}$ write $\mathsf{gr}(I) = \langle \mathsf{h}(f) \;|\; f \in I \rangle$.  
Then $\mathsf{gr}(I_{n}) \supseteq \langle \Sym_{n}^{+} \rangle$, and Gr\"{o}bner basis theory gives a linear isomorphism $R_{n}\big/\mathsf{gr}(I_{n})  \cong R_{n}\big/I_{n}$.  We therefore have
\[
|S_{n}| = \dim\big(R_{n}\big/\langle \Sym_{n}^{+} \rangle\big) \ge \dim\big(R_{n}\big/\mathsf{gr}(I_{n})\big) = \dim\big(R_{n}\big/I_{n}) \ge \dim(R_{n}\big/\mathbf{I}(S_{n})\big) = |S_{n}|,
\]
so that $I_{n} = \mathbf{I}(S_{n})$ and $\mathsf{gr}(I_{n}) = \langle \Sym_{n}^{+} \rangle$, and $R_{n}\big/\langle \Sym_{n}^{+} \rangle \cong R_{n}\big/\mathbf{I}(S_{n})$ as vector spaces.  
This isomorphism respects the $S_{n}$-action on each quotient: both $\mathbf{I}(S_{n})$ and $\langle \Sym_{n}^{+} \rangle$ are fixed spaces for the standard $S_{n}$-action on $R_{n}$, and this action coindices with the action on points for $R_{n}\big/\mathbf{I}(S_{n})$.  
Thus, we have an $S_{n}$-module isomorphism $R_{n}\big/\langle \Sym_{n}^{+} \rangle \cong R_{n}\big/\mathbf{I}(S_{n})$, though the left hand side has a natural grading and the right hand side does not.

Our work in~\cite{BG} applies this approach to quasisymmetric functions and Temperley--Lieb algebras. 
It is known that $\langle \Sym_{n}^{+} \rangle \subseteq \langle \QSym_{n}^{+} \rangle$, and that there is a surjective algebra homomorphism $\phi: \CC S_{n} \to \TL_{n}(2)$. 
Guided by these relationships, we searched for a subset $\QSV_{n} \subseteq S_{n} \subseteq \QQ^{n}$ which satisfies:
\begin{enumerate}[itemsep = -.8ex, label=(\roman*)]
\item $|\QSV_{n}| = C_{n}$,
\item the image $\phi(\QSV_{n})$ is a basis of $\TL_{n}(2)$, and
\item considering the vanishing ideal $\mathbf{I}(\QSV_{n})$, we have $\mathsf{gr}\big(\mathbf{I}(\QSV_{n})\big) = \langle \QSym_{n}^{+} \rangle$.
\end{enumerate}
Assuming such a set exists, one can define an action of $\TL_{n}(2)$ on the space $R_{n}\big/\langle \QSym_{n}^{+} \rangle$ using Gr\"{o}bner basis theory and the multiplication constants for the basis obtained from $\QSV_{n}$.  
However, $\QSV_{n}$ is not readily found: it took several years of computer exploration to find a list of candidates for small values of $n$.  
We have now found it, along with a number of remarkable properties that should be of interest to the wider community.

The set $\QSV_{n} \subseteq S_{n}$ is defined in Section~\ref{sec:QSV}.  
After discovering it, we noticed that the cycle structure of permutations in $\QSV_{n}$ determine a noncrossing partition, tying them to a more general story of Coxeter--Catalan combinatorics for the symmetric groups~\cite{Baine} (see also~\cite{McCammond}).  
For example, writing $Q_{\lambda}$ to denote the element of $\QSV_{n}$ indexed by the partition $\lambda$,
\[
\lambda = \begin{tikzpicture}[scale = 0.75, baseline = 0.75*-0.2]
\foreach \x in {1, ..., 7}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {5/6, 3/5,2/7}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}
\qquad\text{corresponds to}\qquad
Q_{\lambda} = (1)(72)(653)(4).
\]
Through this connection,~\cite{Gobet, GW16} and~\cite{Z02} have studied bases of general Temperley--Lieb algebras which specialize to $\phi(\QSV_{n})$ for $\TL_{n}(2)$, so only condition (iii) remains.

Our initial attempts to prove condition (ii) also led us to an exciting discovery about how $\QSV_{n}$ sits in $S_{n}$.  
In Section~\ref{sec:excedance} we define an equivalence relation $\sim$ on $S_{n}$ using the weak excedance set of a permutation and its inverse.  
We call the equivalence classes of $S_{n}\big/\!\!\sim$ \emph{excedance classes}, and show that each noncrossing partition $\lambda$ bijectively determines an excedance class $\CCC_{\lambda}$.  
Surprisingly, the Bruhat order induces a well-defined quotient order on excedance classes.  
In the following, $\preceq$ denotes the order on noncrossing partitions which is dual to Young's lattice, described further in Section~\ref{sec:QSV}.

\begin{introthm}{\ref{thm:excedancequotient}}
Writing $\le$ for the relation on excedance classes $S_{n}\big/\!\! \sim$ induced by the Bruhat order, $\CCC_{\lambda} \le \CCC_{\mu}$ if and only if $\lambda \preceq \mu$.
\end{introthm}

This exhibits a duality between sub- and quotient orders of the Bruhat poset: 
a parallel result is given by~\cite{GW16} for the set $\QSV_{n}$ as a sub-poset of the Bruhat order (see Section~\ref{sec:QSV}).  The result of~\cite{GW16} also simplifies the proof of Theorem~\ref{thm:excedancequotient} we give in~\cite{BG}.  

\begin{introcor}{\ref{cor:interval}}
Each excedance class $\CCC_{\lambda}$ is an interval in the Bruhat order, with upper bound $Q_{\lambda}\in \QSV_n$ and lower bound given by a $321$-avoiding permutation.
\end{introcor}

The combinatorics of excedance classes are very rich, and there is much left to explore.   
In Section~\ref{sec:TLbasis}, we use excedance classes of $S_{n}$ to produce bases of $\TL_{n}(2)$.  Using results of~\cite{GW16} and~\cite{Z02}, our Theorem~\ref{thm:TLbasis} restates the fact that $\QSV_{n}$ satisfies condition (ii) above.  However, our technique is more general, and produces many (often novel) bases of $\TL_{n}(2)$ coming from the surjection $\phi: \CC S_{n} \to \TL_{n}(2)$.

\begin{introthm}{\ref{thm:TLbases}}
Let $n \ge 0$ and for each noncrossing partition $\lambda$ of size $n$, fix an element $w_{\lambda} \in \CCC_{\lambda}$. Then the set $\{\phi(w_{\lambda}) \;|\; \text{noncrossing partitions $\lambda$}\}$ is a basis of $\TL_{n}(2)$.
\end{introthm}

Finally, in Section~\ref{sec:vanishingtheorems} we outline our approach to proving that the set $\QSV_{n}$ satisfies condition (iii) above.  
The space of positive-degree quasisymmetric polynomials $\QSym_{n}$ has a homogeneous basis of monomial quasisymmetric functions $M_{\alpha}$ indexed by the compositions $\alpha \vDash d$ of positive integers $d > 0$ with length $\ell(\alpha) \le n$.  
For each such composition $\alpha$, we construct a nonhomogeneous polynomial $P_{\alpha} \in R_{n}$ for which $\mathsf{h}(P_{\alpha}) = M_{\alpha}$ and show the following.

\begin{introthm}{\ref{thm:vanishingQSV}}
The ideal $\langle P_{\alpha} \;|\; \text{$\alpha \vDash d $ with $d> 0$ and $\ell(\alpha) \le n$} \rangle \subseteq R_n$ is the vanishing ideal $\mathbf{I}(\QSV_n)$ and 
$ \langle \QSym_{n}^{+} \rangle = \mathsf{gr}\big(\mathbf{I}(\QSV_{n})\big).$
\end{introthm}

From this, we obtain a linear isomorphism
$R_{n}\big/\mathbf{I}(\QSV_{n}) \cong R_{n}\big/\langle \QSym_{n}^{+} \rangle.$
%Future work will explore the module structure on $R_{n}\big/\langle \QSym_{n}^{+} \rangle$ implicit in this result.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Noncrossing partitions and Bruhat order}
\label{sec:ncp}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%
\medskip\noindent{\bf Noncrossing partitions}:
%%%%%%%%%%
Let $n$ be a nonnegative integer.  A \emph{noncrossing partition} of size $n$ is a diagram $\lambda$ consisting of:
\begin{enumerate}[itemsep = -.5ex]
\item the positive integers $1, \ldots, n$, placed from left to right along a horizontal axis; and

\item a set of left-to-right arcs $\edge{i}{j} = (i, j)$, $i < j$ drawn above the axis with no intersections or coterminal points: $\lambda$ contains no pair $\edge{i}{k}, \edge{j}{l}$ with $i \le j < k \le l$.

\end{enumerate}
For example,
\begin{equation}
\label{eq:noncrossingpartitionexample}
\lambda = \begin{tikzpicture}[scale = 0.75, baseline = 0.75*-0.2]
\foreach \x in {1, ..., 7}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {5/6, 3/5,2/7}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}
\end{equation}
is a noncrossing partition of size $7$ containing three arcs: $\edge{2}{7}$, $\edge{3}{5}$, and $\edge{5}{6}$.

Considering a noncrossing partition $\lambda$ as an (undirected) graph, the connected components of $\lambda$ give a partition of the set $[n] = \{1, \ldots, n\}$, which is the origin of the term.  For example, the noncrossing partition shown in Equation~\eqref{eq:noncrossingpartitionexample} corresponds to the set partition $\big\{ \{1\}, \{2, 7\}, \{3, 5, 6\}, \{4\}  \big\}$.  Let
\[
\NCP_{n} = \{ \text{noncrossing partitions of size $n$} \}.
\]
The size of $\NCP_{n}$ is the $n$th Catalan number, $C_{n} = \frac{1}{n+1}\binom{2n}{n}$~\cite{S99}.

Given an arc $ \edge{i}{j} \in \lambda$, say that $i$ is the \emph{left endpoint} and $j$ is the \emph{right endpoint}, and let
\[
\lambda^{+} = \{\text{left endpoints in $\lambda$}\}
\qquad\text{and}\qquad
\lambda^{-} = \{\text{right endpoints in $\lambda$}\}.
\]
For example, with the noncrossing partition $\lambda$ in~\eqref{eq:noncrossingpartitionexample}, $\lambda^{+} = \{2, 3, 5\}$ and $\lambda^{-} = \{5, 6, 7\}$.  The arcs in $\lambda$ give a bijection between the sets $\lambda^{+}$ and $\lambda^{-}$, so that $|\lambda^{+}| = |\lambda^{-}|.$

%%%%%%%%%%
\medskip \noindent {\bf Permutations and the Bruhat order}:
%%%%%%%%%%
Let $S_n$ denote the group of permutations of $[n]$.  We represent elements of $S_{n}$ either by using the standard one- and two-line notations or as a product of cycles.  We also write $\ell$ for the length function, so that for $w \in S_{n}$, $\ell(w)$ is the number of inversions of $w$:
$
\ell(w) = |\{(i, j) \;|\; \text{$1 \le i < j \le n$ and $w_{i} > w_{j}$}\}|.
$

The \emph{Bruhat order} on $S_{n}$ is the partial order generated by the relation
\[
v < w \qquad\text{if and only if} \qquad \text{$wv^{-1}$ is a transposition $(i\,j)$ and $\ell(v) < \ell(w)$}.
\]
This order is ubiquitous in the study of $S_{n}$ and related objects (for examples, see~\cite{BjornerBrenti}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The set $\QSV_{n}$}
\label{sec:QSV}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%In this section we define the set $\QSV_{n} \subseteq S_n$ and establish its elementary properties.  Our treatment is essentially the standard  in the literature on noncrossing partitions and is originally due to~\cite{Baine}.  In Section~\ref{sec:bruhatballot}, we turn to the restriction of the Bruhat order to $\QSV_{n}$ and recall the combinatorial description of this order from~\cite{GW16}. 

Let $\lambda$ be a noncrossing partition of size $n$.
%and recall the sets $\lambda^{+}$ and $\lambda^{-}$ from Section~\ref{sec:ncp}.  
Define a permutation $Q_{\lambda} \in S_{n}$ by 
\[
Q_{\lambda}(j) = \begin{cases} i & \text{if $j \in \lambda^{-}$ and $ \edge{i}{j} \in \lambda$} \\
k & \text{if $j \notin \lambda^{-}$ and $k$ is the largest element connected to $j$ in $\lambda$}
\end{cases}
\]
Thus, $Q_{\lambda}$ sends each $j \in [n]$ to its leftward neighbor in $\lambda$, if such a neighbor exists, and otherwise sends $j$ to the rightmost element of its connected component.  


The cycles of $Q_{\lambda}$ correspond to the connected components of $\lambda$, for example, with
\[
\lambda = \begin{tikzpicture}[scale = 0.75, baseline = 0.75*-0.2]
\foreach \x in {1, ..., 7}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {5/6, 3/5,2/7}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}
\qquad\text{we have}\qquad
Q_{\lambda} = (1)(72)(653)(4) = 1764352.
\]

Let
$
\QSV_{n} = \{Q_{\lambda} \;|\; \lambda \in \NCP_{n} \}.
$
For example, the elements of $\QSV_{3}$ are:
\[
Q_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = 321, \qquad
Q_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2, 2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = 312, \qquad
Q_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = 213, 
\]
\[
Q_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = 132, \qquad\text{and}\qquad
Q_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\end{tikzpicture}} = 123.
\]

\begin{rem}
\label{rem:QSVnoncrossing}
Given any $n$-cycle $c \in S_{n}$,~\cite{Baine} gives a bijection between $\NCP_{n}$ and the interval between the identity and $c$ in the absolute order on $S_{n}$.  Our construction of the permutations $Q_{\lambda}$ realize this bijection for the $n$-cycle $c = (n\cdots 21)$.  
\end{rem}


%%%%%%%%%%%%%%%
\medskip\noindent{\bf The Bruhat order on $\QSV_{n}$}:
%\label{sec:bruhatballot}
%%%%%%%%%%%%%%%
The Bruhat order on $S_{n}$ described in Section~\ref{sec:ncp} restricts to a partial order on the set $\QSV_{n}$.
This order turns out to be very natural, as is described in the paper~\cite{GW16}, and we recall the description for use in later sections.

Define a partial order $\preceq$ on the set $\NCP_{n}$ of noncrossing partitions as the extension of the covering relation: $\lambda$ is covered by $\mu$ if and only if $\lambda$ is obtained from $\mu$ in one of the following ways:
\begin{enumerate}[itemsep = -.5ex]
\item removing an arc of the form $ \edge{i}{i+1}$ from $\mu$, or

\item replacing any arc $ \edge{i}{k}$ in $\mu$ with two arcs $ \edge{i}{j}$ and $ \edge{j}{k}$ for some $i < j < k$ which do not intersect or share a left or right endpoint with any other arc in $\mu$.

\end{enumerate}

\begin{prop}[{\cite[Theorem 1.1 and Corollary 7.5]{GW16}}]
\label{prop:QSVorderbijection}
Let $\lambda$ and $\mu$ be noncrossing partitions of size $n$.  The following are equivalent:
\begin{enumerate}[itemsep =-.5ex]
\item $\lambda \preceq \mu$, 

\item $Q_{\lambda} \le Q_{\mu}$ in the Bruhat order.%, and

%\item for all $1 \le k \le 2n$, $\sum_{i = 1}^{k} b^{\lambda}_{k} \le \sum_{i = 1}^{k} b^{\mu}_{k}$.
\end{enumerate}
Moreover, the partial orders on $\NCP_{n}$ and $\QSV_{n}$ are each dual to the interval between the empty diagram and the staircase in Young's lattice; see Figure~\ref{fig:Hassediagrams}.
\end{prop}

%For $n = 3$ the (isomorphic) orders on $\QSV_{n}$, $\NCP_{n}$, and ballot sequences of length $2n$ are shown in Figure~\ref{fig:Hassediagrams}.

\begin{figure}
\begin{center}
\begin{tikzpicture}
\node at (0, 4.5) (13b2) {$321$};
\node at (0, 3) (123) {$312$};
\node at (1.5, 1.5) (1b23) {$132$};
\node at (-1.5, 1.5) (12b3) {$213$};
\node at (0, 0) (1b2b3) {$123$};
\draw[thick] (1b2b3) -- (1b23);
\draw[thick] (1b2b3) -- (12b3);
\draw[thick] (1b23) -- (123);
\draw[thick] (12b3) -- (123);
\draw[thick] (123) -- (13b2);
\end{tikzpicture}
\hspace{0.75cm}
\begin{tikzpicture}
\node at (0, 4.5) (13b2) {\tikz[scale = 0.75, baseline = 0.75*-0.2]{
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}}};
\node at (0, 3) (123) {\tikz[scale = 0.75, baseline = 0.75*-0.2]{
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2, 2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}}};
\node at (1.5, 1.5) (1b23) {\tikz[scale = 0.75, baseline = 0.75*-0.2]{
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}}};
\node at (-1.5, 1.5) (12b3) {\tikz[scale = 0.75, baseline = 0.75*-0.2]{
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}}};
\node at (0, 0) (1b2b3) {\tikz[scale = 0.75, baseline = 0.75*-0.2]{
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}}};
\draw[thick] (1b2b3) -- (1b23);
\draw[thick] (1b2b3) -- (12b3);
\draw[thick] (1b23) -- (123);
\draw[thick] (12b3) -- (123);
\draw[thick] (123) -- (13b2);
\end{tikzpicture}
\hspace{0.75cm}
\begin{tikzpicture}
\node at (0, 4.5) (13b2) {$\emptyset$};
\node at (0, 3) (123) {\begin{tikzpicture}[scale = 1.5] \draw (0,0)--(0,.2)--(.2,.2)--(.2,0)--(0,0); \end{tikzpicture}};
\node at (1.5, 1.5) (1b23) {\begin{tikzpicture}[scale = 1.5] \draw (0,0)--(.2,0)--(.2,.4)--(0,.4)--(0,0);  \draw (.2,.2)--(0,.2); \end{tikzpicture}};
\node at (-1.5, 1.5) (12b3) {\begin{tikzpicture}[scale = 1.5] \draw (0,0)--(0,.2)--(.4,.2)--(.4,0)--(0,0);  \draw (.2,.2)--(.2,0); \end{tikzpicture}};
\node at (0, 0) (1b2b3) {\begin{tikzpicture}[scale = 1.5] \draw (0,0)--(0,.2)--(.4,.2)--(.4,0)--(0,0);  \draw (.2,0)--(.2,.4)--(0,.4)--(0,.2); \end{tikzpicture}};
\draw[thick] (1b2b3) -- (1b23);
\draw[thick] (1b2b3) -- (12b3);
\draw[thick] (1b23) -- (123);
\draw[thick] (12b3) -- (123);
\draw[thick] (123) -- (13b2);
\end{tikzpicture}
\end{center}
\caption{From left to right, the Hasse diagrams of: $\QSV_{3}$ with the Bruhat order; $\NCP_{3}$ with $\preceq$; and the dual interval in the Young's lattice.
}
\label{fig:Hassediagrams}
\end{figure}

\begin{rem}\label{rem:auto}
%We make several additional remarks about Proposition~\ref{prop:QSVorderbijection} below.
%\begin{enumerate}
In fact,~\cite{GW16} describes the Bruhat order on the set $\{\omega_0w\omega_0^{-1}\; |\; w \in \QSV_{n}\}$, where $\omega_0$ is the longest element of $S_n$. 
Vis-a-vis Remark~\ref{rem:QSVnoncrossing}, these are the non-crossing partitions associated with the cycle $(12\ldots n)$ instead of $(n\ldots 21)$.
Since conjugation by $\omega_{0}$ is an automorphism of the Bruhat order, this result is equivalent to Proposition~\ref{prop:QSVorderbijection}.
\end{rem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The excedance quotient of the Bruhat order}
\label{sec:excedance}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we describe a novel equivalence relation $\sim$ on $S_{n}$ and show that it induces a quotient of the Bruhat order.  
This equivalence relation is defined in a simple way using the weak excedances of a permutation.  
We have discovered a number of nice properties of the equivalence classes in $S_{n}\big/\!\!\sim$, which we summarize after our initial definition.


Given a permutation $w \in S_{n}$, a \emph{weak excedance} of $w$ is a pair $(i, w_{i})$ for which $i \le w_{i}$.  We define the \emph{excedance values} $\EV(w)$ and \emph{excedance positions} $\EP(w)$ to be the sets
\begin{align*}
\EV(w) &= \{ w_{i} \;|\; \text{$(i, w_{i})$ is a weak excedance of $w$}\},\;\text{and} \\[0.5em]
\EP(w) &= \{ i  \;|\; \text{$(i, w_{i})$ is a weak excedance of $w$}\}.
\end{align*}
The sets $\EV(w)$ and $\EP(w)$ are most easily seen using two-line notation for permutations.  For example, marking the non-excedances of a permutation in red,
\[
w = \overset{1}{3} \overset{2}{5} {\color{red} \overset{3}{1}} \overset{4}{4} {\color{red} \overset{5}{2}} \overset{6}{6} {\color{red} \overset{7}{5}} \overset{8}{8},
\qquad
\EP(w) = \{1, 2, 4, 6, 8\},\qquad\text{and}\qquad
\EV(w) = \{3, 4, 5, 6, 8\}.
\]
We define the \emph{excedance relation} $\sim$ on $S_{n}$ by:
\begin{equation}
\label{eq:excednacerel}
v \sim w \qquad\text{if and only if} \qquad \text{$\EV(v) = \EV(w)$ and $\EP(v) = \EP(w)$},
\end{equation}
and say that each equivalence class of $S_{n}\big/\!\!\sim$ is an \emph{excedance class}.

We now summarize our main results on excedance classes.  
Each noncrossing partition $\lambda$ of size $n$ determines an excedance class: 
%recall the sets $\lambda^{+}$ and $\lambda^{-}$ defined in Section~\ref{sec:ncp}, and let
\[
\CCC_{\lambda} = \{ w \in S_{n} \;|\;  \text{$\EV(w) = [n] \setminus \lambda^{+}$ and $\EP(w) = [n] \setminus \lambda^{-}$}  \}.
\]
%In Section~\ref{sec:ex1}, we show that t
This construction is bijective, so that the excedance classes are counted by the Catalan numbers.  For example, the five excedance classes of $S_{3}$ are:
\[
\mathcal{C}_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = \{ \stackrel{1}{3}  \stackrel{2}{2} \color{red} \stackrel{3}{1} \color{black}, \stackrel{1}{2}\stackrel{2}{3} \color{red} \stackrel{3}{1} \color{black} \}, \qquad
\mathcal{C}_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2, 2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = \{ \stackrel{1}{3} \color{red} \stackrel{2}{1} \stackrel{3}{2}  \color{black} \}, \qquad
\mathcal{C}_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/2}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = \{\stackrel{1}{2}  \color{red} \stackrel{2}{1} \color{black}  \stackrel{3}{3}\}, 
\]
\[
\mathcal{C}_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\foreach \i\j in {2/3}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}} = \{\stackrel{1}{1} \stackrel{2}{3}  \color{red} \stackrel{3}{2} \color{black} \}, \qquad\text{and}\qquad
\mathcal{C}_{\begin{tikzpicture}[scale = 0.35, baseline = 0.35*-0.2]
\foreach \x in {1, ..., 3}{\draw[fill] (\x - 1, 0) circle (2pt) node[inner sep = 2pt] (\x) {};}
\foreach \x in {1, ..., 3}{\node[below] at (\x) {$\scriptstyle \x$};}
\end{tikzpicture}} = \{\stackrel{1}{1} \stackrel{2}{2} \stackrel{3}{3} \}.
\]

The Bruhat order induces a relation on $S_{n}\big/\!\!\sim$.
Recall the order $\preceq$ from Section~\ref{sec:QSV}.

\begin{thm}
\label{thm:excedancequotient}
Writing $\le$ for the relation on excedance classes $S_{n}\big/\!\! \sim$ induced by the Bruhat order, $\CCC_{\lambda} \le \CCC_{\mu}$ if and only if $\lambda \preceq \mu$.
\end{thm}

Our proof Theorem~\ref{thm:excedancequotient} in~\cite{BG} includes the intermediate result that each excedance class $\CCC_{\lambda}$ contains unique Bruhat-minimal and Bruhat-maximal elements, and moreover these are respectively a $321$-avoiding permutation and the element $Q_{\lambda} \in \QSV_{n}$.  Combined with Theorem~\ref{thm:excedancequotient}, this implies the following corollary.  

\begin{cor}\label{cor:interval}
Each excedance class $\CCC_{\lambda}$ is an interval in the Bruhat order, with maximum $Q_{\lambda}\in \QSV_n$ and minimum given by a $321$-avoiding permutation.
\end{cor}

We now identify the minimal element of each excedance class.  For a noncrossing partition $\lambda$ of size $n$, enumerate the sets $\lambda^{+}$, $\lambda^{-}$, $[n] \setminus \lambda^{+}$, and  $[n] \setminus \lambda^{-}$ in increasing order as
\[
\lambda^{+} = \{a_{1} < a_{2} < \cdots < a_{s}\},
\qquad
\lambda^{-} = \{b_{1} < b_{2} < \cdots < b_{s}\},
\]
\[
[n] \setminus \lambda^{+} = \{x_{1} < x_{2} < \cdots < x_{n-s}\},
\qquad\text{and}\qquad
[n] \setminus \lambda^{-} = \{y_{1} < y_{2} < \cdots < y_{n-s}\}.
\]
Let $T_{\lambda} \in S_{n}$ be the permutation with
\[
T_{\lambda}(i) = \begin{cases} a_{r} & \text{if $i \in \lambda^{-}$ and $i = b_{r}$} \\ x_{r} & \text{if $i \notin \lambda^{-}$ and $i = y_{r}$.}  \end{cases}
\]
Thus, the two-line notation for $T_{\lambda}$ can be obtained by placing the elements of $\lambda^{+}$ in increasing left-to-right order below the elements of $\lambda^{-}$, and placing the elements of $[n] \setminus \lambda^{+}$ below the elements of $[n] \setminus \lambda^{-}$ in the same manner.  For example, with $n = 8$ and 
\[
\lambda = \begin{tikzpicture}[scale = 0.75, baseline = 0.75*-0.2]
\foreach \x in {1, ..., 8}{\draw[fill] (\x - 1, 0) node[inner sep = 2pt] (\x) {$\scriptstyle \x$};}
\foreach \i\j in {1/5, 2/3, 5/7}{\draw[thick] (\i) to[out = 35, in = 145] (\j);}
\end{tikzpicture}
\]
we have $\lambda^{+} = \{1, 2, 5\}$ and $\lambda^{-} = \{3, 5, 7\}$, $[8] \setminus \lambda^{+} = \{3, 4, 6, 7, 8\}$, and $[8] \setminus \lambda^{-} = \{1, 2, 4, 6, 8\}$, and consequently
\[
T_{\lambda} = \overset{1}{3} \overset{2}{4} {\color{red} \overset{3}{1}} \overset{4}{6} {\color{red} \overset{5}{2}} \overset{6}{7} {\color{red} \overset{7}{5}} \overset{8}{8},
\]
where non-excedances are marked in red, as at the beginning of Section~\ref{sec:excedance}.

\begin{prop}
\label{prop:321avoid}
For all noncrossing partitions $\lambda$, $T_{\lambda} \in \CCC_{\lambda}$, is the Bruhat-minimum element of $\CCC_{\lambda}$, and is $321$-avoiding.
\end{prop}

\begin{rem}
Proposition~\ref{prop:321avoid} implicitly defines a bijection between $321$-avoiding permutations and noncrossing partitions.  This bijection is equivalent to one used by Zinno in~\cite{Z02} and Gobet in~\cite{Gobet}.
\end{rem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bases for the Temperley--Lieb Algebra $\TL_{n}(2)$}
\label{sec:TLbasis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The Temperley--Lieb algebra $\TL_{n}(2)$ is the $\CC$-algebra generated by elements $e_{1}, \ldots, e_{n-1}$ subject to the following relations for each $1 \le i, j \le n$
\[
e_{i}^{2} = 2 e_{i}; \qquad
e_{i}e_{j} = e_{j}e_{i}  \ \text{if $|i - j| > 1$}; \qquad
e_{i} e_{j} e_{i} = e_{i} \  \text{if $|i - j| = 1$}.
\]
There is a surjective algebra morphism from the symmetric group algebra $\CC S_{n}$ to $\TL_{n}(2)$ given by $\phi: \CC S_{n} \to \TL_{n}(2)$ where $\phi(s_{i})= 1 - e_{i}$.
In particular $\TL_{n}(2)\cong S_n\big/\!\ker(\phi)$.

It is well-known that the images of all $321$-avoiding permutations under $\phi$ forms a basis for $\TL_{n}(2)$.  
Gobet~\cite{Gobet} shows that the set $\QSV_{n}$ has a similar property.


\begin{thm}[{\cite[Theorem 7.21]{Gobet}}]
\label{thm:TLbasis}
For all $n \ge 0$, the set $\phi(\QSV_{n})$ is a basis for $\TL_{n}(2)$.
\end{thm}


In our investigation of excedance classes we found an application of their structure the problem of computing sets of permutations which give bases of $\TL_{n}(2)$ under $\phi$.  
We include it here  as it is a nice result of our current investigation.

\begin{thm}
\label{thm:TLbases}
Let $n \ge 0$ and for each noncrossing partition $\lambda$ of size $n$, fix an element $w_{\lambda} \in \CCC_{\lambda}$. Then the set $\{\phi(w_{\lambda}) \;|\; \text{noncrossing partitions $\lambda$}\}$ is a basis of $\TL_{n}(2)$.
\end{thm}

%A proof of Theorem~\ref{thm:TLbases} is given in Section~\ref{sec:basistheoremproof}.  
Here, we discuss its implications: taking $w_{\lambda} = Q_{\lambda}$ in the theorem gives yet another proof of Theorem~\ref{thm:TLbasis}, confirming the results of~\cite{GW16} and~\cite{Z02}.  In general, however, many bases obtained via Theorem~\ref{thm:TLbases} are novel.  The smallest novel example can be found with $n = 4$: the set 
\[
\{
\stackrel{1}{4} \stackrel{2}{3} \color{red} \stackrel{3}{1} \stackrel{4}{2} \color{black}, 
\stackrel{1}{4} \stackrel{2}{2} \stackrel{3}{3}  \color{red} \stackrel{4}{1} \color{black}, 
\stackrel{1}{4} \stackrel{2}{2}\color{red}  \stackrel{3}{1} \stackrel{4}{3} \color{black}, 
\stackrel{1}{3} \color{red}  \stackrel{2}{1} \color{black} \stackrel{3}{4} \color{red} \stackrel{4}{2}\color{black} , 
\stackrel{1}{1} \stackrel{2}{4} \stackrel{3}{3} \color{red} \stackrel{4}{2} \color{black}, 
\stackrel{1}{4} \color{red} \stackrel{2}{1} \stackrel{3}{2} \stackrel{4}{3} \color{black}, 
\stackrel{1}{3} \stackrel{2}{2} \color{red} \stackrel{3}{1} \color{black} \stackrel{4}{4}, 
\stackrel{1}{3} \color{red} \stackrel{2}{1} \stackrel{3}{2} \color{black} \stackrel{4}{4}, 
\stackrel{1}{2} \color{red} \stackrel{2}{1} \color{black} \stackrel{3}{4} \color{red} \stackrel{4}{3} \color{black}, 
\stackrel{1}{1} \stackrel{2}{3} \color{red} \stackrel{3}{2} \stackrel{4}{3} \color{black}, 
\stackrel{1}{2}  \color{red} \stackrel{2}{1} \color{black} \stackrel{3}{3} \stackrel{4}{4}, 
\stackrel{1}{1} \stackrel{2}{3} \color{red} \stackrel{3}{2} \color{black} \stackrel{4}{4}, 
\stackrel{1}{1} \stackrel{2}{2} \stackrel{3}{4}  \color{red} \stackrel{4}{3} \color{black},
\stackrel{1}{1} \stackrel{2}{2} \stackrel{3}{3} \stackrel{4}{4}
\}
\]
meets the criteria of Theorem~\ref{thm:TLbases}, and accordingly maps to a basis of $\TL_{n}(2)$ under $\phi$. 
This set is neither $\QSV_{4}$ nor the set of $321$-avoiding permutations ($4312 \notin \QSV_{4}$ and is not $321$-avoiding).
Moreover, the set above is not described in~\cite{GW16, Z02}: each subset of $S_{4}$ in these sources which is not $\QSV_{4}$ contains more than one element from certain excedance classes and none from others.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The quasisymmetric variety}
\label{sec:vanishingtheorems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section, we summarize Theorem~\ref{thm:vanishingQSV} and its proof, which is given in full in our paper~\cite{BG}.  
As in the introduction, let $\QSym_{n}$ denote the quasisymmetric polynomials in $R_{n} = \QQ[x_{1}, \ldots, x_{n}]$ and write $M_{\alpha}$ for the monomial quasisymmetric function indexed by the composition $\alpha$.  In Section~\ref{sec:QSymvanish}, we define a family of non-homogeneous polynomials $P_{\alpha}$ which are also indexed by compositions and we show that
\begin{equation}
\label{eq:Palphahomogeneous}
P_{\alpha} = M_{\alpha} + \text{lower degree terms}.
\end{equation}
For a permutation $\sigma \in S_{n}$, we write $P_{\alpha}(\sigma)$ for the evaluation of $P_{\alpha}$ at $x_{1} = \sigma_{1}$, $x_{2} = \sigma_{2}$, and so on.  Recall the set $\QSV_{n}$ defined in Section~\ref{sec:QSV}.

\begin{thm}
\label{thm:vanishing}
For each non-empty integer composition $\alpha$ with at most $n$ parts and any $\sigma\in \QSV_n$ we have $P_{\alpha} (\sigma)=0$.
\end{thm}

Our proof of Theorem~\ref{thm:vanishing} in~\cite{BG} uses the noncrossing cycle structure of each element $\sigma\in \QSV_n$, as well as a sign-reversing involution to establish desired vanishing property.

Now recall that for any $f \in R_{n}$, $\mathsf{h}(f)$ denotes the homogeneous top-degree component of $f$, and that for any ideal $I \subseteq R_{n}$, we write
$
\mathsf{gr}(I) = \langle \mathsf{h}(f) \;|\; f \in I \rangle.
$
Standard results in Gr\"{o}bner basis theory give a linear isomorphism $R_{n}\big/I \cong R_{n} \big/ \mathsf{gr}(I)$.  With Theorem~\ref{thm:vanishing} and the dimension considerations set out in the introduction, this proves of our main result.  

\begin{thm}\label{thm:vanishingQSV} 
The ideal $\langle P_{\alpha} \;|\; \text{non-empty compositions $\alpha$ of length $\ell(\alpha) \le n$} \rangle \subseteq R_n$ is the vanishing ideal $\mathbf{I}(\QSV_n)$ and 
\[
\langle \QSym_{n}^{+} \rangle = \mathsf{gr}\big(\mathbf{I}(\QSV_{n})\big),
\]
where  $\QSym_{n}^{+}$ denotes the set of positive-degree quasisymmetric functions.
 \end{thm}

Using Gr\"{o}bner basis theory again, we obtain the following corollary.

\begin{cor}
We have $R_n\big/\langle \QSym_{n}^{+} \rangle \cong R_n\big/\mathbf{I}(\QSV_{n})$ as vector spaces.
\end{cor}

\begin{rem}
Remarks~\ref{rem:QSVnoncrossing} and~\ref{rem:auto} describe the combinatorics of the sets $\{w \sigma w \;|\; \sigma \in \QSV_{n}\}$, each of which corresponds to a unique $n$-cycle $c \in S_{n}$.  
It is natural to consider how Theorems~\ref{thm:vanishing} and~\ref{thm:vanishingQSV} generalize to these sets as well, and we explain this below.
\begin{enumerate}
\item For the set $\{\omega_{0} \sigma \omega_{0} \;|\; \sigma \in \QSV_{n}\}$ corresponding to the Coxeter element $c = (1\,2\ldots n)$, our results generalize completely.  In particular, the modified polynomials
	$$\omega_0P_\alpha\omega_0=P_\alpha(-x_n+n+1,\ldots, -x_2+n+1,-x_1+n+1)$$
vanish on every permutation $\omega_{0} \sigma \omega_{0}$ for $\sigma \in \QSV_{n}$. Moreover,
 \[
 \mathsf{h}\big(\omega_0P_\alpha\omega_0\big) = M_{\alpha}(-x_n,\ldots,-x_2,-x_1)=(-1)^{|\alpha|} M_{\overleftarrow{\alpha}},
 \]
where for a composition $\alpha=(\alpha_1,\ldots,\alpha_k)$,  $M_{\overleftarrow{\alpha}}$ denotes the monomial quasisymmetric function corresponding to the reverse $\overleftarrow{\alpha}=(\alpha_k,\ldots,\alpha_1)$.  This is closely related to the automorphisms of the ring of quasisymmetric functions (see, for example~\cite{JWY}).

\item For the sets corresponding to $n$-cycles other than $(1\,2\,\ldots\,n)$ and $(n\,\ldots\,2\,1)$, the vanishing ideal does not have top-degree homogeneous component $\langle \QSym_{n}^{+} \rangle$.  
%However, this ideal appears to be quite nice and may be the subject of future work.

\end{enumerate}
\end{rem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The vanishing polynomial $P_{\alpha}$}
\label{sec:QSymvanish}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we define the polynomials $P_{\alpha}$ and prove Theorem~\ref{thm:vanishing}.  We begin with a short review of compositions and the refinement order as they relate to $\QSym$.  

A \emph{composition} is a sequence of positive integers $\alpha = (\alpha_{1}, \ldots, \alpha_{k})$.  We refer to $k$ as the \emph{length} of $\alpha$ and to $d = \sum_{i = 1}^{k} \alpha_{i}$ as the \emph{size} of $\alpha$.  Compositions are partially ordered by refinement: the composition $\alpha$ refines another composition $\beta = (\beta_{1}, \ldots, \beta_{\ell})$ if there exists a sequence $1 = f_{1} < f_{2} < \cdots < f_{\ell + 1} = k+1$ for which $\beta_{i} = \alpha_{f_{i}} + \alpha_{f_{i} + 1} + \cdots + \alpha_{f_{i+1} - 1}$, and in this case we write $\beta \succeq \alpha$.  Whenever we have a refinement relation $\beta \succeq \alpha$, we will use the notation $f_{1}, f_{2}, \ldots, f_{\ell+1}$ to refer to the sequence of indices in the definition.

For each composition of length $k \ge 1$, the monomial quasisymmetric function $M_{\alpha} \in R_{n}$ is defined by
\[
M_{\alpha} = \sum_{1\le i_1<i_2<\cdots<i_k\le n} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2}\cdots  x_{i_k}^{\alpha_k},
\]
where the sum is over subsets $\{i_{1}, \ldots, i_{k}\}$ of $[n]$, enumerated in increasing order.  Using the same convention we define the vanishing polynomial $P_{\alpha} \in R_{n}$ to be
\[
P_{\alpha} =  
\sum_{\beta \succeq \alpha}
\hspace{0.6em}
\sum_{1\le i_{1} < i_{2} < \cdots < i_{\ell} \le n} 
\hspace{0.6em}
\prod_{j = 1}^{\ell}
\Big(
(x_{i_{j}}^{\alpha_{f_{j}}} - i_{j}^{\alpha_{f_{j}}}) 
\prod_{s = f_{j} + 1}^{f_{j+1} - 1} (- i_{j})^{\alpha_{s}}
\Big).
\]
While this formula appears to be quite dense, expanding it reveals an intuitive combinatorial structure.  We compute one example in its entirety for the sake of exposition: 
\begin{align*}
P_{(1, 2, 1)}(x_{1}, \ldots, x_{4}) =& (x_{1} - 1)(x_{2}^{2} - 2^{2})(x_{3} - 3) + (x_{1} - 1)(x_{2}^{2} - 2^{2})(x_{4} - 4) \\
&+ (x_{1} - 1)(x_{3}^{2} - 3^{2})(x_{4} - 4) + (x_{2} - 2)(x_{3}^{2} - 3^{2})(x_{4} - 4) \\[1ex]
&\hspace{1.2em} -  (x_{1} - 1)(x_{2}^{2} - 2^{2})2 -  (x_{1} - 1)(x_{3}^{2} - 3^{2})3 -  (x_{1} - 1)(x_{4}^{2} - 4^{2})4  \\
&\hspace{1.2em} -  (x_{2} - 2)(x_{3}^{2} - 3^{3})3 -  (x_{2} - 2)(x_{4}^{2} - 4^{2})4 -  (x_{3} - 3)(x_{4}^{2} - 4^{2})4 \\[1ex]
&\hspace{2.4em} -  (x_{1} - 1)1^{2}(x_{2} - 2) -  (x_{1} - 1)1^{2}(x_{3} - 3) -  (x_{1} - 1)1^{2}(x_{4} - 4) \\
&\hspace{2.4em} -  (x_{2} - 2)2^{2}(x_{3} - 3) -  (x_{2} - 2)2^{2}(x_{4} - 4) -  (x_{3} - 3)3^{2}(x_{4} - 4) \\[1ex]
&\hspace{3.6em} + (x_{1} - 1) 1^{3} + (x_{2} - 2) 2^{3} + (x_{3} - 3) 3^{3} + (x_{4} - 4) 4^{3},
\end{align*}
where summands corresponding to the same index $\beta \succeq (1, 2, 1)$ are grouped horizontally and by alignment.  These values of $\beta$ are respectively $(1, 2, 1)$, $(1, 3)$, $(3, 1)$, and $(4)$.

%\medskip
\acknowledgements{This work is supported in part by Bergeron's York Research Chair and NSERC. We thank the participants of the Algebraic Combinatorics working seminar at the Fields Institute where this paper originated: K.~Chan, F.~G\'elinas, A.~Lao, A.~A.~Lazzeroni, C.~McConnell, Y.~Solomon, F.~Soltani,  N.~Wallace and 
M.~ Zabrocki. We are especially grateful to K.~Chan for helping us understand some of our intermediate construction of $\QSV_n$ at an early stage.
We are also grateful to R.~Gonz\'alez~D'L\'eon for his  inspiring discussions.}% related to Section~\ref{sec:weakorder}. 

%\renewcommand*{\bibfont}{\normalfont\small}
\printbibliography

\end{document}

