Toda Equations and Piecewise Polynomiality for Mixed Double Hurwitz Numbers
I. P. Goulden
%Some notes on approximation schemes for characters of ``big'' algebras. %
1307.2137.tex

%%
%% This is LaTeX2e input.
%%

%% The following tells LaTeX that we are using the 
%% style file amsart.cls (That is the AMS article style
%%
\documentclass{amsart}

%% This has a default type size 10pt.  Other options are 11pt and 12pt
%% This are set by replacing the command above by
%% \documentclass[11pt]{amsart}
%%
%% or
%%
%% \documentclass[12pt]{amsart}
%%

%%
%% Some mathematical symbols are not included in the basic LaTeX
%% package.  Uncommenting the following makes more commands
%% available. 
%%

\usepackage{amsmath,amssymb}
\usepackage{hyperref}
\usepackage{graphics}

%%
%% The following is commands are used for importing various types of
%% grapics.
%% 

%\usepackage{epsfig}      % For postscript
%\usepackage{epic,eepic}       % For epic and eepic output from xfig

%%
%% The following is very useful in keeping track of labels while
%% writing.  The variant   \usepackage[notcite]{showkeys}
%% does not show the labels on the \cite commands.
%% 

%\usepackageshowkeys}


%%%%
%%%% The next few commands set up the theorem type environments.
%%%% Here they are set up to be numbered section.number, but this can
%%%% be changed.
%%%%

\newtheorem{thm}{Theorem}%[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}


%%
%% If some other type is need, say conjectures, then it is constructed
%% by editing and uncommenting the following.
%%

%\newtheorem{conj}[thm]{Conjecture} 


%%% 
%%% The following gives definition type environments (which only differ
%%% from theorem type invironmants in the choices of fonts).  The
%%% numbering is still tied to the theorem counter.
%%% 

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}

%%
%% Again more of these can be added by uncommenting and editing the
%% following. 
%%

%\newtheorem{note}[thm]{Note}


%%% 
%%% The following gives remark type environments (which only differ
%%% from theorem type invironmants in the choices of fonts).  The
%%% numbering is still tied to the theorem counter.
%%% 


\theoremstyle{remark}

\newtheorem{remark}[thm]{Remark}


%%%
%%% The following, if uncommented, numbers equations within sections.
%%% 

\numberwithin{equation}{section}


%%%
%%% The following show how to make definition (also called macros or
%%% abbreviations).  For example to use get a bold face R for use to
%%% name the real numbers the command is \mathbf{R}.  To save typing we
%%% can abbreviate as

\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\Tr}{\operatorname{Tr}}

%%
%% The comment after the defintion is not required, but if you are
%% working with someone they will likely thank you for explaining your
%% definition.  
%%
%% Now add you own definitions:
%%

