%%\documentclass[12pt]{amsart}
\documentclass[finalversion]{FPSAC2020}
\articlenumber{24}
\usepackage{mathrsfs}

\usepackage{mathtools}
\usepackage{amsthm,bm}

%\usepackage{comment}

\usepackage{amsfonts,amsmath,amssymb}
%\usepackage{amsxtra,anysize,times}
\usepackage{tikz, float}
%\usepackage{latexsym}


\usetikzlibrary{arrows,decorations.markings,decorations.pathmorphing}
\usepackage{forest}
\usepackage{enumitem}
\usepackage{tabularx, booktabs}
\newcolumntype{Y}{>{\centering\arraybackslash}X}

%\usepackage[latin1]{inputenc}
\usepackage{subfigure}
\usepackage{xcolor}
\usepackage{multicol}
\usepackage{scalefnt}


\definecolor{mygreen}{rgb}{0.0, 0.5, 0.0}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and
%use \thanks{} for contact details
%\author[Optional shorter names]{Longer names
%me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me
%was partially supported by Grant
%2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here


\author[Eugene Gorsky, Mikhail Mazin, and Monica Vazirani]{Eugene Gorsky\thanks{
\href{mailto:egorskiy@math.ucdavis.edu}{egorskiy@math.ucdavis.edu}.
Partially supported by the NSF grants DMS--1700814 , DMS--1760329 and the Russian Academic Excellence Project 5-100.
}\addressmark{1,3},
Mikhail Mazin\thanks{
\href{mailto:mmazin@math.ksu.edu}{mmazin@math.ksu.edu}.
Partially supported by the Simons Foundation Collaboration Grant for Mathematicians, No.~524324.
}\addressmark{2}, \and
 Monica Vazirani\thanks{
\href{mailto:vazirani@math.ucdavis.edu}{vazirani@math.ucdavis.edu}.
Partially supported by the Simons Foundation Collaboration Grant for Mathematicians, No.~319233.
}\addressmark{1}
}
\address{\addressmark{1}
{Department of Mathematics, University of California at Davis, CA, USA}
\\
\addressmark{2}
{Department of Mathematics, Kansas State University, Manhattan, KS, USA}
\\
\addressmark{3}
{International Laboratory of Representation Theory and Mathematical Physics, NRU-HSE, Moscow, Russia}
}

\received{\today}
\title{Recursions for rational $q,t$-Catalan numbers}

\keywords{rational Dyck paths, rational Catalan combinatorics,
 simultaneous core partitions, invariant integer subsets, semigroups}


\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}%[section]
\newtheorem{conjecture}[lemma]{Conjecture}%[section]
\newtheorem{corollary}[lemma]{Corollary}%[section]
\newtheorem{proposition}[lemma]{Proposition}%[section]
\theoremstyle{definition} %i don't like all those italics
\newtheorem{example}[lemma]{Example}%[section]
\newtheorem{remark}[lemma]{Remark}%[section]
\newtheorem{definition}[lemma]{Definition}%[section] 
 
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\Rspan}{span}
\DeclareMathOperator{\Perm}{Perm}
\DeclareMathOperator{\An}{\mathcal{A}} %generalized Andersen map
\DeclareMathOperator{\Core}{Core}
\DeclareMathOperator{\Quot}{Quot}
%\DeclareMathOperator{\dinv}{dinv}
%\DeclareMathOperator{\arm}{arm}
%\DeclareMathOperator{\leg}{leg}
\newcommand{\dinv}{\mathtt{dinv}}  
\newcommand{\codinv}{\mathtt{codinv}}  
\newcommand{\Cogen}{\mathtt{Cogen}}  
\newcommand{\Ngen}{\mathtt{Ngen}}  
\renewcommand{\a}{\mathtt{g}} % for generic Ngen vs a  
%\renewcommand{\a}{\mathtt{X}} % for generic Ngen , seeing how X looks
\newcommand{\NgenD}{\mathtt{Ngen}(\Delta)}  
\newcommand{\MgenD}{\mathtt{Mgen}(\Delta)}  
\newcommand{\Mgen}{\mathtt{Mgen}}  
\newcommand{\arm}{\mathtt{arm}}  
\newcommand{\leg}{\mathtt{leg}}  
\newcommand{\area}{\mathtt{area}}  
\newcommand{\coarea}{\mathtt{co-area}}  
\newcommand{\gap}{\mathtt{gap}}  
\newcommand{\bepsilon}{\bar{\epsilon}}   % can change if need be

\DeclareMathOperator{\cond}{cond}
\DeclareMathOperator{\hgt}{ht}
\DeclareMathOperator{\PF}{\mathcal{PF}}
%\DeclareMathOperator{\area}{area}
%\DeclareMathOperator{\coarea}{co-area}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\SSRT}{SSRT}
\DeclareMathOperator{\SRT}{SRT}
\DeclareMathOperator{\jump}{jump}
\DeclareMathOperator{\spin}{spin}
\DeclareMathOperator{\ides}{ides}
\DeclareMathOperator{\ias}{ias}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\SSYT}{SSYT}
\DeclareMathOperator{\Dyck}{Dyck}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\st}{st}
 

