%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{97}
\addbibresource{97.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{definition}[thm]{Definition}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{example}[thm]{Example}
\newtheorem{remark}[thm]{Remark}

\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\rec}{rec}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\NAF}{NAF}
\DeclareMathOperator{\leg}{leg}
\DeclareMathOperator{\arm}{arm}
\DeclareMathOperator{\coinv}{coinv}
\DeclareMathOperator{\States}{States}
\DeclareMathOperator{\ASEP}{ASEP}
\DeclareMathOperator{\skipped}{skipped}
\DeclareMathOperator{\free}{free}
\DeclareMathOperator{\inc}{inc}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\rev}{rev}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\F}{F_{\mu}(\mathbf{x}; q, t)}
\newcommand{\tsigma}{\tilde{\sigma}}
\newcommand{\x}{{\mathbf x}}

\usepackage{lipsum}

%% define your title in the usual way
\title{From multiline queues to Macdonald polynomials via the exclusion process}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sylvie Corteel\thanks{\href{mailto:corteel@irif.fr}{corteel@irif.fr} SC was in residence at MSRI in Berkeley (NSF grant DMS-1440140) during the fall of 2017 and was funded by the Miller Institute, Berkeley during the spring of 2018.}\addressmark{1}, Olya Mandelshtam\thanks{\href{mailto:olya@math.brown.edu}{olya@math.brown.edu}}\addressmark{2}, \and Lauren Williams\thanks{\href{mailto:williams@math.harvard.edu}{williams@math.harvard.edu} LW was partially supported by NSF grant DMS-1600447.}\addressmark{3}}
 


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}IRIF, CNRS et Universit\'e Paris Diderot, France \\ 
\addressmark{2}Department of Mathematics, Brown University, Providence, RI \\ 
\addressmark{3}Department of Mathematics, Harvard University, Cambridge, MA}

%% 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{Recently James Martin introduced \emph{multiline queues}, and used them to give a combinatorial formula for the stationary distribution of the multispecies asymmetric simple exclusion exclusion process (ASEP) on a circle. The ASEP is a model of particles hopping on a one-dimensional lattice, which has been extensively studied in statistical mechanics, probability, and combinatorics. In this article we give an independent proof of Martin's result, and we show that by introducing additional statistics on multiline queues, we can use them to give a new combinatorial formula for both the symmetric	Macdonald polynomials $P_{\lambda}(\mathbf{x}; q, t)$, and the nonsymmetric Macdonald polynomials $E_{\lambda}(\mathbf{x}; q, t)$, where $\lambda$ is a partition. This formula is rather different from others that have appeared in the literature (Haglund-Haiman-Loehr'05,  Ram-Yip'11, and Lenart'09). Our proof uses results of Cantini, de Gier, and Wheeler who recently linked the multispecies ASEP on a circle to Macdonald polynomials.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{asymmetric simple exclusion process, Macdonald polynomials}

%% 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, ie. [xx, yy] in the text

%%%%%%%%%%%%%%%%%%%%%bibliography part

%%%%%%% 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{sample.bib}
%%%%%%% note the \printbibliography command at the end of the file which goes with these biblatex commands

%\addbibresource{bibliography.bib}

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction and results}

Introduced in the late 1960s \cite{bio, Spitzer},
the \emph{asymmetric simple exclusion process} (ASEP) is a model
of interacting
particles hopping left and right on a one-dimensional lattice of $n$
sites. There are many versions of the ASEP: the lattice might be a lattice with open boundaries,
or a ring, among others; and we may allow multiple species of particles with different ``weights".
In this article, we will be concerned with the multispecies ASEP on a ring, 
where the rate of two adjacent particles swapping places is either $1$ or $t$, depending
on their relative weights.
Recently James Martin \cite{Martin} gave a combinatorial formula in terms of 
\emph{multiline queues} for the stationary distribution 
of this multispecies ASEP on a ring, building on his earlier joint work 
with Ferrari \cite{FerrariMartin}.

