%% 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]{FPSAC2020}
\articlenumber{94}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

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

\usepackage{latexsym,amssymb,amsfonts,bm}
\usepackage{fancyhdr,caption}
\usepackage{youngtab}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix}
\usepackage{mathrsfs}
% \usepackage{refcheck}

%% define your title in the usual way
\title{On the Algebraic Combinatorics of Injections}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Peter Dukes\thanks{\href{mailto:dukes@uvic.ca}{dukes@uvic.ca}. Supported by NSERC grant 312595--2017}\addressmark{1}, Ferdinand Ihringer\thanks{\href{mailto:ferdinand.ihringer@ugent.be}{ferdinand.ihringer@ugent.be}. Supported by a postdoctoral fellowship of
		the Research Foundation - Flanders (FWO)}\addressmark{2}, \and  Nathan Lindzey\thanks{\href{mailto:nathan.lindzey@colorado.edu}{nathan.lindzey@colorado.edu}.}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{ \addressmark{1}Mathematics and Statistics, University of Victoria, Victoria, BC, Canada\\ \addressmark{2}Vakgroep Wiskunde:
	Analyse, Logica en Discrete Wiskunde, Ghent University, Belgium\\ \addressmark{3}Computer Science, University of Colorado, Boulder, CO, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{ 
We consider the algebraic combinatorics of the set of injections from a $k$-element set to an $n$-element set. In particular, we give a new combinatorial formula for the spherical functions of the Gelfand pair $(S_k \times S_n, \text{diag}(S_k) \times S_{n-k})$.
We use this combinatorial formula to give new LP bounds on the size of codes over injections.

}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Representation theory of the symmetric group, Gelfand pairs, spherical functions, symmetric functions}


\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


\section{Introduction}

Let $S_n$ denote the symmetric group on $n$ elements and let $S_{k,n}$ denote the set of injections $f$ from $[k] := \{1,2,\cdots, k\}$ to $[n]$. Let $G_{k,n} := S_k \times S_n$ and $K_{k,n} := \text{diag}(S_k) \times S_{n-k}$. In this work, we investigate the algebraic combinatorics of $S_{k,n}$ via the Gelfand pair $(G_{k,n},K_{k,n})$. The spherical functions of $(G_{k,n},K_{k,n})$ have combinatorial significance, as they describe the eigenvalues of a natural family of graphs defined over $S_{k,n}$, i.e., the character table of the so-called \emph{injection association scheme}~\cite{LR,M}. We begin with a brief overview of previous work related to the subject.

Diaconis and Shahshahani first observed that $(G_{k,n},K_{k,n})$ is a Gelfand pair by showing the double coset algebra $\mathbb{C}[K_{k,n} \backslash G_{k,n} / K_{k,n} ]$ is commutative~\cite{Diaconis}. Later, Greenhalgh~\cite{Greenhalgh} found a closed expression for the spherical functions of $(G_{k,n},K_{k,n})$ evaluated at the double coset $K_{k,n} \backslash (k,k+1) / K_{k,n}$, equivalently, the eigenvalues of the graph over $S_{k,n}$ where $\sigma,\sigma'$ is an edge if their respective mappings agree on all but one symbol of the domain. Using this expression, he showed that the mixing time of the uniform random walk on this graph is approximately $(n-k)\log n + cn$ for some constant $c > 0$~\cite{Greenhalgh}.

In quantum computing, the algebraic combinatorics of $S_{k,n}$ have been used to show adversarial lower bounds on the time-complexity of the \textsc{Collision}, \textsc{Set-Equality}, and \textsc{Index-Erasure} problems. These lower bounds are derived from properties of the dual characters and Krein parameters of the injection association scheme, which are expressed in terms of the spherical functions of $(G_{k,n},K_{k,n})$~\cite{Ambainis,BR,LR}.

In coding theory, a relaxation of permutation codes known as \emph{injection codes} was introduced in \cite{Dukes}.  As the name suggests, one considers the problem of packing injections in $S_{k,n}$ with respect to Hamming distance.  In \cref{sec:codes}, via computing the character table of the injection scheme, we obtain new upper bounds on small injection codes, and we point out some  connections between injection codes and some problems in design theory.

In his thesis, Greenhalgh~\cite{Greenhalgh} posed the question of investigating the spherical functions of $(G_{k,n},K_{k,n})$, as they quite often correspond to interesting families of orthogonal polynomials (e.g., special functions). For the case $k = n-1$, the so-called "unbalanced" pair $(S_{n-1} \times S_n, \text{diag}(S_{n-1}))$, Strahov~\cite{Strahov} showed that many of the classical results in the theory of symmetric functions have unbalanced analogues. In particular, he gave a Murnaghan-Nakayama type rule and a Jacobi-Trudi identity for evaluating its spherical functions. Note that the "balanced" pair $(S_{n} \times S_n, \text{diag}(S_{n}))$ recovers the classical representation theory of $S_n$~\cite{MacDonald95}.

Such expressions for the cases $2 \leq k \leq n-2$ are not known, and to what extent the classical representation theory of the symmetric group carries over to these cases is an intriguing question. Indeed, the absence of useful combinatorial formulas for the spherical functions of $(G_{k,n},K_{k,n})$ has been a major obstacle in each of the areas above. 