\newcommand{\mias}{minimal integral acceptable shift}
\newcommand{\miasing}{minimal integral acceptable shifting}
\newcommand{\Sym}{\mathcal{S}} %symmetric group
\newcommand{\Sn}{\Sym_n}
\newcommand{\Sd}{\Sym_d}
\newcommand{\aSmn}{\widetilde{S}_n^m} %m-stable part of AFFINE symm group
\newcommand{\maSn}{{}^m\widetilde{S}_n} %m-restricted part of AFFINE symm groupi
\newcommand{\quotient}[2]{{\left.\raisebox{.2em}{$#1$}\middle/\raisebox{-.2em}{$#2$}\right.}}
\newcommand{\BC}{\mathbb{C}}
\newcommand{\BZ}{\mathbb{Z}}
\newcommand{\BR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}_{\ge 0}}
\newcommand{\aSn}{\widetilde{S}_n}
\newcommand{\CF}{\mathcal{F}}
\newcommand{\CD}{\mathcal{D}}
\newcommand{\CG}{\mathcal{G}}
\newcommand{\CM}{\mathcal{M}}
\newcommand{\CH}{\mathcal{H}}

\newcommand{\om}{\omega}
\newcommand{\rect}{R}
\newcommand{\Rnm}{\rect_{n,m}}
\newcommand{\Rknm}{\rect_{kn,km}}
\newcommand{\RNM}{\rect_{N,M}}

%%%% macros involving m,n 

\newcommand{\M}{\mathbf{M}}  %% or can make mathbb{M}, which looks a bit like matrices 
\newcommand{\Mi}[2]{\M_{#1,#2}}
\newcommand{\Mnm}{\Mi{n}{m}}
\newcommand{\MNM}{\Mi{N}{M}}
\newcommand{\MNkN}{\Mi{N}{kN}}
\newcommand{\ver}{\mathtt{v}}
\newcommand{\hor}{\mathtt{h}}
\newcommand{\bver}{\mathbf{{v}}}
\newcommand{\bhor}{\mathbf{{h}}}
\newcommand{\verc}{\color{red} \mathtt{v}} 
\newcommand{\horc}{\color{blue}{\mathtt{h}}}
\newcommand{\bverc}{\color{red}{\mathbf{{v}}}}
\newcommand{\bhorc}{\color{blue}{\mathbf{{h}}}}
\newcommand{\Y}{Y}
\newcommand{\Yi}[2]{\Y_{{#1,#2}}}
\newcommand{\Ynm}{\Yi{n}{m}}
\newcommand{\YNM}{\Yi{N}{M}}
\newcommand{\nm}{(n,m)} %% for invariant sets %% ok to change notation back
\newcommand{\NM}{(N,M)} %% for invariant sets %% ok to change notation back
%%\newcommand{\l}{\ell} %  now used for leg
\newcommand{\rank}{\mathtt{rank}} % for rank
\newcommand{\Z}{\mathbb{Z}}
%%%%%\usepackage[asymmetric]{geometry}
	% to change the page dimensions for comments
%\geometry{a4paper} % or letterpaper (US) or a5paper or....
\newcommand{\MV}[1]{\marginpar{\tiny{{\color{red} {#1} }}}}
\newcommand{\MVlong}[1]{{{{\color{red} {#1} }}}}
\newcommand{\MM}[1]{\marginpar{\tiny{{\color{mygreen} {#1} }}}}

\newcommand{\bu}{\bm{u}}  %macro - feel free to change
	%% the style, like the old mathbf u or textbf u etc
	%% but i think it is good to be uniform
\newcommand{\bv}{\bm{v}}
\newcommand{\bw}{\bm{w}}
\newcommand{\bx}{\bm{x}}
\newcommand{\by}{\bm{y}}
\newcommand{\bz}{\bm{z}}
\newcommand{\Pu}{P_{\bm{u}}}

\newcommand{\IMN}{I_{M,N}} %% for invariant sets
\newcommand{\IMNo}{I_{M,N}^0} %% for invariant sets zero normalized
\newcommand{\one}{{1^{M+N}}} %%  to replace 1 \ldots 1
\newcommand{\zero}{{0^{M+N}}} %%  to replace 1 \ldots 1
\newcommand{\zeroMN}{{0^{M},0^{N}}} %%  to replace 1 \ldots 1
\newcommand{\ngaps}[1]{\sharp\overline{#1}}
\newcommand{\ngapsD}{\ngapsD{\Delta}}
\newcommand{\gaps}[1]{\overline{#1}}
\newcommand{\gapsD}{\gapsD{\Delta}}

\usepackage{todonotes}

\addbibresource{mn.bib}

\begin{document}
\abstract{
We give a simple recursion labeled by binary sequences which computes rational $q,t$-Catalan power series, both in relatively prime and non relatively prime cases. It is inspired by, but not identical to recursions due to B. Elias, M. Hogancamp, and A. Mellit, obtained in their study of link homology. We also compare our recursion with that of Hogancamp--Mellit's and verify a connection between the Khovanov--Rozansky homology of $(M,N)$ torus links and the rational $q,t$-Catalan power series for general positive $M,N.$

}

\maketitle


\section{Introduction}

In the last decade the rational $q,t$-Catalan numbers attracted a lot of interest in algebraic combinatorics. Given a pair of integers $(M,N)$, we can consider the set of all partitions which are simultaneously $M$- and $N$-cores, that is, none of their hook lengths are divisible by $M$ or $N$. It is easy to see (e.g. \cite{GM2}) that such $(M,N)$-cores are in bijection with the subsets $\Delta\subset\BZ_{\ge 0}$ such that
$0 \in \Delta$, $\Delta+N\subset \Delta,\Delta+M\subset\Delta$ and $\overline{\Delta}:=\BZ_{\ge 0}\setminus\Delta$ is finite. We will relax the normalization condition $0\in\Delta$ and call such subsets \textit{$(M,N)$--invariant}.

If $M$ and $N$ are coprime, then  Anderson \cite{Anderson} proved that the set of $(M,N)$ cores is finite and, in fact, is in bijection with the set $\Dyck(M,N)$ of Dyck paths in the $M\times N$ rectangle. For such paths one can define two statistics $\area$ and $\dinv$ and define a bivariate polynomial
$$
c_{M,N}(q,t)=\sum_{D\in \Dyck(M,N)}q^{\area(D)}t^{\dinv(D)}.
$$
This polynomial generalizes $q,t$-Catalan numbers of Garsia and Haiman \cite{GaHa}  (which appear at $M=N+1$)
 and has 
lots of remarkable properties, for example, it is symmetric in $q$ and $t$. The latter follows from the so-called Rational Shuffle Conjecture \cite{GN,BGLX} recently proved by Mellit \cite{Mellit1}.  The statistic $\dinv$ has several equivalent definitions (see \cref{def:codinv} below); the most elegant one is obtained using the sweep map of Armstrong et.~al.~\cite{ALW,AHJ}. Using the above bijections, one can   translate $\dinv$ as a statistics on $(M,N)$-invariant subsets, which was explicitly defined in \cite{GM1}, see \cref{sec:recursion} for details. Thus, 
\begin{equation}
\label{def cMN}
c_{M,N}(q,t)=\sum_{\Delta\in \IMNo}q^{\area(\Delta)}t^{\dinv(\Delta)}=(1-q)\sum_{\Delta\in \IMN}q^{\area(\Delta)}t^{\dinv(\Delta)}.
\end{equation}
where $\IMN$ ($\IMNo$) denotes the set of 
finite gap $(M,N)$ invariant subsets (resp. with
$0 \in \Delta$). 

If $M$ and $N$ are not coprime, then the sets of $(M,N)$ cores and invariant subsets  are still in bijection and are infinite,
but the relation between them and Dyck paths is more involved. Still, in \cite{GMV16} the authors defined a surjection from $\IMNo$ to $\Dyck(M,N),$ such that the $\dinv$ statistic is constant on the fibers, and the $\area$ statistic behaves in a natural and easily controlled way. In this case one can define $c_{M,N}(q,t)$ by the same equation \eqref{def cMN}. However,  $c_{M,N}(q,t)$ is no longer a polynomial
but a power series. In fact, we will show that it is a rational function with denominator $(1-q)^{d-1}$, where $d =\gcd(M,N)$. 

The work of A. Mellit on the Shuffle Conjecture can be extended to show that the polynomial $(1-q)^{d-1}c_{M,N}(q,t)$ is symmetric in $q$ and $t$ in the non relatively prime case as well. However, to our knowledge, this did not appear in the literature yet. Note that in the non relatively prime case the coefficients of $(1-q)^{d-1}c_{M,N}(q,t)$ are not necessarily positive anymore (see \cref{ex: 22,ex: 33,ex-46}).

One of the most remarkable properties of $c_{M,N}(q,t)$ is its connection to {\em Khovanov--Rozansky homology} of  $(M,N)$ torus links conjectured in \cite{Gor,GN,GNR}. Elias, Hogancamp and Mellit proved this connection in various special cases (see \cite{EH,Hog,Mellit2}). 
In all those cases, the comparison between the power series  $c_{M,N}(q,t)$ and the Poincar\'e power series of this homology is proved by obtaining certain recursions on the topological side and then verifying them on combinatorial side. In a recent preprint \cite{HogMellit} Hogancamp and Mellit introduced a recursion for the Khovanov--Rozansky homology that works for any $(M,N)$ torus link. The terms in these recursions are labeled by binary sequences of varying length. 


We introduce a recursion on the related power series $\Pu(q,t)$,
which are labeled by binary sequences of fixed length $M+N$. 
Our main objective 
is to understand these recursions as clearly as possible in
combinatorial terms, and  the recursions become quite natural expressed
in terms of the sequences $\bu$. 
More precisely, given a finite gap $(M,N)$ invariant subset $\Delta$, we
consider a length $M+N$ binary sequence $\bu=\bu(\Delta)$ recording the
characteristic function of the intersection $\Delta\cap [0,M+N-1]$.
We define
$$
P_{\bu}(q,t):=\sum_{\Delta\in I_{M,N}, \, \bu(\Delta)=\bu}q^{\area(\Delta)}t^{\codinv(\Delta)},
$$
where $\codinv$ is closely related to $\dinv$ (see Definition
\ref{def:codinv} below). Note that one gets $$P_{0^{M+N}}(q,t) = \frac{q^{M+N} t^{\delta(M,N)}}{1-q} c_{M,N}(q,t) .$$
We use it to prove the connection between
$c_{M,N}(q,t)$
and  
the Poincar\'e power series of the Khovanov--Rozansky homology of $(M,N)$
torus links for general $(M,N).$ 
For a more detailed version of this extended abstract, see \cite{GMV19}.






\section*{Acknowledgments}

The authors would like to thank Ben Elias, Matt Hogancamp and Anton Mellit for patiently explaining their work to them and 
sharing the early drafts of \cite{HogMellit}.


The authors also thank the
NSF Focused Research Group ``Algebra and Geometry Behind Link Homology'' 
 for financial support and hosting their participation
in the ``Hilbert schemes, categorification and combinatorics'' workshop
at Davis.



\section{The recursion}
\label{sec:recursion}


Let $(M,N)=(dm,dn)$ be a pair of positive integers, where $m$ and $n$ are relatively prime, so $d=\gcd(M,N).$ 

\begin{definition}
The set $\IMN$ of finite gap
  $M,N$-invariant subsets is defined by
\begin{equation*}
I_{M,N}:=\{\Delta\subset\BZ_{\ge 0}: \Delta+N\subset \Delta,\Delta+M\subset\Delta,\sharp\overline{\Delta}<\infty\},
\end{equation*}
%%\begin{equation*}
%\Delta+N:=\{k\in \BZ: k-N\in\Delta\},
%%\end{equation*}
where 
$\Delta+N:=\{k\in \BZ: k-N\in\Delta\} $
denotes the shift of $\Delta$ by $N,$ %i.e. 
%%the complement to $\Delta,$ is
%%%$\overline{\Delta}:=\BZ_{\ge 0}\setminus\Delta$,
$\overline{\Delta}:=\BZ_{\ge 0}\setminus\Delta$ is the
complement to $\Delta,$
and $\sharp\overline{\Delta}$ is the
number of elements in $\overline{\Delta}.$
The elements of $\overline{\Delta}$ are often called
\textit{gaps} in $\Delta$.
We will more simply refer to such $\Delta$ as invariant subsets.
\end{definition}


%Let $\Delta\subset\BZ_{\ge 0}$ be an $(M,N)$-invariant subset of the set of positive integers, i.e. a subset such that $\Delta+M\subset\Delta$ and $\Delta+N\subset\Delta.$ We will also always assume that $\sharp\overline{\Delta}<\infty$ where $\overline{\Delta}:=\BZ_{\ge 0}\setminus\Delta.$ 

We define statistics $\area$ and $\codinv$ on the invariant
subsets. The $\area$ statistic simply counts the number of gaps
in $\Delta.$
The statistics $\dinv$ and $\codinv$ are  more involved. 

\begin{definition}
We set $\area(\Delta):=\sharp\overline{\Delta}.$
\end{definition}


\begin{definition}
Let $\Delta\in I_{M,N}$ be an invariant subset. The set $\Ngen(\Delta)$ of $N$-generators of $\Delta$ is defined by 
\begin{equation*}
\Ngen(\Delta):=\Delta\setminus(\Delta+N)=\{\a\in\Delta:\a-N\notin\Delta\}.
\end{equation*}
\end{definition} 

%%\begin{remark}
%%The condition $\sharp\overline{\Delta}<\infty$ implies that $\Delta$ has exactly $N$ $N$-generators, one in each remainder modulo $N$.  
%%\end{remark}




\begin{definition}
\label{def:codinv}
%Let $a_1<a_2<\ldots<a_N$ be the set of $N$-generators of $\Delta,$ i.e. $\{a_1,\ldots,a_N\}=\Delta\setminus (\Delta+N).$ 
We set
\begin{equation*}
\codinv(\Delta)=\sum\limits_{\a\in\Ngen(\Delta)} [\a,\a+M-1]\cap\overline{\Delta},
\qquad \dinv = \delta(N,M) - \codinv(\Delta),
\end{equation*}
%where  $\delta(N,M)$ is as in \eqref{eq:delta} and 
%%%where $\delta(N,M):=\frac{NM-N-M+\gcd(M,N)}{2}$ and
where $\delta(N,M):=\frac{1}{2}(NM-N-M+\gcd(M,N))$ and
we use the \textit{integer interval} notation:
\begin{equation*}
[\a,\a+k]:=\{\a,\a+1,\ldots,\a+k\}.
\end{equation*}
\end{definition}


%%Let $I_{M,N}$ be the set of all $(M,N)$-invariant subsets in $\BZ_{\ge 0}. $  %% already defined above 

\begin{definition}
Let ${\bu}=(u_0,\ldots,u_{N+M-1})$ be a sequence of $0$'s and $1$'s. We set
\begin{equation*}
I_{\bu}:=\{\Delta\in I_{M,N}: \forall \, 0\le i< N+M,\ i\in\Delta \Leftrightarrow u_i=1\}.
\end{equation*}
We say that a sequence $\bu$ is \textit{admissible} if $I_{\bu}\neq \emptyset.$ Note that we number the entries of $\bu$ starting at $0$.
\end{definition}  


\begin{definition}
Let the power series $\Pu(q,t)$ be given by
\begin{equation*}
P_{\bu} = P_{\bu}(q,t) :=\sum\limits_{\Delta\in I_{\bu}} q^{\area(\Delta)}t^{\codinv(\Delta)}.
\end{equation*}
\end{definition}

\noindent
Observe $P_{1^{M+N}} =1$, and this is the base case of
our recursion for computing $P_{\bu}$. %% for admissible $\bu$. 


\begin{lemma}
\label{lem: zero and catalan}
One has 
$$
P_{\zero}(q,t)=q^{M+N}\sum_{\Delta\in \IMN}q^{\area(\Delta)}t^{\codinv(\Delta)},
$$
and
$$
c_{M,N}(q,t)=q^{-N-M}t^{\delta(N,M)}(1-q)P_{\zero}(q,t^{-1}).
$$
\end{lemma}
\begin{proof}
Indeed, for $\bu=\zero$ the set $I_{\bu}$ consists of all $(M,N)$--invariant subsets which do not intersect with  $[0,M+N-1]$. All such subsets are obtained from $(M,N)$--invariant subsets in $\IMN$ by shift by $(M+N)$. It is easy to see that the shift does not change $\codinv$ and changes $\area$ by $(M+N)$.  The second formula now follows from Equation \eqref{def cMN} and the relation $\dinv(\Delta)+\codinv(\Delta)=\delta(N,M)$.
\end{proof}

\begin{definition} \label{def:rho}
Define
$\rho:\IMN\to \IMN$
to be the shift map
given by
$$
\rho(\Delta)=
\begin{cases}
\Delta-1 & \text{if } 0\notin\Delta
\\
(\Delta\setminus\{0\})-1 & \text{if } 0\in\Delta.
\end{cases}
$$
\end{definition}
\begin{definition} \label{def:lambda}
Let $\bu \in \{0,1\}^{M+N}$. We define
$$\lambda({\bu}):=\sum\limits_{i=0}^{M-1}(u_{i+N}-u_i).$$
If $\Delta \in I_{\bu}$ we set $\lambda(\Delta):= \lambda(\bu)$.
\end{definition}



\begin{theorem}\label{Theorem: recursion binary N+M}
Let $\bu=(u_0,\ldots,u_{N+M-1})$ be an admissible sequence. Let also 
%%%\begin{equation*}
%\begin{aligned}
%&\bv=(u_1,\ldots,u_{N+M-1},1),\\
%&\bv'=(u_1,\ldots,u_{N+M-1},0).
%\end{aligned}
%\end{equation*}
$$\bv=(u_1,\ldots,u_{N+M-1},1), \qquad
\bv'=(u_1,\ldots,u_{N+M-1},0).$$
The power series $\Pu$ satisfy the following recurrence relation:
\begin{equation}
\label{eq-recursion binary N+M}
\Pu=
\begin{cases} 
q(P_{\bv}+P_{{\bv'}}),& \text{if} \ \ u_0=u_N=u_M=0,\\
qP_{\bv},& \text{if} \ \ u_0=0 \ \  \text{and} \ u_N+u_M>0,\\
t^{\lambda(\bu)}P_{\bv},& \text{if} \ \ u_0=u_N=u_M=1.
\end{cases}
\end{equation}
\end{theorem}

\begin{proof}
%[Proof of \cref{Theorem: recursion binary N+M}]
With respect to the statistics above, the shift map $\rho$
of \cref{def:rho} has the following properties:
\begin{enumerate}
\setlength\itemsep{1pt}
\item[(a)] If $0\notin \Delta,$ then $\area(\rho(\Delta))=\area(\Delta)-1,$ while if $0\in \Delta,$ then $\area(\rho(\Delta))=\area(\Delta).$
\item[(b)] If at least one of the numbers $N$ and $M$ belongs to $\Delta,$ then $N+M-1\in\rho(\Delta),$ while if neither $N$ nor $M$ are in $\Delta,$ then either possibility $N+M-1\in\rho(\Delta)$ or $N+M-1\notin\rho(\Delta)$ may occur.
\item[(c)] If $0\notin \Delta,$ then $\codinv(\rho(\Delta))=\codinv(\Delta).$
\item[(d)] If $0\in \Delta,$ %%%%then 
%%\begin{equation*}
%\codinv(\rho(\Delta))=\codinv(\Delta)-\sharp\left([0,M-1]\cap\overline{\Delta}\right)+\sharp\left([N,N+M-1]\cap\overline{\Delta}\right).
%\end{equation*}  \MV{changed}
$\codinv(\rho(\Delta))=\codinv(\Delta)-\sharp\left([0,M-1]\cap\overline{\Delta}\right)+\sharp\left([N,N+M-1]\cap\overline{\Delta}\right).$
\end{enumerate}
To prove part (d), one should observe that all the $N$-generators of $\Delta,$ except $0,$ are simply shifted down by one in $\rho(\Delta),$ while retaining the same contributions to $\codinv.$ The $N$-generator $0\in\Delta$ get replaced by $N-1\in\rho(\Delta).$ The contribution to $\codinv$ changes accordingly,
and this change is measured by $\lambda(\bu)$ for $\Delta \in I_{\bu}$. 
\end{proof}


%%\MV{do we say somewhere that the tree moves preserve
%%admissibility?}
\begin{definition}
\label{def: decision tree}
We visualize the recursion \eqref{eq-recursion binary N+M} using the {\it decision tree}.
Each node corresponds to a binary sequence $\bu$ and the edges connect $\bu$ with $\bv$ and $\bv'$
and are labeled by the corresponding coefficients:
\begin{center}
\begin{tabular}{p{1.5in} p{1.5in} p{1.5in}}
\quad case 1 & case 2 & case 3 \\
{\scalefont{0.7}
\begin{forest}
[$0\bw$, s sep=7mm
[$\bw 1$,  edge label={node[left,midway]{q}}, edge=->]
[$\bw 0$,  edge label={node[right, midway]{q}},edge=->]]
\end{forest}
} %scalefont
&
{\scalefont{0.7}
\begin{forest}
[$0 \bw$
[$\bw 1$,  edge label={node[right,midway]{q}},edge=->]
]
\end{forest}
} %scalefont
&
{\scalefont{0.7}
\begin{forest}
[$1\bw$
[$\bw 1$,  edge=red, ,edge=->,
	edge label={node[right,midway,red]{$t^{\lambda(1\bw)}$}}]]
\end{forest}
} %scalefont
\end{tabular}
\end{center}
Here $\bw \in \{0,1\}^{M+N-1}$, $\bu=0\bw$ in cases 1 and 2 and $\bu=1\bw$ in case 3,
$\bv=\bw1$ and $\bv'=\bw0$. 
%Note that we can view case 2 as a special instance of case 1 for which $\bw 0$ is {\it not} admissible and so $P_{\bw 0}=0$.
We color edges and labels in case 3 in {\textcolor{red}{red}}
to emphasize that these carry powers of $t$ while
all other (black) edges are labeled by $q$.
\end{definition}


\begin{remark}
\label{rem: decision tree}
If we never identify vertices with the same label, we will
indeed get an infinite tree. However, it is convenient to make the graph finite by 
keeping each $\one$ as a terminal vertex, and identifying the pairs of vertices with the same label, whenever one vertex is a predecessor of another. This leads to directed cycles, which we analyze below. See also 
the examples in \cref{sec:examples}.
\end{remark}

%\begin{definition}
%\label{def-periodic}
%We will call $\bu \in \{0,1\}^{M+N}$ {\em $p$-periodic} if for all $i\in \Z$, $\tilde u_i = \tilde u_{i+p}$, where $\tilde \bu$ is the infinite sequence formed via $\tilde u_{i +r(M+N)} := u_i$ for $r \in \Z$, $0 \le i < M+N$.
%\end{definition}

\begin{theorem}
\label{Theorem: recursion unique}
The recursion in \cref{Theorem: recursion binary N+M} has a unique solution given the initial condition 
$P_{\one}(q,t)=1.$ Moreover, for any sequence $\bu$ the power series $P_{\bu}(q,t)$ can be expressed as a rational function with the denominator $\prod_{i=1}^d (1-q^{\ell_i}),$ where $0<\ell_i<d$ for all $i.$ 
\end{theorem}



We will see in \cref{sec:comparison} that the denominator of
$P_{0^{N+M}}$ can %%, in fact,
be reduced to $(1-q)^d.$

\section{Examples}
\label{sec:examples}

In this section we present some examples of decision trees defined in \cref{def: decision tree} and \cref{rem: decision tree}. 
As all black edges have weight $q$, we can drop this label.
Further, it is sometimes convenient to just record the (new) rightmost
entry at each node, simplifying the picture in \cref{def: decision tree} as follows: 

\begin{center}
{\scalefont{0.7}
\begin{forest}
[{}, s sep=7mm [1] [0]]
\end{forest}
} %scale
\qquad
\qquad
{\scalefont{0.7}
\begin{forest}
[{} [1] ]
\end{forest}
} %scale
\qquad
\qquad
{\scalefont{0.7}
\begin{forest}
[{} [1,  edge=red, edge label={node[right,midway,red]
	{$t^{\lambda(\text{parent} )}$}}]]
\end{forest}
} %scale
\end{center}
Also, we will replace all branches with a single terminal vertex by the corresponding monomial.
We will refer to the result as to ``compact decision tree''.

%%\noindent
%%lthough we call it a decision {\it tree}, we actually draw
%%below a graph with appropriate directed cycles, making
%%the nodes labeled $\one$ terminal.


\begin{example}
\label{ex: 22}
The decision tree  for $(M,N)=(2,2)$ is shown in \cref{fig: 22}.
We %immediately
compute
$$
P_{1011}=qt,\quad P_{0101}=q(P_{1011}+P_{0101}),
\quad
P_{0001}=q^3+q^2P_{0101},
\quad
P_{0000}=qP_{0001}+qP_{0000}.
$$
%%%%so $$ P_{0101}=\frac{q^2t}{1-q}.  $$ Now 
%%$$ P_{0001}=q^3+q^2P_{0101}=q^3+\frac{q^4t}{1-q}.  $$
Finally, 
%%%$$ P_{0000}=qP_{0001}+qP_{0000}
%P_{0000}=\frac{qP_{0001}}{1-q}=\frac{q^4}{1-q}+\frac{q^5t}{(1-q)^2}. $$
%%hence
$$
P_{0101}=\frac{qP_{1011}}{1-q},\quad P_{0000}=\frac{qP_{0001}}{1-q}=\frac{q^4}{1-q}+\frac{q^5t}{(1-q)^2}.
$$
Observe the  $q, t$-symmetry of
%%$
$(1-q)c_{2,2}(q,t)=q^{-4} t (1-q)^2 P_{0000}(q, t^{-1}) = {q+t-qt}$.
%%$$
%\MV{change}
\end{example}


\begin{figure}[ht!]
\begin{center}
\begin{multicols}{2}
{\scalefont{0.6}
\begin{forest}
for tree={s sep= 2em, l=2ex}
[0000, name=root
[000\color{blue}{1}, edge label={node[right,midway] {$q$}}, edge=->
  [001\color{blue}{1}, edge label={node[left, midway] {$q$}}, edge=-> 
[011\color{blue}{1}, edge label={node[right, midway] {$q$}}, edge=->
[111\color{blue}{1}, edge label={node[right, midway] {$q$}}, edge=->]]]
[001\color{blue}{0}, edge label={node[right, midway] {$q$}}, edge=->
[010\color{blue}{1}, edge label={node[right, midway] {$q$}}, edge=->,
name=loop
   [101\color{blue}{1}, edge label={node[left, midway] {$q$}}, edge=->
 [011\color{blue}{1}, edge=red, edge=->, edge label={node[midway,right, red]{t}} 
[111\color{blue}{1}, edge label={node[right, midway] {$q$}}, edge=->]]]
[101\color{blue}{0}, edge label={node[right, midway] {$q$}}, edge=->, name=end] ]
] ] ]
{\scalefont{1.3}
\draw[->, red] (end) .. controls +(south east:1cm) and +(east:2cm) .. 
node[near start,right, red]{$\;1$} (loop);
\draw[->] (root) .. controls +(south east:2cm) and +(east:2cm) .. 
node[near start,right]{\quad $q$} (root);
}
\end{forest}
}

\columnbreak

{\scalefont{0.6}
\begin{forest}
for tree={s sep= 2em, l=1ex}
[0000, name=root
[\color{blue}{1}
 [\color{blue}{1}\\{$q^2$}, align=right, base=top, name=0011  ]
 [\color{blue}{0} [\color{blue}{1}, name=loop
        [\color{blue}{1}\\{$qt$}, align=right, base=top, name=1011 ] 
                                [\color{blue}{0}, name=end] ]
                        ]
 ] ]
{\scalefont{1.3}
\draw[->, red] (end) .. controls +(south east:1cm) and +(east:2cm) .. 
node[near start,right, red]{$1$} (loop);
\draw[->] (root) .. controls +(south east:2cm) and +(east:2cm) .. 
node[near start,right]{\quad $q$} (root);
%%\node at (0011) [below] {\, $q^2$};
%\node at (1011) [below] {\, $qt$};
}
\end{forest}
}
\end{multicols}
\end{center}
\caption{
Decision tree for $(M,N)=(2,2)$ and the corresponding compact decision tree on the right.}
\label{fig: 22}
\end{figure}






\begin{example}
\label{ex: 33}
For $(M,N)=(3,3)$ we compute
\begin{equation*}
q^{-6}{P_{000000}}=\frac{1+qt}{1-q}+\frac{qt^2+2q^2t^2}{(1-q)^2}+\frac{q^3t^3}{(1-q)^3}.
\end{equation*}
Observe the $q, t$-symmetry of 
\begin{align*}
(1-q)^2c_{3,3}(q,t)&=t^3 q^{-6}(1-q)^3 P_{000000}(q, t^{-1})\\
&=q^3t^2+q^2t^3 - 2q^3t-2qt^3 + q^3+t^3  +q^2t+qt^2- 2q^2t^2 +qt
\end{align*}
%%}

\end{example}


\begin{example}
\label{ex-46}
The decision tree  for $(M,N)=(4,6)$ is shown in
\cref{fig: 46}.
%%We remind the reader that although we draw a tree in 
%%\cref{fig: 46},
%%some nodes may have the same label. For example the 
%%nodes labeled ${\color{mygreen} A}$ are $P_{0001010101}$,
%%and the nodes labeled $\color{blue}{(01)^5 }$ are $P_{0101010101}$.
We will use the shorthand notation $P_{0^{10}} := P_{0000000000}$
and $P_{(01)^5} = P_{0101010101}$ and so on. 
We compute
$$
P_{(01)^5} = q P_{(01)^5} + q^2 t (q^3 t + q^4 t^6)
\qquad
P_{0^{10}}=qP_{0^{10}}+qP_{0^9 1}.
$$
%%%and so $$ P_{(01)^5} =  \frac{q^5 t^6}{1-q} (1 + q t).  $$
Hence
\begin{equation*}
\begin{aligned}
{q^{-10}}{P_{0^{10}}}
=\frac{1}{1-q}
\left(q^7t^7
\right.
+ &q^6t^6+q^6t^7
+ q^5t^5+q^5t^6
+ q^4t^4 + q^4t^5 +q^4t^6 \ +
\\
q^3t^3&+ q^3t^4+ 2q^3t^5
\left.
+ q^2t^2+q^2t^3+2q^2t^4
+ qt+qt^2+qt^3
+1 \right) \quad +\\
\frac{1}{(1-q)^2}(&q^4t^6+q^5t^7+q^7t^7+q^8t^8).
\end{aligned}
\end{equation*}
 Observe the $q, t$-symmetry of 
\begin{align*}
 (1-q)c_{4,6}(q,t)&={t^8(1-q)^2}{q^{-10}} P_{0^{10}}(q, t^{-1})\\
  &= -q^8t  - qt^8 + q^8+ t^8 - q^7t^2 - q^2t^7+ q^7t+ qt^7 
- q^6t^3 - q^3t^6+ q^6t  + %qt^6 \ + %overful hbox
\\
&\ \ \ \ \ \ qt^6 + q^5t + qt^5 - q^5t^4 - q^4t^5
- q^4t^3 - q^3t^4 + 2q^4t^2 + 2q^2t^4 + 2q^3t^3.
\end{align*}


\end{example}

\begin{figure}
\begin{center}
\input{tree46tiny}
\end{center}
\caption{Compact decision tree for $(M,N)=(4,6).$}
\label{fig: 46}
\end{figure}

\section{Comparison with the work of Hogancamp and Mellit.}
\label{sec:comparison}

%\subsection{Hogancamp-Mellit recursion}


Our next goal is match this recursion with the $a=0$ specialization of the following recursion due to Hogancamp and Mellit \cite{HogMellit}. 

\begin{definition}[\cite{HogMellit}]
\label{def:R}
The power series $R_{\bx,\by}(q,t,a)$ in variables $q,t$ and $a$ depend on a pair of words $\bx$ and $\by$ in the alphabet $\{0,\times\}.$ These power series satisfy the following recursive relations:

%%%%%%
%\begin{equation*}
%\begin{aligned}
%&R_{0{\bx},0{\by}}=t^{-|{\bx}|}R_{{\bx}\times,{\by}\times}+qt^{-|{\bx}|}R_{{\bx}0,{\by}0},\\
%&R_{\times{\bx},0{\by}}=R_{{\bx}\times,{\by}},\\
%&R_{0{\bx},\times{\by}}=R_{{\bx},{\by}\times},\\
%&R_{\times{\bx},\times{\by}}=(t^{|{\bx}|}+a)R_{{\bx},{\by}},\\
%&R_{\emptyset,\emptyset}=1,
%\end{aligned} 
%\end{equation*}
%%%%%%%
%%%%%%
\begin{minipage}{0.45\textwidth}
\begin{equation*}
\begin{aligned}
&R_{0{\bx},0{\by}}=t^{-|{\bx}|}R_{{\bx}\times,{\by}\times}+qt^{-|{\bx}|}R_{{\bx}0,{\by}0},\\
&R_{\times{\bx},0{\by}}=R_{{\bx}\times,{\by}},\\
&R_{0{\bx},\times{\by}}=R_{{\bx},{\by}\times},\\
%%&R_{\times{\bx},\times{\by}}=(t^{|{\bx}|}+a)R_{{\bx},{\by}},\\
%%&R_{\emptyset,\emptyset}=1,
\end{aligned} 
\end{equation*}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{equation*}
\begin{aligned}
%%&R_{0{\bx},0{\by}}=t^{-|{\bx}|}R_{{\bx}\times,{\by}\times}+qt^{-|{\bx}|}R_{{\bx}0,{\by}0},\\
%%&R_{\times{\bx},0{\by}}=R_{{\bx}\times,{\by}},\\
%%&R_{0{\bx},\times{\by}}=R_{{\bx},{\by}\times},\\
&R_{\times{\bx},\times{\by}}=(t^{|{\bx}|}+a)R_{{\bx},{\by}},\\
&R_{\emptyset,\emptyset}=1,
\end{aligned} 
\end{equation*}
\end{minipage}

\noindent
where $|{\bx}|$ denotes the number of $\times$'s in ${\bx}.$
\end{definition}

\begin{remark}
\label{rem:reverse}
Our recursion differs from the one in \cite{HogMellit} by reversing the order in both sequences $\bx,\by$. 
\end{remark}

In order to compare recursions, we will need to go through certain reformulations and also adjust both the $\area$ and $\codinv$ statistics. First, we will need to replace the binary sequence $\bu$ of length $N+M$ by two sequences $(\bv,\bw)$ in the alphabet $\{0,\bullet,\times\}$ of lengths $M$ and $N$ respectively. Sequence $\bv$ records gaps (encoded by $0$), $N$-generators (encoded by $\times$), and the rest of the elements of $\Delta$ (encoded by $\bullet$) on the interval $[N,N+M-1].$ Similarly, sequence $\bw$ records gaps, $M$-generators, and the rest of the elements of $\Delta$ on the interval $[M,N+M-1].$ More formally, one gets the following definition:

\begin{definition}\label{Definition:vwfromu}
Let ${\bu}=(u_0,\ldots,u_{N+M-1})\in \{0,1\}^{N+M}$ be an admissible binary sequence. Define ${\bv}=(v_0,\ldots,v_{M-1})\in \{0,\bullet,\times\}^M$ and ${\bw}=(w_0,\ldots,w_{N-1})\in \{0,\bullet,\times\}^N$ as follows:

\smallskip

\begin{minipage}{0.45\textwidth}
\begin{enumerate}[wide, labelwidth=!, labelindent=0pt]
\setlength\itemsep{1pt}
\item $v_i=0$ whenever $u_{N+i}=0,$
\item $v_i=\bullet$ whenever $u_{N+i}=u_i=1,$
\item $v_i=\times$ whenever $u_{N+i}=1\ u_i=0.$
\end{enumerate}
\end{minipage}
\quad 
\begin{minipage}{0.45\textwidth}
\begin{enumerate}[wide, labelwidth=!, labelindent=0pt]
\setlength\itemsep{1pt}
\item $w_i=0$ whenever $u_{M+i}=0,$
\item $w_i=\bullet$ whenever $u_{M+i}=u_i=1,$
\item $w_i=\times$ whenever $u_{M+i}=1,\ u_i=0.$
\end{enumerate}
\end{minipage}

\smallskip

We say that a pair of sequences $(\bv,\bw)$ is
admissible if $\bv$ and $\bw$ are obtained from an admissible binary
sequence $\bu$ according to the rule above.
\end{definition} 

Clearly, the pair of sequences $\bv,\bw$ fully determine the binary
sequence $\bu.$
In other words, the above \cref{Definition:vwfromu}
 describes a map
\[
{\mathbf{b}}:\{0,1\}^{M+N} %M+N or N+M ?????
\to \{0,\bullet,\times\}^M \times \{0,\bullet,\times\}^N
\]
and it is injective when restricted to the domain of
admissible sequences. 

 

\begin{definition}\label{Definition: Iv,w Pv,w}
By %slightly
abusing notation, we set \,
$I_{{\bv},{\bw}}:=I_{\bu}$ \, and \,
$ P_{{\bv},{\bw}}(q,t):=P_{\bu}(q,t)$.
%%\begin{equation*}
%I_{{\bv},{\bw}}:=I_{\bu},
%\end{equation*}
%and
%\begin{equation*}
%P_{{\bv},{\bw}}(q,t):=P_{\bu}(q,t),
%\end{equation*}
\end{definition} 


$ P_{{\bv},{\bw}}(q,t)$ satisfies a recursion, given in Theorem
\ref{Theorem: recursion Q_v,w}
below,  
that looks very similar to the $a=0$ version of the 
Hogancamp--Mellit \cite{HogMellit} recursion, but it is
 not exactly the same.
In order to get an exact match, let us make the following adjustments
to the statistics:


\begin{definition}
Define
statistics $\area'$ and $\codinv'$ on the set $\IMN$ of $(M,N)$-invariant subsets in $\BZ_{\ge 0}$ by 
\begin{equation*}
\area'(\Delta)=\sharp (\overline{\Delta}\cap\BZ_{\ge N+M}),
\qquad \text{ and}
\end{equation*}
%%%and
\begin{equation*}
\begin{aligned}
\codinv'(\Delta)=\sum\limits_{\a\in\Ngen(\Delta)}&\sharp\left([\a,\a+M-1]\cap \overline{\Delta}\cap \BZ_{\ge N+M}\right)
-\frac{\lambda(\Delta)(\lambda(\Delta)-1)}{2}\\
%%&-\sharp\{a_1,a_2\in\Ngen(\Delta):N\le a_1<a_2<M+N\}.
\end{aligned}
\end{equation*}
\end{definition}


\begin{definition}
As before, let ${\bu}=(u_0,\ldots,u_{N+M-1})\in\{0,1\}^{N+M}$ be an admissible binary sequence. The generating series $Q_{\bu}(q,t)$ is defined by
\begin{equation*}
Q_{\bu}(q,t):=\sum\limits_{\Delta\in I_{\bu}} t^{-\codinv'(\Delta)}q^{\area'(\Delta)}.
\end{equation*}
When $(\bv,\bw) = \mathbf{b}(\bu)$,
we also set
\begin{equation*}
Q_{{\bv},{\bw}}(q,t):=Q_{\bu}(q,t).
\end{equation*}
\end{definition}

Note that for any $\Delta\in I_{\zero}$ one gets that
$\area'(\Delta)
=%%q^{-N-M}
-N-M + \area(\Delta)$ and 
that  $\codinv'(\Delta)=\codinv(\Delta).$ Therefore,
\begin{equation}\label{Equation: Q vs P}
Q_{\zeroMN}(q,t)=q^{-N-M}P_{\zeroMN}(q,t^{-1}).
\end{equation}

\begin{theorem}\label{Theorem: recursion Q_v,w}
The following recursions hold:

\begin{minipage}{0.45\textwidth}
\begin{equation*}
\begin{aligned}
&P_{0{\bv},0{\bw}}=q(P_{{\bv}\times,{\bw}\times}+P_{{\bv}0,{\bw}0}),\\
&P_{\times{\bv},0{\bw}}=qP_{{\bv}\times,{\bw}\bullet},\\
&P_{0{\bv},\times{\bw}}=qP_{{\bv}\bullet,{\bw}\times},\\
&P_{\times{\bv},\times{\bw}}=qP_{{\bv}\bullet,{\bw}\bullet},\\
&P_{\bullet{\bv},\bullet{\bw}}=t^{|{\bv}|}P_{{\bv}\bullet,{\bw}\bullet}.\\
\end{aligned} 
\end{equation*}
\end{minipage}
\quad %
\begin{minipage}{0.45\textwidth}
\begin{equation*}
\begin{aligned}
&Q_{0{\bv},0{\bw}}=t^{-|{\bv}|}Q_{{\bv}\times,{\bw}\times}+qt^{-|{\bv}|}Q_{{\bv}0,{\bw}0},\\
&Q_{\times{\bv},0{\bw}}=Q_{{\bv}\times,{\bw}\bullet},\\
&Q_{0{\bv},\times{\bw}}=Q_{{\bv}\bullet,{\bw}\times},\\
&Q_{\times{\bv},\times{\bw}}=t^{|{\bv}|}Q_{{\bv}\bullet,{\bw}\bullet},\\
&Q_{\bullet{\bv},\bullet{\bw}}=Q_{{\bv}\bullet,{\bw}\bullet},\\
\end{aligned} 
\end{equation*}
\end{minipage}

where the recursions on the left are
equivalent to those in  \eqref{eq-recursion binary N+M}.
\end{theorem}

The final observation is that in the recursion for $Q$ one can completely ignore %%all
the $\bullet$'s.

\begin{definition}
\label{def:phi}
Let $\phi$ be the map from the words in the alphabet $\{0,\bullet,\times\}$ to the words in the alphabet $\{0,\times\}$ given by simply forgetting all $\bullet$s.
\end{definition}
\begin{theorem}
\label{thm:ignore bullets}
Let $\bx=\phi(\bv)$ and $\by=\phi(\bw).$ Then
\begin{equation*}
R_{\bx,\by}(q,t,0)=Q_{\bv,\bw}(q,t).
\end{equation*}
\end{theorem}


By \cref{thm:ignore bullets} and \cref{lem: zero and catalan} we immediately get the following.

\begin{corollary}
\label{cor:R vs catalan}
We have
$$
R_{0^M,0^N}(q,t,0)=Q_{0^M,0^N}(q,t)=q^{-N-M}P_{0^{M+N}}(q,t^{-1})=\frac{t^{-\delta(N,M)}}{1-q}c_{M,N}(q,t).
$$
\end{corollary}

The Hogancamp--Mellit recursion for the series
$R_{\bx,\by}(q,t,0)$ as well as for the full series
$R_{\bx,\by}(q,t,a)$
has an important advantage over the recursion for $P_{\bu}(q,t):$ one can use it to show that the denominator of $R_{\bx,\by}(q,t,a)$ can be simplified to a power of $(1-q)$ as compared to 
the denominator $\prod_{i=1}^d (1-q^{\ell_i}),$ $0<\ell_i<d$
predicted by \cref{Theorem: recursion unique} before 
reducing expressions. Indeed, the decision tree for the recursion for $R_{\bx,\by}(q,t,a)$ can only have loops of length one, producing $(1-q)$ in the denominator, while the decision trees for $P_{\bu}(q,t)$ might include loops of lengths equal to any divisor of $d,$ producing factors $(1-q^l),\ l<d$ in the denominator.   

\begin{corollary}
The power series $P_{0^{M+N}}(q,t)$ can be expressed as a rational function with denominator equal to  $(1-q)^d,$ where $d=\gcd(N,M).$ 
\end{corollary}

\section{Higher $a$-degrees}
\label{sec-new-higher-a}

The Hogancamp--Mellit construction involves an extra variable $a.$ One can enhance the generating series and the recurrence relations described in 
\cref{sec:recursion} to recover the full three variable functions in the following way.

\begin{definition}
Let $\Delta\in \IMN$ be an invariant subset. A number $k\in\overline{\Delta}$ is called a \textit{double cogenerator} of $\Delta$ if $k+N\in\Delta$ and $k+M\in\Delta.$ Let $\Cogen(\Delta)\subset\overline{\Delta}$ denote the set of all double cogenerators of $\Delta.$
\end{definition}

\begin{remark}
Note that we only consider \textbf{non-negative} double cogenerators. If $\Delta\in I_{0\ldots 0},$ then all cogenerators are positive, so it does not matter for such $\Delta$'s. However, this choice will matter for the recurrence relations.
\end{remark}

We will also need the following statistic:

\begin{definition}
Let $\Delta\in I_{N,M}$ be an invariant subset, and $k\in\BZ$ be an integer. We set
\begin{equation*}
\lambda_k(\Delta):=\sharp(\Ngen(\Delta)\cap [k+N+1,k+N+M]).
\end{equation*}
\end{definition}
%%%%


Now we are ready to define the enhancement of the counting function from \cref{sec:recursion}.

\begin{definition}
Let the power series $\hat{P}_{\bu}(q,t,a)$ be given by
\begin{equation*}
\hat{P}_{\bu}:=\sum\limits_{\Delta\in I_{\bu}} q^{\area(\Delta)}t^{\codinv(\Delta)}\prod\limits_{k\in\Cogen(\Delta)}\left(1+at^{\lambda_k(\Delta)}\right).
\end{equation*}
\end{definition}


\begin{theorem}\label{Theorem: enhanced recursion binary N+M}
Let $\bu=(u_0,\ldots,u_{N+M-1})$ be an admissible sequence. Let also 
\begin{equation*}
\begin{aligned}
&\bv=(u_1,\ldots,u_{N+M-1},1),\\
&\bv'=(u_1,\ldots,u_{N+M-1},0).
\end{aligned}
\end{equation*}
The power series $\hat{P}_{\bu}$ satisfy the following recurrence relation:
\begin{equation*}
\hat{P}_{\bu}=
\begin{cases} 
q(P_{\bv}+P_{\bv'}),& \text{if} \ \ u_0=u_N=u_M=0,\\
qP_{\bv},& \text{if} \ \ u_0=0 \ \  \text{and} \ u_N+u_M=1,\\
q\left(1+at^{\lambda(\bv)}\right)P_{\bv},& \text{if} \ \ u_0=0 \ \  \text{and} \ u_N=u_M=1,\\
t^{\lambda(\bu)}P_{\bv},& \text{if} \ \ u_0=u_N=u_M=1.
\end{cases}
\end{equation*}
\end{theorem}

Similar to \cref{sec:comparison}, in order to match with the recursion of Hogancamp and Mellit, we switch to the adjusted statistics $\area'$, $\codinv'$, and $\dinv'.$

\begin{definition}
\label{def:hatQ}
As before, let ${\bu}=(u_0,\ldots,u_{N+M-1})\in\{0,1\}^{N+M}$ be an admissible binary sequence. The generating series $\hat Q_{\bu}(q,t,a)$ is defined by
\begin{equation*}
\hat{Q}_{\bu}(q,t,a):=\sum\limits_{\Delta\in I_{\bu}} t^{-\codinv'(\Delta)}q^{\area'(\Delta)}\prod\limits_{k\in\Cogen(\Delta)}\left(1+at^{-\lambda_k(\Delta)}\right).
\end{equation*}


We also set
$\hat{Q}_{{\bv},{\bw}}(q,t,a):=\hat{Q}_{\bu}(q,t,a),$
where the sequences ${\bv}=(v_0,\ldots,v_{M-1})\in\{0,\bullet,\times\}^M$ and ${\bw}=(w_0,\ldots,w_{N-1})\in\{0,\bullet,\times\}^N$ are determined in the same way as in \cref{Definition:vwfromu},
i.e. $(\bv,\bw) = \mathbf{b}(\bu)$.
\end{definition}

Note that similar to \cref{sec:comparison}, one gets
$\hat{Q}_{\zeroMN}(q,t,a)=q^{-N-M}\hat{P}_{\zeroMN}(q,t^{-1},a).$

%%%\begin{theorem}\label{Theorem: recursion hatQ_v,w} The
%following recursion holds:
% \begin{equation*} \begin{aligned}
%&\hat{Q}_{0{\bv},0{\bw}}=t^{-|{\bv}|}\hat{Q}_{{\bv}\times,{\bw}\times}+qt^{-|{\bv}|}\hat{Q}_{{\bv}0,{\bw}0},\\
%&\hat{Q}_{\times{\bv},0{\bw}}=\hat{Q}_{{\bv}\times,{\bw}\bullet},\\
%&\hat{Q}_{0{\bv},\times{\bw}}=\hat{Q}_{{\bv}\bullet,{\bw}\times},\\
%&\hat{Q}_{\times{\bv},\times{\bw}}=(t^{|{\bv}|}+a)\hat{Q}_{{\bv}\bullet,{\bw}\bullet},\\
%&\hat{Q}_{\bullet{\bv},\bullet{\bw}}=\hat{Q}_{{\bv}\bullet,{\bw}\bullet},\\
%\end{aligned} \end{equation*} \end{theorem}

\begin{theorem}\label{Theorem: recursion hatQ_v,w}
The following recursion holds:

\begin{minipage}{0.45\textwidth}  %\MV{change}
\begin{equation*}
\begin{aligned}
&\hat{Q}_{0{\bv},0{\bw}}=t^{-|{\bv}|}\hat{Q}_{{\bv}\times,{\bw}\times}+qt^{-|{\bv}|}\hat{Q}_{{\bv}0,{\bw}0},\\
&\hat{Q}_{\times{\bv},0{\bw}}=\hat{Q}_{{\bv}\times,{\bw}\bullet},\\
&\hat{Q}_{0{\bv},\times{\bw}}=\hat{Q}_{{\bv}\bullet,{\bw}\times},
\end{aligned} 
\end{equation*}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{equation*}
\begin{aligned}
&\hat{Q}_{\times{\bv},\times{\bw}}=(t^{|{\bv}|}+a)\hat{Q}_{{\bv}\bullet,{\bw}\bullet},\\
&\hat{Q}_{\bullet{\bv},\bullet{\bw}}=\hat{Q}_{{\bv}\bullet,{\bw}\bullet}.\\
\end{aligned} 
\end{equation*}
\end{minipage}
\end{theorem}


\begin{corollary}\label{cor:R vs hatQ}
Let $\bx=\phi(\bv)$ and $\by=\phi(\bw).$ 
Then
$R_{\bx,\by}(q,t,a)
=\hat{Q}_{\bv,\bw}(q,t,a).$
\end{corollary}


\printbibliography
\end{document}

