% LaTeX Article Template - using defaults
% LaTeX file for a 22 page document
\documentclass[12pt]{amsart}

%\usepackage{amsmath, latexsym, amssymb}
\usepackage{graphicx}

%% The lines between the two rows of %'s are more or less compulsory.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\textwidth}{6in}
\setlength{\textheight}{8.7in}
%\setlength{\topmargin}{0.5in}
%\setlength{\headsep}{0pt}
%\setlength{\headheight}{0pt}
%\setlength{\oddsidemargin}{0pt}
%\setlength{\evensidemargin}{0pt}
\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\makeatother
%\pagestyle{plain}

%\newcounter{example}

\newtheorem{thm}{Theorem}
\newtheorem{conj}{Conjecture}
\newtheorem{defn}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\theoremstyle{remark}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}

\newcommand{\qbinom}[2]{{\genfrac{[}{]}{0pt}{}{#1}{#2}}_q}
\newcommand{\zbinom}[2]{{\genfrac{[}{]}{0pt}{}{#1}{#2}}_t}
\newcommand{\btop}[2]{{\genfrac{}{}{0pt}{}{#1}{#2}}}

%\newenvironment{proof}{\medskip\noindent
%{\it Proof.\ }}{\hfill \mbox{$\Box$}\medskip}
%\newenvironment{ex}{}{\stepcounter{example} 
%\begin{center} {\bf Example \theexample} \end{center} }

 
\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc J. Haglund}
\vskip7pt
\centerline{Department of Mathematics}
\centerline{University of Pennsylvania}
\centerline{Philadelphia, PA 19104-6395}
\centerline{\tt jhaglund@math.upenn.edu}
}

\title{The Genesis of the Macdonald Polynomial Statistics}

\author[J. Haglund]{\box\Adr}%\\

\date{}
%\small MR Subject Classifications: 05A15, 05E05 }     

\dedicatory{Dedicated to Adriano Garsia}

\begin{abstract}
Recently M. Haiman, N. Loehr and the author [{\it J. Amer. Math. Soc.} {\bf 18}
(2005), 735--761]
proved that for $\mu$ a partition of
$n$, the modified
Macdonald polynomial ${\tilde H}_{\mu}[z_1,\ldots ,z_n;q,t]$ can be expressed 
as a sum of monomials in the $z_i$ times 
certain nonnegative integral powers of $q,t$ with direct combinatorial
descriptions (i.e. statistics).  These powers
are generalizations of the classical permutation 
statistics $\text{maj}$ and $\text{inv}$.
The result 
was first conjectured by the author 
[{\it Proc. Nat. Acad. Sci. U.S.A.} {\bf 101} (2004), 16127--16131], and was partially motivated by a
conjectured formula for the character of the space of diagonal
harmonics [{\it Duke J. Math.} {\bf 126} (2005), 195--232].
Beyond giving
a long-sought after 
combinatorial formula for Macdonald polynomials, this result has many
nice corollaries, including a simple proof of 
Lascoux and Sch\"utzenberger's formula,
involving the statistic $\text{cocharge}$,
for Hall-Littlewood polynomials.  
In this paper we describe the sequence of experimental
steps and {\sl Maple} calculations which led
to the discovery of these Macdonald polynomial statistics.


\medskip
\medskip
\noindent
{\sc Riassunto.}
In un recente lavoro in collaborazione con M. Haiman, N. Loehr 
[{\it J. Amer. Math. Soc.} {\bf 18}
(2005), 735--761] dimostriamo che per una partizione di $n$, $\mu$,
il polinomio di Macdonald modificato ${\tilde H}_{\mu}[z_1,\ldots ,z_n;q,t]$ puo' essere espresso come un polinomio
nelle variabili $z_i$ i cui cofficienti sono  potenze non negative di $q, t$. Questo risultato ha una diretta interpretazione
combinatoria (o meglio statistica). Gli esponenti dei coefficienti sono una generalizzazione delle classiche statistiche di
permutazione  $\text{maj}$ e $\text{inv}$.
L'ipotesi di un tale risultato fu avanzata in 
[{\it Proc. Nat. Acad. Sci. U.S.A.} {\bf 101} (2004), 16127--16131] 
e in parte fu motivata dalla formula, in forma di congettura,
per i caratteri dello spazio delle armoniche diagonali 
[{\it Duke J. Math.} {\bf 126} (2005), 195--232].
Questo risultato non solo da' un'interpretazione combinatoria, cercata da lungo tempo, dei polinomi di Macdonald, ma permette
di derivare anche altri risultati rilevanti. Per esempio e' possibile dare una dimostrazione semplificata della formula di
Lascoux and Sch\"utzenberger riguardante la statistica $\text{cocharge}$ per i polinomi di Hall-Littlewood.
In questo articolo descriviamo la sequenza di passaggi sperimentali e di calcoli fatti utilizzando {\sl Maple} che portano alla
scoperta della statistica dei polinomi di Macdonald.
\end{abstract}

\maketitle

%\newpage

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54A \rms (2006), Article~B54Ao\hfill}
\def\thepage{}
%
%


\section{Introduction}

Given a sequence $\mu = (\mu _1, \mu_2,\ldots )$ of nonincreasing,
nonnegative integers with $\sum_i \mu _i =n$, we say
$\mu$ is a partition of $n$, denoted by either $|\mu|=n$ or $\mu \vdash n$. 
By adding or subtracting parts of size $0$ if necessary, we will always
assume partitions of $n$ have exactly $n$ parts.
We let $n(\mu) = \sum _{i}(i-1)\mu _i$,
and if $\lambda$ is another partition, set ${\tilde K}_{\lambda, \mu}(q,t) = 
t^{n(\mu)}K_{\lambda ,\mu}(q,1/t)$, 
where $K_{\lambda, \mu}(q,t)$ is Macdonald's $q,t$-Kostka
polynomial \cite[p.354]{Macdonald}.  We call 
${\tilde H}_{\mu}[Z;q,t] =
\sum _{\lambda \vdash |\mu|} s_{\lambda} {\tilde K}_{\lambda, \mu}(q,t)
$ the
modified Macdonald polynomial, where $s_{\lambda}=s_{\lambda}[Z]$ is the
Schur function, the sum is over all $\lambda \vdash |\mu|$, and $Z=z_1,\ldots ,z_n$.  
The ${\tilde H}_{\mu}[Z;q,t]$ can be easily transformed by a plethystic substitution
into Macdonald's original symmetric functions $P_{\mu}[Z;q,t]$.  Macdonald
defined the $P_{\mu}$ in terms of orthogonality with respect to a scalar
product, and conjectured $K_{\lambda ,\mu}(q,t) \in \mathbb N[q,t]$ 
\cite [p. 355]{Macdonald}.  (From their definition, all one can infer is that
the $K_{\lambda ,\mu}(q,t)$ are rational functions in $q,t$).
This conjecture in turn led Garsia and Haiman to the ``$n!$ conjecture" \cite{GaHm93},
which was proved by 
Haiman in $2000$ \cite{Hai01}.
This result implies that ${\tilde K}_{\lambda, \mu}(q,t) \in \mathbb N [q,t]$, and moreover that
${\tilde H}_{\mu}[X;q,t]$ is the character of a certain $S_n$-module $V(\mu)$, and thus gives a
representation-theoretical interpretation for the coefficients of ${\tilde K}_{\lambda,\mu}(q,t)$.
Macdonald also posed the problem of finding a combinatorial
rule to describe the $K_{\lambda ,\mu}(q,t)$, which is still open.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL J. HAGLUND}{\SMALL THE GENESIS OF THE MACDONALD POLYNOMIAL STATISTIC}
%
%

Recently the author introduced a conjectured combinatorial formula for
the coefficient of a monomial in ${\tilde H}_{\mu}[Z;q,t]$ \cite{Hag04b}.  The formula,
described in Section \ref{formula}, is manifestly in $\mathbb N [q,t,z_1,\ldots ,z_n]$.
Soon after its introduction, the conjecture was proved by M. Haiman, N. Loehr and the
author:  
the formula took 
much longer to find than to prove.
Some comments on the surprisingly short and elegant proof are made in Section \ref{proof}.
As a corollary they obtain a new, short proof of a
famous result of Lascoux and Sch\"utzenberger, namely that the coefficients in the Schur
function expansion of
the Hall-Littlewood polynomial ${\tilde H}_{\mu}[Z;0,t]$ 
can be expressed as a sum, over semi-standard Young tableaux $W$, of $q$ to a statistic known
as $\text{cocharge}(W)$.  This new proof is discussed in more detail in Section \ref{cocharge}.
Also, since the matrix expressing the Schur basis in terms of the
monomial basis is upper unitriangular, another consequence is a new proof that
the ${\tilde K}_{\lambda ,\mu}(q,t) \in Z[q,t]$.  
In addition a simple formula for
the ${\tilde K}_{\lambda, \mu}(q,t)$ is obtained when $\mu$ has two columns.
It is hoped that further refinements will
result in combinatorial formulas for the ${\tilde K}_{\lambda, \mu}(q,t)$ for general $\mu$.

The idea for this article was suggested by A. Garsia, who thought it would be
beneficial to have a detailed description of the sequence of steps which led the author to the
discovery of the formula.  In Section \ref{diagonal} we overview
the pioneering work of Garsia, Haiman and others on the $n!$ conjecture, the space of diagonal
harmonics $DH_n$, and the $q,t$-Catalan numbers.  These numbers were defined by Garsia and Haiman
as a complicated sum of rational functions in $q,t$, which they conjectured simplified to
a polynomial in $\mathbb N [q,t]$ \cite{GaHm96b}. 
We then discuss a series of discoveries by the author, M. Haiman and others
involving combinatorial formulas for the $q,t$-Catalan numbers and other sequences connected
to $DH_n$, which culminated in the introduction of the ``shuffle conjecture" by
Haglund, Haiman, Loehr, Remmel and Ulyanov \cite{HHLRU05},
which gives a combinatorial formula for the character of $DH_n$.

In Section \ref{connection} we discuss how various special cases of the 
shuffle conjecture led the author
to suspect an analogous combinatorial formula for the monomial expansion of
${\tilde H}_{\mu}[X;q,t]$ could be found. We then include an explanation of the
various stages and {\sl Maple} calculations
in the experimental process which resulted in the discovery of the statistics.

\section {The Formula} 
\label{formula}

We assign (row,column)-coordinates to squares in the first quadrant,
obtained by permuting the $(x,y)$ coordinates of the upper right-hand corner of the
square, so the lower left-hand square has coordinates $(1,1)$, the
square above it $(2,1)$, etc..
For a square $w$, we call the first coordinate of $w$ the {\it row value} of $w$, 
denoted $\text{row}(w)$, and
the second coordinate of $w$ the {\it column value} of $w$, denoted $\text{col}(w)$.
Given $\mu \vdash n$, we let $\mu$ also stand for the Ferrers diagram of
$\mu$ (French convention), consisting of the set of $n$ squares with 
coordinates $(i,j)$, with $ 1\le i \le n$, $1\le j \le \mu _i$.

Let $T$ be a finite set of squares in the first quadrant.  A subset of
squares of $T$ consisting of all those $w \in T$ with a given row value 
is called a row of $T$, and a
subset of squares of $T$ consisting of all those $w \in T$ with a given column value 
is called a column of $T$.
Furthermore, we let $T(i)$ denote the $i$th square of $T$ encountered
if we read across rows from left to right, starting with the squares of largest
row value and working downwards.   
Given a square $w \in T$, 
define the
leg of $w$, denoted $\text{leg}(w)$, to be the number of squares in $T$ 
which are strictly above and in the same column 
as $w$, and the arm of $w$, denoted $\text{arm}(w)$, 
to be the number of squares in $T$ strictly to the right and in
the same row as $w$.  
Also, if $w$ has coordinates $(i,j)$, we let $\text{south}(w)$ denote the
square with coordinates $(i-1,j)$.

A word $\sigma$ of length $n$ in an alphabet $\mathcal A$ is a linear sequence
$\sigma _1 \sigma _2 \cdots \sigma _n$, with $\sigma _i \in \mathcal A$.
Note that repeats are allowed.  If the letter $i$ occurs
$\alpha _i$ times in $\sigma$, for each 
$i\ge 1$, we say $\sigma$ has content $\alpha$, denoted $\text{content}(\sigma) = \alpha$.
We call a pair
$(\sigma ,T)$, where $\sigma $ is a word of positive integers and $T$ is a
set of squares in the first quadrant, a {\it filling}.
We represent $(\sigma ,T)$ geometrically by placing  
$\sigma _i$ in square $T(i)$, for $1\le i \le n$.
For $w \in T$, we let $\sigma (w)$ denote the element 
of $\sigma$ placed in square $w$, and we call $\sigma _1 \cdots \sigma _n$ the
{\it reading word} of $(\sigma ,T)$.  A
{\it descent} of $(\sigma, T)$ is a square $w \in T$,
with $\text{south}(w) \in T$ 
and $\sigma (w) > \sigma (\text{south}(w))$.   

Let $\text{Des}(\sigma, T)$ denote the set
of all descents of $(\sigma, T)$.  For partitions $\mu$,   
define a generalized major index statistic $\text{maj}(\sigma ,\mu)$ via 
\begin{align}
\text {maj} (\sigma,\mu) = \sum_{w \in \text{Des}(\sigma,\mu)}
(1+\text{leg}(w)).
\end{align}
An {inversion} of $(\sigma ,T)$ is a pair of squares 
$(a,b)$ with $a,b \in T$, $\sigma (a)>\sigma (b)$,
and either
\begin{align}
\begin{cases} \text{$\text{row}(a)=\text{row}(b)$ and 
$\text{col}(a)<\text{col}(b)$, $\quad$ or} \\
\text{ $\text{row}(a)=\text{row}(b)+1$ and
$\text{col}(a)>\text{col}(b)$ }.
\end{cases}
\end{align}
Let $\text{Inv}(\sigma, T)$ denote the set of all inversions of $(\sigma,T)$, and
define the inversion statistic $\text{inv}(\sigma ,T)$ via
\begin{align}
\text {inv} (\sigma,T) = |\text{Inv}(\sigma, T)|
- \sum_{w \in \text{Des}(\sigma,T)} \text{arm}(w),
\end{align}
where $|T|$ denotes the cardinality of a set $T$.  For example, if
$(\sigma ,\mu)$ is the filling in Figure \ref{filling}, 
then representing squares by their coordinates,
\begin{align}
\notag
\text{Des}(\sigma ,\mu) &= \{(2,1),(4,2),(2,2)\}, \\
\text{Inv}(\sigma ,\mu) &= 
\{((3,1),(3,2)),((2,2),(2,3)),((2,2),(1,1)),((2,3),(1,1)),((2,3),(1,2))\}, 
\end{align}
so
$\text{maj}(\sigma ,\mu) = 3+1+3=7$,
$\text{inv}(\sigma ,\mu) = 5-(2+0+1)=2$.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=.5]{filling2.pdf}
\caption{
A filling of the partition $(3,3,2,2)$ by the word $2221353114$.}
\label{filling}
\end{center}
\end{figure}

Note that, if $1^n$ denotes a column of $n$ cells, then 
\begin{align}
\text{maj}(\sigma ,1^n) = \sum_{i \in \text{Des}(\sigma ,1^n)}i,
\end{align}
the usual major index statistic on the word $\sigma$, while  
\begin{align}
\text{inv}(\sigma ,(n)) = \sum_{ \btop{ 1\le i < j \le n }{ \sigma _i > \sigma _{j} } }1,
\end{align}
the usual inversion statistic.  

For $\mu \vdash n$, define
\begin{align}
\label{Cdef}
{\tilde C}_{\mu}[Z;q,t] = 
\sum_{\sigma} t^{\text{maj}(\sigma ,\mu)}
q^{\text{inv}(\sigma ,\mu)} z^{\sigma},
\end{align}
where 
$z^{\sigma} = \prod_{i=1}^n z_{\sigma _i}$ is the ``weight" of $\sigma$  
and the sum is over all words $\sigma$ of $n$ positive integers satisfying $1\le \sigma _i \le n$ 
for $1\le i \le n$.  The following result was conjectured by the author \cite{Hag04b} and
proved by Haglund, Haiman, Loehr \cite{HHL05b}).
\begin{thm} 
For all partitions $\mu$,
\label{main}
\begin{align}
{\tilde C}_{\mu}[Z;q,t] = 
{\tilde H}_{\mu}[Z;q,t].
\end{align}
\end{thm}

Given a set $T$ of squares and a subset $S\subseteq T$, define
\begin{align}
\label{Fdef}
F_{T}[Z;q,S] = \sum_{\btop {\sigma}{\text{Des}(\sigma ,T) = S}}
q^{\text{inv}(\sigma ,T)}z^{\sigma}.
\end{align}
In \cite{Hag04b} the following result is obtained.
\begin{thm}
\label{symmetric}
For all $S,T$,
$F_{T}[Z;q,S]$ is a symmetric function in the $z_i$.
\end{thm}
Given $S \subseteq \mu$, let 
\begin{align}
P(S) = \sum _{w \in S} (1+\text{leg}(w)).
\end{align}
Note that by the definition of $\text{maj}(\sigma ,\mu)$, 
\begin{align}
\label{blocks}
{\tilde C}_{\mu}[Z;q,t] = \sum _{S \subseteq \mu}
t^{P(S)}F_{\mu}[Z;q,S].
\end{align}
In \cite{HHL05b} it is shown that the $F_T[Z;q,t]$ are special cases of 
polynomials introduced by Lascoux, Leclerc and Thibon \cite{LLT97}, commonly known as
LLT polynomials.  These are symmetric polynomials whose description involves a tuple
of arbitrary skew shapes and whose coefficients depend on
$q$.
It has been an open conjecture of theirs that the coefficients of
these polynomials when expanded in the Schur basis are in $\mathbb N [q]$.
Thus we now have the expansion of ${\tilde H}_{\mu}[Z;q,t]$ into
LLT polynomials, and furthermore understanding the positivity of the coefficients of the
${\tilde K}_{\lambda, \mu}(q,t)$ is reduced to understanding the special case of the positivity of LLT
polynomials (when each skew-shape in the tuple is a ribbon).

\begin{defn}
Given a word $\sigma$ of content $(\gamma _1,\gamma _2,\ldots )$,
construct a permutation $\sigma ^{\prime}$, the {\it standardization} of $\sigma$,
by replacing the $\gamma_1$ $1$'s in
$\sigma $ by the numbers $1,\ldots ,\gamma _1$, the $\gamma _2$ $2$'s
in $\sigma$ by 
the numbers $\gamma _1 +1,\ldots ,\gamma _1+\gamma _2$, etc., in
such a way that, for $i<j$, $\sigma _i\le\sigma _j$ if and only if  
$\sigma ^{\prime} _i
<\sigma ^{\prime} _j$.  For example, if $\sigma =224123114$
then $\sigma ^{\prime}=458167239$.
\end{defn}

\begin{remark}  
\label{triples}
At first glance it may seem that $\text{inv}(\sigma, T)$ may not always
be nonnegative, but given a square $u \in \text{Des}(\sigma ,T)$, for each square
$v$ in the same row as $u$ and to the right of $u$, either $\sigma (u) > \sigma (v)$,
or $\sigma (v)>\sigma (\text{south}(u))$, or both.  Assume for the moment that
$\sigma$ has distinct entries.  If we adopt the convention that for a square 
$w \notin T$, $\sigma (w)=\infty$, it follows that $\text{inv}(\sigma ,T)$
equals the number of triples of 
squares $u,v,w$, where $u \in T$, $v \in T$, $\text{row}(u)=\text{row}(v)$,
$\text{col}(u)<\text{col}(v)$,  and $\text{south}(u)=w$, and if we draw
a circle through $u,v,w$, and read in the $\sigma$ values of $u,v,w$ 
in counterclockwise order around the circle, starting at the smallest 
value, then the three values form a strictly increasing sequence.  
If $\sigma$ has repeated entries, first standardize
then count triples
in $(\sigma ^{\prime},T)$ as above.  
\end{remark}

\section{The Proof}
\label{proof}

Let $p_k(Z) = \sum_i z_i^k$ be the $k$th power sum.  Given a real parameter
$w$, let $p_k[Z(1-w)] = \sum_i z_i^K(1-w^k)$ and $p_k[Z/(1-w)] = \sum_i z_i^k/(1-w^k)$.  These are
both special cases of plethystic notation, indicated by the square brackets around $Z(1-w)$ and
$Z/(1-w)$.  For an arbitrary symmetric function $F(Z)$, let $F[Z(1-w)]$ (respectively
$F[Z/(1-w)]$) be the result of first
expressing $F(Z)$ as a polynomial in the $p_k(Z)$, then replacing each $p_k(Z)$ by
$p_k[Z(1-w)]$ (respectively $p_k[Z/(1-w)]$). 

The polynomial ${\tilde H}_{\mu}[Z;q,t]$ can be defined \cite{Hai03a}
as the unique polynomial 
satisfying the following axioms, where $\lambda \le \mu$ refers to the dominance order
$\lambda _1 +\ldots +\lambda _i \le \mu _1 + \ldots + \mu _i -1$ for $1\le i \le n$:
\begin{itemize}
\item[(M1)] ${\tilde{H}}_{\mu}[Z(q-1)]=\sum_{\lambda\leq \mu ^{\prime}} a_{\lambda,\mu} m_{\lambda}
$ for some $a_{\lambda,\mu}\in \mathbb Q (q,t)$
\item[(M2)] ${\tilde{H}}_{\mu}[Z(t-1)]=\sum_{\lambda\leq \mu } a_{\lambda,\mu} m_{\lambda}
$ for some $a_{\lambda,\mu}\in \mathbb Q (q,t)$
\item[(M3)] The coefficient of $z_1^n$ in the expansion of ${\tilde H}_{\mu}[Z;q,t]$ into monomials
equals $1$.
\end{itemize}

We call a filling of $\mu$ by arbitrary nonzero integers a ``super filling".  We usually represent
negative letters, such as $-2,-4,-7$ by ``barred letters" ${\overline 2},{\overline 4},
{\overline 7}$.  
Assume the letters
satisfy the ordering
\begin{align}
\label{ordering1}
1<{\overline 1} < 2 <{\overline 2} <\cdots <n <{\overline n}.
\end{align}
Given a super filling $\sigma$, we define the standardization $\sigma ^{\prime}$
of $\sigma$ to be the unique
permutation satisfying $\sigma ^{\prime}_i<\sigma ^{\prime}_j$ whenever
$\sigma _i < \sigma _j$, or 
whenever $i<j$ and $\sigma _i=\sigma _j$ with $\sigma _i$ a positive letter, or 
whenever $i>j$ and $\sigma _i=\sigma _j$ with $\sigma _i$ a negative letter.
We then 
extend the definition of $\text{maj}$ and $\text{inv}$ to super fillings by
letting
$\text{maj}(\sigma ,\mu) = \text{maj}(\sigma ^{\prime},\mu)$ and 
$\text{inv}(\sigma ,\mu) = \text{inv}(\sigma ^{\prime},\mu)$.  
Furthermore,
we let $|\sigma|$ be the filling obtained by replacing each $\sigma _i$ by its
absolute value.

Using some general results about quasi-symmetric functions and the superization of
a symmetric function derived in \cite{HHLRU05},
one easily obtains the fact that
\begin{align}
\label{tri1}
{\tilde C}_{\mu}[Z(q-1);q,t] =
\sum_{\sigma}  (-1)^{m(\sigma)}q^{p(\sigma)+\text{inv}(\sigma, \mu)}
t^{\text{maj}(\sigma, \mu)} z^{|\sigma|} \\
\label{tri2}
{\tilde C}_{\mu}[Z(t-1);q,t] =
\sum_{\sigma}  (-1)^{m(\sigma)}q^{\text{inv}(\sigma, \mu)}
t^{p(\sigma)+\text{maj}(\sigma, \mu)} z^{|\sigma|} 
\end{align}
where the sum is over all super fillings $\sigma$ of $\mu$,
$m(\sigma)$ is the number of negative letters in $\sigma$, and
$p(\sigma)$ is the number of positive letters in $\sigma$.

We say two squares $u,v$ of a Ferrers shape attack each other if they are either in the
same row, or if $u$ is one row above $v$ and in a column strictly to the right of $v$.
Otherwise $u,v$ are said to be nonattacking.  We call a super filling $(\sigma, \mu)$ 
nonattacking if 
for all $u,v \in \mu$,
$|\sigma (u)|=|\sigma (v)|$ implies $u,v$ are nonattacking.  

The first step in the proof of Theorem \ref{main} involves the construction of a sign-reversing 
involution on super fillings of $\mu$ which cancels most of the terms in
(\ref{tri1}).  The involution looks for an attacking pair of squares containing $1$'s or ${\overline 1}$'s.
If more than one such pair exists, it chooses the last such pair in the reading word, and switches the
sign of the first element of the pair in the reading word.  One checks that the $q,t$-weights are preserved.
If no attacking pairs containing $1,{\overline 1}$'s exist, then you search for attacking pairs containing
$2,{\overline2}$'s, etc.  The fixed points are super fillings with no attacking pairs, which are easily seen
to satisfy the triangularity condition 
(M1).  

So far we have assumed (\ref{ordering1}) holds, but in fact (\ref{tri1}) and (\ref{tri2}) hold for
{\it any} fixed total ordering of the alphabet of positive and negative letters.  We now construct
a second involution assuming the
ordering
\begin{align}
\label{ordering2}
1<2<\cdots <n <{\overline n} < \cdots < {\overline 2} < {\overline 1}.
\end{align}
Search for the first occurrence of a $1$ or ${\overline 1}$ in the reading word, ignoring any such letters in the
bottom row.  If such a $1$, ${\overline 1}$ exists, then switch its sign.
If there is no such $1$ or ${\overline 1}$, look for the first occurrence of a $2$ or ${\overline 2}$, ignoring any
letters in the bottom two rows, etc.  As in the first involution, the $q,t$ weights are preserved.  The fixed points
are now super fillings with no $1$'s or ${\overline 1}$'s above the bottom row, no
$2$'s or ${\overline 2}$'s above the bottom two rows, etc..  Hence the weight $z^{|\sigma|}$ must
satisfy $\lambda _1 \le \mu _1$, $\lambda _1+\lambda _2 \le \mu_1+\mu_2$, etc., and (M2) is
satisfied.  The proof is completed by noting that if $\sigma$ is the filling of all $1$'s, 
$\text{inv}(\sigma ,\mu)=\text{maj}(\sigma ,\mu)=0$, which implies (M3).

\section{The Cocharge Formula}
\label{cocharge}

In this section we briefly highlight two consequences of Theorem \ref{main}, which are
described in more detail in \cite{HHL05b}.
The first is the following famous result of Lascoux and
Sch\"utzenberger, where
$SSYT(\lambda, \mu)$ denotes the set of
a semi-standard Young tableau of shape $\lambda$ and weight $\mu$, i.e. the set of
fillings
of $\lambda$ by $\mu _1$-$1$'s, $\mu _2$-$2$'s, etc.,
with entries that are weakly increasing across rows and strictly
increasing up columns.

\begin{thm}
\label{LS}
\begin{align}
{\tilde H}_{\mu}[Z;0,t] = \sum_{\lambda} s_{\lambda}
\sum_{T \in SSYT(\lambda,\mu)} t^{\text{cocharge}(\text{read}(T))},
\end{align}
where the statistic $\text{cocharge}$ is described (in the proof) below.
\end{thm}
\begin{proof}
We begin by describing the set of fillings with no inversions.  Let $M_i$ be an arbitrary
multiset of $\mu _i$ positive integers, for
$1\le i \le \mu ^{\prime}_1$, and consider those fillings of $\mu$ where the elements of
$M_i$ are placed in the $i$th row of $\mu$, in any arbitrary order, for each $i$ in the range
$1\le i \le \mu ^{\prime}_1$.  It turns out there is exactly one of these fillings with no inversions.
This
filling can be constructed by first filling the bottom row of $\mu$ with the elements
of $M_1$, in nondecreasing order left to right.  Then in square $(2,1)$, place the
smallest integer in $M_2$ which is strictly bigger than $\sigma _{{\mathbf M}}(1,1)$, if
it exists.  If all elements of $M_2$ are less than or equal to $\sigma_{{\mathbf M}}(1,1)$, then
place the smallest element of $M_2$ in $(2,1)$.  It is easy to see that this will
force any triple of squares of the form $\{(2,1),(2,j),(1,1)\}$, $j\ge 2$, to form a clockwise
circle in the sense of Remark \ref{triples}.  Next remove $\sigma _{{\mathbf M}}(2,1)$ from
$M_2$ to form $M_2 ^{\prime}$, and place the smallest element of
$M_2^{\prime}$ larger than $\sigma _{{\mathbf M}}(1,2)$ in square $(2,2)$, if it exists.  If not, 
place the smallest element of $M_2^{\prime}$ in square $(2,2)$.  Now iterate the
process, moving left to right, in each square of row two placing the
smallest remaining element larger than the element in the square just below, if it exists,
and otherwise placing the smallest remaining element in the square.  The same process is then
applied to row $3$, comparing elements of $M_3$ to elements in the second row of
$\sigma _{{\mathbf M}}$, then moving on to row $4$, etc..  If $\mu=5531$, $M_1 = \{1,1,3,6,7\}$,
$M_2 = \{1,2,4,4,5\}$,
$M_3 = \{1,2,3\}$, and
$M_4 = \{2\}$, then $\sigma _{{\mathbf M}}$ is the filling in Figure \ref{noinv}. 

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=.5]{noinv.pdf}
\caption{A filling with no inversions.
}
\label{noinv}
\end{center}
\end{figure}

We now construct a word associated to a filling $\sigma$ we call the $\text{cocharge}$ word
$\text{cword}(\sigma)$.  Initialize 
$\text{cword}(\sigma)$ to the empty string, then 
scan through the reading word of $\sigma$, starting
at the beginning.
Whenever a $1$ is encountered, adjoin the number of the row containing this $1$ to the left of 
$\text{cword}(\sigma)$.  After reaching the end of the reading word, scan through the
reading word again, from the beginning, this time looking for $2$'s.  
Whenever a $2$ is encountered, adjoin the row
number to the left of 
$\text{cword}(\sigma)$ as before.  After finishing the $2$'s, loop back and scan through the
reading word for $3$'s, etc.
For example, if $\sigma$ is the filling in Figure \ref{noinv}, 
$\text{cword}(\sigma) = 11222132341123$.

Next we translate the statistic $\text{maj}(\sigma ,\mu)$ into a statistic
on 
$\text{cword}(\sigma)$.  Note that $\sigma (1,1)$ corresponds to the rightmost
$1$ in 
$\text{cword}(\sigma)$ - denote this $1$ by $w_{11}$.  
If $\sigma (2,1)>\sigma (1,1)$, $\sigma (2,1)$
corresponds to the rightmost $2$ which is left of $w_{11}$, otherwise it corresponds to
the rightmost $2$ 
(in $\text{cword}(\sigma)$).  In any case denote this $2$ by $w_{12}$.  More generally, the
element in 
$\text{cword}(\sigma)$ corresponding to $\sigma (i,1)$ is the first $i$ encountered
when travelling left from $w_{1,i-1}$, looping around and starting at the beginning
of 
$\text{cword}(\sigma)$ if necessary.  To find the subword $w_{21}w_{22} \cdots
w_{2\mu^{\prime}_2}$ corresponding to the second column of $\sigma$,
we do the same algorithm on the word
$\text{cword}(\sigma)^{\prime}$ obtained by removing the elements $w_{11}w_{12}\cdots
w_{1\mu^{\prime}_1}$ from
$\text{cword}(\sigma)$, then remove $w_{21}w_{22}\cdots
w_{2\mu^{\prime}_2}$ and apply the same process to find
$w_{31}w_{32}\cdots w_{3\mu^{\prime}_3}$ etc..

Clearly $\sigma (i,j) \in \text{Des}(\sigma ,\mu)$ if and only if $w_{ij}$ occurs to the
left of $w_{i,j-1}$ in
$\text{cword}(\sigma)$.  Thus $\text{maj}(\sigma ,\mu)$ is transparently equal
to the statistic $\text{cocharge}(\text{cword}(\sigma))$ described in 
\cite[pp.48-49]{Manivel}.  

It is well known that for any word $w$ of partition content,
$$\text{cocharge }(w) = 
\text{cocharge }(\text{read}(P(w))),$$ 
where  $\text{read}(P(w))$ is the reading word of
the insertion tableau $P(w)$ under the RSK algorithm \cite[pp.48-49]{Manivel},
\cite[p.417]{Stanley2}.  Also, the RSK algorithm induces a bijection between
certain two-line arrays of positive integers
and pairs $(P,Q)$ of SSYT of the same shape.  The two-line arrays
have the property that the entries in the upper row are nondecreasing, and 
below equal entries in the upper row the entries in the lower row are also nondecreasing.
Under this bijection, the content of the upper row is the content of $Q$, and the
content of the lower row is the content of $P$.  
The number of different $Q$ tableau of content
$\nu$ matched to a given $P$ tableau of shape $\lambda$ is the Kostka number
$K_{\lambda,\nu}$ \cite[p.319]{Stanley2}.  

We 
associate a two-line array to a filling $\sigma$
with no inversions by letting the upper row be nonincreasing
with the same content as $\sigma$, and the
lower row be $\text{cword}(\sigma)$.  For example, to the filling in Figure \ref{noinv}
we associate the two-line array 
\begin{align}
\notag
&7\, 6\, 5\, 4\, 4\, 3\, 3\, 2\, 2\, 2\, 1\, 1\, 1\, 1 \\
&1\, 1\, 2 \,2 \,2 \,1 \,3\, 2\, 3\, 4\, 1\, 1\, 2\, 3
\end{align}
By construction, below equal entries in the upper row the entries in the lower
row are nondecreasing.  As is, the upper row is nonincreasing instead of nondecreasing,
but we can get around this problem by 
replacing $j$ by $n-j+1$ in the upper row, for $1\le j \le n$, 
where $n$ is the size of $\mu$.  At the
same time, we reverse the order of the variables, replacing $x_j$ by $x_{n-j+1}$ for
$1\le j \le n$ -
this doesn't change $C_{\mu}$ since it is a symmetric function.  Then $x^{\sigma}$
is the same as the content of $Q$, and since
$\text{cocharge}(\text{cword}(\sigma))$ depends only on the $P$ tableau,
\begin{align}
\notag
{\tilde C}_{\mu}[X;0,t] 
&= \sum_{\nu} m_{\nu}
\sum _{\lambda} \sum_{\btop{P \in SSYT (\lambda,\mu)}{Q \in SSYT(\lambda ,\nu)}}
t^{ \text{cocharge}( \text{read}(P) ) }\\
\notag
&= \sum_{\lambda} 
\sum_{P \in SSYT (\lambda,\mu)}
t^{ \text{cocharge}( \text{read}(P) ) }
\sum _{\nu} m_{\nu} K_{\lambda,\nu} \\
&= \sum_{\lambda} s_{\lambda}
\sum_{P \in SSYT (\lambda,\mu)}
t^{ \text{cocharge}( \text{read}(P) ) }.
\end{align}
\end{proof}

For our second consequence of Theorem \ref{main}, we 
use the super filling interpretation for
${\tilde H}_{\mu}[Z(q-1);q,t]$ from (\ref{tri1}) 
to obtain a new formula for 
the expansion of Macdonald's symmetric function $J_{\mu}[Z;q,t]$ into
monomials.
We then show how our formula immediately implies a result of
Knop and Sahi for Jack symmetric functions.

By definition we have 
\begin{align}
\notag
J_{\mu}[Z;q,t] &=
t^{n(\mu)} {\tilde H}_{\mu}[Z(1-t);q,1/t] \\
\notag
&=t^{n(\mu)} {\tilde H}_{\mu}[Zt(1/t-1);q,1/t] \\
\label{1a}
&=t^{n(\mu)+n} {\tilde H}_{\mu^{\prime}}[Z(1/t-1);1/t,q] 
\end{align}
using the well-known relation 
${\tilde H}_{\mu}[Z;q,t]= 
{\tilde H}_{\mu^{\prime}}[Z;t,q]$.  The first involution from the proof of Theorem \ref{main}
gives a combinatorial
interpretation for (\ref{1a}) in terms of super fillings of $\mu ^{\prime}$.  Say two super fillings
$\sigma, \beta$ are ``companions" if $|\sigma| = |\beta|$.  Note that companionship forms an
equivalence relation.  By grouping
fillings according to this relation, one can easily derive the following result.
\begin{thm}  
\label{Jmu}
For any partition $\mu$,
\begin{align}
\notag
\label{4b}
J_{\mu}[Z;q,t] &=
\sum_{ \text{nonattacking fillings $(T,\mu ^{\prime} )$} } z^{T} 
q^{\text{maj}(T ,\mu ^{\prime})}
t^{n(\mu) - \text{inv}(T,\mu^{\prime})} \\
&\times
\prod _{ \btop { w \in \mu ^{\prime} }
{ T(w) = T(\text{South}(w)) } }
(1- q^{1+\text{leg}(w) }t^{ 1+\text{arm}(w) } )
\prod _{ \btop { w \in \mu ^{\prime} }
{ T(w) \ne T( \text{South}(w) ) } }
(1-t).
\end{align}
\end{thm}

\begin{remark}
The (integral form) Jack polynomials $J_{\mu}^{\alpha}[Z]$ can be defined as
\cite[p.381]{Macdonald}
\begin{align}
\label{Jlim}
\lim _{t \to 1} (1-t)^{-|\mu|}J_{\mu}[Z;t^{\alpha},t].
\end{align}
By setting $q=t^{\alpha}$ in Theorem \ref{Jmu} and taking the limit as $t \to 1$
of (\ref{Jlim}) we immediately get the following formula of Knop and Sahi \cite{KnSa97}.
\begin{align}
J_{\mu}^{\alpha}[Z] &=
\sum_{ \text{nonattacking fillings $(T,\mu ^{\prime} )$} } z^{T} 
\prod _{ \btop { w \in \mu ^{\prime} }
{ T(w) = T(\text{South}(w)) } }
(1+\alpha (1+\text{leg}(w))+1+\text{arm}(w)).
\end{align}
\end{remark}

\section {Diagonal Harmonics and the $\mathbf {n!}$ Conjecture}
\label{diagonal}
Assume $\mu \vdash n$, $w_1,\ldots ,w_n$ is an arbitrary 
ordering of the squares of $\mu$, and
set 
\begin{align}
\Delta_{\mu}(x_1,\ldots ,x_n,y_1,\ldots ,y_n) =
\left | x_i^{\text{row}(w_j)}
 y_i^{\text{col}(w_j)} \right | _{1\le i,j \le n}.
\end{align}
For example, 
\begin{align}
\Delta_{221} = 
\left | \begin{matrix} 1 &y_1 &x_1 &x_1y_1 &x_1^2 \\
1 &y_2 &x_2 &x_2y_2 &x_2^2 \\
1 &y_3 &x_3 &x_3y_3 &x_3^2 \\
1 &y_4 &x_4 &x_4y_4 &x_4^2 \\
1 &y_5 &x_5 &x_5y_5 &x_5^2.
\end{matrix}
\right |
\end{align}
Note that $\Delta _{1^n}$ is, up to sign, the Vandermonde determinant in $x_1,\ldots ,x_n$.

Next define the Garsia-Haiman module $V(\mu)$ as the linear span over $\mathbb C$ of
$\Delta _{\mu}$ and its partial derivatives of all orders.  An element 
$\sigma = \sigma _1 \cdots \sigma _n$ in
the symmetric group
$S_n$ acts on a polynomial $f\in V(\mu)$ via the ``diagonal action"
\begin{equation}
\label{action}
\sigma f(x_1,\ldots ,x_n,y_1,\ldots ,y_n) =
f(x_{\sigma _1},\ldots ,x_{\sigma _n} ,y_{\sigma _1},\ldots ,y_{\sigma _n}).
\end{equation}
Note that $V(\mu) = \bigoplus_{i,j\ge 0} V(\mu)^{(i,j)}$, where $V(\mu)^{(i,j)}$ is the
portion of $V(\mu)$ of bihomogeneous $(x,y)$-degree $(i,j)$, and that the diagonal action
respects this bigrading.

In $2000$ Haiman \cite{Hai01} proved the ``$n!$ conjecture", first posed
in \cite{GaHm93}, which says that
the dimension of $V(\mu)$ equals $|\mu|!$.
It had
previously been shown \cite{Hai99} that the $n!$ conjecture 
implies 
the coefficient of $q^it^j$ in 
${\tilde K}_{\lambda ,\mu}(q,t)$
equals the multiplicity of the
irreducible $S_n$ character $\chi ^{\lambda}$ in the character of
$V(\mu)^{(i,j)}$ under the diagonal action, or equivalently that
${\tilde H}_{\mu}[Z;q,t]$ equals the image of the character of $V(\mu)$ under the
Frobenius map which sends $\chi ^{\lambda}$ to $s_{\lambda}$.
Macdonald's conjecture that 
${\tilde K}_{\lambda ,\mu}(q,t) \in \mathbb N [q,t]$ follows.  

The definition of the statistic $|\text{Inv}(\sigma ,\mu)|$ was motivated by
the ``$\text{dinv}$" statistic occurring in recent work on the
combinatorics of the space $DH_n$ of diagonal harmonics \cite{HHLRU05}, \cite{HaLo05}.
This space is defined \cite{Hai94}
as the linear span over $\mathbb Q$ of
the set of all polynomials $f(x_1,\ldots ,x_n,y_1,\ldots ,y_n)$ satisfying
\begin{align}
\sum_{i=1}^n \partial^h_{x_i} \, \partial^k_{y_i} \, f =0, \forall h+k>0.
\end{align}
We can write $DH_n = \bigoplus _{i,j \ge 0} DH_n^{(i,j)}$, and the diagonal action
(\ref{action}) respects this bigrading.
The modules $V(\mu)$ are $S_n$-submodules of $DH_n$.

Let $\nabla$ be the linear operator on symmetric functions defined on the
${\tilde H}_{\mu}[Z;q,t]$ basis via
\begin{align}
\nabla 
{\tilde H}_{\mu}[Z;q,t] =
t^{n(\mu)}q^{n(\mu ^{\prime})}{\tilde H}_{\mu}[Z;q,t].
\end{align}
Another famous result of Haiman \cite{Hai02} is that the bigraded character of $DH_n$ under the
diagonal action is given by $\nabla e_n$, where $e_n$ is the $n$th elementary symmetric function.
This was first conjectured by Garsia and Haiman
in the early $1990$'s, who made a special study of $<\nabla e_n, s_{1^n}>$,
the coefficient of $s_{1^n}$ in the expansion of
$\nabla e_{n}$ into Schur functions.  They called $<\nabla e_n,s_{1^n}>$ the ``$q,t$-Catalan
sequence", denoted $C_n(q,t)$, 
since they were able to prove that $C_n(1,1)=\binom{2n}{n}/(n+1)$, the $n$th Catalan
number.  As in the case of ${\tilde K}_{\lambda ,\mu}(q,t)$, all one can infer from its definition
is that $C_n(q,t)$ is a complicated sum of rational functions in $q,t$.

A Dyck path is a
lattice path, consisting of north $(0,1)$ and east $(1,0)$ steps,
starting at $(0,0)$ and ending at $(n,n)$, which never goes below the diagonal $x=y$.
The first major step in the path to the Macdonald polynomial statistics
%understanding the combinatorics of $DH_n$ was made in $2000$, when Haglund
was made in $2000$, when Haglund
discovered empirically that $C_n(q,t)$ appeared to be expressible as
the sum of $q^{\text{area}}t^{\text{bounce}}$ over Dyck paths, for combinatorial statistics
$\text{area}, \text{bounce}$  \cite{Hag03}.  
Shortly after, this conjecture
was independently discovered by Haiman in the following form, which is more convenient for
generalization.
\begin{align}
C_n(q,t) = \sum _{D} q^{\text{dinv}(D)}t^{\text{area}(D)}.
\end{align}
Here $\text{area}(D)$ is the number of complete squares below $D$ but strictly above
$y=x$.  We let $a_i=a_i(D)$ denote the number of these squares in the $i$th row, from the bottom
of the square $n\times n$ grid, and define $\text{dinv}(D)$, 
the number of ``diagonal" inversions of $D$, as the
number of pairs $(i,j)$ with 
\begin{align}
\label{conditions}
\text{$1\le i <j \le n$ and $a_i=a_j$ or $a_i=a_j+1$}.  
\end{align}
For example,
for the path in Figure \ref{gpark} (ignore the numbers in the grid for the moment), 
we have $\text{area}=9,\text{dinv}=13$.  

The Haglund-Haiman
conjecture for $C_n(q,t)$ was proved shortly after 
by Garsia and Haglund \cite{GaHa01}, \cite{GaHa02}, by a complicated application of plethystic
symmetric function identities previously developed by Garsia, Bergeron and others through a series of
papers \cite{GaTe96}, \cite{BGHT99}, \cite{GHT99}.   
More recently Haglund \cite{Hag04a} used the same techniques to
prove a more general result conjectured by Egge, Haglund, Kremer and Killpatrick \cite{EHKK03}
giving the coefficient of an arbitrary hook shape in
$\nabla e_n$ in terms of statistics on lattice paths with diagonal $(1,1)$ steps also allowed
(known as Schr\"oder paths).

A consequence of Haiman's formula for the character of $DH_n$ is the fact that the dimension
of $DH_n$, as a $\mathbb Q$-vector space, is $(n+1)^{n-1}$.  This number is well-known to
equal the number of parking functions on $n$ cars, which can be represented geometrically by
starting with a Dyck path $D$, then placing the numbers $1$ through $n$ immediately to the right
of the North steps of $D$, with strict decrease down columns.
Shortly after the proof of the combinatorial formula for $C_n(q,t)$, Haglund and Loehr \cite{HaLo05}
conjectured that the Hilbert series of $DH_n$ equals the sum of
$q^{\text{dinv}(P)}t^{\text{area}(P)}$ over all parking functions on $n$ cars.  Here the
statistic $\text{area}(P)$ is simply $\text{area}(D)$ for the underlying Dyck path $D$.  If we refer
to the number $j$ as $\text{car}_j$, then 
$\text{dinv}(P)$ is the number of pairs $(i,j)$ which satisfy the conditions
(\ref{conditions}), and in addition, if $a_i=a_j$, then the car in the $j$th row is larger than the
car in the $i$th row, while if $a_i=a_j+1$, then the car in the $j$th row is smaller than the
car in the $i$th row.  
The Haglund--Loehr conjecture is still open. 

The research into the combinatorics of $DH_n$ culminated with the discovery of 
the ``shuffle conjecture"
about two years ago by Haglund et al.\ \cite{HHLRU05}.  This gives a formula for 
$\nabla e_n$ in terms of statistics on ``word parking functions", which are placements
of positive integers in the columns as before, but we allow repeats (but still require strict
decrease down columns, and require cars to be no larger than $n$).  A given object $P$ 
of this type
is weighted by 
$z^{P} q^{\text{dinv}(P)}t^{\text{area}(P)}$,
where $\text{area}(P)$ is again the area of the underlying Dyck path.  
The description of $\text{dinv}(P)$
involves the {\it diagonal reading word} $\sigma =\sigma (P)$ of $P$, 
which is obtained by reading in the cars along diagonals
(lines parallel to $y=x$), outside to in and top to bottom.  Next standardize $\sigma$
as in Remark
\ref{triples}, regard $\sigma ^{\prime}$ as the reading word of some $P^{\prime}$,
then set $\text{dinv}(P) = \text{dinv}(P ^{\prime})$.  For example, if
$P$ is the word parking function in Figure \ref{gpark}, we have $\sigma = 64641532$, 
$\sigma ^{\prime}=74851632$, $\text{area}=9$, and $\text{dinv}=6$, with inversion
``pairs" $(i,j)$ of rows equal to $(3,8)$, $(4,8)$, $(1,7)$, $(2,7)$, $(5,6)$ and $(3,4)$
each contributing $1$ to $\text{dinv}$.  Also, $z^{P}$ is defined as $z^{\sigma}$.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=.4]{gpark.pdf}
\caption{A word parking function with the $a_i$ on the right}
\label{gpark}
\end{center}
\end{figure}

\begin{conj}[\sc The shuffle conjecture - \cite{HHLRU05}]  
\label{shuffle}
\begin{align}
\label{tabs}
\nabla e_n = \sum_{P} z^{P} q^{\text{dinv}(P)}t^{\text{area}(P)},
\end{align}
where the sum is over all word parking functions $P$ with $n$ cars.
\end{conj}

An equivalent formulation of the conjecture is that the coefficient of
the monomial $z_1^{\lambda _1}z_2^{\lambda _2}\cdots$ in $\nabla e_n$ equals the sum of
$q^{\text{dinv}}t^{\text{area}}$ over all parking functions whose diagonal reading word
is a shuffle of increasing sequences of lengths $\lambda _1, \lambda _2, \ldots$, hence the
phrase ``shuffle conjecture".
As is well known, the Hilbert series is the coefficient of $z_1\cdots z_n$ in the expansion of
the character into monomials, hence the shuffle conjecture contains Haglund and
Loehr's conjectured formula for the Hilbert series of
$DH_n$ as a special case.  In \cite{HaLo05} it is shown that it also
implies the formula for $C_n(q,t)$, as well as the formula for hook shapes in terms of
Schr\"oder paths.

\section{The Empirical Method}
\label{connection}

Recall that ${\tilde H}_{\mu}[Z;q,t]$ is the character of the $S_n$ module $V(\mu)$, which is a 
submodule of $DH_n$.  Thus we could hope that some version of the shuffle conjecture would
hold for ${\tilde H}_{\mu}[Z;q,t]$.  Furthermore, since the statistics in the shuffle
conjecture are defined solely in terms of the statistics for the Hilbert series of $DH_n$,
together with the simple operation of standardization, we could hope that discovering
statistics for the Hilbert series of $V(\mu)$ would result in a combinatorial
formula for the monomial expansion of ${\tilde H}_{\mu}[Z;q,t]$ through a similar
standardization process.

Let $\text{Hilb}_{\mu}(q,t)$ denote the bigraded Hilbert series of $V(\mu)$.
The problem of finding a combinatorial description of $\text{Hilb}_{\mu}(q,t)$ was studied 
by Garsia and Haiman, who obtained statistics when $\mu$ has two 
rows or is a hook shape \cite{GaHm96c}.
The author had also made some previous unsuccessful attempts at this problem, but the reasoning in the
above paragraph increased the stakes dramatically, and so the author decided to give a more
determined attack on the problem.

Since the dimension of $V(\mu)$ is $n!$, it is natural to view the problem in terms of searching for
a pair of permutation statistics, which depend on $\mu$, to generate $\text{Hilb}_{\mu}(q,t)$.  
Since $\mu$ has $n$ squares, permutations are
in bijection with fillings of $\mu$ by distinct integers, and furthermore from a result of 
Macdonald \cite[p.365,Ex.6]{Macdonald} one can easily deduce that
\begin{align}
\label{tonly}
\text{Hilb}_{\mu}(1,t) = \sum_{\sigma \in S_n} t^{\text{maj}(\sigma ,\mu)}.
\end{align}
We now assume that there exists some $q$-statistic to match with this
$\text{maj}$ $t$-statistic, and try to find it.

For a given Dyck path $D$, let $t^{\text{area}(D)}F_{D}(Z;q)$ denote the restriction of the sum
on the right-hand-side of (\ref{tabs}) to those word parking functions for $D$.  
It is proved in \cite{HHLRU05} that $F_{D}(Z;q)$ is a symmetric function, and moreover
is a constant power of $q$ times an LLT polynomial (as described in \cite{HHLRU05},
LLT polynomials can be 
parameterized by tuples of skew shapes; in the case of the $F_{D}$ 
the elements of the tuple
are vertical columns associated with the lengths of the vertical segments of $D$).  
Let $\mu$ be a partition, and abbreviate $\mu _1$ by $\ell$. 
While working with the $F_{D}$, the author proved that if $D=D(\mu)$ is the special type of
path consisting of $\mu _{\ell}^{\prime}$ vertical steps, 
followed by $\mu _{\ell}^{\prime}$ horizontal steps,
followed by $\mu _{\ell -1}^{\prime}$ vertical steps, followed by $\mu _{\ell -1}^{\prime}$ 
horizontal steps, etc., then
\begin{align}
\label{monK}
F_{D(\mu)}(Z;q) = q^{n(\mu)}\sum_{\lambda \vdash n} s_{\lambda} K_{\lambda ^{\prime},
\mu ^{\prime}}(q),
\end{align}
where $K_{\lambda ,\mu}(q) = q^{n(\mu)} {\tilde K}_{\lambda ,\mu}(q^{-1})$ is the
charge version of the polynomial from Section \ref{cocharge}.  This can be proved from 
recurrences for the $F_{D(\mu)}$, obtained by placing the largest car $n$ at the top of columns, then
showing these recurrences are equivalent to those obtained by Garsia and Procesi
\cite{GaPr92} for the Hall-Littlewood polynomials.  (This fact also follows from 
statements in 
\cite{SSW01}, where it is deduced from
recurrences of this type for general LLT polynomials).

Since 
\begin{align}
{\tilde H}_{\mu}[Z;0,q] =
\sum_{\lambda} s_{\lambda} {\tilde K}_{\lambda ,\mu}(q),
\end{align}
and since by (\ref{monK}) the monomial expansion of 
\begin{align}
\sum_{\lambda \vdash n} s_{\lambda} K_{\lambda ^{\prime},
\mu ^{\prime}}(q)
\end{align}
can be obtained by summing $q^{-n(\mu)+ \text{dinv}(T)}z^{T}$ over word parking functions
for $D(\mu)$, one could hope that the power of $q$ to insert into (\ref{tonly}) involves
$\text{dinv}$ in some way.  
A parking function $\sigma$ for $D(\mu)$ can be transformed into a filling $\sigma$ of $\mu$ by
pushing all squares in the $i$th column from the left
down $i-1$ squares, removing all empty columns, and finally rotating $180$ degrees, as in Figure
\ref{ntransform}.  Furthermore this sends $\text{dinv}(\sigma)$ to $|\text{Inv} (\sigma, \mu)|$.  
Note that $\text{area}$ gets sent to $\text{maj}$, since we have descents everywhere.
We are thus led to 
\begin{align}
\label{eduguess}
\sum_{\sigma \in S_n} t^{\text{maj}(\sigma ,\mu)}
q^{-n(\mu) + |\text{Inv}(\sigma ,\mu)|}
\end{align}
as a candidate for the $\text{Hilb}_{\mu}(q,t)$.  

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=.4]{ntransform.pdf}
\caption{Transforming a parking function into a filling}
\label{ntransform}
\end{center}
\end{figure}