We make some progress in this direction by giving a combinatorial formula for the spherical functions of $(G_{k,n},K_{k,n})$. The formula is significantly more revealing than the known formulas, and it is much easier to compute. It can be used to estimate the eigenvalues and ranks of matrices in the Bose--Mesner algebra of the injection scheme, in special cases, giving exact closed-form expressions (we do not pursue this direction in the present abstract), and it also allows us to efficiently compute the character tables of injection schemes to advance the state-of-the-art on upper bounds for injection codes.  


%---------------------------------------------------
\section{Injections and their Representation Theory}

Recall that a \emph{generalized permutation} is a $2 \times m$ array of positive integers
$$\left(\begin{array}{cccc}
i_1 & i_2 & \cdots & i_m\\
j_1 & j_2 & \cdots & j_m\
\end{array}\right) \text{ such that } i_1 \leq \cdots \leq i_m \text{, and if } i_r = i_{r+1}, \text{then } j_r \leq j_{r+1}.$$
\emph{Robinson-Schensted-Knuth Correspondence} (RSK) associates a pair of semistandard Young tableau of the same shape to each generalized permutation, and vice versa.
We may encode an injection $1 \mapsto j_1,2 \mapsto j_2,\cdots,k \mapsto j_k =: (j_1, j_2,\cdots, j_k)$ as a generalized permutation:
$$\left(\begin{array}{cccccccc}
1 & 2 & \cdots & k & k+1 & \cdots & k+1\\
j_1 & j_2 & \dots & j_k & j_{k+1} & \cdots & j_n\\
\end{array}\right),$$
where $j_{k+1}, \cdots, j_n \in [n] \setminus \{j_1,\cdots,j_k\}$ are ordered from least to greatest. It is easy to see that RSK associates to each injection a standard Young tableau $P$ and a semistandard Young tableau $Q$ of the same shape $\lambda \vdash n$. The subtableau of cells labeled $k+1$ in $Q$ form a horizontal strip on $n-k$ cells. Removing this horizontal strip results in a standard Young tableau of shape $\mu \vdash k$ such that $\lambda / \mu$ is a horizontal strip, and so we arrive at the following theorem.
\begin{thm}
	RSK gives an explicit bijection between $S_{k,n}$ and pairs $(P,Q)$ where $P$ is a standard Young tableau of shape $\lambda \vdash n$ and $Q$ is a standard Young tableau of shape $\mu \vdash k$ such that $\lambda / \mu$ is a horizontal strip.
\end{thm}

For example, let $n = 4$ and $k = 2$. There are $4!/2! = 12$ injections from $[2]$ to $[4]$:
$$(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),$$ 
$$(3,1),(3,2),(3,4),(4,1),(4,2),(4,3).$$
Their respective unique pairs $(P,Q)$ of standard Young tableau are listed from left to right as follows:\\
\scriptsize
\[
\begin{array}{llllll}
\young(1234)~\young(12\times\times) \quad & \young(124,3)~\young(12\times,\times) \quad & \young(123,4)~\young(12\times,\times)  \quad &
\young(134,2)~\young(1\times\times,2) \quad & \young(134,2)~\young(12\times,\times) \quad & \young(13,24)~\young(12,\times\times)\\
\\
\young(124,3)~\young(1\times\times,2) \quad & \young(14,2,3)~\young(1\times,2,\times) \quad & \young(12,34)~\young(12,\times\times) \quad &
\young(123,4)~\young(12\times,\times) \quad & \young(13,2,4)~\young(1\times,2,\times) \quad & \young(12,3,4)~\young(1\times,2,\times).\\
\end{array}
\]
\normalsize
\begin{cor}\label{cor:count}
	The number of injections from $[k]$ to $[n]$ can be counted as follows: 
	$$|S_{k,n}| = \sum_{\mu,\lambda} f^{\mu} f^{\lambda}$$
	where the sum runs over pairs $\mu \vdash k,\lambda \vdash n$ such that $\lambda / \mu$ is a horizontal strip.
\end{cor} 
\noindent This generalizes the well-known identity $|S_n| = \sum_{\lambda \vdash n} \left(f^\lambda \right)^2$ where $f^\lambda$ denotes the number of standard Young tableaux of shape $\lambda$.
We now present the corroborating representation theory for this count (see~\cite{LR} for a more detailed discussion). For undefined terminology concerning association schemes and Gelfand pairs, we refer the reader to~\cite{Godsil} and~\cite{MacDonald95} respectively.

The group $G_{k,n}$ acts on an injection $\sigma\colon[k]\rightarrow[n]$ as
$(\pi,\rho)\colon \sigma \mapsto \rho *\sigma *\pi^{-1}$, where $(\pi,\rho)\in G$ and $*$ denotes the composition of functions. The stabilizer of the identity injective function with respect to this action is the group $K_{k,n}$, i.e., the cosets $G_{k,n}/K_{k,n}$ are in one-to-one correspondence with injective functions. Since $(G_{k,n},K_{k,n})$ is a symmetric Gelfand pair, the action above gives a permutation representation $1 \uparrow_K^G$ that is multiplicity-free. By the Littlewood-Richardson rule, we have
\begin{align}
	1 \!\uparrow_{K_{k,n}}^{G_{k,n}}~~ \cong\!\!\!\!\!\!\! \bigoplus_{ \substack{ \mu \vdash k,\lambda \vdash n \\ \lambda/\mu \text{ is a horiz.~strip} }} \!\!\!\!\!\!\! \mu \otimes \lambda.
