\documentclass[Unicode,ALCO,NoThmDefs,published]{cedram}
\begin{DefTralics}
\newcommand{\external}{\bigwedge\nolimits}
\renewcommand{\C}{\mathbb{C}}
\newcommand{\GLm}{\operatorname{GL}_m}
\newcommand{\GLn}{\operatorname{GL}_n}
\newcommand{\GLk}{\operatorname{GL}_k}
\end{DefTralics}
%\usepackage[english]{babel}
%\usepackage{hyperref}
\usepackage[capitalize,noabbrev]{cleveref}
\usepackage{embrac}
% \usepackage[backgroundcolor=yellow!10]{todonotes}
%\usepackage{footmisc}
\usepackage{tikz,ytableau}
\usepackage[config, labelfont={normalsize}]{caption,subfig}
%\usepackage{graphicx}
\usepackage{gensymb}
\newtheorem{proposition}{Proposition}
\numberwithin{proposition}{section}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{definition}[proposition]{Definition}
\newtheorem*{definition*}{Definition}
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{claim}[proposition]{Claim}
\newtheorem{problem}[proposition]{Problem}
\theoremstyle{remark}
\newtheorem{remark}[proposition]{Remark}
\newtheorem{example}[proposition]{Example}
\newtheorem*{example*}{Example}
\renewcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\external}{\bigwedge\nolimits}
\newcommand{\GLm}{\operatorname{GL}_m}
\newcommand{\GLn}{\operatorname{GL}_n}
\newcommand{\GLk}{\operatorname{GL}_k}
\newcommand{\Sym}[1]{\mathfrak{S}_{#1}}
\newcommand{\ii}{\mathbf{i}}
\newcommand{\jj}{\mathbf{j}}
\newcommand{\mn}{m^n}
\newcommand{\nm}{n^m}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\id}{id}
%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\author{\firstname{Greta} \lastname{Panova}}
\address{UPenn Mathematics Department,
209 South 33rd St,
Philadelphia, PA 19104, USA}
\email{panova@math.upenn.edu}
\thanks{Research of GP is partially supported by the NSF. Research of PŚ was supported by \emph{Narodowe Centrum Nauki}, grant number $2014/15/\text{B/ST}1/00064$.}
\author{\firstname{Piotr} \lastname{\'Sniady}}
\address{Institute of Mathematics, Polish Academy of Sciences, ul.~Śniadec\-kich 8, 00-956 Warszawa, Poland}
\email{psniady@impan.pl}
\title%
[Skew Howe duality and random rectangular Young tableaux]%
{Skew Howe duality\\ and random rectangular Young tableaux}
\subjclass[2010]
{%
22E46, %Semisimple Lie groups and their representations
20C30, %Representations of finite symmetric groups
60C05 %Combinatorial probability
}
\keywords{Skew Howe duality, random Young diagrams, representations of general linear groups $\GLm$,
representations of finite symmetric groups}
\begin{document}
\begin{abstract}
We consider the decomposition into irreducible components
of the external power $\external^p(\C^m\otimes \C^n)$ regarded as a
$\GLm\times\GLn$-module.
Skew Howe duality implies that
the Young diagrams from each pair $(\lambda,\mu)$
which contributes to this decomposition turn out to be conjugate
to each other, i.e.~$\mu=\lambda'$.
We show that the Young diagram $\lambda$ which corresponds to a randomly selected
irreducible component $(\lambda,\lambda')$ has the same distribution
as the Young diagram which consists of the boxes with entries $\leq p$
of a random Young tableau of rectangular shape with $m$ rows and $n$ columns.
This observation allows treatment of the asymptotic version of this decomposition
in the limit as $m,n,p\to\infty$ tend to infinity.
\end{abstract}
\maketitle
\section{Introduction}
\label{sec:problem}
\subsection{The problem}
In this note we address the following question.
\begin{quotation}
\emph{Consider
\begin{equation}
\label{eq:decomposition}
\external^p(\C^m\otimes \C^n)=\bigoplus_{\lambda}S^{\lambda}\C^m\otimes S^{\lambda'}\C^n
\end{equation}
as a $\GLm\times \GLn$-module.
[\dots]
I would
like any information on the shapes of pairs of Young diagrams $(\lambda,\lambda')$ that
give the largest contribution to the dimension asymptotically.
[\dots]
}
\hfill Joseph M.~Landsberg \cite{Landsberg2012}\footnote{The question of Landsberg is reproduced here in a slightly
redacted version. In particular, the original question considered only the special case $m=n$.}
\end{quotation}
\bigskip
Above, $\external^p(\C^m\otimes \C^n)$ denotes the external power of the tensor product $\C^m\otimes \C^n$.
Also, $S^{\lambda}\C^m$ denotes the Schur functor applied to $\C^m$ or, in other words,
the irreducible representation of the general linear group $\GLm$
with the highest weight $\lambda$.
The sum in \eqref{eq:decomposition} runs over Young diagrams
$\lambda\subseteq n^m$ with $p$ boxes, and such that
the number of rows of $\lambda$ is bounded from above by $m$, and the number of columns of $\lambda$
is bounded from above by~$n$.
The decomposition \eqref{eq:decomposition} is nowadays referred to as
\emph{skew Howe $(\GLm\times\GLn)$-duality}, cf.~\cite[Theorem 4.1.1]{Howe}.
Even though \eqref{eq:decomposition}
provides full information about the decomposition into irreducible components, it is not very
convenient for answering such asymptotic questions, see the introduction to the work of Biane \cite{Biane1998}
for discussion of difficulties related to similar problems.
Despite improvements in the understanding of asymptotic problems related to the representation theory
of the general linear groups $\GLm$ \cite{Biane1995,Bufetov2015,Collins2016},
we do not see generic tools which would be suitable for investigation of the external
power \eqref{eq:decomposition}.
\subsection{Motivations: Geometric Complexity Theory}
Besides the natural interest in the question as a problem in asymptotic representation theory,
this question is also relevant within Geometric Complexity Theory (GCT).
The decomposition appears in the study of the complexity of matrix multiplication~\cite{Landsberg2015}
and, in particular,
in the study of the border rank of the matrix multiplication tensor as a standard measure of complexity.
A lower bound for the border rank is obtained from the rank of a particular linear map,
whose kernel can be decomposed as a $\operatorname{GL}(V)\times \operatorname{GL}(W)$ representation.
The general approach in GCT would be to study the irreducible components for polynomials to play the role of
``obstruction candidates'' and,
depending on the precise setup, the multiplicities would show where to find the obstructions.
\subsection{The main result}
A partial answer to the question of Landsberg which we give in the current paper
is based on a simple result which transforms the original problem
into a question about the representation theory of the symmetric group $\Sym{p}$
for which more asymptotic tools are available, see \cref{sec:applications} below.
We state our main result in two equivalent versions which are of quite distinct flavors:
\begin{itemize}
\item
as \cref{theo:enum} which is conceptually simpler and is a purely enumerative statement
which relates some dimensions of the representations of the general linear groups $\GLk$
to the dimensions of some representations of the symmetric groups $\Sym{p}$, and
\item
as \cref{theo:main} which is a probabilistic statement which relates the distribution of
a random irreducible component of the external power \eqref{eq:decomposition}
to the distribution of a random irreducible component
of a certain representation of the symmetric group $\Sym{p}$.
This second formulation is more convenient for addressing Landsberg's problem.
\end{itemize}
The proof of \cref{theo:enum} is shorter, but the proof of \cref{theo:main}
might be advantageous for some readers who prefer more representation-theoretic
viewpoint.
\subsection{The main result: the enumerative version}
Let $m,n\geq 1$ be integers
and let $\lambda\subseteq n^m$ be a Young diagram with $p$ boxes which has at most $m$ rows
and at most $n$ columns.
We denote by $\nm$ the rectangular Young diagram with $m$ rows and $n$ columns.
We denote by $f^{\lambda}$ the dimension of the irreducible representation of $\Sym{p}$
corresponding to the Young diagram $\lambda$. Note that
the skew Young diagram $\nm / \lambda$ is a rotation by $180\degree$
of a certain Young diagram therefore
it defines an \emph{irreducible} representation of $\Sym{p}$.
\begin{theorem}
\label{theo:enum}
For a Young diagram $\lambda\subseteq n^m$ with $p$ boxes
we have the following relationship between dimensions of representations
of $\GLm$, $\GLn$ and $\Sym{p}$:
\begin{equation}
\label{eq:main-identity}
\frac{ \dim(S^{\lambda} \C^m) \dim(S^{\lambda'}\C^n) }{ \dim \external^p (\C^m \otimes \C^n )}
=
\frac{ f^\lambda f^{n^m / \lambda} }{ f^{n^m} }.
\end{equation}
\end{theorem}
Our proof of this result (see \cref{sec:enum-proof})
will be based on al\-ge\-bra\-ic com\-bi\-na\-to\-rial manipulations with the
hook-length formula and the hook-content formula.
\subsection{Bijective proofs?}
\cref{theo:enum} implies the following result.
\begin{claim}
\label{claim:fraction}
For all integers $n,m\geq 1$ and $0\leq p\leq nm$ the fraction
\[
C_{n,m,p}:=\frac{ f^\lambda f^{n^m / \lambda} }{ \dim(S^{\lambda} \C^m) \dim(S^{\lambda'}\C^n) }\]
is a constant which does not depend on the choice of a Young diagram $\lambda\subseteq n^m$ with $p$ boxes.
\footnote{The value of the constant is clearly given by \eqref{eq:what-is-cnmp};
we decided to state the Claim in this weaker form without the explicit value of $C_{n,m,p}$
for reasons which will become clear later.}
\end{claim}
Conversely, \cref{claim:fraction} implies \cref{theo:enum} since
\[
C_{n,m,p} \sum_{\substack{\lambda\vdash p \\ \lambda\subseteq n^m}} \dim(S^{\lambda} \C^m) \dim(S^{\lambda'}\C^n)
= \sum_{\substack{\lambda\vdash p \\ \lambda\subseteq n^m}} f^\lambda f^{n^m / \lambda} \]
implies
\[
C_{n,m,p}\ \dim \external^p(\C^m\otimes \C^n) = f^{n^m} \]
(the left-hand side is an application of skew Howe duality \eqref{eq:decomposition})
which determines uniquely the constant
\begin{equation}
\label{eq:what-is-cnmp}
C_{n,m,p}=\frac{f^{n^m}}{\dim \external^p(\C^m\otimes \C^n) }=\frac{f^{n^m}}{\binom{nm}{p}}.
\end{equation}
\medskip
This observation opens the following challenging problem.
\begin{problem}
For a pair of Young diagrams $\lambda,\mu\subseteq n^m$, each with $p$ boxes,
find a \emph{bijective} proof of the identity
\begin{equation}
\label{eq:bijective-problem1}
\dim(S^{\lambda} \C^m)\ \dim(S^{\lambda'}\C^n) \ f^{\mu} f^{n^m / \mu}
=
\dim(S^{\mu}\C^m)\ \dim (S^{\mu'}\C^n)\
f^\lambda\ f^{n^m / \lambda}
\end{equation}
which is clearly equivalent to \cref{claim:fraction} and thus to \cref{theo:enum}.
\end{problem}
Clearly, each of the factors which contribute to \eqref{eq:bijective-problem1} has a natural
combinatorial interpretation as the number of (semi)standard Young tableaux of some specific shape.
In fact, it would be enough to find such a bijection in the special case when $\mu$ is obtained from $\lambda$
by a removal and an addition of a single box.
\subsection{The main result: the probabilistic version}
\begin{theorem}
\label{theo:main}
Let $m,n\geq 1$ and $0\leq p\leq mn$ be integer numbers.
The random irreducible component of \eqref{eq:decomposition}
corresponds to a pair of Young diagrams $(\lambda,\lambda')$,
where $\lambda$ has the same distribution as
the Young diagram which consists of the boxes with entries $\leq p$
of a uniformly random Young tableau with rectangular shape $n^m$
with $m$~rows and $n$ columns.
\smallskip
Alternatively: the random Young diagram $\lambda$ has the same distribution
as a Young diagram which corresponds to a random irreducible component of
the restriction $V^{n^m}\big\downarrow^{\Sym{mn}}_{\Sym{p}}$
of the irreducible representation $V^{n^m}$ of the symmetric group
$\Sym{mn}$ which corresponds to the rectangular diagram $n^m$.
\end{theorem}
Above, when we speak about a \emph{random irreducible component of a representation}
we refer to the following concept.
\begin{definition}
\label{def:random-representation}
For a representation $V$ of a group $G$ we consider its decomposition into
irreducible components
\[ V = \bigoplus_{\zeta \in \widehat{G} } m_\zeta V^\zeta, \]
where $m_\zeta\in\{0,1,\dots\}$ denotes the multiplicity of $V^\zeta$ in $V$.
This defines a probability measure $\mathbb{P}_V$
on the set $\widehat{G}$ of irreducible representations
given by
\[ \mathbb{P}_V(\zeta)=\mathbb{P}^G_V(\zeta)
:= \frac{m_\zeta \operatorname{dim} V^{\zeta}}{\operatorname{dim} V}.\]
\end{definition}
With this definition in mind, each side of the identity
\eqref{eq:main-identity} from \cref{theo:enum} can be interpreted as
the probability that an
appropriate random Young diagram (which appears in \cref{theo:main})
has a specified shape. This provides the link between \cref{theo:enum}
and \cref{theo:main}.
\subsection{Application: back to Landsberg's problem}
\label{sec:applications}
\begin{figure}
\centering
\includegraphics[scale=0.8]{limit-curves.pdf}
\caption{Asymptotic limit shapes of typical random Young diagrams
which appear in \cref{theo:main}, cf.~\cite[Figure~3]{Pittel2007}.
We draw Young diagrams in the French convention.
In this example the rectangle ratio is given by $\frac{m}{n}=\frac{1}{2}$.
The limit curves correspond to $\frac{p}{mn}\in\left\{ \frac{1}{6},\frac{2}{6},
\frac{3}{6},\frac{4}{6},\frac{5}{6}\right\}$.}
\label{fig:romik}
\end{figure}
The problem of Landsberg is exactly a
question about the statistical properties of the random Young diagram
$\lambda$ which appears in \cref{theo:main}.
This result gives an alternative description of $\lambda$
in terms of the representation theory of the symmetric groups $\Sym{p}$
in which many asymptotic problems have well-known answers.
Fortunately, this happens to be the case for the problem of understanding the
restriction of irreducible representations which we encounter
in \cref{theo:main}.
In particular, the law of large numbers for the corresponding random
Young diagrams has been proved in a much wider generality by Biane
\cite[Theorem 1.5.1]{Biane1998}
using the language of \emph{free cumulants} of Young diagrams.
The asymptotic Gaussianity of their fluctuations around the limit shape has been proved
by the second-named author
\cite[Example 7 combined with Theorem 8]{Sniady2006}
using the same language.
In the specific case of the restriction $V^{n^m}\big\downarrow^{\Sym{mn}}_{\Sym{p}}$
which is in the focus of the current paper, the above-mentioned generic tools
\cite{Biane1998,Sniady2006} can be applied in the scaling when
$m,n,p\to\infty$ tend to infinity
in such a way that the rectangle ratio $\frac{m}{n}$ converges to a strictly positive limit
and the fraction $\frac{p}{mn}$ converges to some limit.
Pittel and Romik \cite{Pittel2007} have worked out this specific example
and, among other results,
found explicit asymptotic limit shapes of typical Young diagrams
which contribute to such representations, see \cref{fig:romik}.
In the light of \cref{theo:main}, the above references provide a partial answer to the question of
Landsberg.
For more on this topic see the work of Sevak Mkrtchyan \cite{Mkrtchy2017}.
\subsection{Hypothetical extensions of \cref{theo:main}}
The formulation of \cref{theo:main} might suggest that it is a special case of
a more general result. We state it concretely as the following problem.
\begin{problem}
Find a natural \emph{quantum random walk}
\upn(in the spirit of Biane \cite{Biane1991}\upn)
on the set of irreducible representations \upn(of some group? of some algebra?\upn)
with the property that
the probability distribution on the set of paths of this random walk
can be identified \upn(via some hypothetical analogue of \cref{theo:main}\upn)
with the uniform distribution on the set of standard Young tableaux
of rectangular shape $n^m$.
\end{problem}
\section{Proof of \cref{theo:enum}}
\label{sec:enum-proof}
First, we give an enumerative proof of \cref{theo:enum} using the classical dimension formulas:
the hook-length formula for $f^{\nu}$
$$f^{\nu}= \frac{ |\nu|!}{\prod_{\Box \in \nu} h_\Box} =: \frac{ |\nu|!}{H_\nu},$$
where $H_\nu$ denotes the product of hook lengths in $\nu$,
and the hook-content formula for the dimensions of representations of $\GLk$:
\begin{equation}
\label{eq:dimension-glk}
\dim S^\nu \C^k = s_{\nu}(1^k) = \frac{ \prod_{\Box\in \nu} (k+c(\Box))}{\prod_{\Box \in \nu}h_\Box},
\end{equation}
where $h_\Box$ is the hook-length of a box $\Box$ in the diagram of $\nu$, and the content $c(\Box) = j-i$,
if $\Box=(i,j)$ is at row $i$ and column $j$ of the diagram.
Here $s_\nu(x_1,\ldots,x_k)$ is the corresponding Schur function.
\begin{claim}
\label{claim:complementary}
We have that
\begin{equation}
\label{eq:complementary}
s_{\nu}(1^n) = s_{m^n / \nu}(1^n) = s_{\bar{\nu}}(1^n)
\end{equation}
for any $\nu \subseteq m^n$,
where $\bar{\nu} = (m-\nu_n,m-\nu_{n-1},\ldots,m-\nu_1)$ is the complementary partition.
\end{claim}
\begin{proof}
\emph{Representation-theoretic proof:} the left-hand side of \eqref{eq:complementary} is equal to the dimension of the
representation $S^\nu\C^n$ of $\GLn$ which corresponds to the Young diagram $\nu$
while the right-hand side is equal to the dimension of the tensor product
of the one-dimensional representation $\GLn\ni g \mapsto (\det g)^m$
with the representation contragradient to~$S^\nu\C^n$. Their dimensions are clearly equal.
\bigskip
\emph{Combinatorial (bijective) proof:}
SSYTs with entries $1,\ldots,n$ of shape $\nu$ correspond to SSYTs with entries $1,\ldots,n$ and shape $\bar{\nu}$
via the following bijection. Consider an SSYT $T$ of shape $\nu$ as sitting inside the $m^n$ rectangle. In a given column $j$ of $m^n$, let $a_1<\cdots