On the other hand, recent work of 
Cantini, de Gier, and Wheeler 
\cite{CGW} gave a link between the multispecies ASEP on a ring and \emph{Macdonald polynomials}.
Symmetric Macdonald polynomials $P_{\lambda}(\mathbf{x}; q, t)$ \cite{Macdonald} are a family of multivariable orthogonal polynomials
indexed by partitions, whose coefficients depend on two parameters $q$ and $t$; they generalize
multiple important families of polynomials, 
including Schur polynomials (at $q=t=0$)  and
Hall-Littlewood polynomials (at $q=0$).
\emph{Nonsymmetric Macdonald polynomials} \cite{Cher1, MacdonaldBourbaki} were introduced shortly 
after the introduction of Macdonald polynomials, and defined in terms of 
\emph{Cherednik operators}; the symmetric Macdonald polynomials can be constructed from 
their nonsymmetric counterparts.


There has been a lot of work devoted to understanding Macdonald polynomials from a combinatorial
point of view.
Haglund-Haiman-Loehr \cite{HHL2, HHL1} gave a combinatorial formula for the 
\emph{transformed Macdonald polynomials} $\tilde{H}_{\mu}(\mathbf{x}; q, t)$
(which are connected to the 
 geometry of the Hilbert scheme
\cite{HaimanHilbert}) as well as for the \emph{integral forms}
$J_{\mu}(\mathbf{x}; q, t)$, which are scalar multiples of the classical monic
forms $P_{\mu}(\mathbf{x}; q, t)$.  
They also 
 gave a formula for the nonsymmetric  Macdonald polynomials
\cite{HHL3}.  Building on work of Schwer \cite{Schwer}, 
Ram and Yip \cite{RamYip} gave general-type 
formulas for both the Macdonald polynomials 
$P_{\lambda}(\mathbf{x}; q, t)$ and the nonsymmetric Macdonald polynomials; 
however, their type $A$ formulas have many terms.  
Lenart \cite{Lenart} showed how to ``compress" the Ram-Yip formula in type 
A to obtain a Haglund-Haiman-Loehr type formula for the polynomials
$P_{\lambda}(\mathbf{x}; q, t)$ for $\lambda$ with all parts distinct.  Finally, Ferreira \cite{thesis}  and Alexandersson \cite{A} gave Haglund-Haiman-Loehr type formulas for \emph{permuted basement Macdonald polynomials}, which generalize the 
nonsymmetric Macdonald polynomials.


The main goal of this article is to 
define some polynomials combinatorially 
in terms of multiline queues which simultaneously
compute the stationary distribution of the multispecies ASEP and also 
symmetric Macdonald 
polynomials $P_{\lambda}(\mathbf{x}; q, t)$.  More specifically, we introduce some polynomials
$F_{\mu}(x_1,\dots,x_n; q, t) = F_{\mu}(\mathbf{x};q,t) \in \Z(q,t)[x_1,\dots,x_n]$ 
which are certain weight-generating functions
for multiline queues with bottom row $\mu$, where $\mu=(\mu_1,\dots,\mu_n)$ is an arbitrary weak composition.  
We show that these polynomials have the following properties:
\begin{enumerate}
\item \label{one} When $x_1=\dots=x_n=1$ and $q=1$, $F_{\mu}(\mathbf{x}; q, t)$ is proportional to the steady state probability that the multispecies ASEP is in state $\mu$. (This recovers a result of Martin \cite{Martin}, but we give an independent proof.) 

\item \label{two} 
When $\mu$ is a partition, $F_{\mu}(\mathbf{x}; q, t)$ is equal to the nonsymmetric Macdonald
polynomial $E_{\mu}(\mathbf{x}; q, t)$. 
\item \label{three} 
For any partition $\lambda$, the quantity $Z_{\lambda}(\mathbf{x}; q, t) := \sum_{\mu} F_{\mu}(\mathbf{x}; q, t)$ (where the sum is over all distinct compositions obtained by permuting the parts of 
$\lambda$) is equal to the symmetric Macdonald polynomial $P_{\lambda}(\mathbf{x}; q, t)$.
\end{enumerate}  

In the remainder of the introduction we will make the above statements more precise.

\subsection{The multispecies ASEP}

We start by defining the multispecies ASEP or the $L$-ASEP as a Markov chain on the 
cycle $\Z_n$ with $L$ classes of particles as well as holes. The $L$-ASEP on a ring is a natural generalization for the two-species ASEP; for the latter, 
solutions were given using a matrix product formulation in terms of a quadratic algebra similar to the matrix ansatz described in \cite{DEHP}. 