\end{align} 

The orbitals of $G_{k,n}$ acting diagonally on $G_{k,n}/K_{k,n} \times G_{k,n}/K_{k,n}$ are in one-to-one correspondence with double cosets $K_{k,n} \backslash G_{k,n} / K_{k,n}$. Thinking of injections graphically as maximum matchings of the complete bipartite graph $\mathbf{K}_{k,n}$, we observe that the double cosets and orbitals are in one-to-one correspondence with graph isomorphism classes that arise from the multiunion of any injection $\sigma \in S_{k,n}$ with the identity injection $e := (1,2,\cdots,k)$, i.e., a disjoint union of even paths and even cycles.\footnote{Note that an isolated vertex is an even path of length 0.} In light of this, we use the notation $(\lambda | \rho)$ to denote this isomorphism class, or the index of the orbital or double coset corresponding to this isomorphism class, containing a cycle of length $2\lambda_i$ for all $1 \leq i \leq \ell(\lambda)$, and a path of length $2\rho_i$ for all $1 \leq i \leq \ell(\rho)$. 

Let $C_{(\lambda | \rho)}$ be the set of injections of cycle-path type $(\lambda | \rho)$. For example, for $k=4$ and $n=8$, we have $(1,2,3,4) \in C_{(1^4 | 0^4)}$, $(2,1,3,5) \in C_{(2,1|0^3,1)}$, and $(5,6,7,8) \in C_{( \emptyset| 1^4)}$. The following result (see~\cite{LR}) gives a simple count for the sizes of these sets, analogous to the well-known formula for determining the size of a conjugacy class in $S_n$. 
\begin{prop}\label{prop:spheresizes}
	For any cycle-path type $(\lambda | \rho)$, the size of the $(\lambda|\rho)$-sphere is
	\[ |C_{\lambda | \rho}| = \frac{k!(n-k)!}{\prod_{i=0}^k i^{\ell_i} \ell_i!r_i! } \]
	where $\lambda=(0^{\ell_0},1^{\ell_1},\cdots,k^{\ell_k})$, $\rho=(0^{r_0}, 1^{r_1},\cdots,k^{r_k})$, and $\ell(\rho)=r_1+\cdots+r_k$.
\end{prop} 
\noindent In analogy with $S_n$, let $z_{(\lambda|\rho)} := \prod_{i =0}^k i^{\ell_i} \ell_i!r_i!$ where the $\ell_i$'s and $r_i$'s are as defined above.

The aforementioned orbitals can be represented as a set $\mathcal{A}_{k,n} := \{A_{(\lambda|\rho)}\}$ of symmetric matrices, i.e.,
\[
[A_{(\lambda|\rho)}]_{i,j} = 
\begin{cases}
1 \quad &\text{if } i \cup j \cong (\lambda|\rho); \\
0 \quad &\text{otherwise}
\end{cases}
\]  
for all injections $i,j \in S_{k,n}$ and cycle-path types $(\lambda|\rho)$. Moreover, these matrices pairwise commute and sum to the all-ones matrix, hence $\mathcal{A}_{k,n}$ is a symmetric association scheme, namely, \emph{the injection scheme}.\footnote{More precisely, \emph{the $(k,n)$-injection scheme}, also dubbed \emph{the $(k,n)$-partial permutation scheme}. } This scheme is of immediate combinatorial interest as it is a simultaneous generalization of the symmetric group scheme and the Johnson scheme. Its valencies $v_{(\lambda | \rho)}$ equal $|C_{(\lambda | \rho)}|$ and its multiplicities $m_{(\lambda | \rho)}$ are the dimensions of the irreducibles corresponding to $(\lambda | \rho)$. This latter correspondence is described as follows.

Recall that the irreducibles that appear in the aforementioned permutation representation of $G_{k,n}$ on $S_{k,n}$ have the form $\alpha \otimes \beta$ where $\beta / \alpha$ is a horizontal strip of size $n-k$. Consider a tableau of $\beta$ such that the cells of $\beta / \alpha$ are marked $\times$.
Every column of $\alpha$ in $\beta$ with a marked cell below it corresponds to a part in $\rho$ whereas an unmarked column corresponds to a part in $\lambda$. 
For instance, taking $\alpha = (2,1)$ and $n = 7$, we have the following cycle-path types for varying $\alpha \otimes \beta$:
\small
\[\underbrace{\young(~~\times\times,~\times,\times)}_{(\varnothing | 2,1,0^2)} \quad \quad \quad 
\underbrace{\young(~~\times\times\times,~,\times)}_{(1|2,0^3)} \quad \quad \quad 
\underbrace{\young(~~\times\times\times,~\times)}_{(2|1,0^3)} \quad  \quad \quad 
\underbrace{\young(~~\times\times\times\times,~)}_{(2,1|0^4)}. \]
\normalsize
Recall that if $(G,K)$ be a Gelfand pair such that $|K \backslash G /K| = d$, then the functions $\omega^1, \omega^2, \cdots,\omega^d \in \mathbb{C}[G/K]$ defined such that  
\begin{align}\label{eq:spherical}
\omega^i(g) = \frac{1}{|K|} \sum_{k \in K} \chi_i (g^{-1}k) \quad \forall g \in G
\end{align}
are called the \emph{spherical functions} and form an orthogonal basis for the double coset algebra $\mathbb{C}[K \backslash G /K]$. We call \eqref{eq:spherical} \emph{the projection formula}.
Let $\alpha \otimes \beta$ be the irreducible corresponding to $(\lambda|\rho)$. For any $(\mu|\nu)$, pick a double coset representative of the form $((),\sigma) \in G_{k,n}$ of $(\mu|\nu)$, which is possible due to the fact that the one-sided action of $S_n$ on $S_{k,n}$ is transitive. We may write the $(\lambda|\rho)$-spherical function (($\alpha \otimes \beta$)-spherical function) evaluated at $(\mu|\nu)$ as the following projection onto the space of $K_{k,n}$ invariant functions:
	\begin{align*}
	\omega^{(\lambda|\rho)}_{(\mu|\nu)} = \omega^{(\lambda|\rho)}(((),\sigma)) &= \frac{1}{|K_{k,n}|}\sum_{k\in K_{k,n}} \chi_{\alpha \otimes \beta}(((),\sigma)^{-1}k)\\
	&= \frac{1}{|K_{k,n}|}\sum_{(k_1,k_2) \in K_{k,n}} \chi_{\alpha \otimes \beta}((k_1,\sigma^{-1}k_1k_2))\\
	&= \frac{1}{k!(n-k)!}\sum_{k_1 \in S_k} \chi_{\alpha}(k_1) \sum_{k_2 \in S_{n-k}} \chi_{\beta}(\sigma^{-1}k_1k_2),
	\end{align*}