%%%
%%% Mathematical operators (things like sin and cos which are used as
%%% functions and have slightly different spacing when typeset than
%%% variables are defined as follows:
%%%

\DeclareMathOperator{\dist}{dist} % The distance.



%%
%% This is the end of the preamble.
%% 


\begin{document}

%%
%% The title of the paper goes here.  Edit to your title.
%%

\title{Toda Equations and Piecewise Polynomiality for Mixed Double Hurwitz Numbers}

%%
%% Now edit the following to give your name and address:
%% 

\author{I. P. Goulden}
\address{Department of Combinatorics \& Optimization,
University of Waterloo, Canada}
\email{ipgoulden@uwaterloo.ca}

\author{Mathieu Guay-Paquet}
\address{LaCIM, Universit\'e du Qu\'ebec \`a Montr\'eal, Canada}
\email{mathieu.guaypaquet@lacim.ca}


\author{Jonathan Novak}
\address{Department of Mathematics, Massachusetts Institute of Technology, USA}
\email{jnovak@math.mit.edu}

%%%
%%% The following is for the abstract.  The abstract is optional and
%%% if not used just delete, or comment out, the following.
%%%

%\begin{abstract}
  %Some notes on approximation schemes for characters of ``big'' algebras. 
%\end{abstract}

%%
%%  LaTeX will not make the title for the paper unless told to do so.
%%  This is done by uncommenting the following.
%%

 \maketitle

%%
%% LaTeX can automatically make a table of contents.  This is done by
%% uncommenting the following:
%%

%%
%%  To enter text is easy.  Just type it.  A blank line starts a new
%%  paragraph. 
%%

\begin{abstract}
	This article introduces \emph{mixed double Hurwitz numbers}, which interpolate
	combinatorially between the classical double Hurwitz numbers studied by Okounkov
	and the monotone double Hurwitz numbers introduced recently by Goulden, Guay-Paquet
	and Novak.  Generalizing a result of Okounkov, we prove that a certain generating series for the 
	mixed double Hurwitz numbers solves the $2$-Toda hierarchy of partial differential equations.  
	We also prove that the mixed double Hurwitz numbers are
	piecewise polynomial, thereby generalizing a result of Goulden, Jackson and Vakil.
\end{abstract}

\section{Introduction}

Consider the right Cayley graph of the symmetric group $S(d)$, 
as generated by the full conjugacy class of transpositions.
This is a ${d \choose 2}$-regular graded graph with levels $L_0,L_1,\dots,L_{d-1}$,
where $L_k$ is the set of permutations with $d-k$ cycles.
Each level $L_k$ decomposes as the disjoint union
of those conjugacy classes in $S(d)$ labelled by Young diagrams with $d-k$ rows.  

Let us introduce an edge labelling of the Cayley graph by marking each edge corresponding
to the transposition $\tau=(s\ t)$ with $t$, the larger of the two elements interchanged by
$\tau$.  This edge labelling was used by Stanley \cite{Stanley} and Biane \cite{Biane} to 
study various connections between permutations, parking functions, and noncrossing 
partitions\footnote{Stanley and Biane use $s$ as the edge label instead of $t$, but 
this is a minor difference.}.  

Given integers $k,l \geq 0$ and partitions $\alpha,\beta \vdash d$,
let $W^{k,l}(\alpha,\beta)$ denote the number of $(k+l)$-step
walks 

	\begin{equation*}
		\sigma = \rho\underbrace{(s_1\ t_1) \dots (s_k\ t_k)}_k \underbrace{(s_{k+1}\ t_{k+1}) \dots (s_{k+l}\ t_{k+l})}_l
	\end{equation*}	
	
\noindent
on the Cayley graph beginning in the conjugacy class $C_\alpha$ and ending in the conjugacy class
$C_\beta$ which satisfy 

	\begin{equation*}
		t_1 \leq \dots \leq t_k.
	\end{equation*}
	
\noindent
In words, this monotonicity condition states that 
the labels of the edges traversed in the first $k$ steps of the walk form
a weakly increasing sequence.  

While elementary to define, the numbers $W^{k,l}(\alpha,\beta)$ are related to some
rather sophisticated mathematics.  Let $z,t,u,a_1,a_2,\dots,b_1,b_2,\dots$ be 
commuting indeterminates, and form the generating function

	\begin{equation*}
		\mathbf{W}(z,t,u,A,B) = 1 + \sum_{d=1}^{\infty} \frac{z^d}{d!}
		\sum_{k,l=0}^{\infty} t^k \frac{u^l}{l!} \sum_{\alpha,\beta \vdash d} 
		W^{k,l}(\alpha,\beta) p_\alpha(A) p_\beta(B),
	\end{equation*}
	
\noindent
where $p_\alpha(A)$ and $p_\beta(B)$ denote the power-sum symmetric functions
in the variables $A=\{a_1,a_2,\dots\}$ and $B=\{b_1,b_2,\dots\}$, respectively.  The series 

	\begin{equation*}
		\mathbf{H}(z,t,u,A,B) = \log \mathbf{W}(z,t,u,A,B) 
	\end{equation*}
	
\noindent
is a well-defined element of $\mathbb{Q}[[z,t,u,A,B]]$.  Set

	\begin{equation*}
		H^{k,l}(\alpha,\beta) = \bigg{[} z^d t^k \frac{u^l}{l!} p_\alpha(A) p_\beta(B) \bigg{]}\mathbf{H}(z,t,u,A,B),
	\end{equation*}

\noindent
where $[X]Y$ denotes the coefficient of the term $X$ in a series $Y$.

The numbers $H^{0,l}(\alpha,\beta)$ were first studied by Okounkov \cite{Okounkov},
who called them the \emph{double Hurwitz numbers}.  By a classical
construction due to Hurwitz --- the monodromy construction --- $H^{0,l}(\alpha,\beta)$ is a weighted count of degree $d$ branched covers 
of the Riemann sphere by a compact, connected Riemann surface such that the covering map has profile $\alpha$ over $0$,
$\beta$ over $\infty$, and simple ramification over each of the $l$th roots of unity.  The Riemann-Hurwitz
formula determines the genus of the covering surface in terms of the ramification data of the covering map:

	\begin{equation*}
		g=\frac{l+2-\ell(\alpha)-\ell(\beta)}{2}.
	\end{equation*}
	
Verifying and extending a conjecture of Pandharipande \cite{Pan} in Gromov-Witten theory,
Okounkov proved that the generating function $\mathbf{H}(z,0,u,A,B)$ is a solution
of the $2$-Toda hierarchy of Ueno and Takasaki.
The $2$-Toda hierarchy is a countable collection
of partial differential equations, each of which yields a recurrence relation satisfied by the double
Hurwitz numbers.  A construction of the Toda hierarchy may be found in \cite[\S 4]{OP2}.
Kazarian and Lando \cite{KL} subsequently showed that, when combined with
the ELSV formula \cite{ELSV}, Okounkov's result yields a streamlined proof of the
Kontsevich-Witten theorem relating intersection theory in moduli spaces of curves to 
integrable hierarchies.

Goulden, Jackson and Vakil \cite{GJV} gave an alternative interpretation of the 
double Hurwitz number $H^{0,l}(\alpha,\beta)$ as counting lattice points in a
certain integral polytope.  As a consequence of this interpretation
and Ehrhart's theorem, it was shown in \cite{GJV} that, after a simple rescaling,
$H^{0,l}(\alpha,\beta)$ is a piecewise 
polynomial function of the parts of $\alpha$ and $\beta$, when $\ell(\alpha)$ and $\ell(\beta)$
are held fixed.  Detailed structural properties of this piecewise polynomial behaviour were postulated
in \cite{GJV}, and subsequently shown to hold by Johnson \cite{Johnson} using
the combinatorics of the infinite wedge representation of $\mathfrak{gl}(\infty)$.  
Shadrin, Spitz and Zvonkine \cite{SSZ} have recently generalized double Hurwitz numbers
to the setting of the completed cycle theory introduced by Okounkov and Pandharipande \cite{OP}.
It is shown in \cite{SSZ} that piecewise polynomiality of double Hurwitz numbers with completed
cycle insertions follows from a suitable modification of  Johnson's arguments.
 
The \emph{monotone double Hurwitz numbers} $H^{k,0}(\alpha,\beta)$ were introduced by
the present authors in \cite{GGN1}, where it was shown that they are the combinatorial objects 
underlying the asymptotic expansion of the Harish-Chandra-Itzykson-Zuber integral, an important special
function in random matrix theory.  Structural properties of the monotone single Hurwitz numbers
$H^{k,0}(\alpha)=H^{k,0}(\alpha,1^d)$
were studied in detail in \cite{GGN2,GGN3}, where it was shown that they enjoy 
a high degree of structural similarity with the classical single Hurwitz numbers $H^{0,l}(\alpha)=H^{0,l}(\alpha,1^d)$.

In this article, we extend the theorems of Okounkov and Goulden-Jackson-Vakil to the more general setting of
the \emph{mixed double Hurwitz numbers} $H^{k,l}(\alpha,\beta)$, which interpolate between the 
classical double Hurwitz numbers ($k=0$) and the monotone double Hurwitz numbers ($l=0$).  

	\begin{thm}
		\label{thm:integrability}
		The generating function $\mathbf{H}$ is a solution of 
		the $2$-Toda hierarchy.
	\end{thm}
	
	\begin{thm}
		\label{thm:polynomiality}
		The mixed double Hurwitz numbers are piecewise
		polynomial.
	\end{thm}
	
\section{Toda equations}
\label{sec:Toda}
Let us group the transposition generators of $S(d)$ into a matrix,

	\begin{equation*}
		T=\begin{bmatrix}
			(1\ 2) & (1\ 3) & \dots & (1\ d) \\
			{} & (2\ 3) & \dots & (2\ d) \\
			{} & {} & \ddots  & \vdots\\
			{} & {} & {} & (d-1\ d)
		\end{bmatrix}.
	\end{equation*}

\noindent
Denote by 

	\begin{align*}
		J_2 &= (1\ 2) \\
		J_3 &= (1\ 3) + (2\ 3) \\
		&\vdots \\
		J_d &= (1\ d) + (2\ d) + \dots + (d-1\ d),
	\end{align*}	
	
\noindent 
the column sums of this matrix, viewed as elements of 
the group algebra $\mathbb{Q}S(d)$.  These elements commute.
Set $J_1:=0$, and introduce the multiset

	\begin{equation*}
		\Xi_d =\{\{J_1,\dots,J_d,0,0,\dots\}\}.
	\end{equation*}

Let $\Lambda$ denote the $\mathbb{Q}$-algebra of symmetric
functions.  We will consider the evaluation of the
complete symmetric function $h_\mu \in \Lambda$ indexed by the
$(k,l)$-hook Young diagram $\mu =(k, 1^l)$ on the alphabet $\Xi_d$.
From the definition of the complete symmetric functions, we have

	\begin{align*}
		h_{(k,1^l)}(\Xi_d) &= h_k(\Xi_d) h_1(\Xi_d)^l \\
		&=\bigg{(} \sum_{2 \leq t_1 \leq \dots \leq t_k \leq d} J_{t_1} \dots J_{t_k} \bigg{)} \bigg{(} \sum_{t=2}^d J_t \bigg{)}^l \\
		&= \bigg{(}\sum_{2 \leq t_1 \leq \dots \leq t_k \leq d} \bigg{(} \sum_{s_1<t_1} (s_1\ t_1) \bigg{)} \dots \bigg{(} \sum_{s_k<t_k} (s_k\ t_k) \bigg{)} \bigg{)}
			\bigg{(} \sum_{2 \leq t \leq d} \sum_{s < t} (s\ t) \bigg{)}^l\\
		&=  \sum_{\substack{t_1, \dots t_{k+l}=2\\ t_1 \leq \dots \leq t_k\\ s_i < t_i}}^d (s_1\ t_1) \dots (s_k\ t_k) (s_{k+1}\ t_{k+1}) \dots (s_{k+l}\ t_{k+l}).
	\end{align*}

\noindent
Thus

	\begin{equation*}
		W^{k,l}(\alpha,\beta) = [C_{(1^d)}]C_\alpha h_{(k,1^l)}(\Xi_d)C_\beta,
	\end{equation*}
	
\noindent
where we have identified each conjugacy class in $S(d)$ with the formal sum 
of its elements in $\mathbb{Q}S(d)$.  In other words, $W^{k,l}(\alpha,\beta)$
is the normalized character of $C_\alpha h_{(k,1^l)}(\Xi_d)C_\beta$ in the regular representation
of $\mathbb{Q}S(d)$.  

The columns sums of $T$ are known as the \emph{Jucys-Murphy 
elements} of $\field{Q}S(d)$.
It was observed by Jucys and Murphy (see \cite{DG} for a proof)
that $e_r(\Xi_d)$, the $r$th elementary symmetric function
evaluated on the alphabet of Jucys-Murphy elements, 
is precisely the sum of the permutations
on level $L_r$ of the Cayley graph:

	\begin{equation*}
		e_r(\Xi_d) = \sum_{\substack{\mu \vdash d\\ \ell(\mu) = d-r}} C_\mu.
	\end{equation*}
	
\noindent
In particular, $e_r(\Xi_d)$ belongs to the center $Z(d)$ of $\mathbb{Q}S(d)$.
Since $\Lambda=\field{Q}[e_1,e_2,\dots]$, the substitution 
$f \mapsto f(\Xi_d)$ defines a specialization $\Lambda \rightarrow Z(d)$.
In fact, since the levels of the Cayley graph generate $Z(d)$, 
this specialization is surjective  \cite{FH}. 


Since $C_\alpha h_{(k,1^l)}(\Xi_d) C_\beta$ belongs to the centre of $\field{Q}S(d)$, we
can calculate its character in the regular representation using the Fourier transform.
Let $(V^\lambda,\rho^\lambda),\ \lambda \vdash d$, be pairwise non-isomorphic irreducible
representations of $\mathbb{Q}S(d)$, so that the map 

	\begin{equation*}
		\sigma \mapsto (\rho^\lambda(\sigma): \lambda\vdash d)
	\end{equation*}
	
\noindent
defines an algebra isomorphism

	\begin{equation*}
		\mathbb{Q}S(d) \rightarrow \bigoplus_{\lambda \vdash d} \operatorname{End}V^\lambda.
	\end{equation*}

\noindent
The normalized character of $C_\alpha h_{(k,1^l)}(\Xi_d)C_\beta$ in the regular representation of $\mathbb{Q}S(d)$ 
is thus

	\begin{align*}
		[C_{(1^d)}] C_\alpha h_{(k,1^l)}(\Xi_d)C_\beta 
		&= \sum_{\lambda \vdash d} \Tr \rho^\lambda(C_\alpha h_{(k,1^l)}(\Xi_d) C_\beta) \frac{\dim V^\lambda}{d!} \\
		&= \sum_{\lambda \vdash d} \Tr \rho^\lambda(C_\alpha) \rho^\lambda(h_{(k,1^l)}(\Xi_d)) \rho^\lambda(C_\beta) \frac{\dim V^\lambda}{d!} \\
		&= \sum_{\lambda \vdash d} \Tr \omega^\lambda(C_\alpha) \omega^\lambda(h_{(k,1^l)}(\Xi_d)) \omega^\lambda(C_\beta) \frac{(\dim V^\lambda)^2}{d!},
	\end{align*}
	
\noindent
where, for any $C \in Z(d)$, we denote by $\omega^\lambda(C)$ the unique eigenvalue
of the scalar operator $\rho^\lambda(C) \in \operatorname{End} V^\lambda$, i.e.
$\rho^\lambda(C) = \omega^\lambda(C)I_{V^\lambda}$.  The eigenvalue $\omega^\lambda(C)$ is known
as the \emph{central character} of $C$ in the representation $(V^\lambda,\rho^\lambda)$.

The central character of any conjugacy class $C_\mu$ is given, in terms of the usual character

	\begin{equation*}
		\chi^\lambda_\mu = \Tr \rho^\lambda(\sigma), \quad \sigma \in C_\mu,
	\end{equation*}
	
\noindent
by the formula

	\begin{equation*}
		\omega^\lambda(C_\mu) = |C_\mu| \frac{\chi^\lambda_\mu}{\dim V^\lambda}.
	\end{equation*}

\noindent
The central character of any symmetric function $f$ evaluated on $\Xi_d$ is simply

	\begin{equation*}
		\omega^\lambda(f(\Xi_d))=f(\operatorname{Cont}_\lambda),
	\end{equation*}		
	
\noindent
the evaluation of $f$ on the multiset of contents of the Young diagram $\lambda$.
This remarkable result is due to Jucys and Murphy, see \cite{DG} for a proof.

Recalling that the Schur functions have the expansion

	\begin{equation*}
		s_\lambda = \ \sum_{\mu \vdash d} \frac{|C_\mu|}{d!}\chi^\lambda_\mu p_\mu,
	\end{equation*}

\noindent
where $\lambda \vdash d$, the generating function $\mathbf{W}$ may be 
rewritten as follows:

	\begin{align*}
		\mathbf{W}(z,t,u,A,B) &= 1+\sum_{d=1}^{\infty}\frac{z^d}{d!} \sum_{k,l=0}^{\infty} t^k \frac{u^l}{l!}
		\sum_{\alpha,\beta,\lambda \vdash d} W^{k,l}(\alpha,\beta) p_\alpha(A) p_\beta(B) \\
		&= 1+\sum_{d=1}^{\infty}\frac{z^d}{d!} \sum_{k,l=0}^{\infty} t^k \frac{u^l}{l!} 
		\sum_{\alpha,\beta,\lambda \vdash d} \bigg{(} \frac{1}{d!}\sum_{\lambda \vdash d} 
		|C_\alpha| \chi^\lambda_\alpha h_{(k,1^l)}(\operatorname{Cont}_\lambda) |C_\beta| \chi^\lambda_\beta\bigg{)} p_\alpha(A) p_\beta(B) \\
		&= 1+\sum_{d=1}^{\infty}z^d \sum_{k,l=0}^{\infty} t^k \frac{u^l}{l!} \sum_{\lambda \vdash d} h_{(k,1^l)}(\operatorname{Cont}_\lambda)
		\bigg{(} \sum_{\alpha \vdash d} \frac{|C_\alpha|}{d!} \chi^\lambda_\alpha p_\alpha(A)\bigg{)}
		\bigg{(} \sum_{\beta \vdash d} \frac{|C_\beta|}{d!} \chi^\lambda_\beta p_\beta(B)\bigg{)} \\
		&=1+\sum_{d=1}^{\infty}z^d \sum_{k,l=0}^{\infty} t^k \frac{u^l}{l!} \sum_{\lambda \vdash d} h_{(k,1^l)}(\operatorname{Cont}_\lambda)s_\lambda(A)s_\lambda(B) \\
		&=1+\sum_{d=1}^{\infty}z^d \sum_{\lambda \vdash d} s_\lambda(A)s_\lambda(B) \bigg{(} \sum_{k=0}^{\infty} t^k h_k(\operatorname{Cont}_\lambda) \bigg{)}
			\bigg{(} \sum_{l=0}^{\infty} \frac{u^l}{l!} h_1(\operatorname{Cont}_\lambda)^l \bigg{)} \\
		&= \sum_{\lambda \in \mathcal{Y}} Y(\lambda) s_\lambda(A)s_\lambda(B).
	\end{align*}
	
\noindent
Here $\mathcal{Y}$ is the set of all Young diagrams (including the empty diagram) and

	\begin{equation*}
		Y(\lambda) = Y(\lambda;z,t,u) = \prod_{\Box \in \lambda} \frac{ze^{c(\Box)u}}{1-c(\Box)t},
	\end{equation*}

\noindent
where for any Young diagram $\lambda$ and cell $\Box$ in $\lambda$, $c(\Box)$ denotes the content of this
cell, i.e. its column index less its row index.  By convention, an empty product equals $1$.

In order to complete the proof of Theorem \ref{thm:integrability}, we appeal to 
the following result of Orlov and Scherbin \cite{OS}, and Carrell \cite{Carrell}.

	\begin{thm}
		\label{thm:contentProduct}
		Let $\{y_k : k \in \mathbb{Z}\}$ be a set of variables indexed by the integers, and
		set 
		
			\begin{equation*}
				Y(\lambda) = \prod_{\Box \in \lambda} y_{c(\Box)}
			\end{equation*}
			
		\noindent
		for each $\lambda \in \mathcal{Y}$.  The series
		
			\begin{equation*}
				\log \bigg{(} \sum_{\lambda \in \mathcal{Y}} Y(\lambda) s_\lambda(A) s_\lambda(B)\bigg{)}
			\end{equation*}
			
		\noindent
		is a solution of the $2$-Toda lattice hierarchy in the variables
		$p_1(A),p_2(A),\dots$ and $p_1(B),p_2(B),\dots$.
	\end{thm}
	
Solutions of the Toda equations of the form described in Theorem \ref{thm:contentProduct}
are known as \emph{diagonal content-product solutions}.  
Our computations above show that the generating function 

	\begin{equation*}
		\mathbf{H}(z,t,u,A,B) = \log \vec{\mathbf{W}}(z,t,u,A,B)
	\end{equation*}
	
\noindent
of the mixed double Hurwitz numbers is a diagonal content-product 
solution, with 

	\begin{equation*}
		y_k = y_k(z,t,u) = \frac{ze^{ku}}{1-kt}.
	\end{equation*}
	
\noindent
In particular, Okounkov's generating function $\mathbf{H}(z,0,u,A,B)$ for the classical double Hurwitz 
numbers is the diagonal content product solution with 

	\begin{equation*}
		y_k = ze^{ku},
	\end{equation*}
	
\noindent
while the generating function $\mathbf{H}(z,t,0,A,B)$ for the monotone double Hurwitz numbers
is the diagonal content product solution with 

	\begin{equation*}
		y_k = \frac{z}{1-kt}.
	\end{equation*}


\section{Piecewise polynomiality}
\label{sec:Polynomiality}
To prove Theorem \ref{thm:polynomiality}, let us begin by formulating precisely the
relationship between the numbers $W^{k,l}(\alpha,\beta)$ and $H^{k,l}(\alpha,\beta)$.
To this end, consider the generating functions $\mathbf{W}$ and $\mathbf{H}$ as
elements of $\field{Q}[[t,u,A,B]][[z]]$ by writing

	\begin{equation*}
		\mathbf{W}(z) = 1+ \sum_{d=1}^{\infty} \frac{z^d}{d!} \mathbf{W}_d(t,u,A,B), \quad
		\mathbf{H}(z) = \sum_{d=1}^{\infty} \frac{z^d}{d!} \mathbf{H}_d(t,u,A,B),
	\end{equation*}
	
\noindent
where, for each $d \geq 1$,

	\begin{equation*}
		\begin{split}
		 \mathbf{W}_d(t,u,A,B) &= \sum_{k,l=0}^{\infty} t^k\frac{u^l}{l!} \sum_{\alpha,\beta \vdash d} W^{k,l}(\alpha,\beta) p_\alpha(A)p_\beta(B) \\
		  \mathbf{H}_d(t,u,A,B) &= d!\sum_{k,l=0}^{\infty} t^k\frac{u^l}{l!} \sum_{\alpha,\beta \vdash d} H^{k,l}(\alpha,\beta) p_\alpha(A)p_\beta(B).
		  \end{split}
	\end{equation*}
	
\noindent
Then, by the exponential formula, we have 

	\begin{equation*}
		 \mathbf{W}_d(t,u,A,B) = \sum_{r=1}^d\ \sum_{P_1 \sqcup \dots \sqcup P_r}\ \prod_{j=1}^r |P_j|! \mathbf{H}_{|P_j|}(t,u,A,B)
	\end{equation*}	
	
\noindent
for each $d \geq 1$, as an identity in $\field{Q}[[t,u,A,B]]$.
In this identity, the inner sum is over partitions $P_1 \sqcup \dots \sqcup P_r$ of $\{1,\dots,d\}$ 
into $r$ disjoint nonempty sets.  Equating the coefficient of $t^k\frac{u^l}{l!}$ on either side 
of this identity, we obtain

	\begin{align*}
		\sum_{\alpha,\beta \vdash d} W^{k,l}(\alpha,\beta)p_\alpha(A)p_\beta(B) =
		\sum_{r=1}^d\ \sum_{P_1 \sqcup \dots \sqcup P_r}\ \prod_{j=1}^r |P_j|! 
				\sum_{\zeta^j,\eta^j \vdash |P_j|} H^{k,l}(\zeta^j,\eta^j) p_{\eta^j}(A) p_{\zeta^j}(B),
	\end{align*}
	
\noindent
for each $d \geq 1$ and $k,l \geq 0$, as an identity in $\field{Q}[[A,B]]$.  
Note that the sum on the right hand side depends only on the overall block 
structure of the set partition $P_1 \sqcup \dots \sqcup P_r$, and not on the internal structure of the individual blocks.
We can thus replace the right hand side by a sum over integer partitions,

	\begin{equation*}
		\sum_{\alpha,\beta \vdash d} W^{k,l}(\alpha,\beta)p_\alpha(A)p_\beta(B) = 
		\sum_{\theta \vdash d} c_\theta \sum_{\substack{(\zeta^1,\dots,\zeta^{\ell(\theta)})\\ \zeta^j \vdash \theta_j}}
		\sum_{\substack{(\eta^1,\dots,\eta^{\ell(\theta)})\\ \eta^j \vdash \theta_j}} \bigg{(} \prod_{j=1}^{\ell(\theta)} H^{k,l}(\zeta^j,\eta^j) \bigg{)}
		p_{\zeta^1 \cup \dots \cup \zeta^{\ell(\theta)}}(A) p_{\eta^1 \cup \dots \cup \eta^{\ell(\theta)}}(B),
	\end{equation*}
	
\noindent
where the coefficient $c_\theta$ is given by

	\begin{equation*}
		c_\theta = |f^{-1}(\theta)| \prod_{i=1}^{\ell(\theta)} \theta_i!
	\end{equation*}
	
\noindent
and $f$ denotes the surjection 

	\begin{equation*}
		P_1 \sqcup \dots \sqcup P_r \mapsto \bigg{(} \max_{1 \leq j \leq r} |P_j|, \dots, \min_{1 \leq j \leq r} |P_j|\bigg{)}
	\end{equation*}

\noindent	
from set partitions of $\{1,\dots,d\}$ onto integer partitions of $d$.  The internal sums run over 
sequences of partitions whose $j$th element is a partition of the $j$th part of $\theta$, and if $(\mu^1,\dots,\mu^k)$ is any
sequence of partitions then $\mu^1 \cup \dots \cup \mu^k$ denotes the partition obtained by arranging the parts of
$\mu^1,\dots,\mu^k$ in weakly decreasing order.  

Extracting the coefficient of $p_\alpha(A)p_\beta(B)$ on 
each side of the above identity in $\mathbb{Q}[[A,B]]$, we obtain the numerical identity

	\begin{equation*}
		W^{k,l}(\alpha,\beta) = \sum_{\theta \vdash d} c_\theta
		 \sum_{\substack{(\zeta^1,\dots,\zeta^{\ell(\theta)})\\ \zeta^j \vdash \theta_j \\ \zeta^1 \cup \dots \cup \zeta^{\ell(\theta)}=\alpha}}\
		  \sum_{\substack{(\eta^1,\dots,\eta^{\ell(\theta)})\\ \eta^j \vdash \theta_j \\ \eta^1 \cup \dots \cup \eta^{\ell(\theta)}=\beta}} 
		   \prod_{j=1}^{\ell(\theta)} H^{k,l}(\zeta^j,\eta^j).
	\end{equation*}

\noindent
The sum on the right hand side receives non-zero contributions from Young diagrams $\theta$ whose rows
can be obtained by gluing together rows of $\alpha$, and by gluing together rows of $\beta$.  This is 
possible if and only if, for each row $\theta_k$ of $\theta$, there exist subsets $I_k,J_k \subseteq \{1,\dots,d\}$ such 
that 

	\begin{equation}
		\label{eqn:RowConstraint}
		\sum_{i \in I_k} \alpha_i = \sum_{j \in J_k} \beta_j = \theta_k. 
	\end{equation}
	
\noindent
In the case of the one-row Young diagram $\theta=(d)$, the required 
sets are simply $I_1=J_1=\{1,\dots,d\}$, so we have

	\begin{equation*}
		W^{k,l}(\alpha,\beta) = d!H^{k,l}(\alpha,\beta) + \dots,
	\end{equation*}
	
\noindent
where the ellipsis stands for contributions from Young diagrams $\theta$ that have
at least two rows.  These contributions are zero unless the constraint 
\ref{eqn:RowConstraint} is met for each row of $\theta$.
We thus conclude that $W^{k,l}(\alpha,\beta)$ and 
$H^{k,l}(\alpha,\beta)$ typically agree, up to a factor of $d!$.  

We can give a geometric interpretation of the above as follows. 
Fix two positive integers $m$ and $n$ and consider the 
convex region 

	\begin{equation*}
		\mathfrak{R}_{m,n} = \{(x_1,\dots,x_m,y_1,\dots,y_n) : x_1 \geq \dots \geq x_m >0,\ y_1 \geq \dots \geq y_n >0,\ \sum_{i=1}^m x_i = \sum_{j=1}^n y_j\}
	\end{equation*}
	
\noindent
in Euclidean space $\mathbb{R}^{m+n}$.
Pairs of partitions $(\alpha,\beta)$ such that

	\begin{equation*}
		|\alpha|=|\beta|,\quad \ell(\alpha)=m, \quad \ell(\beta)=n
	\end{equation*}
	
\noindent
may be identified with lattice points in $\mathfrak{R}_{m,n}$ via 

	\begin{equation*}
		(\alpha,\beta) \mapsto (\alpha_1,\dots,\alpha_m,\beta_1,\dots,\beta_n).
	\end{equation*} 
	
\noindent
Given proper nonempty subsets $I \subset \{1,\dots,m\}$ and $J \subset \{1,\dots,n\}$, 
define a hyperplane $\mathfrak{W}_{IJ}$ in $\mathbb{R}^{m+n}$ by

	\begin{equation*}
		\mathfrak{W}_{IJ} = \{(x_1,\dots,x_m,y_1,\dots,y_n) \in \mathbb{R}^{m+n} : \sum_{i \in I} x_i = \sum_{j \in J} y_j\}.
	\end{equation*}
	
\noindent
The hyperplanes $\mathfrak{W}_{IJ}$, as $I$ ranges over proper nonempty subsets of $\{1,\dots,m\}$ and
$J$ ranges over proper nonempty subsets of $\{1,\dots,n\}$, constitute the \emph{resonance arrangement} 
of \cite{Johnson}.  A chamber $\mathfrak{c}$ of the resonance arrangement is a connected component of the 
complement of a hyperplane $\mathfrak{W}_{IJ}$ in $\mathfrak{R}_{m,n}$.  On any chamber 
$\mathfrak{c}$ of the resonance arrangement, we have that 

	\begin{equation*}
		W^{k,l}(\alpha,\beta) = d! H^{k,l}(\alpha,\beta)
	\end{equation*}
	
\noindent
for all lattice points $(\alpha,\beta) \in \mathfrak{c}$.

Theorem \ref{thm:polynomiality} claims that for each chamber $\mathfrak{c}$
there exists a polynomial $p_{\mathfrak{c}}^{k,l}$ in $m+n$ variables such that

	\begin{equation*}
		H^{k,l}(\alpha,\beta) = p^{k,l}_{\mathfrak{c}}(\alpha_1,\dots,\alpha_m,\beta_1,\dots,\beta_n)
	\end{equation*}
	
\noindent
for all lattice points $(\alpha,\beta) \in \mathfrak{c}$.  From the above discussion and Section \ref{sec:Toda},
we know that $H^{k,l}(\alpha,\beta)$ is given by the character formula

	\begin{equation}
		\label{eqn:CharacterFormula}
		H^{k,l}(\alpha,\beta) = \frac{|C_\alpha|}{d!} \frac{|C_\beta|}{d!} \sum_{\lambda \vdash d} \chi^\lambda_\alpha
		h_{(k,1^l)}(\operatorname{Cont}_\lambda) \chi^\lambda_\beta, \quad d=|\alpha|=|\beta|,
	\end{equation}
	
\noindent
on any chamber of the resonance arrangement.  In order to deduce Theorem
\ref{thm:polynomiality} from this character formula, we appeal to a recent result of 
Shadrin, Spitz and Zvonkine \cite{SSZ} which asserts the piecewise polynomiality of 
a general class of sums of the above form.
  
Let $\mathbb{C}^{\mathcal{Y}}$ denote the algebra of all functions $\mathcal{Y} \rightarrow \mathbb{C}$. 
Following Olshanski \cite[Proposition 2.4]{Olshanski},
we define the algebra $\mathbb{A}$ of \emph{regular functions} on Young diagrams to 
be the subalgebra of $\mathbb{C}^{\mathcal{Y}}$ generated by the functions

	\begin{equation*}
		\lambda \mapsto f(\operatorname{Cont}_\lambda), \quad f \in \Lambda,
	\end{equation*}
	
\noindent
together with the function $\lambda \mapsto |\lambda|$.  Consider the transform 

	\begin{equation*}
		S: \mathbb{C}^{\mathcal{Y}} \rightarrow \mathbb{C}^{\mathcal{Y} \times \mathcal{Y}}
	\end{equation*}
	
\noindent
from functions on Young diagrams to functions on pairs of Young diagrams defined by

	\begin{equation*}
		S^f(\alpha,\beta) = \frac{|C_\alpha|}{d!} \frac{|C_\beta|}{d!} \sum_{\lambda \vdash d} \chi^\lambda_\alpha
		f(\lambda) \chi^\lambda_\beta,
	\end{equation*}
	
\noindent
where $d=|\alpha|=|\beta|$.  This definition assumes that $\alpha,\beta$ have the same size; if $|\alpha|>|\beta|$ or 
vice versa, complete the smaller diagram by adding unicellular rows.  The result of Shadrin, Spitz and Zvonkine that 
we need may be stated as follows: if $f \in \mathbb{A}$ is a regular function, then $S^f$ is piecewise polynomial with respect to 
the resonance arrangement.

	\begin{thm}
		\label{thm:SSZ}
		Given a regular function $f \in \mathbb{A}$, positive integers $m$ and $n$, and a chamber $\mathfrak{c}$
		of the resonance arrangement in $\mathfrak{R}_{m,n}$, there exists a polynomial $p^f_{\mathfrak{c}}$
		in $m+n$ variables such that
		
			\begin{equation*}
				S^f(\alpha,\beta) = p^f_{\mathfrak{c}}(\alpha_1,\dots,\alpha_m,\beta_1,\dots,\beta_n)
			\end{equation*}
			
		\noindent
		for all lattice points $(\alpha,\beta) \in \mathfrak{c}$.
	\end{thm}
	
From the character formula \ref{eqn:CharacterFormula},
we see that Theorem \ref{thm:polynomiality} follows by applying
Theorem \ref{thm:SSZ} with $f$ the regular function 

	\begin{equation*}
		\lambda \mapsto h_{(k,1^l)}(\operatorname{Cont}_\lambda).
	\end{equation*}


		
\bibliographystyle{amsplain}
\begin{thebibliography}{10}

	\bibitem{Biane}
	P. Biane,
	\textit{Parking functions of types A and B},
	Electron. J. Combin. \textbf{9} (2002), \#N7.

	\bibitem{Carrell}
	S. R. Carrell,
	\textit{Diagonal solutions to the $2$-Toda hierarchy},
	Math. Res. Lett., to appear.
	
	\bibitem{DG}
	P. Diaconis, C. Greene,
	\textit{Applications of Murphy's elements},
	Stanford University Technical Report No. 335, Sept. 1989.
	
	\bibitem{ELSV}
	T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein,
	\textit{Hurwitz numbers and intersections on moduli spaces of curves},
	Invent. Math. \textbf{146} (2001), 297-327.
	
	\bibitem{FH}
	H. K. Farahat, G. Higman,
	\textit{The centres of symmetric group rings},
	Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. \textbf{250}(1261) (1959), 212-221.
	
	\bibitem{GGN1}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Monotone Hurwitz numbers and the HCIZ integral},
	\textsf{arXiv:1107.1015}.
	
	\bibitem{GGN2}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Monotone Hurwitz in genus zero},
	Canad. J. Math, in press.
	
	\bibitem{GGN3}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Polynomiality of monotone Hurwitz in higher genera},
	Adv. Math. \textbf{238} (2013), 1-23.
	
	\bibitem{GJ}
	I. P. Goulden, D. M. Jackson,
	\textit{The KP hierarchy, branched covers, and triangulations},
	Adv. Math. \textbf{219} (2008), 932-951.
	
	\bibitem{GJV}
	I. P. Goulden, D. M. Jackson, R. Vakil,
	\textit{Towards the geometry of double Hurwitz numbers},
	Adv. Math. \textbf{198} (2005), 43-92.
	
	\bibitem{Johnson}
	P. Johnson,
	\textit{Double Hurwitz numbers via the infinite wedge},
	\textsf{arXiv:1008.3266}.
	
	\bibitem{KL}
	M. Kazarian, S. Lando,
	\textit{An algebro-geometric proof of Witten's conjecture},
	J. Amer. Math. Soc. \textbf{20}(4) (2007), 1079-1089.
	
	%\bibitem{Macdonald}
	%I. G. Macdonald,
	%Symmetric Functions and Hall Polynomials, Second Edition, 
	%Oxford University Press, Reprinted 2008.
	
	\bibitem{Okounkov}
	A. Okounkov, 
	\textit{Toda equations for Hurwitz numbers},
	Math. Res. Lett. \textbf{7} (2000), 447-453.
	
	\bibitem{OP}
	A. Okounkov, R. Pandharipande,
	\textit{Gromov-Witten theory, Hurwitz theory, and completed cycles},
	Ann. Math. \textbf{163} (2006), 517-560.
	
	\bibitem{OP2}
	A. Okounkov, R. Pandharipande,
	\textit{The equivariant Gromov-Witten theory of $\mathbf{P}^1$},
	Ann. Math. \textbf{163} (2006), 561-605.
	
	\bibitem{Olshanski}
	G. Olshanski,
	\textit{Plancherel averages: remarks on a paper by Stanley},
	Electron. J. Combin. \textbf{17} (2010), \#R43.
	
	\bibitem{OS}
	A. Yu. Orlov, D. M. Scherbin,
	\textit{Hypergeometric solutions of soliton equations},
	Theoretical and Mathematical Physics \textbf{128}(1) (2001), 906-926.
		
	\bibitem{Pan}
	R. Pandharipande,
	\textit{The Toda equations and the Gromov-Witten theory of
	the Riemann sphere},
	Lett. Math. Phys. \textbf{53} (2000), 59-74.
	
	%\bibitem{Schramm}
	%O. Schramm,
	%\textit{Compositions of random transpositions},
	%Israel J. Math \textbf{147} (2005), 221-243.
	
	%\bibitem{SSV}
	%S. Shadrin, M. Shapiro, A. Vainshtein,
	%\textit{Chamber behavior of double Hurwitz numbers in genus 
	%zero},
	%Adv. Math. \textbf{217} (2008), 79-96.
	
	\bibitem{SSZ}
	S. Shadrin, L. Spitz, D. Zvonkine,
	\textit{On double Hurwitz numbers with completed cycles},
	J. London Math. Soc., to appear.
	
	\bibitem{Stanley}
	R. P. Stanley,
	\textit{Parking functions and noncrossing partitions},
	Electron. J. Combin. \textbf{4}(2) (1997), \#R20.
	

\end{thebibliography}	

\end{document}







1307.2137.extracted_bib
\begin{thebibliography}{10}

	\bibitem{Biane}
	P. Biane,
	\textit{Parking functions of types A and B},
	Electron. J. Combin. \textbf{9} (2002), \#N7.

	\bibitem{Carrell}
	S. R. Carrell,
	\textit{Diagonal solutions to the $2$-Toda hierarchy},
	Math. Res. Lett., to appear.
	
	\bibitem{DG}
	P. Diaconis, C. Greene,
	\textit{Applications of Murphy's elements},
	Stanford University Technical Report No. 335, Sept. 1989.
	
	\bibitem{ELSV}
	T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein,
	\textit{Hurwitz numbers and intersections on moduli spaces of curves},
	Invent. Math. \textbf{146} (2001), 297-327.
	
	\bibitem{FH}
	H. K. Farahat, G. Higman,
	\textit{The centres of symmetric group rings},
	Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. \textbf{250}(1261) (1959), 212-221.
	
	\bibitem{GGN1}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Monotone Hurwitz numbers and the HCIZ integral},
	\textsf{arXiv:1107.1015}.
	
	\bibitem{GGN2}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Monotone Hurwitz in genus zero},
	Canad. J. Math, in press.
	
	\bibitem{GGN3}
	I. P. Goulden, M. Guay-Paquet, J. Novak,
	\textit{Polynomiality of monotone Hurwitz in higher genera},
	Adv. Math. \textbf{238} (2013), 1-23.
	
	\bibitem{GJ}
	I. P. Goulden, D. M. Jackson,
	\textit{The KP hierarchy, branched covers, and triangulations},
	Adv. Math. \textbf{219} (2008), 932-951.
	
	\bibitem{GJV}
	I. P. Goulden, D. M. Jackson, R. Vakil,
	\textit{Towards the geometry of double Hurwitz numbers},
	Adv. Math. \textbf{198} (2005), 43-92.
	
	\bibitem{Johnson}
	P. Johnson,
	\textit{Double Hurwitz numbers via the infinite wedge},
	\textsf{arXiv:1008.3266}.
	
	\bibitem{KL}
	M. Kazarian, S. Lando,
	\textit{An algebro-geometric proof of Witten's conjecture},
	J. Amer. Math. Soc. \textbf{20}(4) (2007), 1079-1089.
	
	%\bibitem{Macdonald}
	%I. G. Macdonald,
	%Symmetric Functions and Hall Polynomials, Second Edition, 
	%Oxford University Press, Reprinted 2008.
	
	\bibitem{Okounkov}
	A. Okounkov, 
	\textit{Toda equations for Hurwitz numbers},
	Math. Res. Lett. \textbf{7} (2000), 447-453.
	
	\bibitem{OP}
	A. Okounkov, R. Pandharipande,
	\textit{Gromov-Witten theory, Hurwitz theory, and completed cycles},
	Ann. Math. \textbf{163} (2006), 517-560.
	
	\bibitem{OP2}
	A. Okounkov, R. Pandharipande,
	\textit{The equivariant Gromov-Witten theory of $\mathbf{P}^1$},
	Ann. Math. \textbf{163} (2006), 561-605.
	
	\bibitem{Olshanski}
	G. Olshanski,
	\textit{Plancherel averages: remarks on a paper by Stanley},
	Electron. J. Combin. \textbf{17} (2010), \#R43.
	
	\bibitem{OS}
	A. Yu. Orlov, D. M. Scherbin,
	\textit{Hypergeometric solutions of soliton equations},
	Theoretical and Mathematical Physics \textbf{128}(1) (2001), 906-926.
		
	\bibitem{Pan}
	R. Pandharipande,
	\textit{The Toda equations and the Gromov-Witten theory of
	the Riemann sphere},
	Lett. Math. Phys. \textbf{53} (2000), 59-74.
	
	%\bibitem{Schramm}
	%O. Schramm,
	%\textit{Compositions of random transpositions},
	%Israel J. Math \textbf{147} (2005), 221-243.
	
	%\bibitem{SSV}
	%S. Shadrin, M. Shapiro, A. Vainshtein,
	%\textit{Chamber behavior of double Hurwitz numbers in genus 
	%zero},
	%Adv. Math. \textbf{217} (2008), 79-96.
	
	\bibitem{SSZ}
	S. Shadrin, L. Spitz, D. Zvonkine,
	\textit{On double Hurwitz numbers with completed cycles},
	J. London Math. Soc., to appear.
	
	\bibitem{Stanley}
	R. P. Stanley,
	\textit{Parking functions and noncrossing partitions},
	Electron. J. Combin. \textbf{4}(2) (1997), \#R20.
	

\end{thebibliography}