{\sl Maple} computations verified that (\ref{eduguess}) correctly predicts the coefficient
of $t^{n(\mu)}$ (the highest power of $t$) in $\text{Hilb}_{\mu}(q,t)$, and that
the coefficient of $t^0$ would be correct if we didn't have the $-n(\mu)$ in the
$q$-power.  This led to the hypothesis that $|\text{Inv} (\sigma,\mu)|$ formed an upper bound for the
correct $q$-statistic, and that the key was to find the right thing to subtract from it, something  
possibly depending on the descent set.
The final stage involved a series of {\sl Maple} calculations, each testing a different idea
for something to subtract.  Many things worked up through $n=4$ and for various special cases
like $\mu = 2,1,1,1,...$, but continually failed for $n=5$.  Here is a sample of the author's
daily journal summarizing the experiments;

\medskip
\noindent 
{\it Journal entry:}

On $3/29/04$, ran pistolbad.map, which computes inversion in columns for $\text{tstat}$
and $\text{dinv}$ minus $\text{mindinv}$ for $\text{qstat}$.  Bombs for $\mu =[2,2,1]$.  See bomb.out.
Tried a modification, where comaj of the columns replaced the tstat, same
qstat.  This also bombed in general, but surprisingly works for $\mu =221$,
$\mu =222$, $\mu =2221$, and $\mu =2222$.  Bombs for $\mu =2211$ though.