For the $L$-ASEP when $t=0$ (i.e. particles only hop in one direction), 
Ferrari and Martin \cite{FerrariMartin} proposed 
a combinatorial solution for the stationary distribution using multiline queues. This construction was restated as a matrix product solution in 
\cite{EvansFerrariMallick08} and was generalized to 
the partially asymmetric case ($t$ generic) in 
\cite{ProlhacEvansMallick09}.
In \cite{AritaAyyerMallickProlhac12} 
the authors explained how to construct an explicit 
representation of the algebras involved in the $L$-ASEP.
Finally James Martin \cite{Martin}
gave an ingenious combinatorial solution
for the stationary distribution of the $L$-ASEP when $t$ is generic,
using more general multiline queues and building on ideas from  \cite{FerrariMartin} and \cite{EvansFerrariMallick08}. 


\begin{definition}\label{def:ASEP}
Let $\lambda = \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n \geq 0$
be a partition with greatest part $\lambda_1 = L$, and let $t$ be a constant such that $0 \leq t \leq 1$.
Let $\States(\lambda)$ be the set of all weak compositions of length $n$ obtained by permuting the parts of $\lambda$. We consider indices modulo $n$; i.e. if $\mu=\mu_1\ldots \mu_n$ is a composition, then $\mu_{n+1}=\mu_1$. The \emph{multispecies asymmetric simple exclusion process} $\ASEP(\lambda)$ on a ring is the Markov chain on $\States(\lambda)$ with transition probabilities:
\begin{itemize}
\item If $\mu = A i j B$ and $\nu = A j i B$ are in $\States(\lambda)$ (here $A$ and $B$ are words in the parts of $\lambda$), then $P_{\mu,\nu} = \frac{t}{n}$ if $i>j$ and $P_{\mu,\nu} = \frac{1}{n}$ if $i<j$.
\item Otherwise $P_{\mu,\nu} = 0$ for $\nu \neq \mu$ and $P_{\mu,\mu} = 1-\sum_{\mu \neq \nu} P_{\mu,\nu}$.
\end{itemize}
We think of the $1$'s, $2$'s, \dots, $L$'s as representing various types of
particles of different weights; each $0$ denotes an empty site.
See \cref{parameters1}.
\end{definition}

\begin{figure}[!ht]
  \centerline{\includegraphics[height=1in]{MLQ_intro_param_flipped.pdf}}
