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

\usepackage{amsfonts,tikz}
\usetikzlibrary{patterns}
\usepackage{graphicx, subcaption}
%\usepackage{todonotes}
\usepackage{genyoungtabtikz}
\usepackage{ytableau}
\ytableausetup{smalltableaux, centertableaux}
\usepackage{diagbox}


\colorlet{myblue}{cyan!50}
\colorlet{myorange}{orange!50}

\YFrench
\Yvcentermath1
\Yboxdim{0.5cm}
\newcommand{\Yred}{\Yfillcolour{red}}
\newcommand{\Ycyan}{\Yfillcolour{myblue}}
\newcommand{\Ywhite}{\Yfillcolour{white}}	



%\newcommand{\gmf}[1]{\textcolor{blue}{\textbf{#1}}}
%\newcommand{\igmf}[1]{\todo[color=blue!50,inline]{\textbf{Gabe:}  #1}}
%\newcommand{\Flo}[1]{{\color{red} #1}}
%\newcommand{\flo}[1]{\todo[color=red!50]{\textbf{Flo:}  #1}}
%\newcommand{\iflo}[1]{\todo[color=red!50,inline]{\textbf{Flo:}  #1}}


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

%\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rem}[thm]{Remark}

\DeclareMathOperator{\nw}{nw}
\DeclareMathOperator{\shift}{shift}

\newcommand{\RS}{{\rm RS}}
\newcommand{\RSK}{{\rm RSK}}
\newcommand{\dRSK}{qt{\rm RSK}^*}
\newcommand{\qrst}{q{\rm RS}t}
\newcommand{\Ret}{\mathbf{R}}
\newcommand{\Set}{\mathbf{S}}
\newcommand{\SYT}{{\rm SYT}}
\newcommand{\SSYT}{{\rm SSYT}}
\newcommand{\la}{\lambda}
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\rk}{{\rm rank}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\col}{{\rm col}}
\newcommand{\row}{{\rm row}}
\newcommand{\vp}{\varphi}
\newcommand{\hl}[1]{h_{#1}^\ell}
\newcommand{\ha}[1]{h_{#1}^a}

\newcommand{\ds}{\displaystyle}
\newcommand{\mb}[1]{\mathbf{#1}}
\newcommand{\bb}[1]{\mathbb{#1}}
\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\wh}[1]{\widehat{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\deff}[1]{\emph{\color{rub-grun} #1}} % emphasis of a definition
%\newcommand{\deff}[1]{\emph{\color{cyan!80!blue!80!black} #1}} % emphasis of a definition
\newcommand{\tb}[1]{\textbf{#1}}


\newcommand{\lacell}{
\begin{tikzpicture}[scale=0.4]
\draw[thick, magenta, pattern=horizontal lines, pattern color=magenta] (0,0) rectangle (1,1);
\end{tikzpicture}
}
\newcommand{\mucell}{
\begin{tikzpicture}[scale=0.4]
\draw[thick, orange, fill=myorange] (0,0) rectangle (1,1);
	\node at (.5,.5) {$-$};
\end{tikzpicture}
}
\newcommand{\nucell}{
\begin{tikzpicture}[scale=0.4]
\draw[thick, blue, fill=myblue] (0,0) rectangle (1,1);
	\node at (.5,.5) {$+$};
\end{tikzpicture}
}
\newcommand{\rhocell}{
\begin{tikzpicture}[scale=0.4]
\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (0,0) rectangle (1,1);
\end{tikzpicture}
}

\newcommand{\circled}[1]{
\begin{tikzpicture}[scale=0.4]
\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (0,0) rectangle (1,1);
\end{tikzpicture}
}

\makeatletter
\newcommand\mathcircled[1]{
  \mathpalette\@mathcircled{#1}
}
\newcommand\@mathcircled[2]{%
  \tikz[baseline=(math.base)] \node[draw,circle,inner sep=1pt] (math) {$\m@th#1#2$};%
}
\makeatother



\title{$qt{\rm RSK}^*$: A probabilistic dual RSK correspondence for Macdonald polynomials}
\author{Gabriel Frieden\thanks{\href{mailto:gabriel.frieden@mcgill.ca}{gabriel.frieden@mcgill.ca}}\addressmark{1} \and Florian Schreier-Aigner\thanks{\href{mailto:florian.schreier-aigner@univie.ac.at}{florian.schreier-aigner@univie.ac.at}. FSA was supported by Austrian Science Fund FWF: J4387, P34931 and      P36863.}\addressmark{2}}
\address{\addressmark{1}McGill University, Canada \\ \addressmark{2}University of Vienna, Austria}

%% put the date of submission here
\received{\today}
%% leave this blank until submitting a revised version
%\revised{}

\abstract{We introduce a probabilistic generalization of the dual Robinson--Schensted--Knuth correspondence, called $qt{\rm RSK}^*$, depending on two parameters $q$ and $t$. This correspondence extends the $q{\rm RS}t$ correspondence, recently introduced by the authors, and allows the first tableaux-theoretic proof of the dual Cauchy identity for Macdonald polynomials. By specializing $q$ and $t$, one recovers the row and column insertion version of the classical dual RSK correspondence as well as of $q$- and $t$-deformations thereof which are connected to $q$-Whittaker and Hall--Littlewood polynomials, but also a novel correspondence for Jack polynomials.}

\keywords{dual RSK, growth diagrams, Macdonald polynomials, Jack polynomials}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{dual_qtRSK.bib}



\begin{document}
\maketitle

\section{Introduction}
\label{sec:intro}

The Robinson--Schensted--Knuth (RSK) correspondence is a bijection between matrices of nonnegative integers with finite support and pairs of semistandard Young tableaux of the same shape and has significant applications in combinatorics, representation theory, probability theory and algebraic geometry. 
It was introduced by Knuth \cite{Knuth70} and generalizes the Robinson--Schensted correspondence (RS) introduced by Robinson \cite{Robinson38} for permutations and independently by Schensted \cite{Schensted61} for words.  A closely related bijection is the dual RSK correspondence ($\RSK^*$) introduced by Knuth \cite{Knuth70}  which yields a bijective proof of the dual Cauchy identity
\begin{equation}
\label{eq:dual cauchy}
\sum_{\la}s_\la(\x) s_{\la^\prime}(\y) = \prod_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}} (1+x_iy_j),
\end{equation}
where the sum is over all partitions $\la$, $s_\la$ denotes the Schur polynomial in the variables $\mb{x}=(x_1,\ldots,x_m)$ or $\y=(y_1,\ldots,y_n)$ respectively, and $\la^\prime$ is the conjugate of $\la$.


%The Robinson--Schensted--Knuth (RSK) correspondence is a bijection between matrices of nonnegative integers with finite support and pairs of semistandard Young tableaux of the same shape. It was introduced by Knuth \cite{Knuth70} and generalizes the Robinson-Schensted (RS) correspondence which was introduced by Robinson \cite{Robinson38} for permutations and independently by Schensted \cite{Schensted61} for words\footnote{We refer by ``RS'' to the special case of RSK for permutations and by ``RS for words'' to the special case of RSK for words.}. Both correspondences have many applications in combinatorics, representation theory, probability theory and algebraic geometry. In particular RSK gives a bijective proof of the Cauchy identity
%\begin{equation}
%\label{eq:cauchy}
%\sum_\la s_\la(\x)s_\la(\y) = \prod_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}} \frac{1}{1-x_iy_j},
%\end{equation}
%where the sum is over all partitions $\la$ and $s_\la(\mb{z})$ denotes the Schur polynomial in the variables $\mb{x}=(x_1,x_2,\ldots,x_m)$ or $\y=(y_1,\ldots,y_n)$ respectively. A closely related bijection is the dual RSK correspondence ($\RSK^*$) introduced by Knuth \cite{Knuth70}  which yields a bijective proof of the dual Cauchy identity
%\begin{equation}
%\label{eq:dual cauchy}
%\sum_{\la}s_\la(\x) s_{\la^\prime}(\y) = \prod_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}} (1+x_iy_j),
%\end{equation}
%where the sum is again over all partitions $\la$.


All of the above mentioned correspondences have been extended in various directions throughout the last few decades. Among others several randomized generalizations of RS, RSK and $\RSK^*$ were introduced in
\cite{BorodinPetrov16, BufetovMatveev18, BufetovPetrov15, MatveevPetrov17, OConnellPei13, Pei14, Pei17}. These generalizations associate to each permutation or nonnegative integer matrix respectively a distribution on pairs of (dual) (semi)standard Young tableaux depending on a parameter $q$ or $t$ and thereby giving a proof of the (dual) Cauchy identity for $q$-Whittaker or Hall--Littlewood symmetric functions. Similar to the classical RSK algorithm, these randomized generalizations have many applications to probabilistic models, compare for example with \cite{BorodinPetrov16,BufetovMatveev18,BufetovPetrov15,MatveevPetrov17}.


In a previous paper \cite{AignerFrieden22}, the authors introduced a randomized generalization for RS called $\qrst$ depending on two parameters $q$ and $t$. This generalization was designed to prove the squarefree part of the Cauchy identity for the Macdonald symmetric functions $P_\la(\x;q,t)$ and $Q_\la(\x;q,t)$. Analogously to Macdonald symmetric functions, which specialize to $q$-Whittaker, Hall--Littlewood and Schur symmetric polynomials, the $\qrst$ correspondence specializes to the corresponding randomized variations of RS, and to the row and column insertion versions of RS itself for $q=t=0$ or $q=t\rightarrow \infty$ respectively.\bigskip

In this abstract we present a unifying generalization of both $\qrst$ and $\RSK^*$, called $\dRSK$, and thereby give the first tableaux-theoretic proof of the dual Cauchy identity for Macdonald polynomials
\begin{equation}
\label{eq:dual cauchy mac}
\sum_\la P_\la(\x;q,t) P_{\la^\prime}(\y;t,q) = \prod_{\substack{1 \leq i \leq m \\ 1 \leq j \leq n}} (1+x_iy_j).
\end{equation}
Our map specializes to known randomized generalizations of $\RSK^*$ by specializing $q$ or $t$ respectively, and to $(q,t)$-variations of RS for words or RS, i.e., $\qrst$, by restricting the input matrices. In particular we obtain a novel correspondence for Jack polynomials with an intriguing property when restricting to words.
% we obtain an intriguing property of our correspondence when restricting to Jack polynomials.

This extended abstract is organized as follows. In \S \ref{sec:dual cauchy} we present the notion of an insertion algorithm by using local growth rules. In \S \ref{sec:Mac} we review Macdonald polynomials and introduce $(q,t)$-analogue of up and dual down operators. In \S \ref{sec:probabilities} we define the forward and backward probabilities which are the building block of $\dRSK$ which is introduced in \S \ref{sec:dual RSK}. In \S \ref{sec:properties} we discuss the properties of $\dRSK$. For further details, including the proofs, we refer the reader to our paper \cite{FriedenSchreierAigner24}.

\subsection*{Notation}
We assume the reader is familiar with (skew) Young diagrams, semistandard Young tableaux (abbreviated $\SSYT$), and Schur polynomials, as defined, e.g., in \cite[Ch. 7]{EC2}. We draw Young diagrams in French notation and starting from \S\ref{sec:probabilities} in \deff{Quebecois notation}, in which the boxes are right-justified instead of left-justified.  We write $\SSYT(\la)$ (resp., $\SSYT^*(\la)$) for the set of SSYTs (resp., dual SSYTs) of shape $\la$, where a dual SSYT is a filling of the cells of $\la$ with strictly increasing rows and weakly increasing columns. If $T$ is a (dual) SSYT, we denote by $T^{(i)}$ the shape of the subtableau consisting of entries at most $i$.



\section{Insertion algorithms and local dual growth rules}
\label{sec:dual cauchy}


\deff{Young's lattice} is the partial order $(\bb{Y}, \subseteq)$  on partitions defined by the inclusion of Young diagrams; its meet and join are given by $\cap$ and $\cup$, respectively. 
 We say that $\la/\mu$ is a \deff{horizontal strip} (resp., vertical strip) if no two cells of $\la / \mu$ are in the same column (resp., row), where we use the notation $\mu \prec \la$ (resp., $\mu \prec^\prime \la$). 
We define the \deff{up operator} $U_x$ and \deff{dual down operator} $D_y^*$ as $\bb{Q}(x,y)$-linear maps on the $\bb{Q}(x,y)$-vector space $\bb{Q}(x,y)\bb{Y}$ with basis $\bb{Y}$ via
\[
U_x \lambda = \sum_{\nu \succ \la} x^{|\nu / \la|} \nu, \qquad \qquad
D_y^* \lambda = \sum_{\mu \prec^\prime \la} y^{|\la / \mu|} \mu.
\]
The up and dual down operator satisfy the commutation relation
\begin{equation}
\label{eq:Schur dual commutation relation}
D_y^* U_x = (1+xy) U_x D_y^*.
\end{equation}
The commutation relation immediately implies the dual Cauchy identity \eqref{eq:dual cauchy}. Indeed by rewriting the Schur polynomials as
\begin{equation}
\label{eq:Schur via up and down}
s_\la(\x) = \left\langle U_{x_m} \cdots U_{x_1} \emptyset, \la \right\rangle, \qquad\qquad
s_{\la^\prime}(\y) = \left\langle D^*_{y_1} \cdots D^*_{y_n} \la, \emptyset \right\rangle,
\end{equation}
where $\langle \cdot,\cdot\rangle$ is the inner product defined by $\langle \lambda, \mu \rangle = \delta_{\lambda,\mu}$, for all $\la,\mu \in \bb{Y}$, the dual Cauchy identity follows by a straight forward induction using the commutation relation, see for example \cite[\S 2.2]{FriedenSchreierAigner24}.
%Note that the commutation relation \eqref{eq:Schur dual commutation relation} is a special case of the skew version of the dual Cauchy identity for Schur polynomials, compare to \cite[Ch. 1, Eq. (5.8 a)]{Mac}.
Define the sets $\U^k(\la,\rho):=\{ \nu : \la \prec^\prime \nu \succ \rho, |\nu / (\la \cup \rho)|=k\}$ and $\D^k(\la,\rho) := \{ \mu : \la \succ \mu \prec^\prime \rho, |(\la \cap \rho)/\mu|=k\}$.
The equation \eqref{eq:Schur dual commutation relation} can be reformulated as the set of equations
\begin{equation}
\label{eq:up-down on sets}
|\U^k(\la,\rho)| = |\D^k(\la,\rho)| + |\D^{k-1}(\la,\rho)|.
\end{equation}
for all partitions $\la,\rho$ and non-negative integers $k$. It turns out to be quite fruitful to prove these equations bijectively. 

An \deff{inner corner} of a partition $\lambda$ is a cell $c \in \la$ such that $\la/\mu = \{c\}$ for a partition $\mu \subseteq \la$. An \deff{outer corner} of $\la$ is a cell $c \notin \la$ such that $\nu/\la =\{c\}$ for a partition $\nu$ with $\la \subseteq \nu$.
 We call an inner corner $c$ of $\la \cap \rho$ \deff{removable} with respect to $(\la,\rho)$ if $\la/\mu$ is a horizontal strip and $\rho/\mu$ is a vertical strip, where $(\la \cap \rho)/\mu=\{c\}$. Analogously we call an outer corner $c$ of $\la \cup \rho$ \deff{addable} with respect to $(\la,\rho)$ if $\nu/\la$ is a vertical strip and $\nu/\rho$ is a horizontal strip, where $\nu/(\la \cup \rho)=\{c\}$. For both removable and addable corners we omit referring to $(\la,\rho)$ whenever the partitions $\la,\rho$ are clear from context.
For an example see Figure~\ref{fig:inner outer corners}.


\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.1]
\tyng(0,0,7,5,3,2,2)
\draw[fill, color=myorange] (3,.5) rectangle (3.5,0);
\draw (3,.5) rectangle (3.5,0);
\draw[fill, color=myorange] (2,.5) rectangle (2.5,1);
\draw (2,.5) rectangle (2.5,1);
\draw[fill, color=myorange] (1,1.5) rectangle (1.5,1);
\draw (1,1.5) rectangle (1.5,1);
\draw[fill, color=myorange] (1,2.5) rectangle (.5,2);
\draw (1,2.5) rectangle (.5,2);
\node at (3.25,.25) {$-$};
\node at (2.25,.75) {$-$};
\node at (1.25,1.25) {$-$};
\node at (.75,2.25) {$-$};

\draw[line width=1.75pt] (0,0) -- (3.5,0) -- (3.5,.5) -- (2.5,.5) -- (2.5,1) -- (1.5,1) -- (1.5,1.5) -- (1,1.5) -- (1,2.5) -- (0,2.5) -- (0,0) -- (1,0);

\begin{scope}[xshift=4.5cm]
\tyng(0,0,8,7,4,2,2,1)
%\draw[thick, magenta, pattern=horizontal lines, pattern color=magenta] (2.5,.5) rectangle (3.5,1);
%\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (3.5,.5) rectangle (4,0);
%\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (2,1) rectangle (1.5,1.5);
%\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (0,2.5) rectangle (.5,3);
\draw[fill, color=myblue] (4.5,.5) rectangle (4,0);
\draw[fill, color=myblue] (3.5,.5) rectangle (4,1);
\draw[fill, color=myblue] (2.5,1.5) rectangle (2,1);
\draw[fill, color=myblue] (1,1.5) rectangle (1.5,2);
\draw[fill, color=myblue] (1,2.5) rectangle (.5,3);
\draw[fill, color=myblue] (0,3.5) rectangle (.5,3);

\node at (.25,3.25) {$+$};
\node at (.75,2.75) {$+$};
\node at (1.25,1.75) {$+$};
\node at (2.25,1.25) {$+$};
\node at (3.75,.75) {$+$};
\node at (4.25,.25) {$+$};

\draw[line width=1.75pt] (0,0) -- (4,0) -- (4,.5) -- (3.5,.5) -- (3.5,1) -- (2,1) -- (2,1.5) -- (1,1.5) -- (1,2.5) -- (.5,2.5) -- (.5,3) -- (0,3) -- (0,0) -- (1,0);
\end{scope}

\begin{scope}[xshift=10cm]
\tyng(0,0,7,5,3,2,2)
\draw[thick, magenta, pattern=horizontal lines, pattern color=magenta] (2.5,.5) rectangle (3.5,1);
\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (3.5,.5) rectangle (4,0);
\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (2,1) rectangle (1.5,1.5);
\draw[thick, green!70!black, pattern=vertical lines, pattern color=green!70!black] (0,2.5) rectangle (.5,3);
\draw[fill, color=myorange] (2,.5) rectangle (2.5,1);
\draw (2,.5) rectangle (2.5,1);
\draw[fill, color=myorange] (1,2.5) rectangle (.5,2);
\draw (1,2.5) rectangle (.5,2);
\draw[fill, color=myblue] (3.5,.5) rectangle (4,1);
\draw[fill, color=myblue] (1,1.5) rectangle (1.5,2);
\draw[fill, color=myblue] (0,3.5) rectangle (.5,3);

\node at (.25,3.25) {$+$};
\node at (1.25,1.75) {$+$};
\node at (3.75,.75) {$+$};
\node at (2.25,.75) {$-$};
\node at (.75,2.25) {$-$};

\draw[line width=1.75pt] (0,0) -- (3.5,0) -- (3.5,.5) -- (2.5,.5) -- (2.5,1) -- (1.5,1) -- (1.5,1.5) -- (1,1.5) -- (1,2.5) -- (0,2.5) -- (0,0) -- (1,0);
\end{scope}

\begin{scope}[yshift=.25cm]
\begin{scope}[xshift=.25cm]
\node at (1,-1) {\lacell};
\node at (1,-1.5) {$\lambda/ (\lambda \cap \rho) = (\lambda \cup \rho)/\rho$};
\end{scope}

\begin{scope}[xshift=5.25cm]
\node at (1,-1) {\rhocell};
\node at (1,-1.5) {$\rho/ (\lambda \cap \rho)=(\lambda \cup \rho) / \lambda$};
\end{scope}

\begin{scope}[xshift=9cm]
\node at (1,-1) {\mucell};
\node at (1,-1.5) {inner corner};
\end{scope}

\begin{scope}[xshift=12cm]
\node at (1,-1) {\nucell};
\node at (1,-1.5) {outer corner};
\end{scope}
\end{scope}

\end{tikzpicture}
\end{center}
\caption{\label{fig:inner outer corners}
For $\la=(7,7,3,2,2)$ and $\rho=(8,5,4,2,2,1)$: (left) the partition $\la \cap \rho$ together with all inner corners, (middle) the partition $\la \cup \rho$ with all outer corners, and (right) $\la \cap \rho$ with all \deff{removable} inner corners of $\la \cap \rho$ and \deff{addable} outer corners of $\la \cup \rho$. At the bottom we show the color and shading code for cells in certain skew shapes.
}
\end{figure}




%\iflo{change paragraph below}
%Denote by $d$ the number of removable inner corners of $\la \cap \rho$. For a subset $\Ret \subseteq [d] = \{1,2,\ldots d\}$ we define $\mu^{(\Ret)}$ as the partition obtained by removing from $\la \cap \rho$ the $i$-th removable inner corner, counted from bottom to top, for all $i\in \Ret$. For a subset $\Set\subseteq [0,d]=\{0,1,\ldots, d\}$ we define $\nu^{(\Set)}$ as the partition obtained by adding to $\la \cup \rho$ the $i$-th addable (``supplementable'') outer corner, where we count the addable outer corners again from bottom to top but starting with $0$.
%\bigskip
%
%Denote by $d$ the number of removable inner corners of $\la \cap \rho$. We label the removable inner corners of of $\la \cap \rho$ from bottom to top by $1,\ldots,d$ and the addable outer corners of $\la \cup \rho$ from bottom to top by $0,\ldots,d$. Each partition $\mu$ in $\D^k(\la,\rho)$ corresponds to a $k$-subset $\Ret$ of the removable inner corners of $\la \cap \rho$, i.e., $\Ret \subseteq [d]=\{1,\ldots,d\}$. Analogously each partition $\nu$ in $\U^k(\la,\rho)$ corresponds to a $k$-subset $\Set$ of the addable outer corners of $\la \cup \rho$


Each partition $\nu$ in $\U^k(\la,\rho)$ corresponds to a $k$-subset of the addable outer corners of $\la \cup \rho$ and each partition $\mu$ in $\D^k(\la,\rho)$ corresponds to a $k$-subset of the removable inner corners of $\la \cap \rho$. We call a collection $F_\bullet=\{F_{\la,\rho,k}: \la,\rho \in \bb{Y}, k \in \bb{N}\}$ of bijections
\[
F_{\la,\rho,k}: \D^{k-1}(\la,\rho) \cup \D^k(\la,\rho) \rightarrow \U^k(\la,\rho),
\]
a set of \deff{local dual growth rules}.
Two of the many possible bijections $F_{\la,\rho,k}$ are very natural: the \deff{dual row insertion bijection}  $F_{\la,\rho,k}^\row$ and the \deff{dual column insertion bijection} $F_{\la,\rho,k}^\col$.
%which are defined as
 For $k=1$ the dual row (resp., column) insertion bijection maps a removable inner corner to the next addable outer corner in a row above (resp., column to the right) and sends the empty set to the lowest (resp., left-most) addable outer corner. Figure \ref{fig: row and col insertion map} illustrates this case. For $k> 1$ both maps are defined recursively by
\begin{equation}
\label{eq:recursion for F bijection}
F^\bullet_{\la,\rho,k} (X) = \begin{cases}
\bigcup\limits_{x \in X} F^\bullet_{\la,\rho,1}(\{x\}) \qquad &|X|=k, \\
F^\bullet_{\la,\rho,1}(\emptyset) \cup \bigcup\limits_{x \in X} F^\bullet_{\la,\rho,1}(\{x\})  &|X|=k-1,
\end{cases}
\end{equation}
where $F^\bullet_{\la,\rho,k}$ stands for $F^\row_{\la,\rho,k}$ or $F^\col_{\la,\rho,k}$ respectively.
%\[
%F_{\la,\rho,k}^{\row}(\Ret) = \begin{cases}
%\Ret \quad & |\Ret|=k,\\
%\Ret \cup\{0\} & |\Ret|=k-1,
%\end{cases} \qquad
%F_{\la,\rho,k}^{\col}(\Ret) = \begin{cases}
%\{x-1:x\in \Ret\} \quad & |\Ret|=k,\\
%\{x-1:x\in \Ret\} \cup\{d\} & |\Ret|=k-1,
%\end{cases}
%\]



\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1]
\tyng(0,0,8,8,4,3,2,1)
\draw[fill, color=myorange] (2,.5) rectangle (2.5,1);
\draw (2,.5) rectangle (2.5,1);
\draw[fill, color=myorange] (1,2.5) rectangle (.5,2);
\draw (1,2.5) rectangle (.5,2);
\draw[fill, color=myblue] (3.5,.5) rectangle (4,1);
\draw[fill, color=myblue] (1,1.5) rectangle (1.5,2);
\draw[fill, color=myblue] (0,3.5) rectangle (.5,3);

\draw[line width=1.75pt] (0,0) -- (4,0) -- (4,.5) -- (3.5,.5) -- (3.5,1) -- (2,1) -- (2,1.5) -- (1,1.5) -- (1,2.5) -- (.5,2.5) -- (.5,3) -- (0,3) -- (0,0) -- (1,0);
\node at (2,-.5) {$F^\row_{\la,\rho,1}$};
\draw [->,line width=1.3pt] (2.25,.75) to [out=90,in=0] (1.25,1.75);
\draw [->,line width=1.3pt] (.75,2.25) to [out=90,in=0] (.25,3.25);

\begin{scope}[xshift=6cm]
\tyng(0,0,8,8,4,3,2,1)
\draw[fill, color=myorange] (2,.5) rectangle (2.5,1);
\draw (2,.5) rectangle (2.5,1);
\draw[fill, color=myorange] (1,2.5) rectangle (.5,2);
\draw (1,2.5) rectangle (.5,2);
\draw[fill, color=myblue] (3.5,.5) rectangle (4,1);
\draw[fill, color=myblue] (1,1.5) rectangle (1.5,2);
\draw[fill, color=myblue] (0,3.5) rectangle (.5,3);

\draw[line width=1.75pt] (0,0) -- (4,0) -- (4,.5) -- (3.5,.5) -- (3.5,1) -- (2,1) -- (2,1.5) -- (1,1.5) -- (1,2.5) -- (.5,2.5) -- (.5,3) -- (0,3) -- (0,0) -- (1,0);
\draw [->,line width=1.3pt] (2.25,.75) to [out=0,in=180] (3.75,.75);
\draw [->,line width=1.3pt] (.75,2.25) to [out=0,in=90] (1.25,1.75);
\node at (2,-.5) {$F^\col_{\la,\rho,1}$};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{\label{fig: row and col insertion map} The two maps $F^\row_{\la,\rho,1}$ (left) and $F^\col_{\la,\rho,1}$ (right) for $\la=(7,7,3,2,2)$ and $\rho=(8,5,4,2,2,1)$. The removable inner corners (colored in orange) and the addable outer corners (colored in blue) are obtained in Figure~\ref{fig:inner outer corners}.}
\end{figure}



Each set of local growth rules $F_\bullet$ determines a bijection 
\[
\RSK^*_{F_\bullet}: \{0,1\}^{m \times n} \rightarrow \bigcup_\la \SSYT(\la)\times \SSYT^*(\la),
\qquad A \mapsto (P,Q).
\]
While the bijection $\RSK^*_{F_\bullet}$ is best understood by using Fomin's growth diagrams \cite{Fomin86}, we describe it as an insertion algorithm in order to save space and refer the reader to \cite[\S 2.3]{FriedenSchreierAigner24} for more details.

\begin{defn}
Let $F_\bullet$ be a set of local dual growth rules, $T$ an SSYT and $i_1<\cdots<i_r$ positive integers. We define the \deff{$F_\bullet$-insertion} of $i_1,\ldots,i_r$ into $T$ as the SSYT $\wh{T}$ obtained as follows.
Call the (multi-)\footnote{Note that at the initial step this is just an ordinary set. The same is true for Definition~\ref{def:qtRSK insertion}.} set $\{i_1,\ldots,i_r\}$ the \deff{insertion queue}.
Let $i$ be the smallest integer of the insertion queue. Denote by $C$ the set of cells of $F_{\la,\rho,k}(\mu)/(\la\cup\rho)$ where $\la=T^{(i)}$, $\rho=\wh{T}^{(i-1)}$, $\mu=T^{(i-1)}$ and $k$ is the multiplicity of $i$ in the insertion queue. Place $i$ into each cell of $C$, delete all $i$'s from the insertion queue and add all entries which have been replaced (bumped) in the current step to the insertion queue.
Repeat the previous step until the insertion queue is empty.
%\begin{itemize}
%\item Call the (multi-) set $\{i_1,\ldots,i_r\}$ the \deff{insertion set}.
%\item Let $i$ be the smallest integer of the insertion set. Denote by $C$ the set of cells of $F_{\la,\rho,k}(\mu)/(\la\cup\rho)$ where $\la=T^{(i)}$, $\rho=\wh{T}^{(i-1)}$, $\mu=T^{(i-1)}$ and $k$ is the multiplicity of $i$ in the insertion set. Place $i$ into each cell of $C$, delete all $i$'s from the insertion set and add all entries which have been replaced (bumped) in the current step to the insertion set.
%\item Repeat the previous step until the insertion set is empty.
%\end{itemize}
\end{defn}

For a $m \times n$ $\{0,1\}$-matrix $A$ denote by $i_{1}^{(j)}<\cdots<i_{r_j}^{(j)}$ the rows for which $A$ has a $1$ entry in the $j$-th column. The \deff{insertion tableau} $P$ is obtained by the successive $F_\bullet$-insertion of $i_{1}^{(j)},\ldots,i_{r_j}^{(j)}$, starting with $j=1$, into the empty tableau. The \deff{recording tableau} $Q$ is the dual SSYT such that $Q^{(j)}$ has the same shape as $P$ after the $j$-th insertion process.







\section{Macdonald polynomials}
\label{sec:Mac}

We review certain basic properties of Macdonald polynomials, following \cite[Ch. VI]{Mac}. The \deff{Macdonald symmetric functions} $P_\la(\mb{x}; q,t)$ are symmetric functions in an infinite set of variables $\mb{x} = (x_1, x_2, \ldots)$ with coefficients in the field $\bb{Q}(q,t)$ of rational functions in two additional variables $q$ and $t$. While they are originally defined indirectly by a linear algebra criterion, we take the somewhat unusual perspective to define them combinatorially using their monomial expansion via SSYTs. %In order to describe these expansions we need some notations.

We define for a cell $c=(x,y) \in \la$ its \deff{arm-length} $a_\lambda(c)$ and its \deff{leg-length} $\ell_\lambda(c)$ by
\[
a_\lambda(c)= \lambda_y-x, \qquad \qquad
\ell_\lambda(c)=\lambda_x^\prime-y.
\]
The \deff{hook-length} of $c$ is defined as $h_\lambda(c)=a_\lambda(c)+\ell_\lambda(c)+1$. The cell $c$ as in Figure \ref{fig: Young diagram} has arm-length $a_\la(c) = 5$, leg-length $\ell_\la(c) = 3$, and hook-length $h_\la(c) = 9$.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\Yboxdim{16 pt}
\Ylinecolour{lightgray}
\tyng(0,0,7,6,3,2)
\Ylinecolour{black}
\tgyoung(0pt,0pt,:;)
\node at (24pt,8pt) {$c$};
\node at (72pt,8pt) {$a_\lambda(c)$};
\draw[->] (86pt,8pt) -- (106pt,8pt);
\draw[->] (58pt,8pt) -- (38pt,8pt);
\node at (24pt,40pt) {$\ell_\lambda(c)$};
\draw[<-] (24pt,20pt) -- (24pt,30pt);
\draw[->] (24pt,50pt) -- (24pt,60pt);
\end{tikzpicture}
\end{center}
\caption{\label{fig: Young diagram} The Young diagram of the partition $\la = (7,6,3,2)$ for which the cell $c=(2,1)$ is marked.}
\end{figure}
We define the \deff{$(q,t)$-hook-lengths} $\hl{\la}(c) = 1-q^{a_\la(c)}t^{\ell_\la(c)+1}$ and $\ha{\la}(c) = 1-q^{a_\la(c)+1}t^{\ell_\la(c)}$ for $c \in \la$, and $\hl{\la}(c) = \ha{\la}(c) = 1$ if $c \not \in \la$.  Further we need their ratio which is denoted by $b_\lambda(c)$
\[
b_\lambda(c) = \dfrac{\hl{\la}(c)}{\ha{\la}(c)}.
\]
For $\mu \subseteq \la$, define\footnote{Contrary to Macdonald \cite[Ch. VI (6.24)]{Mac} we use the symbol $\vp^*$ instead of $\psi^\prime$.}
\[
\psi_{\la/\mu}(q,t) = \prod_{c \in \mc{R}_{\la/\mu} - \mc{C}_{\la/\mu}} \dfrac{b_\mu(c)}{b_\la(c)}, \qquad\qquad \vp^*_{\la/\mu}(q,t) = \prod_{c \in \mc{C}_{\la/\mu} - \mc{R}_{\la/\mu}} \dfrac{b_\la(c)}{b_\mu(c)},
\]
where $\mc{R}_{\la/\mu}$ (resp., $\mc{C}_{\la/\mu}$) is the set of all cells in $\la$  which are in the same row (resp., column) as a cell of $\la/\mu$. %This is the definition used by Macdonald\footnote{Contrary to Macdonald \cite[Ch. VI (6.24)]{Mac} we use the symbol $\vp^*$ instead of $\psi^\prime$.} and differs from the one in \cite{AignerFrieden22}.
For a semistandard Young tableau $T$ and a dual semistandard Young tableau $T^*$, define the rational functions $\psi_T(q,t), \vp^*_{T^*}(q,t)$ by
\[
\psi_T(q,t) = \prod_{i \geq 1} \psi_{T^{(i)}/T^{(i-1)}}(q,t), \qquad\qquad
\vp^*_{T^*}(q,t) = \prod_{i \geq 1} \vp_{T^{*(i)}/T^{*(i-1)}}(q,t).
\]
Macdonald \cite[Ch. VI ($7.13$)]{Mac} showed the following monomial expansions over semistandard Young tableaux of shape $\la$
%that the Macdonald polynomials have the following monomial expansions over semistandard Young tableaux of shape $\la$
\begin{equation}
\label{eq:P via SSYT}
P_\la (\x; q,t) = \sum_{T \in \SSYT(\la)} \psi_T(q,t) \tb{x}^T, \qquad \qquad
P_{\la^\prime} (\x; t,q) = \sum_{T^* \in \SSYT^*(\la)} \vp^*_{T^*}(q,t) \tb{x}^{T^*}.
\end{equation}
By using the linear algebraic definition, Macdonald proved the following generalization of the dual Cauchy identity.

\begin{thm}[{\cite[Ch. VI (5.4)]{Mac}}]
\label{thm:dual Cauchy Mac}
Let $\tb{x} = (x_1, x_2, \ldots)$ and $\tb{y} = (y_1, y_2, \ldots)$ be two sets of variables. Then
\begin{align}
\label{eq:dual Cauchy Mac}
\prod_{i,j}(1+x_iy_j) &= \sum_\la P_\la(\x ;q,t) P_{\la'}(\mb{y} ;t,q).
\end{align}
\end{thm}

In this abstract our goal is to provide a tableaux-theoretic proof of this theorem by starting with the monomial expansion of Macdonald polynomials.  We define the \deff{$(q,t)$-up operator} and \deff{$(q,t)$-dual down operator} as
\[
U_x(q,t) \la = \sum_{\nu \succ \la} x^{|\nu/\la|} \psi_{\nu/\la}(q,t) \; \nu, \quad\quad 
D_y^*(q,t) \la = \sum_{\mu \prec^\prime \la} y^{|\la/\mu|} \vp_{\la/\mu}^*(q,t) \; \mu.
\]

\begin{thm}
\label{thm:dual DU UD}
The $(q,t)$-up and $(q,t)$-dual down operators satisfy the commutation relation
\begin{equation}
\label{eq:dual DU UD}
D^*_y(q,t) U_x(q,t) = (1+xy) U_x(q,t) D^*_y(q,t).
\end{equation}
\end{thm}

Note that the commutation relation \eqref{eq:dual DU UD} is actually equivalent to the skew version of the dual Cauchy identity, compare to \cite[Ch. VI, Ex 6(c)]{Mac}. It is immediate by the definition of the $(q,t)$-up and $(q,t)$-dual down operator and the monomial expansions of $P_\la$ and $P_{\la^\prime}$ in \eqref{eq:P via SSYT} that 
\[
P_{\la}(\mb{x}; q,t) = \langle U_{x_m}(q,t)\cdots U_{x_1}(q,t) \emptyset, \la \rangle, \qquad \quad
P_{\la'}(\mb{y}; t,q) = \langle D^*_{y_1}(q,t) \cdots D^*_{y_{n}}(q,t) \la, \emptyset \rangle,
\]
when restricting to $\x=(x_1,\ldots,x_m)$ and $\y=(y_1,\ldots,y_n)$.
The Cauchy identity \eqref{eq:dual Cauchy Mac} follows algebraically by the same standard argument as in the Schur case.





\section{The $\dRSK$ correspondence}
\label{sec:probabilities}

%The following definition is due to Bufetov and Petrov \cite{BufetovPetrov19}, although they use the term ``bijectivization'' (or ``coupling'') rather than ``probabilistic bijection.'' 

\begin{defn}
Let $X$ and $Y$ be finite sets equipped with weight functions $\omega : X \rightarrow A$, $\ov{\omega} : Y \rightarrow A$, where $A$ is an algebra. A \deff{probabilistic bijection} from $(X,\omega)$ to $(Y,\ov{\omega})$ is a pair of maps $\mc{P},\ov{\mc{P}} : X \times Y \rightarrow A$ satisfying
\begin{enumerate}
\item for each $x \in X$, $\ds \sum_{y \in Y} \mc{P}(x,y) = 1$, and for each $y \in Y$, $\ds \sum_{x \in X} \ov{\mc{P}}(x,y) = 1$,
\item for each $x \in X$ and $y \in Y$, $\ds \omega(x)\mc{P}(x,y) = \ov{\mc{P}}(x,y)\ov{\omega}(y)$.
\end{enumerate}
\end{defn}

For the remainder of the abstract we write $\mc{P}(x \rightarrow y)$ for $\mc{P}(x,y)$ and $\ov{\mc{P}}(x \leftarrow y)$ for $\ov{\mc{P}}(x,y)$, and think of $\mc{P}(x \rightarrow y)$ as the ``probability'' of mapping $x$ to $y$, called \deff{forward probability}, and of $\ov{\mc{P}}(x \leftarrow y)$ as the ``probability'' of mapping $y$ back to $x$, called the \deff{backward probability}.
 We put ``probability'' in quotes because we do not require $\mc{P}(x \rightarrow y), \ov{\mc{P}}(x \leftarrow y) \in [0,1]$ (they need not even be real-valued).  %Condition (1) states that $\mc{P}$ defines a ``probability distribution'' on $Y$ for each $x$, and (2) says that $\ov{\mc{P}}$ defines a ``probability distribution'' on $X$ for each $y$.
  We refer to (2) as the \deff{compatibility condition}.
 It is immediate that a probabilistic bijection from $(X,\omega)$ to $(Y,\ov{\omega})$ implies the identity
\[
\sum_{x \in X} \omega(x) = \sum_{y \in Y} \ov{\omega}(y).
\]
We want to point out, that there is an easy connection between the concept of probabilistic bijections and joint distributions, compare for example with \cite[Remark 4.1.4]{AignerFrieden22}. 



For partitions $\la,\rho,\mu,\nu$ satisfying $\mu \prec \la \prec^\prime \nu$ and $\mu \prec^\prime \rho \prec \nu$ we define the weights
\begin{align*}
\omega_{\la,\rho}(\mu) = \psi_{\la/\mu}(q,t) \vp_{\rho/\mu}^*(q,t), \qquad \qquad
\ov{\omega}_{\la,\rho}(\nu) = \psi_{\nu/\rho}(q,t) \vp_{\nu/\la}^*(q,t).
\end{align*}
Analogously to \eqref{eq:up-down on sets}, the commutation relation \eqref{eq:dual DU UD} is equivalent to the family of equations
\begin{equation}
\label{eq:sum of weights}
\sum_{\mu \in \D^k(\la,\rho) \cup \D^{k-1}(\la,\rho)}  \omega_{\la,\rho}(\mu) =
\sum_{\nu \in \U^k(\la,\rho)} \ov{\omega}_{\la,\rho}(\nu).
\end{equation}
In the remainder of this section we define the forward probabilities $\mc{P}_{\la,\rho}(\mu \rightarrow \nu)$ and the backward probabilities $\ov{\mc{P}}_{\la,\rho}(\mu \leftarrow \nu)$ which form a probabilistic bijection and thereby prove this equation. %In case we want to emphasize the dependence of the probabilities on $q$ and $t$, we write $\mc{P}_{\la,\rho}(\mu \rightarrow \nu)[q,t]$ and $\ov{\mc{P}}_{\la,\rho}(\mu \leftarrow \nu)[q,t]$. 
Before we can define these probabilities, we need to introduce some notations.\medskip

Denote by $d$ the number of removable inner corners of $\la \cap \rho$. For a subset $\Ret \subseteq [d] = \{1,2,\ldots d\}$ we define $\mu^{(\Ret)}$ as the partition obtained by removing from $\la \cap \rho$ the $i$-th removable inner corner, counted from bottom to top, for all $i\in \Ret$. For a subset $\Set\subseteq [0,d]=\{0,1,\ldots, d\}$ we define $\nu^{(\Set)}$ as the partition obtained by adding to $\la \cup \rho$ the $i$-th addable (``supplementable'') outer corner, where we count the addable outer corners again from bottom to top but starting with $0$.

As we see in a moment, it turns out to be convenient to draw Young diagrams using \deff{Quebecois notation} in which the boxes are right-justified instead of left-justified, i.e., one obtains this new convention by reflecting diagrams in French convention vertically, see Figure \ref{fig: def of pts}.
We define $R_i$ (resp., $\ov{R}_i$) to be the lower right (resp., upper left) corner of the $i$-th removable inner corner of $\la \cap \rho$, $S_i$ (resp., $\ov{S}_i$) to be the lower right (resp., upper left) corner of the $i$-th addable outer corner of $\la \cup \rho$, and set $I_i = \ov{R}_i$ and $O_i=S_i$. For an example see Figure \ref{fig: def of pts}. For the rest of the abstract we identify a point with coordinates $(x,y)$ with the monomial $q^x t^y$. Since the expressions we are interested in are homogeneous rational functions of degree 0 in the above defined points, these expressions are invariant under translation of the points and hence well-defined.


For $\Ret \subseteq [d]$ and $\Set \subseteq [0,d]$, we define the probabilities
\begin{align}
\label{eq:forward using quebecois}
\mc{P}_{\la,\rho}(\mu^{(\Ret)} \rightarrow \nu^{(\Set)}) &= 
\prod_{s \in \Set} \frac{\prod\limits_{i \in [d]\setminus \Ret} (S_s-I_i)}{\prod\limits_{j \in [0,d]\setminus \Set} (S_s-O_j)}
\prod_{r \in \Ret} \frac{\prod\limits_{j \in [0,d]\setminus \Set} (R_r-O_j)}{\prod\limits_{i \in [d]\setminus \Ret} (R_r-I_i)},
\\
\label{eq:backward using quebecois}
\ov{\mc{P}}_{\la,\rho}(\mu^{(\Ret)} \leftarrow \nu^{(\Set)}) &=
\prod_{s \in \Set} \frac{\prod\limits_{i \in [d]\setminus \Ret} (\ov{S}_s-I_i)}{\prod\limits_{j \in [0,d]\setminus \Set} (\ov{S}_s-O_j)}
\prod_{r \in \Ret} \frac{\prod\limits_{j \in [0,d]\setminus \Set} (\ov{R}_r-O_j)}{\prod\limits_{i \in [d]\setminus \Ret} (\ov{R}_r-I_i)}.
\end{align}
%If $\la, \rho$ are clear from the context, we abbreviate the probabilities by 
%\[
%p_{\Ret,\Set} = \mc{P}_{\la,\rho}(\mu^{(\Ret)} \rightarrow \nu^{(\Set)}), 
%\qquad \qquad \ov{p}_{\Ret,\Set} = \ov{\mc{P}}_{\la,\rho}(\mu^{(\Ret)} \leftarrow \nu^{(\Set)}).
%\]
%When we want to emphasize the dependence of our probabilities on $q$ and $t$, we write $p_{\Ret,\Set}[q,t]$ or $\mc{P}_{\la,\rho}(\mu^{(\Ret)} \rightarrow \nu^{(\Set)})[q,t]$.


\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.3, xscale=-1]
\tyng(0,0,8,7,4,2,2,1)
\draw[fill, color=myorange] (2,.5) rectangle (2.5,1);
\draw (2,.5) rectangle (2.5,1);
\draw[fill, color=myorange] (1,2.5) rectangle (.5,2);
\draw (1,2.5) rectangle (.5,2);
\draw[fill, color=myblue] (3.5,.5) rectangle (4,1);
\draw[fill, color=myblue] (1,1.5) rectangle (1.5,2);
\draw[fill, color=myblue] (0,3.5) rectangle (.5,3);

\draw[line width=1.75pt] (0,0) -- (4,0) -- (4,.5) -- (3.5,.5) -- (3.5,1) -- (2,1) -- (2,1.5) -- (1,1.5) -- (1,2.5) -- (.5,2.5) -- (.5,3) -- (0,3) -- (0,0) -- (1,0);

\node at (.25,3.25) {$+$};
\node at (1.25,1.75) {$+$};
\node at (3.75,.75) {$+$};
\node at (2.25,.75) {$-$};
\node at (.75,2.25) {$-$};

\draw[fill, blue] (0,3) circle (1.5pt);
\draw[fill, blue] (.5,3.5) circle (1.5pt);
\draw[fill, blue] (1,1.5) circle (1.5pt);
\draw[fill, blue] (1.5,2) circle (1.5pt);
\draw[fill, blue] (3.5,.5) circle (1.5pt);
\draw[fill, blue] (4,1) circle (1.5pt);

\draw[fill, red] (.5,2) circle (1.5pt);
\draw[fill, red] (1,2.5) circle (1.5pt);
\draw[fill, red] (2,.5) circle (1.5pt);
\draw[fill, red] (2.5,1) circle (1.5pt);

\node[blue] at (3.25,.25)  {$S_0 = O_0$};
\node[blue] at (4,1) [above left] {$\ov{S}_0$};
\node[blue] at (.75,1.25) {$S_1 = O_1$};
\node[blue] at (1.75,2.1) {$\ov{S}_1$};
\node[blue] at (-.75,3) {$S_2 = O_2$};
\node[blue] at (.5,3.5) [above left] {$\ov{S}_2$};

\node[red] at (2,.5) [below right]  {$R_1$};
\node[red] at (2.6,1.3) {$\ov{R}_1=I_1$};
\node[red] at (.5,2) [below right]  {$R_1$};
\node[red] at (1.1,2.8) {$\ov{R}_1=I_1$};

\end{tikzpicture}
\caption{\label{fig: def of pts} The partition $\la \cup \rho$ together with the points $I_i,O_j,R_i,\ov{R}_i,S_j$ and $\ov{S}_j$ for $\la=(7,7,3,2,2)$ and $\rho=(8,5,4,2,2,1)$ as in Figure~\ref{fig:inner outer corners}.}
\end{center}
\end{figure}



For an integer $k \geq 0$ and a set $\Set$, we denote by $\binom{\Set}{k}$ the set of $k$-element subsets of $\Set$.

\begin{thm}
\label{thm:sum to 1}
Let $\la, \rho$ be partitions, $d$ the number of removable inner corners of $\la \cap \rho$, and $k \in [d+1]$. The probabilities defined in \eqref{eq:forward using quebecois} and \eqref{eq:backward using quebecois} satisfy
\begin{align}
\label{eq:sum of forward prob}
\sum_{\Set \in \binom{[0,d]}{k}} \mc{P}_{\la,\rho}(\mu^{(\Ret)} \rightarrow \nu^{(\Set)}) = 1 \qquad &\text{ for each } \Ret\in \binom{[d]}{k-1} \cup \binom{[d]}{k},\\
\label{eq:sum of backward prob}
\sum_{\Ret\in \binom{[d]}{k-1} \cup \binom{[d]}{k}} \ov{\mc{P}}_{\la,\rho}(\mu^{(\Ret)} \leftarrow \nu^{(\Set)}) = 1 \qquad &\text{ for each } \Set \in \binom{[0,d]}{k},\\
\label{eq:prob compatibility}
\frac{\omega_{\la,\rho}(\mu^{(\Ret)})}{\ov{\omega}_{\la,\rho}(\nu^{(\Set)})} = \frac{\ov{\mc{P}}_{\la,\rho}(\mu^{(\Ret)} \leftarrow \nu^{(\Set)})}{\mc{P}_{\la,\rho}(\mu^{(\Ret)} \rightarrow \nu^{(\Set)})}
\qquad &\text{ for each } \Ret\in \binom{[d]}{k-1} \cup \binom{[d]}{k}, \Set \in \binom{[0,d]}{k}.
\end{align}
\end{thm}

The above theorem shows that our probabilities define a probabilistic bijection. The proof of \eqref{eq:sum of forward prob} and \eqref{eq:sum of backward prob} uses an extension of Lagrange  interpolation for symmetric polynomials by Chen and Louck \cite{ChenLouck96}. The proof of \eqref{eq:prob compatibility} is based on a careful analysis of the involved terms and alternative representations of the probabilities. We refer the reader to \cite[\S 5]{FriedenSchreierAigner24} for more details.



\section{The $\dRSK$ correspondence}
\label{sec:dual RSK}

We view the probabilities $\mc{P}_{\la,\rho}$ as a set of ``probabilistic'' local dual growth rules and define the $\dRSK$ correspondence analogously to the insertion algorithm $\RSK^*_{F_\bullet}$ in \S\ref{sec:dual cauchy}.

\begin{defn}
\label{def:qtRSK insertion}
Let $T$ be a semistandard Young tableau and $i_1< \cdots < i_r$ be positive integers. The \deff{$\dRSK$-insertion} of $i_1, \ldots, i_r$ into $T$, denoted
\[
(i_1,\ldots,i_r) \xrightarrow{\dRSK} T = \wh{T},
\]
is the probability distribution computed as follows. Call the (multi-) set $\{i_1,\ldots,i_r\}$ the \deff{insertion queue}.  Let $i$ be the smallest integer of the insertion queue and denote by $k$ the multiplicity of $i$ in the insertion queue.
% For each $\nu \in \U^k\left(T^{(i)},\wh{T}^{(i-1)}\right)$, place $i$ in each cell of $\nu/\left(T^{(i)}\cup\wh{T}^{(i-1)}\right)$ with probability $\mc{P}_{T^{(i)},\wh{T}^{(i-1)}}\left(T^{(i-1)} \rightarrow \wh{T}^{(i)} \right)$. 
 For each $\nu \in \U^k\left(\la,\rho\right)$, place $i$ in each cell of $\nu/\left(\la\cup\rho\right)$ with probability $\mc{P}_{\la,\rho}\left(\mu \rightarrow \nu \right)$, where $\la=T^{(i)}$, $\rho=\wh{T}^{(i-1)}$, $\mu=T^{(i-1)}$.
 Delete all $i's$ from the insertion queue and add all entries which have been replaced (bumped) by an $i$ to the insertion queue.
Repeat the previous step until the insertion queue is empty.
%\begin{itemize}
%\item Call the (multi-) set $\{i_1,\ldots,i_r\}$ the \deff{insertion set}.
%\item Let $i$ be the smallest integer of the insertion set and denote by $k$ the multiplicity of $i$ in the insertion set. For each $\nu \in \U^k\left(T^{(i)},\wh{T}^{(i-1)}\right)$, place $i$ in each cell of $\nu/\left(T^{(i)}\cup\wh{T}^{(i-1)}\right)$ with probability $\mc{P}_{T^{(i)},\wh{T}^{(i-1)}}\left(T^{(i-1)} \rightarrow \wh{T}^{(i)} \right)$. Delete all $i's$ from the insertion set and add all entries which have been replaced (bumped) by an $i$ to the insertion set.
%\item Repeat the previous step until the insertion set is empty.
%\end{itemize}
\end{defn}



For an $m \times n$ $\{0,1\}$-matrix $A$ denote by $i_{1}^{(j)}<\cdots<i_{r_j}^{(j)}$ the rows for which $A$ has a $1$ entry in the $j$-th column. 
The $\dRSK$-correspondence associates to $A$ a probability distribution $\mc{P}(A \rightarrow P,Q)$ on pairs $(P,Q)$ of an SSYT $P$ and a dual SSYT $Q$ of the same shape, where the probability $\mc{P}(A \rightarrow P,Q)$ is the sum of the forward probabilities of all ways to obtain the insertion tableau $P$ by successively $\dRSK$-inserting $i_{1}^{(j)},\ldots,i_{r_j}^{(j)}$, starting with $j=1$, into the empty tableau and $Q$ as the recording tableau by the analogous construction as for $\RSK^*_{F_\bullet}$. 
%$Q$ is the recording tableau defined analogously to $\RSK^*_{F_\bullet}$. 
Note that the backward probabilities $\ov{\mc{P}}(A \leftarrow P,Q)$ are defined analogously by summing over the backward probabilities instead of the forward probabilities. 
By using the perspective of Fomin's growth diagrams, it is not difficult to prove that $\dRSK$ defines a probabilistic bijection between the weighted sets of $m \times n$ $\{0,1\}$-matrices with weight $\omega$ and $\ds \bigsqcup_{\la \subseteq (m^n)} \SSYT(\la) \times \SSYT^*(\la)$ with weight $\ov{\omega}$, where
\[
\omega(A) = \prod_{\substack{1 \leq i \leq m \\1 \leq j \leq n}}(x_iy_j)^{A_{i,j}} \quad\quad \text{ and } \quad\quad \ov{\omega}(P,Q) = \psi_P(q,t)\vp^*_Q(q,t)\mb{x}^P\mb{y}^Q.
\]
See \cite[\S 4.4]{FriedenSchreierAigner24} for more details.


\begin{ex}
\label{ex:qrst insertion}
The insertion $(2,3) \xrightarrow{\dRSK} \young(12,3)$ produces
\[
\begin{array}{llll}
\young(122,33) & \text{ with probability }  &= \mc{P}_{(2),(1)}((1)\rightarrow (3))
=\dfrac{1-qt}{1-q^2t}
,\bigskip \\
\young(123,23) & \text{ with probability } &= \mc{P}_{(2),(1)}((1)\rightarrow (2,1))\mc{P}_{(2,1),(2,1)}((2)\rightarrow (3,2)) \\
&&=q^2 t \dfrac{(1-q)^2(1-t)^2}{(1-qt)(1-q^2)(1-q^2t)(1-q^2t^2)}
,\\
\young(12,23,3) & \text{ with probability } &= \mc{P}_{(2),(1)}((1)\rightarrow (2,1))\mc{P}_{(2,1),(2,1)}((2)\rightarrow (2,2,1)) \\
&&=qt^2\dfrac{(1-q)^2(1-q^2t)}{(1-qt)(1-q^2)(1-q^2t^2)},
\end{array}
\]


\[
\begin{array}{llll}
%\young(122,33) & \text{ with probability }  &= \mc{P}_{(2),(1)}((1)\rightarrow (3))
%=\dfrac{1-qt}{1-q^2t}
%,\bigskip \\
%\young(123,23) & \text{ with probability } &= \mc{P}_{(2),(1)}((1)\rightarrow (2,1))\mc{P}_{(2,1),(2,1)}((2)\rightarrow (3,2)) \\
%&&=q^2 t \dfrac{(1-q)^2(1-t)^2}{(1-qt)(1-q^2)(1-q^2t)(1-q^2t^2)}
%,\\
%\young(12,23,3) & \text{ with probability } &= \mc{P}_{(2),(1)}((1)\rightarrow (2,1))\mc{P}_{(2,1),(2,1)}((2)\rightarrow (2,2,1)) \\
%&&=qt^2\dfrac{(1-q)^2(1-q^2t)}{(1-qt)(1-q^2)(1-q^2t^2)}
%,\\
\young(123,2,3) & \text{ with probability }  &= \mc{P}_{(2),(1)}((1)\rightarrow (2,1))\mc{P}_{(2,1),(2,1)}((2)\rightarrow (3,1,1))\\
&&=qt\dfrac{(1-q)^2(1-t)}{(1-q^2)(1-qt)^2}.
\end{array}
\]
\end{ex}

\section{Properties of $\dRSK$}
\label{sec:properties}

Our randomized $\dRSK$ correspondence can be specialized in two different ways: one can specialize the parameter $q,t$ or restrict the correspondence to a smaller family of matrices.

For $q,t \in [0,1)$ or $q,t \in (1,\infty)$ the probabilities $\mc{P}(A \rightarrow P,Q)$ and $\ov{\mc{P}}(A \leftarrow P,Q)$ take values in $[0,1]$, i.e., they become actual probabilities. The $\dRSK$-insertion specializes to the $q$-Whittaker dual row insertion ($t=0$) first described by Matveev and Petrov \cite[\S 5.1]{MatveevPetrov17} and to a Hall--Littlewood dual-row insertion ($q = 0$), first described Matveev and Petrov in \cite[\S 5.4]{MatveevPetrov17}  as a $q$-Whittaker dual column insertion. Finally for $q=t=0$ or $q=t\rightarrow \infty$ we obtain the row or column insertion version of $\RSK^*$.


By restricting the input of $\dRSK$ to $\{0,1\}$-matrices with at most one entry equal to $1$ in each column, we obtain a $(q,t)$-deformation of RS for words. By further restricting to permutation matrices we obtain the $\qrst$ correspondence.
The restriction of $\dRSK$ to words is in particular interesting when further specializing to Jack polynomials, i.e., by setting $q=t^\alpha$ and taking the limit $t \rightarrow 1$. We prove in \cite[Thm 6.5]{FriedenSchreierAigner24} that in the Jack limit of $\dRSK$ restricted to words,  interchanging adjacent columns of the input matrix does not affect the distribution of the $P$-tableau. Note that this can not be extended to all $\{0,1\}$-matrices. 


Similarly to the classical dual RSK, the $\dRSK$ correspondence also yields a tableaux-theoretic proof of the dual Pieri rule for Macdonald polynomials. This can be obtained by considering a growth diagram with one column for which the number of $1$ entries is fixed to $k$; this corresponds to multiplying by $e_k$.

% tableaux-theoretic proof of the skew dual Cauchy identity for Macdonald polynomials.
%Since the dual Pieri rule for Macdonald polynomials can be obtained as the coefficient of $y_1^r$ of the skew dual Cauchy identity for the special case $\y=(y_1)$, it is immediate that $\dRSK$ yields a 	tableaux-theoretic proof of the dual Pieri rule for Macdonald polynomials. 





%\acknowledgements{TODO?}

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

%\bibliographystyle{abbrvurl}
%\bibliography{dual_qtRSK}



\end{document}