\medskip
\noindent
{\it Journal Entry:}

On 4/2/04 ran pistolbbad.map, which computes inversions in columns for $\text{tstat}$
and $\text{dinv minus mindinv}$ for $\text{qstat}$, where $\text{mindinv}$ 
is defined as the sum over all
descents, of the number of entries to the left of the top element of the decent
pair.  Seems to work for $\mu$ having two rows, but bombs for $\mu =2,2,1$.

\medskip
At this point the author planned to drop the problem, and return
to less speculative projects.  
The idea of subtracting the arm of each descent
occurred to him, however, and he decided to run one last experiment, which successfully
generated $\text{Hilb}_{\mu}(q,t)$ for all $|\mu|\le 8$. 
A subsequent calculation a few days later extended this to $|\mu|\le 9$, and moreover
verified that applying the Hilbert
series statistics to the standardization of words generated the entire monomial expansion of
the ${\tilde H}_{\mu}[Z;q,t]$.
In a phone conversation a few months later after the conjecture was made public
A. Garsia told the author
``You found water on Mars".

\medskip
\noindent
{\it Journal Entry:}

Also on 4/2/04, ran pistolb.map, which computes $\text{maj}$ on columns for $\text{tstat}$,
and uses $\text{mindinv}$ as described in paragraph just above.  Surprisingly, works
for all $\mu$ with $|\mu|<=8!$  The run for $n=9$ took over a week, but finally
finished successfully.