\centering
 \caption{The multispecies ASEP on the lattice $\Z_8$. There is 
one particle of type $3$, 
                three particles of type $2$, one particle of type $1$, and
                three holes ($0$'s),
                 so we refer
                to this Markov chain as $\ASEP(3, 2,2,2,1,0,0,0)$.}
\label{parameters1}
 \end{figure}

%Note that in the literature on the ASEP, the hopping rate is often denoted by $q$.  We are using $t$ here instead in order to be consistent with the notation of \cite{CGW-arxiv, CGW}, and to make contact with the literature on Macdonald polynomials.

\subsection{Multiline queues}
\label{1point2}



We now define ball systems and multiline queues. These concepts are due to Ferrari and Martin \cite{FerrariMartin} 
for $t=0$ and $q=1$ and to Martin \cite{Martin} for $t$ general and $q=1$.
\begin{definition}\label{def:MLQ}
Fix positive integers $L$ and $n$.
A \emph{ball system} $B$
is an $L \times n$ array
in which each of the $Ln$ positions is either empty or occupied by a ball.
We number the rows from bottom to top from $1$ to $L$,
and the columns from left to right from $1$ to $n$.  Moreover we require
that there is at least one ball in the top row,
and that the
 number of balls in each row is weakly increasing from top to bottom.
\end{definition}
\begin{figure}[!ht]
  \centerline{\includegraphics[height=1in]{MLQ_intro0.pdf}}
\centering
 \caption{
A ball system.}
\label{parameters2}
 \end{figure}

\begin{definition}
Given an $L \times n$ ball system $B$, a multiline queue $Q$ (for $B$)
is, for each row $r$ where $2 \leq r \leq L$, a matching of balls
from row $r$ to row $r-1$.  A ball $b$ may be matched to any ball $b'$
in the row below it; we connect $b$ and $b'$ by a shortest strand that 
travels either straight down or from left to right (allowing the strand to wrap around the cylinder
if necessary). We refer to two balls being matched by a \emph{pairing}, with pairings obtained by the following algorithm:

\begin{itemize}
\item We start by matching 
 all balls in row $L$ to a collection of balls (their partners)
in row 
$L-1$. We then match those partners in row $L-1$ to new partners in row $L-2$, 
and so on.  This determines a set of balls, each of which we label by $L$.
\item  We then take the unmatched balls in row $L-1$ and match them 
to partners in row $L-2$.  We then match those partners in row $L-2$ to 
new partners in row $L-3$, and so on.  This determines a set of balls,
each of which we label by $L-1$.
\item We continue in this way, determining a set of balls labeled 
$L-2$, $L-3$, and so on, and finally we label any unmatched balls in row
$1$ by $1$.
\item If at any point there's a free (unmatched) 
ball $b'$ directly underneath the ball $b$ we're matching,
we must match $b$ to $b'$.  We say that $b$ and $b'$ are
\emph{trivially paired}.
\end{itemize}
Let $\mu= (\mu_1,\dots,\mu_n) \in \{0,1,\dots,L\}^n$ be the labeling
of the balls in row $1$ at the end of this process (where
an empty position is denoted by $0$).  We then say that 
$Q$ is a \emph{multiline queue of type $\mu$}.
See \cref{fig:MLQ_example} 
	for an example.
\end{definition}
\begin{figure}[!ht]
  \centerline{\includegraphics[height=1in]{MLQ_intro.pdf}}
\centering
 \caption{
A multiline queue of type $(2,2,0,0,0, 3,2,1)$.}
\label{fig:MLQ_example}
 \end{figure}

\begin{remark}
Note that the induced labeling on the balls satisfies the following
properties:
\begin{itemize}
\item If ball $b$ with label $i$ is directly above 
ball $b'$ with label $j$, then we must have $i \leq j$.
\item Moreover if $i=j$, then those two balls are matched to each other (a trivial pairing).
\end{itemize}
\end{remark}


We now define the weight of each multiline queue. Here we generalize Martin's ideas \cite{Martin} by adding parameters
$q$ and $x_1,\ldots ,x_n$.
\begin{definition}\label{def:wt}
Given a multiline queue $Q$, we let 
$m_i$ be the number of balls in column $i$.
We define the \emph{$x$-weight} of $Q$ to be 
$\wt_x(Q) = x_1^{m_1} x_2^{m_2} \dots x_n^{m_n}$.


We also define the \emph{$q,t$-weight} of $Q$ by associating a weight to 
each nontrivial pairing $p$ of balls.
These weights are computed in order as follows.  
Consider the nontrivial pairings between rows
 $r$ and $r-1$.  We read the balls in row $r$
in decreasing order of their label
(from $L$ to $r$); within a fixed label, we read the 
 balls from right to left.  As we read the balls
in this order, we imagine placing the strands pairing the balls
one by one.  The balls that have not yet been matched in row $r-1$
are considered  \emph{free}. If pairing $p$ matches ball $b$ in row $r$
and column $c$ to ball $b'$ in row $r-1$ and column $c'$, then 
the free balls in row $r-1$ and 
columns $c+1, c+2,\dots, c'-1$  (indices 
considered modulo $n$) 
are considered \emph{skipped}. Note that the balls
which are trivially paired between rows $r$ and $r-1$
are not considered free.  Let $i$ be the label of balls
$b$ and $b'$.  
We then associate to pairing $p$ the weight
$$
\wt_{q,t}(p) = \begin{cases}
\frac{(1-t) t^{\# \skipped}}{1-q^{i-r+1}t^{\# \free}}\cdot q^{i-r+1}
&\mbox {if $c'<c$}\\
\frac{(1-t) t^{\# \skipped}}{1-q^{i-r+1}t^{\# \free}}
&\mbox{if $c'>c$}.
\end{cases}$$
Note that the extra factor $q^{i-r+1}$ appears precisely when 
the strand connecting $b$ to $b'$ wraps around the cylinder.

Having associated a $q,t$-weight to each nontrivial pairing of balls,
we define  the $q,t$-weight of the multiline queue $Q$ to be 
$$\wt_{q,t}(Q) = \prod_p \wt_{q,t}(p),$$
where the product is over all nontrivial pairings of balls in $Q$.

Finally the \emph{weight} of $Q$ is defined to be 
$$\wt(Q) = \wt_{x}(Q) \wt_{q,t}(Q).$$
\end{definition}

\begin{example}
In \cref{fig:MLQ_example}, 
the $x$-weight of the multiline queue 
$Q$ is 
$x_1 x_2^2 x_3 x_4 x_5 x_6^2 x_7 x_8$.

The weight of the unique pairing between row $3$ and row $2$ is 
$\frac{(1-t)t}{1-qt^4}$.  The weight of the pairing of balls labeled
$3$ between row $2$ and $1$ is 
$\frac{(1-t)}{1-q^2 t^5}$, and the weights of the pairings of balls
labeled $2$ are 
$\frac{(1-t) t^2}{1-qt^3} \cdot q$ and 
$\frac{1-t}{1-qt^2}$.  
Therefore 
$$\wt(Q) = 
x_1 x_2^2 x_3 x_4 x_5 x_6^2 x_7 x_8
\cdot \frac{(1-t)t}{1-qt^4}
\cdot \frac{(1-t)}{1-q^2 t^5}
\cdot \frac{(1-t) t^2}{1-qt^3} \cdot q
\cdot \frac{1-t}{1-qt^2}.  $$
\end{example}


We now define the weight-generating function for multiline queues
of a given type, as well as the \emph{combinatorial partition function}
for multiline queues.
\begin{definition}\label{def:Fmu}
Let $\mu = (\mu_1,\dots, \mu_n) \in \{0,1,\dots, L\}^n$ be a 
composition with largest part $L$.  
Set 
$$F_{\mu} = F_{\mu}(x_1,\dots,x_n; q, t)  = F_{\mu}({\bf x}; q, t) 
 = \sum_Q \wt(Q),$$ where the sum is over all
$L \times n$ multiline queues of type $\mu$.

Let $\lambda = \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n \geq 0$
be a partition with $n$ parts and largest part $L$.
We set 
$$Z_{\lambda} = Z_{\lambda}(x_1,\dots,x_n; q, t) = 
Z_{\lambda}({\bf x}; q, t) = \sum_{\mu} F_{\mu}(x_1,\dots,x_n; q, t),$$
where the sum is over all distinct compositions $\mu$ obtained by 
permuting the parts of $\lambda$. We call 
$Z_{\lambda}$ the \emph{combinatorial partition function}.
\end{definition}

\begin{remark} Recently Aas-Grinberg-Scrimshaw \cite{AasGrinbergS} studied
	multiline queues in the case that $t=0$, putting in ``spectral weights"
	(which correspond to our $x$-weight); they then gave
	a connection to tensor products of KR-crystals.
\end{remark}


\subsection{The main result}

The goal of this article is to show that with the refined statistics given
in \cref{def:wt}, we can use multiline queues to give formulas for 
Macdonald polynomials.

\begin{prop}\label{prop:nonsymmetric}
Let $\lambda$ be a \emph{partition}.
Then the nonsymmetric Macdonald polynomial $E_{\lambda}(\mathbf{x}; q, t)$ is equal to the quantity $F_{\lambda}(\mathbf{x}; q, t)$ from \cref{def:Fmu}.
\end{prop}

\begin{theorem}\label{thm:main}
Let $\lambda$ be a partition.
Then the symmetric Macdonald polynomial $P_{\lambda}(\mathbf{x}; q, t)$ is equal to the quantity $Z_{\lambda}(\mathbf{x}; q, t)$ 
from \cref{def:Fmu}.
\end{theorem}

See \cref{fig:E} for an example illustrating \cref{prop:nonsymmetric}.
\begin{figure}[!ht]
  \centerline{\includegraphics[width=\linewidth]{MLQ_221100.pdf}}
\centering
\caption{The generating function for the multiline queues of type 
$(2,2,1,1,0,0)$ give an expression for the nonsymmetric Macdonald 
polynomial $E_{(2,2,1,1,0,0)}({\mathbf x}; q, t)$}
\label{fig:E}
 \end{figure}



\section{The Hecke algebra and its connection to ASEP and Macdonald polynomials}

To explain the connection between the ASEP and Macdonald polynomials, and explain how we 
prove \cref{prop:nonsymmetric} and \cref{thm:main},  we need to introduce 
the Hecke algebra and recall some notions from
\cite{KasataniTakeyama} and
Cantini-deGier-Wheeler \cite{CGW}.

\begin{definition}
The \emph{Hecke algebra} of type $A_{n-1}$ is the algebra with generators $T_i$ for $1 \leq i \leq n-1$
and parameter $t$
which satisfies the following
relations:
\begin{equation}\label{Hecke}
(T_i-t)(T_i+1)=0, \qquad T_i T_{i \pm 1} T_i = T_{i \pm 1} T_i T_{i \pm 1}, \qquad
T_i T_j = T_j T_i \text{ when } |i-j|>1.
\end{equation}
\end{definition}

There is an action of the Hecke algebra on polynomials $f(x_1,\dots,x_n)$ which is defined as follows:
\begin{equation}\label{Heckeaction}
T_i=t-\frac{t x_i-x_{i+1}}{x_i-x_{i+1}}(1-s_i) 
\text{ for }1 \leq i \leq n-1,
\end{equation}
% Our convention for $T_i$ is same as Marshall

where $s_i$ acts  by
\begin{equation}\label{action1}
s_i f(x_1,\ldots, x_i,x_{i+1},\ldots,x_n):=f(x_1,\ldots, x_{i+1},x_{i},\ldots,x_n).
\end{equation}  One can check that the operators 
\eqref{Heckeaction} satisfy the relations \eqref{Hecke}.

We also define the shift operator $\omega$ via $(\omega f)(x_1,\dots,x_n) = f(q x_n,x_1,\dots, x_{n-1})$.
Given a composition $\mu = (\mu_1,\dots,\mu_n)$, we let $|\mu|:=\sum \mu_i$ and define $s_i \mu := s_i (\mu_1,\dots,\mu_n) = (\mu_1,\dots, \mu_{i+1},\mu_i,\dots,\mu_n)$ for $1 \leq i \leq n-1$.

The following notion of \emph{qKZ family} was introduced in 
\cite{KasataniTakeyama}, also explaining the relationship of such 
polynomials to nonsymmetric Macdonald polynomials.
We use the conventions of 
	\cite[Definition 2]{CGW-arxiv}, also 
 \cite[Section 1.3]{CGW},  
and \cite[(23)]{CGW}.

\begin{definition}\label{f-def} 
Fix a partition $\lambda = (\lambda_1,\dots,\lambda_n)$.
	We say that a family 
	$\{f_{\mu=  \lambda \circ \sigma} \}_{\sigma
\in S_n}$ 
	of homogeneous 
	degree $|\lambda|$ 
	polynomials in $n$ variables 
	$\mathbf{x} = (x_1,\dots,x_n)$, with coefficients which are rational functions of 
	$q$ and $t$, is a \emph{qKZ family} if they satisfy 
	\begin{align}
T_i f_{\mu}(\mathbf{x}; q,t) &= f_{s_i \mu} (\mathbf{x};q,t),
\text{ when }\mu_i > \mu_{i+1}, \label{firstproperty}\\
	T_i f_{\mu}(\mathbf{x}; q,t) &= t f_{\mu}(\mathbf{x}; q,t), \text{ when }\mu_i = \mu_{i+1}, \label{secondproperty}\\
q^{\mu_n} f_{\mu}(\mathbf{x}; q,t)
&= 
		f_{\mu_n,\mu_1,\dots,\mu_{n-1}}(q x_n,x_1,\dots,x_{n-1}; q,t).  \label{thirdproperty}
\end{align}
\end{definition}

%\begin{remark}
%Note that \eqref{thirdproperty} can be rephrased as 
%\[ q^{\mu_n} f_{\mu}(\mathbf{x}; q,t) = (\omega f_{\mu_n,\mu_1,\dots,\mu_{n-1}})(\mathbf{x}; q,t). \]
%\end{remark}

The following lemma explains the relationship of the $f_{\mu}$'s to the ASEP.
\begin{lemma}\label{ASEP-f}
	\cite[Corollary 1]{CGW-arxiv}.
	Consider the polynomials $f_{\mu}$ from \cref{f-def}.
	When $q=x_1=\dots=x_n=1$, 
 $f_{\mu}(1,\dots,1; 1, t)$ is proportional to the steady 
state probability that the multispecies ASEP is in state 
$\mu$.
\end{lemma}


As we will explain in 
\cref{Elemma} and 
	\cref{lem:Macdonald}, 
the polynomials $f_{\mu}$ are also related to  Macdonald polynomials.
We first quickly review the relevant definitions.

\begin{definition}\label{def:Macdonald}
Let $\langle \cdot, \cdot \rangle$ denote the 
Macdonald inner product on power sum symmetric functions 
\cite[Chapter VI, (1.5)]{Macdonald}, where $<$ denotes
the dominance order on partitions.  
Let $\lambda$ be a partition.
	The (symmetric) \emph{Macdonald polynomial}
$P_{\lambda}(x_1,\dots,x_n; q, t)$ is the unique homogeneous
symmetric polynomial in $x_1,\dots, x_n$ which satisfies $\langle P_{\lambda}, P_{\mu}\rangle =0, \ \lambda \neq \mu$ and
\[
P_{\lambda}(x_1,\dots,x_n; q, t) = m_{\lambda}(x_1,\dots,x_n)+
\sum_{\mu< \lambda} c_{\lambda, \mu}(q,t) m_{\mu}(x_1,\dots,x_n).
\]
\end{definition}
	
	
The following definition can be found in 
\cite{MacdonaldBourbaki} (also \cite{Marshall} for a nice 
exposition).
\begin{definition}\label{def:nonsymmetric}
For $1 \leq i \leq n$, define the \emph{$q$-Dunkl} or \emph{Cherednik 
operators} \cite{Cherednik1, Cherednik2} by 
$$Y_i = T_i^{-1} \dots T_{n-1}^{-1} \omega T_1 \dots T_{i-1}.$$
%Our convention differs from Marshall in that he would replace
% each T_i by T_i^{-1} and vice-versa


The Cherednik operators commute pairwise, and hence possess a set of 
simultaneous eigenfunctions,  which are (up to scalar)
	the \emph{nonsymmetric Macdonald polynomials}.  We index
	the nonsymmetric Macdonald polynomials $E_{\mu}(\mathbf{x}; q, t)$ by 
compositions $\mu$ so that 
	$$E_{\mu}(\mathbf{x}; q, t) = \mathbf{x}^{\mu} + \sum_{\nu < \mu} 
	b_{\mu \nu} \mathbf{x}^{\nu}.$$

	In particular, when $\lambda = (\lambda_1 \geq  \dots
	\geq \lambda_n \geq 0)$ is a partition,  
 we have that for $1 \leq i \leq n$, 
	\begin{equation}\label{eigenfunction}
Y_i E_{\lambda} = y_i(\lambda) E_{\lambda}
\end{equation}
where 
\[
y_i(\lambda) =
q^{\lambda_i}t^{\#\{j<i| \lambda_j=\lambda_i\}- \#\{j>i| \lambda_j=\lambda_i\}}.
\]
\end{definition}

In the following \cref{Elemma,lem:Macdonald}, let $\{f_{\mu=  \lambda \circ \sigma} \}_{\sigma
\in S_n}$ be a set of homogeneous degree $|\lambda|$ polynomials as in \cref{f-def}. Note that \cref{Elemma} below essentially appears in \cite[Section 3.3]{KasataniTakeyama}. We thank Michael Wheeler for his explanations.

\begin{lemma} \label{Elemma}
Let $\lambda = (\lambda_1,\dots,\lambda_n)$ be a partition. Then $f_{\lambda}$ is a scalar multiple of the nonsymmetric Macdonald polynomial
$E_{\lambda}$.
\end{lemma}


\begin{lemma}[{\cite[Lemma 1]{CGW-arxiv}}]\label{lem:Macdonald}
Let $\lambda$ be a partition.  Then the  Macdonald polynomial $P_{\lambda}(x_1,\dots,\linebreak x_n;q,t)$ is a scalar multiple of 
\[
\sum_{\mu} f_{\mu}(x_1,\dots,x_n;q,t),
\]
where $\mu$  ranges over all distinct compositions which can be obtained by permuting the parts of $\lambda$.
\end{lemma}


The strategy of our proof of \cref{thm:main} is very simple.  
Our main task is to show that the $F_{\mu}$'s 
satisfy the following properties.

\begin{theorem}\label{thm:123}
\begin{align}
\label{a} T_i F_{\mu}(\mathbf{x}; q,t) &= F_{s_i \mu} (\mathbf{x};q,t),
\text{ when }\mu_i > \mu_{i+1},\\
\label{b} T_i F_{\mu}(\mathbf{x}; q,t) &= t F_{\mu}(\mathbf{x}; q,t), \text{ when }\mu_i = \mu_{i+1},\\
q^{\mu_n} F_{\mu}(\mathbf{x}; q,t)
&= 
\label{c} F_{\mu_n,\mu_1,\dots,\mu_{n-1}}(q x_n,x_1,\dots,x_{n-1}; q,t). 
\end{align}
\end{theorem}

We prove \eqref{c} directly using multiline queues. We prove \eqref{b} by showing $F_{\mu}$ is symmetric in $x_i$ and $x_{i+1}$ when $\mu_i=\mu_{i+1}$. Finally we prove \eqref{a} using multiline queues by induction on the number of rows.

Next, we verify the following lemma by comparing the coefficients of $x^{\lambda}$.
\begin{lemma}\label{monic}
For any partition $\lambda$, 
$$F_{\lambda}(\mathbf{x};q,t) = E_{\lambda}(\mathbf{x}; q, t),$$ where $E_{\lambda}$ is the nonsymmetric Macdonald polynomial.
\end{lemma}


Then  \cref{thm:123},   \cref{monic}, 
and \cref{lem:Macdonald} implies \cref{thm:main}, 
that our sum over multiline queues equals the symmetric Macdonald 
polynomial $P_{\lambda}$.  



\section{Comparisons  to other 
 Macdonald polynomial formulas}\label{sec:comparison}



In this paper we 
 used multiline queues to give a new combinatorial formula for the Macdonald polynomial $P_{\lambda}$ 
 and the nonsymmetric Macdonald polynomial
 $E_{\lambda}$ when $\lambda$ is a partition.  
 We note that these new combinatorial formulas are quite different from the combinatorial formulas
 given by Haglund-Haiman-Loehr \cite{HHL1, HHL2, HHL3}, or 
 Ram-Yip \cite{RamYip}, or Lenart \cite{Lenart}.

While it is not obvious combinatorially, 
we show algebraically in \cref{prop:PB} that the polynomials $F_{\mu}$ (for $\mu$ an arbitrary composition) are equal to certain \emph{permuted basement Macdonald polynomials} $E_{\alpha}^{\sigma}({\mathbf x}; q, t)$, which were introduced in \cite{thesis} and further studied in \cite{A} as a generalization of nonsymmetric Macdonald polynomials (where $\sigma \in S_n$ and $\alpha$ is a composition with $n$ parts). They have the property that the nonsymmetric Macdonald polynomial $E_{\mu}$ is equal to $E_{\rev(\mu)}^{w_0}$, where $\rev(\mu)$ denotes the reverse composition $(\mu_n, \mu_{n-1},\dots,\mu_1)$ of $\mu=(\mu_1,\dots,\mu_n)$ and $w_0=(n,\ldots,2,1)$.  

\begin{prop}\label{prop:PB}
For $\mu=(\mu_1,\ldots,\mu_n)$, define $\inc(\mu)$ to be the sorting of the parts of $\mu$ in increasing order. Then
\[F_{\mu}=E_{\inc(\mu)}^{\sigma}
\]
where $\sigma \mu = \inc(\mu)$, i.e. 
$\sigma$ is any permutation such that 
	$\mu_{\sigma(1)} \leq \mu_{\sigma(2)} \leq 
	\dots \leq \mu_{\sigma(n)}$.
\end{prop}




The permuted basement Macdonald polynomials can be described 
combinatorially using \emph{nonattacking fillings} of certain diagrams 
\cite{thesis, A}\footnote{Note however that \cite{thesis} cites
personal communication with Haglund for their introduction.},
which we call \emph{permuted basement tableaux}.  (Note that 
these permuted basement tableaux generalize the nonattacking fillings from 
\cite{HHL3}).
In light of this, one may wonder if there is a bijection between 
multiline queues and these permuted basement tableaux.  %As we explain in \cref{rem:queue}, 
This is the case when the compositions have distinct parts. However, for general compositions, the number of permuted basement tableaux is  different than the number of MLQs (there are more permuted basement tableaux). We conjecture that there is a way to group permuted basement tableaux so that the weight in a group equals the weight of one MLQ.



\acknowledgements{We would like to thank James Martin, for sharing an early draft of his paper \cite{Martin} with us. We would also like to thank Mark Haiman for several interesting conversations about Macdonald polynomials, and Jim Haglund for telling us about permuted basement Macdonald polynomials. Finally we would like to thank Jan de Gier and Michael Wheeler for useful explanations of their results \cite{CGW, CGW-arxiv}, and Sarah Mason for helpful comments on our paper.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
%\printbibliography

%\bibliographystyle{alpha}
%\bibliography{bibliography}
\printbibliography

\end{document}