and the character table $P$ of the injection scheme can be written as
\begin{align}\label{eq:eig}	
P_{(\lambda|\rho),(\mu|\nu)} = |C_{(\mu|\nu)}| \omega^{(\lambda|\rho)}_{(\mu|\nu)}.
\end{align}
Note that the entries of the character table of any symmetric association scheme are algebraic integers, and the characters of the symmetric group are integers; therefore, the projection formula shows that the entries of $P$ are integers. 
As an aside, this gives a much simpler proof of the integrality of the spectrum of so-called \emph{$(n,k,r)$-arrangement graphs}, which live in the Bose--Mesner algebra of the injection scheme (see~\cite{Chen}).

Although the projection formula gives an explicit way of computing the character table of $\mathcal{A}_{k,n}$, it is difficult to work with from both a computational and analytical point of view. It becomes prohibitively difficult to compute the character table of $\mathcal{A}_{k,n}$ using this formula for even modest values of $k,n$, and it seems difficult to derive good expressions for the characters of $\mathcal{A}_{k,n}$ using this formula. In general, we are unaware of any proof that uses the projection formula for spherical functions to derive tractable expressions for the character tables of association schemes associated with Gelfand pairs.  



\section{A Canonical Basis for Injections}


Let $(\rho_1,V_1)$ and $(\rho_2,V_2)$ be two representations of a group $H$, and let $\phi : V_1 \rightarrow V_2$ be a linear map. We say that $\phi$ \emph{intertwines} $\rho_1$ and $\rho_2$ if $ \phi \rho_1(h) =  \rho_2(h) \phi$ for all $h \in H$. 