\medskip
\noindent
{\it Journal Entry:}

On 4/6/04 ran program pistolc.map, which computes the Macdonald poly
from shuffles using the Hilbert series $\text{inv}$ and $\text{maj}$ stats.  Correctly generates the
Macdonald poly ${\tilde H}_{\mu}$ for all $\mu$ with $|\mu|\le 8!$  From 4/7 thru
4/16 ran tempc.map, which extends this computation through $n=9$.

\newcommand{\etalchar}[1]{$^{#1}$}

\bibliographystyle{alpha}

\begin{thebibliography}{HHL{\etalchar{+}}05b}

\bibitem[BGHT99]{BGHT99}
F.~Bergeron, A.~M. Garsia, M.~Haiman, and G.~Tesler.
\newblock Identities and positivity conjectures for some remarkable operators
  in the theory of symmetric functions.
\newblock {\em Methods Appl. Anal.}, 6:363--420, 1999.

\bibitem[EHKK03]{EHKK03}
E.~Egge, J.~Haglund, K.~Killpatrick, and D.~Kremer.
\newblock A {S}chr\"oder generalization of {H}aglund's statistic on {C}atalan
  paths.
\newblock {\em Electron. J. Combin.}, 10:Research Paper 16, 21 pp.
  (electronic), 2003.

\bibitem[GH93]{GaHm93}
A.~M. Garsia and M.~Haiman.
\newblock A graded representation model for {M}acdonald polynomials.
\newblock {\em Proc. Nat. Acad. Sci. U.S.A.}, 90(8):3607--3610, 1993.

\bibitem[GH95]{GaHm96c}
A.~M. Garsia and M.~Haiman.
\newblock Factorizations of {P}ieri rules for {M}acdonald polynomials.
\newblock {\em Discrete Math.}, 139(1-3):219--256, 1995.
\newblock Formal power series and algebraic combinatorics (Montreal, PQ, 1992).

\bibitem[GH96]{GaHm96b}
A.~M. Garsia and M.~Haiman.
\newblock A remarkable $q,t$-{C}atalan sequence and $q$-{L}agrange inversion.
\newblock {\em J. Algebraic Combin.}, 5(3):191--244, 1996.

\bibitem[GH01]{GaHa01}
A.~M. Garsia and J.~Haglund.
\newblock A positivity result in the theory of {M}acdonald polynomials.
\newblock {\em Proc. Nat. Acad. Sci. U.S.A.}, 98:4313--4316, 2001.

\bibitem[GH02]{GaHa02}
A.~M. Garsia and J.~Haglund.
\newblock A proof of the $q,t$-{C}atalan positivity conjecture.
\newblock {\em Discrete Math.}, 256:677--717, 2002.

\bibitem[GHT99]{GHT99}
A.~M. Garsia, M.~Haiman, and G.~Tesler.
\newblock Explicit plethystic formulas for {M}acdonald {$q,t$}-{K}ostka
  coefficients.
\newblock {\em S\'em. Lothar. Combin.}, 42:Art. B42m, 45 pp. (electronic),
  1999.
\newblock The Andrews Festschrift (Maratea, 1998).

\bibitem[GP92]{GaPr92}
A.~M. Garsia and C.~Procesi.
\newblock On certain graded {$S\sb n$}-modules and the {$q$}-{K}ostka
  polynomials.
\newblock {\em Adv. Math.}, 94(1):82--138, 1992.

\bibitem[GT96]{GaTe96}
A.~M. Garsia and G.~Tesler.
\newblock Plethystic formulas for {M}acdonald $q,t$-{K}ostka coefficients.
\newblock {\em Adv. Math.}, 123:144--222, 1996.

\bibitem[Hag03]{Hag03}
J.~Haglund.
\newblock Conjectured statistics for the {$q,t$}-{C}atalan numbers.
\newblock {\em Adv. Math.}, 175(2):319--334, 2003.

\bibitem[Hag04a]{Hag04b}
J.~Haglund.
\newblock A combinatorial model for the {M}acdonald polynomials.
\newblock {\em Proc. Nat. Acad. Sci. U.S.A.}, 101:16127--16131, 2004.

\bibitem[Hag04b]{Hag04a}
J.~Haglund.
\newblock A proof of the {$q,t$}-{S}chr\"oder conjecture.
\newblock {\em Internat. Math. Res. Notices}, 11:525--560, 2004.

\bibitem[Hai94]{Hai94}
M.~Haiman.
\newblock Conjectures on the quotient ring by diagonal invariants.
\newblock {\em J. Algebraic Combin.}, 3:17--76, 1994.

\bibitem[Hai99]{Hai99}
M.~Haiman.
\newblock Macdonald polynomials and geometry.
\newblock In {\em New perspectives in algebraic combinatorics (Berkeley, CA,
  1996--97)}, volume~38 of {\em Math. Sci. Res. Inst. Publ.}, pages 207--254.
  Cambridge Univ. Press, Cambridge, 1999.

\bibitem[Hai01]{Hai01}
M.~Haiman.
\newblock Hilbert schemes, polygraphs, and the {M}acdonald positivity
  conjecture.
\newblock {\em J. Amer. Math. Soc.}, 14:941--1006, 2001.

\bibitem[Hai02]{Hai02}
M.~Haiman.
\newblock Vanishing theorems and character formulas for the {H}ilbert scheme of
  points in the plane.
\newblock {\em Invent. Math.}, 149:371--407, 2002.

\bibitem[Hai03]{Hai03a}
Mark Haiman.
\newblock Combinatorics, symmetric functions, and {H}ilbert schemes.
\newblock In {\em Current developments in mathematics, 2002}, pages 39--111.
  Int. Press, Somerville, MA, 2003.

\bibitem[HHL05a]{HHL05b}
J.~Haglund, M.~Haiman, and N.~Loehr.
\newblock A combinatorial formula for {M}acdonald polynomials.
\newblock {\em J. Amer. Math. Soc.}, 18:735--761, 2005.

\bibitem[HHL{\etalchar{+}}05b]{HHLRU05}
J.~Haglund, M.~Haiman, N.~Loehr, J.~B. Remmel, and A.~Ulyanov.
\newblock A combinatorial formula for the character of the diagonal
  coinvariants.
\newblock {\em Duke J. Math.}, 126:195--232, 2005.

\bibitem[HL05]{HaLo05}
J.~Haglund and N.~Loehr.
\newblock A conjectured combinatorial formula for the {H}ilbert series for
  {D}iagonal {H}armonics.
\newblock {\em Discrete Math. (Proceedings of the FPSAC 2002 Conference held in
  Melbourne, Australia)}, 298:189--204, 2005.

\bibitem[KS97]{KnSa97}
Friedrich Knop and Siddhartha Sahi.
\newblock A recursion and a combinatorial formula for {J}ack polynomials.
\newblock {\em Invent. Math.}, 128(1):9--22, 1997.

\bibitem[LLT97]{LLT97}
Alain Lascoux, Bernard Leclerc, and Jean-Yves Thibon.
\newblock Ribbon tableaux, {H}all-{L}ittlewood functions, quantum affine
  algebras, and unipotent varieties.
\newblock {\em J. Math. Phys.}, 38(2):1041--1068, 1997.

\bibitem[Mac95]{Macdonald}
I.~G. Macdonald.
\newblock {\em Symmetric Functions and Hall Polynomials}.
\newblock Oxford Mathematical Monographs, second ed., Oxford Science
  Publications. The Clarendon Press Oxford University Press, New York, 1995.

\bibitem[Man01]{Manivel}
Laurent Manivel.
\newblock {\em Symmetric functions, {S}chubert polynomials and degeneracy
  loci}, volume~6 of {\em SMF/AMS Texts and Monographs}.
\newblock American Mathematical Society, Providence, RI, 2001.
\newblock Translated from the 1998 French original by John R. Swallow, Cours
  Sp\'ecialis\'es [Specialized Courses], 3.

\bibitem[SSW03]{SSW01}
A.~Schilling, M.~Shimozono, and D.~E. White.
\newblock Branching formula for {$q$}-{L}ittlewood-{R}ichardson coefficients.
\newblock {\em Adv. in Appl. Math.}, 30(1-2):258--272, 2003.
\newblock Formal power series and algebraic combinatorics (Scottsdale, AZ,
  2001).

\bibitem[Sta99]{Stanley2}
R.~P. Stanley.
\newblock {\em Enumerative Combinatorics}, volume~2.
\newblock Cambridge University Press, Cambridge, United Kingdom, 1999.

\end{thebibliography}

\end{document}