\begin{lem}[Schur's Lemma]
	If $(\rho_1,V_1)$ and $(\rho_2,V_2)$ are irreducible representations of $H$ and $\phi$ is an intertwining map for $\rho_1$ and $\rho_2$, then either $\phi$ is the zero map or it is an isomorphism.
\end{lem}
Let $\mathbb{C}[S_{k,n}]$ be space of all complex-valued functions defined over injections $S_{k,n}$. Let $\{e_i\}$ defined such that $e_i(j) = \delta_{i,j}$ for all $i,j \in S_{k,n}$ be the standard basis for this space.
For any $\lambda \vdash n$, let $M^\lambda$ be permutation representation of $S_n$ acting on the set of all $\lambda$-tabloids. Let $\{e_{\{t\}}\}$ defined such that $e_{\{t\}}(\{s\}) = \delta_{\{t\},\{s\}}$ for any two $\lambda$-tabloids $\{t\},\{s\}$ be the standard basis for this space. The product $M^\mu \otimes M^\lambda$ is a $G_{k,n}$-representation with basis $\{e_{\{s\}} \otimes e_{\{t\}}\}$ where $\{s\}$,$\{t\}$ range over all $\mu$-tabloids and $\lambda$-tabloids respectively.

Let $\{s\}$ be $\mu$-tabloid and $\{t\}$ be a $\lambda$-tabloid such that $\mu \vdash k$ and $\lambda \vdash n$. We say that $\{s\},\{t\}$ \emph{covers} an injection $\sigma \in S_{k,n}$ if $\text{row}_{\{s\}}(i) = \text{row}_{\{t\}}(\sigma(i))$ for all $1 \leq i \leq k$. For example, the injections $(1,2,3,4,5)$ in red and $(2,3,1,5,4)$ in blue are covered by the tabloid below, whereas the injection $(4,1,5,6,2)$ in green is not:


\usetikzlibrary{arrows, fit, matrix, positioning, shapes, backgrounds,
}
\[
\begin{tikzpicture}
\matrix (m) [
matrix of math nodes, 
nodes in empty cells,
minimum width=width("8"),
] {
	1 & \mathbf{1} & 2 & \mathbf{2} & 3 & \mathbf{3} & 7 & 8 \\
	4 & \mathbf{4} & 5 & \mathbf{5} \\
	6  \\
};


\draw[red,thick] (m-1-1.center) -- (m-1-2.center);
\draw[red,thick]  (m-1-3.center) --  (m-1-4.center);
\draw[red,thick]  (m-1-5.center) -- (m-1-6.center);
\draw[blue,thick] (m-1-2.center) to [bend right = 40]  (m-1-3.center);
\draw[blue,thick] (m-1-4.center) to [bend right = 40]  (m-1-5.center);
\draw[blue,thick] (m-1-1.center) to [bend left = 40]  (m-1-6.center);

\draw[red,thick]  (m-2-1.center) --  (m-2-2.center);
\draw[red,thick]  (m-2-3.center) --  (m-2-4.center);

\draw[blue,thick] (m-2-1.center) to [bend left = 40]  (m-2-4.center);
\draw[blue,thick] (m-2-2.center) to [bend right = 40]  (m-2-3.center);
       
\end{tikzpicture}
\quad\quad\quad\quad\begin{tikzpicture}
\matrix (m) [
matrix of math nodes, 
nodes in empty cells,
minimum width=width("8"),
] {
	1 & \mathbf{1} & 2 & \mathbf{2} & 3 & \mathbf{3} & 7 & 8 \\
	4 & \mathbf{4} & 5 & \mathbf{5} \\
	6  \\
};


\draw[red,thick] (m-1-1.center) -- (m-1-2.center);
\draw[red,thick]  (m-1-3.center) --  (m-1-4.center);
\draw[red,thick]  (m-1-5.center) -- (m-1-6.center);
\draw[OliveGreen,thick] (m-2-4.center) --  (m-1-3.center);
\draw[OliveGreen,thick] (m-1-1.center) to [bend right = 40]  (m-1-4.center);
\draw[OliveGreen,thick] (m-3-1.center) -- (m-2-2.center);

\draw[red,thick]  (m-2-1.center) --  (m-2-2.center);
\draw[red,thick]  (m-2-3.center) --  (m-2-4.center);

\draw[OliveGreen,thick] (m-2-1.center) -- (m-1-2.center);
\draw[OliveGreen,thick] (m-1-6.center) --   (m-2-3.center);

\end{tikzpicture}.
\]
Let $1_{\{s\},\{t\}} \in \mathbb{C}[S_{k,n}]$ be the characteristic function of the set of injections covered by $\{s\},\{t\}$. For any $\mu \vdash k,\lambda \vdash n$ such that $\lambda / \mu$ is a horizontal strip, let $\phi_{\mu,\lambda} : M^\mu \otimes M^\lambda \rightarrow \mathbb{C}[S_{k,n}]$ be the map defined such that
\[\phi_{\mu,\lambda}(e_{\{s\}} \otimes e_{\{t\}}) = 1_{\{s\},\{t\}} \quad \text{ for all }(\{s\},\{t\}),  \]
then extending linearly. An injection $\sigma$ is covered by $\{s\}, \{t\}$ if and only if $(\tau, \pi) \sigma$ is covered by $(\{\tau s\}, \{\pi t\})$ for all $(\tau,\pi) \in G_{k,n}$. This implies that 
	\[ \phi_{\mu,\lambda}( \tau e_{\{s\}} \otimes \pi e_{\{t\}} ) = (\tau,\pi)\phi_{\mu,\lambda}( e_{\{s\}} \otimes e_{\{t\}} )\quad \text{for all } (\tau,\pi) \in G_{k,n}, \]
	i.e., the linear map $\phi_{\mu,\lambda}$ intertwines $M^\mu \otimes M^\lambda$ and $\mathbb{C}[S_{k,n}]$.


It is well-known that the $\lambda$-isotypic component of $M^\lambda$ has multiplicity 1, and so the $(\mu \otimes \lambda)$-isotypic component of $M^\mu \otimes M^\lambda$ has multiplicity 1.  
Let $(\rho_{\mu,\lambda},V_\mu \otimes V_\lambda)$ be this $G_{k,n}$-irreducible. A basis for $\rho_{\mu,\lambda}$ can be obtained by tensoring all pairs of standard $\mu$-polytabloids and standard $\lambda$-polytabloids. For each standard Young tableau $t$, let $e_t$ denote the corresponding standard polytabloid.

We say that an injection $\sigma$ is \emph{aligned} with respect to $\{s\},\{t\}$ if $\text{row}_{\{s\}}(i) = \text{row}_{\{t\}}(\sigma(i))$ and $\text{column}_{\{s\}}(i) = \text{column}_{\{t\}}(\sigma(i))$ for all $1 \leq i \leq k$. For example, the blue injection $(2,3,6,5,4)$ is not aligned with the tabloids above, but the red injection $(1,2,3,4,5)$ is.
\begin{lem}\label{lem:nz}
	For each irrep $V_\mu \otimes V_\lambda$ of $1\!\!\uparrow_{K_{k,n}}^{G_{k,n}}$, there exists a $v \in V_\mu \otimes V_\lambda$ such that $\phi_{\mu,\lambda}(v) \neq 0$.
\end{lem}
\begin{proof}
	Let $e$ be the identity injection. Consider the pair of standard Young tableaux $s,t$ of shape $\mu$ and $\lambda$ respectively obtained by inserting the numbers $1,2,\cdots,k$ into the rows of $s$ from left to right, top to bottom, then taking $t$ to be the standard Young tableau obtained from $s$ by adding a horizontal strip and labeling the cells $k+1,k+2, \cdots, n$ from left to right. For example, if $\mu = (3,2,1)$ and $\lambda = (4,3,2)$, then $s$ and $t$ are
	\scriptsize
	\[\young(123,45,6) \quad \quad\quad\quad\quad
	\young(1239,458,67). \] 
	\normalsize
	Note that $e$ is aligned with respect to $\{s\},\{t\}$. Let $C_s,C_t$ denote the column-stabilizers of $s$ and $t$ respectively. It is clear that 
	\[e_s \otimes e_t = \sum_{\pi \in C_s,\pi' \in C_t} \text{sgn}(\pi)~\text{sgn}(\pi')~ e_{\{\pi s\}} \otimes e_{\{\pi' t\}}.\]
	Let $v = e_s \otimes e_t$ and $f = \phi_{\mu,\lambda}(v)$. We have
	\[f(e) = \sum_{\pi \in C_s,\pi' \in C_t} \text{sgn}(\pi)~\text{sgn}(\pi')~ 1_{\{\pi s\},\{\pi' t\}}(e). \]
	If $\pi \in C_s$ sends $i$ to $j$ such that $1 \leq i,j \leq k$, then $\pi' \in C_t$ must also send $i$ to $j$, otherwise $\{\pi s\},\{\pi' t\}$ does not cover $e$. On the other hand, if $\pi' \in C_t$ sends $i$ to $j$ such that $1 \leq i \leq k$ and $k+1 \leq j \leq n$, then $(\{\pi s\},\{\pi' t\})$ does not cover $e$ for all $\pi \in C_s$, which implies that the cells of the horizontal strip $\lambda/\mu$ are fixed points of every $\pi' \in C_t$ such that $\{\pi s\},\{\pi' t\}$ covers $e$. The foregoing implies that $\text{sgn}(\pi)~\text{sgn}(\pi') = 1$ if and only if $\{\pi s\},\{\pi' t\}$ covers $\sigma$. In particular, we have
	\[f(\sigma) = \sum_{\pi \in C_s,\pi' \in C_t} \text{sgn}(\pi)~\text{sgn}(\pi')~ 1_{\{\pi s\},\{\pi' t\}}(\sigma) = |C_s|, \]
	thus $f = \phi_{\mu,\lambda}(v)  \neq 0$, as desired.
\end{proof}
\noindent Now let $f_{s,t} := \phi_{\mu, \lambda}$ where $s,t$ are standard Young tableaux of shape $\mu \vdash k$ and $\lambda \vdash n$ such that $\lambda / \mu$ is a horizontal strip.
Let $\mathcal{F} := \{f_{s,t}\}$ where $s$ and $t$ range over all such standard Young tableaux.
\begin{thm}
	The set $\mathcal{F}$ is a basis for $\mathbb{C}[S_{k,n}]$ such that $\langle f_{q,r},f_{s,t}\rangle = 0$ for all $f_{q,r} \in V_{\mu \otimes \lambda}$ and $f_{s,t} \in V_{\mu' \otimes \lambda'}$ such that $\lambda / \mu \neq \lambda' / \mu'$.
\end{thm}
\begin{proof}
	By \cref{lem:nz}, $\phi_{\mu,\lambda}$ is not the zero map, so by Schur's Lemma, we have that $\phi_{\mu,\lambda}$ is an isomorphism. 
	Since the elements of $\mathcal{F}$ are pairwise linearly independent, \cref{cor:count} implies that $\mathcal{F}$ is a basis. as desired.
\end{proof}
\noindent It would be interesting to refine the result above to a \emph{Fourier basis} for $\mathbb{C}[S_{k,n}]$, that is, further require that basis functions in the same isotypic component are orthogonal. Note that Young's orthogonal form furnishes such a basis for the $k=n$ case.
\begin{thm}[Frobenius Reciprocity]\label{thm:frobenius}
	Let $\rho$ be an irreducible representation of a group $H$ and let $K$ be a subgroup of $H$. The multiplicity of the $\rho$-isotypic component of $1\!\uparrow^H_K$ is the dimension of the subspace of $K$-invariant functions of the $\rho$-isotypic component.
\end{thm}
\noindent Let $Q_{k,n}$ denote the projection onto the space of $K_{k,n}$-invariant functions. For any $\mu \vdash k$, define $\mu! := \mu_1!\mu_2!\cdots \mu_{\ell(\mu)}!$.
\begin{lem}
	Let $s,t$ be standard Young tableaux of shape $\mu \vdash k$ and $\lambda \vdash n$ such that $\lambda / \mu$ is a horizontal strip. If $Q_{k,n}f_{s,t} \neq 0$, then $\frac{1}{(\mu^\top)!}Q_{k,n}f_{s,t}$ is the $(\mu \otimes \lambda)$-spherical function. 
\end{lem}
\begin{proof}
	By construction, $f_{s,t} \in \mathbb{C}[S_{k,n}]$ lives in the irreducible $W \leq \mathbb{C}[S_{k,n}]$ that is isomorphic to $V_{\mu} \otimes V_{\lambda}$. Because $Q_{k,n}$ sends $W$ to $W$, we have that $Q_{k,n}f_{s,t} \in W$ is a $K_{k,n}$-invariant function. By Frobenius Reciprocity, the space of $K_{k,n}$-invariant functions of $W$ has dimension 1; therefore, if $Q_{k,n}f_{s,t} \neq 0$, then it is the $(\mu \otimes \lambda)$-spherical function up to scaling. To ensure that the $(\mu,\lambda)$-spherical function is 1 on the $K_{k,n} \backslash () /K_{k,n}$ double coset, we normalize by $|C_s| = (\mu^\top)!$.
\end{proof}
\noindent We are now ready to give a proof of our formula for the spherical functions of $(G_{k,n},K_{k,n})$. Let $s,t$ be the pair of standard Young tableaux as defined in the proof of \cref{lem:nz}.
\begin{thm}\label{thm:main}
	Let $\omega^{\mu \otimes \lambda}$ be the $(\mu \otimes \lambda)$-spherical function of the Gelfand pair $(G_{k,n},K_{k,n})$. Then
	\[ \omega^{\mu \otimes \lambda}_{(\gamma|\rho)} =  \frac{1}{|C_{(\gamma|\rho)}|} \sum_{\pi \in C_t} \emph{sgn}(\pi) |\{ \sigma \in C_{(\gamma|\rho)} : \{s\}, \{\pi t\}\emph{ covers } \sigma \}|. \]
	for all cycle-path types $(\gamma|\rho)$.
\end{thm}
\begin{proof}
	An argument similar to the proof of \cref{lem:nz} shows that $Q_{k,n}f_{s,t} \neq 0$, hence $Q_{k,n}f_{s,t} = \omega^{(\mu \otimes \lambda)}$ by the lemma above. In particular, we have
	\[ \omega^{\mu \otimes \lambda}_{(\gamma|\rho)} =  \frac{1}{(\mu^\top)!|C_{(\gamma|\rho)}|} \sum_{\pi \in C_s, \pi' \in C_t} \text{sgn}(\pi)~\text{sgn}(\pi') |\{ \sigma \in C_{(\gamma|\rho)} : \{\pi s\}, \{\pi't\}\text{ covers } \sigma \}|. \]
	But note that $C_s \leq C_t$, which gives us
	\[ \omega^{\mu \otimes \lambda}_{(\gamma|\rho)} =  \frac{1}{(\mu^\top)!|C_{(\gamma|\rho)}|} \sum_{\pi \in C_s, \tau \pi  \in  C_t\pi } \text{sgn}(\tau) |\{ \sigma \in C_{(\gamma|\rho)} : \{\pi s\}, \{\tau \pi t\}\text{ covers } \sigma \}|. \]
	Since  $\{\pi s\}, \{\tau \pi t\}\text{ covers } \sigma$ if and only if  $\{s\}, \{\tau t\}\text{ covers } \sigma$, we may rewrite the above as
	\[ \omega^{\mu \otimes \lambda}_{(\gamma|\rho)} =  \frac{1}{|C_{(\gamma|\rho)}|} \sum_{\pi \in C_t} \text{sgn}(\pi) |\{ \sigma \in C_{(\gamma|\rho)} : \{s\}, \{\pi t\}\text{ covers } \sigma \}|, \]
	which completes the proof.
\end{proof}

\noindent Just to quickly demonstrate our formula's efficacy, let $\overline{\mu} := (\mu_1 + n -k,\mu_2,\cdots,\mu_{\ell(\mu)}) \vdash n$ for any $\mu \vdash k$, and consider the spherical function $\omega^{\mu \otimes \overline{\mu}}$. If $\rho$ has more than $\mu_1$ non-trivial paths for any $(\gamma|\rho)$, then it is not hard to see that $\omega^{\mu \otimes \overline{\mu}}_{(\gamma|\rho)} = 0$, a fact which is hardly transparent from the projection formula.   
Indeed, the $(\mu \otimes \overline{\mu})$-spherical functions play a crucial role in~\cite{Ambainis,LR}, and our formula may allow one to improve the results of~\cite{LR}.


\section{LP Bounds for Injection Codes}\label{sec:codes}

For more details on association schemes and their connections to coding theory, see~\cite{Godsil,Delsarte}. Let $\mathcal{A}=\{A_0,A_1,\dots,A_d\}$ be an association scheme over a set $X$.
For a subset $Y \subseteq X$, let $\bm{\phi}=\bm{\phi}_Y \in \{0,1\}^X$ be its characteristic function.
Assuming $Y \neq \emptyset$, its \emph{inner distribution vector} $\mathbf{a}=\mathbf{a}_Y=(a_0,a_1,\dots,a_d)$ has entries
\[
a_i = \frac{\bm{\phi}^\top A_i \bm{\phi}}{\bm{\phi}^\top  \bm{\phi}},
\]
representing the relative frequencies of $i$th associates among pairs of elements of $Y$.

The following observation is simple, yet has profound consequences.

\begin{thm}[Delsarte, \cite{Delsarte}]
\label{Delsarte-LP}
For $\emptyset \neq Y \subseteq X$, its inner distribution vector $\mathbf{a}$ satisfies
\[\mathbf{a} Q \ge \mathbf{0},\]
where $Q$ is the dual eigenmatrix.
\end{thm}

Using \cref{Delsarte-LP}, Tarnanen \cite{T} computed LP bounds on permutation codes for $n \le 10$ and various allowed distance sets.  This was extended by Bogaerts \cite{Bogaerts} to $n \le 14$. For the injection scheme $\mathcal{A}_{k,n}$, using the formula of \cref{thm:main} we implemented \cref{Delsarte-LP} for $3 \le k < n \le 15$,
with the exception of a few parameter pairs $(k,n)$ at the larger end of this triangle, which are presently out of reach.  

Following the notation used in \cite{CKL,Dukes,T}, we write $M(n,k,d)$ for the maximum size of an injection code with minimum Hamming distance $d$.  Some basic observations and bounds on $M(n,k,d)$ can be found in \cite{Dukes}.  An easy recursive upper bound is as follows.

\begin{prop}[Singleton bound]
$M(n,k,d) \le n!/(n-k+d-1)! = |S_{k-d+1,n}|.$
\end{prop}

Additional bounds on $M(n,k,d)$ are motivated by interest in the permutation code case, both for applications to powerline communication \cite{CKL,Huc} and as a problem of independent interest in extremal combinatorics.  For example, equality in the Singleton bound is equivalent \cite{Dukes} to existence of an \emph{ordered design}, that is, a set of $k$-tuples of distinct elements from $[n]$ such that, when restricted to any $k-d+1$ positions, every injection in $S_{k-d+1,n}$ appears exactly once.
  
The case $d=k-1$ has special significance for its connection with latin squares.  Colbourn, Kl\o ve and Ling \cite{CKL} showed that the existence of $r$ mutually orthogonal latin squares of order $n$ imply a permutation code of length $n$ and minimum distance $n-1$.  Here, the code permutations correspond to the $n$ level sets occurring among each of the $r$ squares.  With this same construction, it is easy to see that the existence of $r$ mutually orthogonal $k \times n$ latin rectangles implies $M(n,k,k-1) \ge rn$.  It follows that an upper bound on $M(n,k,k-1)$ induces an upper bound on the number of mutually orthogonal $k \times n$ latin rectangles.


\begin{table}[ttttp]
\begin{tabular}{cccr}
$n$ & $k$ & $d$ & $M \le$ \\
\hline
7 & 6 & 4 & 199\\
8 & 6 & 3 & 1513\\
 & 7 & 4 & 1462\\
9 & 7 & 4 & 2846\\
 & 8 & 4 & 12096\\
 &  & 5 & 2417\\
10 & 7 & 3 & 27308\\
 & 8 & 4 & 26206\\
 &  & 5 & 5039\\
 & 9 & 4 & 92418\\
 &  & 5 & 19158\\
 &  & 6 & 4991\\ 
11 & 8 & 4 & 52646\\
\\
\end{tabular}
\hspace{1cm}
\begin{tabular}{cccr}
$n$ & $k$ & $d$ & $M \le$ \\
\hline
11 & 9 & 4 & 256682\\
 &  & 5 & 47073\\
 & 10 & 4 & 936332\\
 &  & 5 & 185560\\
 &  & 6 & 42068\\
12 & 8 & 3 & 602579\\
 & 9 & 4 & 584327\\
 & 10 & 4 & 2699260\\
 &  & 5 & 471981\\
 & 11 & 4 & 10241521\\
 &  & 5 & 1922527\\
 &  & 6 & 411090\\ 
 13 & 9 & 4 & 1185053\\
\\ 
\end{tabular}
\hspace{1cm}
\begin{tabular}{cccr}
$n$ & $k$ & $d$ & $M \le$ \\
\hline
13 & 12 & 4 & 123235550\\
 &  & 5 & 23347599\\
 &  & 6 & 4687470\\
 &  & 7 & 910371\\
14 & 13 & 4 & 1621775700\\
 &  & 5 & 309490273\\
 &  & 6 & 58903464\\
 &  & 7 & 10510496\\
 &  & 8 & 2117618\\
15 & 14 & 4 & 23358981663\\
 &  & 5 & 4130012797\\
 &  & 6 & 804830167\\
 &  & 7 & 138132435\\
 &  & 8 & 24260981
\end{tabular}
\caption{Upper bounds on $M(n, k, d)$ via linear programming.}
\label{mindist}
\end{table}

\section{Future Work and Open Questions}

As mentioned before, our main open-ended question is to what extent the representation theory of the symmetric group (i.e., the Gelfand pair $(S_n \times S_n, \text{diag}(S_n))$) carries over to the Gelfand pair $(G_{k,n},K_{k,n})$. Indeed, we believe there are stronger connections to the representation theory of the symmetric group yet to be discovered. 

For example, following~\cite[I.7]{MacDonald95} and letting 
\[C' := \bigoplus_{k,n~:~k\leq n} \mathbb{C}[K_{k,n} \backslash G_{k,n} / K_{k,n}],\]
one can define a natural bilinear multiplication on $C'$ so that it is a commutative and associative graded $\mathbb{C}$-algebra. Classically, the characteristic map $\text{ch} : C \rightarrow \Lambda$ is an isometric isomorphism between the commutative and associative graded algebra $C$ generated by all irreducible characters of symmetric groups and the ring of symmetric functions $\Lambda$. 
It would be particularly interesting to find an analogous characteristic map $\text{ch'}:C' \rightarrow \Lambda'$ to a suitable polynomial ring $\Lambda'$ such that its vector space $(\Lambda')^k$ of degree-$k$ polynomials has dimension equal to the number of cycle-types of $S_{k,n}$. 

Finally, we suspect there are other "unbalanced" Lie and $q$-analogues of $(G_{k,n},K_{k,n})$ that might be worth investigating, which would likely require different techniques than the ones presented here.



%% 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




\end{document}
