\documentclass[final]{FPSAC2022}
%\usepackage[utf8]{inputenc}
%\usepackage{enumitem}
%\usepackage[T1]{fontenc}



%\usepackage[english]{babel}

\usepackage{tikz-cd}
\usepackage{csquotes}
 


\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem*{conj_MJ}{The Matching-Jack conjecture}


\theoremstyle{definition}
\newtheorem{defi}{Definition}[section]

\theoremstyle{remark}
\newtheorem{rmq}{Remark}
\newtheorem{exe}{Example}[section]

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




\author[H.~Ben Dali]{Houcine Ben Dali\thanks{\href{mailto:houcine.ben-dali@univ-lorraine.fr}{houcine.ben-dali@univ-lorraine.fr}}\addressmark{1,2}}

\address{\addressmark{1}Universit\'e de Lorraine, CNRS, IECL, F-54000 Nancy, France\\
\addressmark{2}Universit\'e de Paris, CNRS, IRIF, F-75006, Paris, France}  
\received{\today} 
\DeclareMathOperator{\Ch}{Ch}
\DeclareMathOperator{\de}{d}

\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\Z}{\mathcal Z}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\tc}{t}
\DeclareMathOperator{\cf}{\mathfrak c}
\DeclareMathOperator{\mf}{\mathfrak m}
\DeclareMathOperator{\ff}{\mathfrak f}
\DeclareMathOperator{\gf}{\mathfrak g}


%\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}






\begin{document}

\title[Integrality in the Matching-Jack Conjecture]{Integrality in the Matching-Jack Conjecture and the Farahat--Higman Algebra}

\abstract{Using Jack polynomials, Goulden and Jackson have introduced a one parameter deformation $\tau_b$ of the generating series of bipartite maps. The Matching-Jack conjecture suggests that the coefficients $c^\lambda_{\mu,\nu}$ of the function $\tau_b$ in the power-sum basis are non-negative integer polynomials in the deformation parameter $b$. 
Do\l{}{\k{e}}ga and F\'eray have proved in 2016 the ``polynomiality'' part in the Matching-Jack conjecture. 
In this paper, we prove the ``integrality'' part.


The proof is based on a recent work of the author that deduces the Matching-Jack conjecture for marginal sums $c^\lambda_{\mu,l}$ from an analog result for the $b$-conjecture, established in 2020 by Chapuy and Do\l{}{\k{e}}ga.  
 A key step in the proof involves a new connection with the graded Farahat--Higman algebra.
}
\keywords{Matching-Jack conjecture, Jack polynomials, Farahat--Higman algebra, top coefficients}

\maketitle




\section{Introduction}
\subsection{Coefficients \texorpdfstring{$c^\lambda_{\mu,\nu}$}{} and the Matching-Jack conjecture} Jack polynomials $J^{(\alpha)}_\theta$ are symmetric functions that depend on a deformation parameter $\alpha$ (see \cite{J,Stan89,Mac}). 
We consider the power-sum functions  $\mathbf{p}:=(p_1,p_2,\ldots)$, $\mathbf{q}:=(q_1,q_2,\ldots)$ and $\mathbf{r}:=(r_1,r_2,\ldots)$ associated to three different alphabets, and we denote by $J^{(\alpha)}_\theta$ the Jack polynomial of parameter $\alpha$ expressed in the power-sum basis.
 In \cite{GJ96b}, Goulden and Jackson have introduced the function $\tau_b$ that depends on the parameter $b:=\alpha-1$ and defined by:
$$\tau_b(t,\mathbf{p},\mathbf{q},\mathbf{r}):=\sum_{n\geq0}t^n\sum_{\theta\vdash n}\frac{1}{j^{(\alpha)}_\theta}J^{(\alpha)}_\theta(\mathbf{p})J^{(\alpha)}_\theta(\mathbf{q})J^{(\alpha)}_\theta(\mathbf{r}),$$ 
where  $j^{(\alpha)}_\theta$ is the square norm of the Jack polynomial $J_\theta^{(\alpha)}$ with the respect to an $\alpha$-deformation of the Hall scalar product. 

%\noindent
The main motivation of studying this function comes from the fact that it gives for $b=0$ and $b=1$ respectively, the generating series of bipartite maps on oriented and general surfaces (see \cite{GJ96a}).
Maps are graphs embedded into surfaces, orientable or not. The enumeration of maps involves various methods such as matrix integrals, representation theory tools and bijective methods \cite{Cha11,Eyn16,LZ04}. 


We consider the coefficients $c^\lambda_{\mu,\nu}(b)$ defined by
\begin{equation}\label{eqtau}
\tau_b(t,\mathbf{p},\mathbf{q},\mathbf{r})=\sum_{n\geq 0}t^n\sum_{\lambda,\mu,\nu\vdash n}\frac{c^\lambda_{\mu,\nu}(b)}{z_\lambda(1+b)^{\ell(\lambda)}}p_\lambda q_\mu r_\nu.
\end{equation}
These coefficients are the main objects of the Matching-Jack conjecture, formulated by Goulden and Jackson \cite[Conjecture 3.5]{GJ96b}.
\begin{conj_MJ}[Goulden and Jackson]
For every partitions $\lambda,\mu,\nu$ of size $n\geq1$, the coefficient $c^\lambda_{\mu,\nu}$ is a polynomial in $b$ with non-negative integer coefficients.
\end{conj_MJ}

The Matching-Jack conjecture is equivalent to saying that $\tau_b$ is a generating series of matchings with some particular weights (see \cite[Conjecture 4.2]{GJ96b}). 
There exists a connected version of this conjecture called the \textit{$b$-conjecture.} The $b$-conjecture suggests that the function $(1+b)\frac{t\partial}{\partial t}\log(\tau_b)$ has also a positivity property and that it enumerates bipartite maps with some weights \cite[Conjectures 6.2 and 6.3]{GJ96b}.  Since bipartite maps can be encoded with matchings (see, \textit{e.g.},~\cite{BD21,DFS14,GJ96a}), the Matching-Jack conjecture and the $b$-conjecture are related. However, no implication between them has been proved and both of them are still open.

\subsection{Former results and main theorem}
In addition to the special cases $b=0$ and $b=1$ that follow from connections with representation theory (see \cite{LZ04,GJ96b}), several partial results related to the Matching-Jack conjecture have been established, we cite here some of them. 

The first type of results is related to coefficients $c^\lambda_{\mu,\nu}$ for general partitions $\lambda,\mu,\nu$. It follows from the Jack polynomials theory that these coefficients are rational functions in $b$, the polynomiality has been proved by Féray and Do\l{}{\k{e}}ga.

\begin{thm}[{\cite[Corollary 4.2]{DF16}}]\label{thm polynomiality}
For all partitions $\lambda,\mu,\nu\vdash n\geq 1$, the coefficient $c^\lambda_{\mu,\nu}$ is polynomial in $b$ with rational coefficients. 
\end{thm}

Other properties about the structure of these polynomials have been proved in \cite{La09}.

The second type of results gives the Matching-Jack conjecture for some family of partitions $(\lambda,\mu,\nu)$ and specializations of the function $\tau_b$.
The following has been established in \cite{BD21}, it has been deduced from an analogous result for the $b$-conjecture proved by Chapuy and Do\l{}{\k{e}}ga in \cite{CD20}.

\begin{thm}[\cite{BD21}]\label{thm mar}
For every $n,l\geq1$ and for every partitions $\lambda,\mu\vdash n$, the marginal coefficient $c^\lambda_{\mu,l}$ defined by 
$$c^\lambda_{\mu,l}:=\sum_{\ell(\nu)=l}c^\lambda_{\mu,\nu}\text{ ,}$$
is a polynomial in $b$ with non-negative integer coefficients. 
\end{thm}

This previous theorem covers other partial results in this direction (see \cite{KV16,KPV18}).
The main result of this paper gives integrality in the Matching-Jack conjecture.

\begin{thm}\label{thm integrality}
For every $\lambda,\mu,\nu\vdash n\geq 1$, the coefficient $c^\lambda_{\mu,\nu}$ is a polynomial in $b$ with integer coefficients. 
\end{thm}

The proof of this theorem is based on \cref{thm mar}. Since the approach used here is independent from the one considered in \cite{DF16}, it gives a new proof of \Cref{thm polynomiality}.

\subsection{The Farahat--Higman algebra}

The Farahat--Higman algebra was introduced in \cite{FH59} in order to study the structure coefficients of the conjugacy classes $C_\mu(n)$ in the center of the symmetric group algebra $Z(\mathbb{Z}\mathfrak{S}_n)$.
It has been shown that the Farahat--Higman algebra is isomorphic to the algebra of integral symmetric functions (see \cite{GJ94,CGS04}), it is also related to the algebra of partial permutations introduced by Ivanov and Kerov in \cite{IK99}.

In \Cref{sec FHA}, we will consider a graded version of the Farahat--Higman algebra that we denote $\mathcal{Z}_\infty$ and that has been introduced in   \cite[Example 24,page 131]{Mac}.
In \Cref{thm g}, we exhibit a new basis of $\Z_\infty$, which is useful in the proof of the main theorem.

\subsection{Steps of the proof}
A key tool of the proof of \Cref{thm integrality} is the following multiplicativity property that can be obtained using the orthogonality of the Jack polynomials (see \cite{BD21b} for more details).
\begin{prop}\label{prop multiplicativity}
For every $\lambda,\mu,\nu \vdash n\geq1$ and $l\geq1$, we have 
    \begin{equation}\label{eq prop mult}
  \sum_{\kappa\vdash n}c^\lambda_{\mu,\kappa}c^\kappa_{\nu,l}=\sum_{\theta\vdash n} c^\lambda_{\theta,l} c^\theta_{\mu,\nu}.
\end{equation}
\end{prop}
This property will be considered as a a system of linear equations that allows to recover $c^\lambda_{\mu,\nu}$ from the coefficients $c^\lambda_{\mu,l}$ (see \Cref{rmq eqsystem}).
 We now give the key steps of the proof of \Cref{thm integrality}.

\begin{itemize}

    \item We prove that for a particular choice of set of parameters $\lambda,\mu,\nu,l$, \cref{eq prop mult} gives a square linear system with some triangularity property that allows to obtain information on $c^\lambda_{\mu,\nu}$ by induction on the length of $\nu$ (see \Cref{lem linearsystem}). 
    \item We prove that the diagonal blocks of the matrix encoding this system, denoted $\mathcal{Q}^{(r)}$, contain some coefficients $\tc^\rho_\pi$, that are independent from $b$ (see \Cref{sec top coef} and \cref{prop Qnr}).
    \item We prove that the matrix $\mathcal{Q}^{(r)}$ is invertible in $\mathbb Z$ by proving that it is a change-of-basis matrix in the graded Farahat--Higman algebra $\Z_\infty$ (see \Cref{prop Q tr mat} and \Cref{thm g}). 
\end{itemize}


Using \Cref{rmq eqsystem} below and the combinatorial interpretation of the coefficients $c^\lambda_{\mu,l}$ given in \cite{BD21}, it is possible to give a new proof for the Matching-Jack conjecture for $b=0$ and $b=1$ that does not use representation theory (such a proof follows in a more intricate way from \cite{CD20}, private communication).
Unfortunately, the non-negativity of the coefficients of $c^\lambda_{\mu,\nu}$ as polynomials in $b$ seems to be out of reach with our approach. 
We were also not able to use the same arguments to obtain integrality in the $b$-conjecture. However, it is possible to obtain the integrality for the cumulants of $c^\lambda_{\mu,\nu}$, which up to rescaling by a factor of the form $\frac{n}{z_\lambda(1+b)^{\ell(\lambda)-1}}$, give the coefficients of the $b$-conjecture.



\subsection{Some notations}\label{sec partitions}
An \textit{integer partition} $\lambda=[\lambda_1,\lambda_2,\dotsc,\lambda_l]$ is a sequence of weakly decreasing positive integers $\lambda_1\geq\lambda_2 \geq \cdots \geq\lambda_l>0$. The integer $l$ is the \textit{length} of the partition $\lambda$, \textit{i.e} its number of parts. It is denoted by $\ell(\lambda)$.   We define the \textit{rank} of a partition $\lambda$ by $\rk(\lambda):=n-\ell(\lambda)$.
We denote by  $\lambda-\mathbf{1}$ the partition  $[\lambda_1-1,\lambda_2-1,\ldots,\lambda_l-1]$, and if $r\geq l$, we denote by $\lambda\oplus 1^{r}$ the partition 
$[\lambda_1+1,\ldots,\lambda_l+1,\underbrace{1,1,\dotsc,1}_{r-l \text{ times}}]$.



\section{Top coefficients \texorpdfstring{$\tc^\rho_\pi$}{}}\label{sec top coef}
As announced in the introduction, the proof of \Cref{thm integrality} involves the resolution of a linear system satisfied by the coefficients $c^\lambda_{\mu,\nu}$. In this section, we introduce the matrices $\mathcal{Q}^{(r)}$ that encode this system. We start by the following lemma, which is a consequence of \Cref{thm mar} and some basic properties of the coefficients $c^\lambda_{\mu,l}$ (see \cite{BD21b} for the proof).
\begin{lem}\label{lem bounddeg}
For every partitions $\lambda,\mu,\vdash n\geq 1$ and $l\geq 1$, we have the following bound on the degree of $c^\lambda_{\mu,l}$ as a polynomial in $b$:
$$\deg_b(c^\lambda_{\mu,l})\leq n-l+\ell(\lambda)-\ell(\mu).$$
\end{lem}

We consider some stability properties of the coefficients $c^\lambda_{\mu,l}$ for which the previous bound
is zero. 
\begin{prop}\label{lem add part1}
Let $\kappa,\nu,\mu\vdash n\geq1,$ such that $\rk(\kappa)=\rk(\nu)+\rk(\mu)$. 
We have
$$c^\kappa_{\nu,\mu}=c^{\kappa\cup1^m}_{\nu\cup{1^m},\mu\cup 1^m}, \hspace{0.5 cm} \text{for every }m\geq1.$$
In particular, for every $\kappa,\nu,\mu\vdash n\geq1,$ and $l\geq1$ such that  $\rk(\kappa)=\rk(\nu)+n-l$, we have 
$$c^\kappa_{\nu,l}=c^{\kappa\cup1^m}_{\nu\cup{1^m},l+m}, \hspace{0.5 cm} \text{for every }m\geq1.$$
\begin{proof}
This is a consequence of \cref{prop FH} and \cref{eq structure coefficients} below.
\end{proof}
\end{prop}

We introduce the following definition.

\begin{defi}\label{def top coefficients}

Let  $\rho$ and $\pi$ be two partitions of size $r\geq 1$. We consider two partitions $\kappa $ and $\nu$ of the same size $n\geq r+\ell(\rho)$, such that $\rho=\kappa-\mathbf{1}$ (or equivalently $\kappa=\rho\oplus 1^{n-r}$),  $\nu=\pi\cup 1^{n-r}$ and $l$ is such that $n-l+\rk(\nu)=r$. We define the \textit{top coefficient}\footnote{This terminology will be justified in \Cref{sec FHA}} $\tc^\rho_{\pi}:=c^{\kappa}_{\nu,l}$.  \\
 Note that given \Cref{lem add part1} this definition does not depend on $n$. 

\end{defi}






 We consider the matrix of top coefficients $\mathcal{Q}^{(r)}:=(\tc^{\rho}_{\pi})_{\pi,\rho\vdash r}$.
We give here $\mathcal{Q}^{(r)}$ for $r=3$, 
\[
 \begin{array}{|c|c|c|c|} \hline
 \pi \backslash \rho &  [3] & [2,1] & [1^3]\\ \hline
 [3] & 4 & 1 & 0  \\ \hline
 [2,1] & 6 & 4 &3  \\ \hline
 [1^3] & 1 & 1 & 1 \\ \hline
   \end{array}.
\]

   
The following theorem will be proved in \Cref{sec FHA} (see \Cref{thm g}).

\begin{thm}\label{thm Qinv}
The matrix $\mathcal{Q}^{(r)}=(\tc^\rho_\mu)_{\rho,\mu\vdash r}$ is invertible in $\mathbb Z$ for every $r\geq 1.$
\end{thm}


There exists an explicit expression of the top coefficients $\tc^\rho_\pi$, see \cite{BG92}. However, for the proof of \Cref{thm Qinv}, it will be more natural to consider the algebraic definition of these coefficients and see the matrix $\mathcal{Q}^{(r)}$ as a change-of-basis matrix (see \Cref{prop Q tr mat}).


\section{Proof of \texorpdfstring{\Cref{thm integrality}}{Theorem 1.3}}

The main purpose of this section is to prove that \Cref{thm Qinv} implies \Cref{thm integrality}.


\noindent We fix $n>0$. 
 For $1\leq r< n$, we introduce the assertion $\mathcal A_{n}^{(r)}$:
\begin{align*}\label{eq assertion}
    \mathcal A_{n}^{(r)}:  &\text{ for every }\lambda,\mu,\kappa\vdash n \text{ such that } \rk(\kappa)=r, c^\lambda_{\mu,\kappa}\text{ is an integer polynomial in } b.
\end{align*}
We will prove $\mathcal A_{n}^{(r)}$ by induction on $r$.


\begin{lem}\label{lem linearsystem}
We fix $1\leq r<n$, and  we assume that the assertions $\mathcal{A}^{(i)}_n$ hold for $i<r$. 
Let $\lambda,\mu\vdash n$ and let $(\nu,l)$ be  a pair satisfying the condition
\begin{equation}\label{condition}
    \nu\vdash n,\rk(\nu) < r \quad \text{ and } \quad n-l+\rk(\nu) = r.
\end{equation} 
Then we have that 
\begin{equation}\label{eq system}
 P^{(r)}_{\lambda,\mu,\nu,l}:=\sum_{\rk(\kappa)=r} c^\lambda_{\mu,\kappa}c^\kappa_{\nu,l}   
 \end{equation}
is an integer polynomial in $b$.
\begin{proof}
Note that with the conditions of the proposition, the right hand-side $\sum_{\theta\vdash n} c^\lambda_{\theta,l}c^\theta_{\mu,\nu}$ in \Cref{eq prop mult}  is an integer polynomial in $b$ (we use the induction hypothesis and \Cref{thm mar}). This implies that the left hand-side $\sum_{\kappa\vdash n}c^\lambda_{\mu,\kappa}c^\kappa_{\nu,l}$ in \Cref{eq prop mult} is an integer polynomial in $b$. We conclude using the two following facts: 
\begin{itemize}
    \item if $\rk(\kappa)>r$ then $c^\kappa_{\nu,l}=0$. Indeed, from \Cref{lem bounddeg}, we get that $$deg_b(c^\kappa_{\nu,l})\leq n-l+\rk(\nu)-\rk(\kappa)=r-\rk(\kappa)<0.$$
    \item if $\rk(\kappa)<r$ then  we know that $c^\lambda_{\mu,\kappa}$ is an integer polynomial from $\mathcal{A}^{\left(\rk(\kappa)\right)}_n$.\qedhere
    \end{itemize}
\end{proof}
\end{lem} 

 For fixed $\lambda,\mu\vdash n$ and  $r<n$, one can note that we get from the previous lemma more equations of type $\eqref{eq system}$  than variables $c^\lambda_{\mu,\kappa}$, where $\rk(\kappa)=r$. In order to obtain a square system, we consider equations $\eqref{eq system}$ indexed by partitions $(\nu,l)$ satisfying the following condition that refines condition \eqref{condition}: \begin{equation}\label{condition 2}
     (\nu,l)=(\pi\cup1^{n-r},l), \text{ where } \pi\vdash r \text{ and } n-l+\rk(\pi)=r.
 \end{equation}

We denote by $\mathcal{S}^{(r)}_{\lambda,\mu}$ the linear system obtained by taking the equations $\eqref{eq system}$ for $(\nu,l)$ satisfying condition \eqref{condition 2}, and we denote by $\mathcal{Q}^{(r)}_n$ the matrix associated to this system. In other terms $\mathcal{Q}^{(r)}_n=(c^\kappa_{\nu,l})$ where indices $\kappa$ of columns are partitions of $n$ of rank $r$, and indices of rows are pairs $(\nu,l)$ satisfying the condition \eqref{condition 2}.
Note that this matrix is independent from $\lambda$ and $\mu$. 
In the case $2r\leq n$, one can see that the system $\mathcal{S}^{(r)}_{\lambda,\mu}$ is a square system and that $\mathcal Q_n^{(r)}$ is the matrix $\mathcal Q^{(r)}$ defined in \cref{sec top coef}. The situation in the case $2r>n$ is more intricate. In general, we have the following proposition:

\begin{prop}\label{prop Qnr}
For every $1\leq r<n$, the matrix $\mathcal{Q}^{(r)}_n$ is a submatrix of $\mathcal{Q}^{(r)}$ defined in \Cref{sec top coef}, obtained by erasing only columns. More precisely, $\mathcal{Q}^{(r)}_n=(t^\rho_\pi)$, where the rows index $\pi$ is a partition of $r$ and the columns index $\rho$ is a partition of $r$ such that $\ell(\rho)\leq n-r.$
\begin{proof}
We have the following bijection
\begin{align*}\label{bijection}
 \left\{\kappa \text{ such that  } \kappa\vdash n \text{ and } \rk(\kappa) =r\right\} &\xrightarrow[\hspace{15pt}]{\sim} \left\{\rho \text{ such that } \rho\vdash r \text{ and } \ell(\rho)\leq n-r\right\}, \\
  \kappa&\longmapsto \kappa-\mathbf{1}, \\
  \rho\oplus1^{n-r} & \, \text{\reflectbox{$\longmapsto$}} \, \rho,
\end{align*}
Recall that $\tc^\rho_\pi=c^{\kappa}_{\pi\cup1^{n-r},n-r+\rk(\pi)}$, where $\kappa=\rho\oplus 1^{n-r}$ (see \Cref{def top coefficients}). This concludes the proof.
\end{proof}
\end{prop}

\noindent We now prove \Cref{thm integrality}.
\begin{proof}[Proof of \cref{thm integrality}]
We prove $\mathcal{A}_{n}^{(r)}$ by induction on $r$.
 For $r=0$, the only partition of rank $0$ is $\kappa=[1^n]$ and we know that $c^\lambda_{\mu,[1^n]}=\delta_{\lambda,\mu}$  for all partitions $\lambda,\mu$, where $\delta_{\lambda,\mu}$ is the Kronecker delta (see \cite[Lemma 3.3]{GJ96b}).
 
  Now we fix $r>0$ and we assume that $\mathcal{A}_{n}^{(j)}$ holds for each $j\leq r-1$. We fix two partitions $\lambda,\mu\vdash n\geq 1$, and we consider the system $\mathcal{S}^{(r)}_{\lambda,\mu}$. It can be written as follows:
$\mathcal{Q}^{(r)}_n X^{(r)}_{\lambda,\mu}=Y_{\lambda,\mu}^{(r)},$
where $Y_{\lambda,\mu}$ is the column vector containing the polynomials $P^{(r)}_{\lambda,\mu,\nu,l}$ for $(\nu,l)$ satisfying \eqref{condition 2}, and $X^{(r)}_{\lambda,\mu}$ is the column vector containing $c^\lambda_{\mu,\kappa}$ for $\kappa\vdash n$ of rank $r$. 
We denote the column vector $\widetilde X^{(r)}_{\lambda,\mu}:=(x^\lambda_{\mu,\rho})$ for $\rho\vdash r$, where 
\[
x^\lambda_{\mu,\rho}:= \begin{cases}
    c^\lambda_{\mu,\rho\oplus1^{n-r}} &\text{if } \ell(\rho)\leq n-r, \\
    0 & \text{otherwise.}
\end{cases}
\]
The system $\mathcal{S}^{(r)}_{\lambda,\mu}$ can be rewritten as follows:
$\mathcal{Q}^{(r)}\widetilde X^{(r)}_{\lambda,\mu}=Y^{(r)}_{\lambda,\mu}.$
But we know from \Cref{thm Qinv} that $\mathcal{Q}^{(r)}$ is invertible in $\mathbb{Z},$ and since the entries of $Y_{\lambda,\mu}$ are integer polynomials in $b$ (see \Cref{lem linearsystem}), we deduce that this is also the case for the entries of $\widetilde X^{(r)}_{\lambda,\mu}$. Hence, the coefficients $c^\lambda_{\mu,\kappa}$ are integer polynomials in $b$, when the partition $\kappa$ has rank $r$. This gives the assertion  $\mathcal{A}_{n}^{(r)}$.
\end{proof}

\begin{rmq}\label{rmq eqsystem}
Note that the previous proof implies that \Cref{eq prop mult} allows to recover the coefficients $c^\lambda_{\mu,\nu}$ form their marginal sums.
More precisely, if we have a family $(y^\lambda_{\mu,\nu})_{\lambda,\mu,\nu\vdash n}$ of rational functions in $b$ indexed by partitions of size $n$,  satisfying 
\[
    y^\lambda_{\mu,[1^n]}=\delta_{\lambda,\mu}
    \quad \text{ and } \quad
    \sum_{\kappa\vdash n} y^\lambda_{\mu,\kappa}c^\kappa_{\nu,l}=\sum_{\theta\vdash n} c^\lambda_{\theta,l} y^\theta_{\mu,\nu},
\]
then we have that $y^\lambda_{\mu,\nu}=c^\lambda_{\mu,\nu}$ for every partitions $\lambda,\mu,\nu\vdash n$.
\end{rmq}


\section{Graded Farahat--Higman Algebra}\label{sec FHA}

In this section we explain the main steps of the proof of \Cref{thm Qinv}. The main idea is to see the matrix $\mathcal{Q}^{(r)}$ as a change-of-basis matrix in the Farahat--Higman algebra.

If $\sigma$ is a permutation of cyclic type $\lambda$, we define its \textit{reduced cyclic type} as the partition $\lambda-\mathbf{ 1}$ (see \cite{MN13}). Hence if $\sigma\in \mathfrak S_n\subset \mathfrak S_{n+1} \cdots$, the reduced cyclic type of $\sigma$ does not depend on $n$. 
For every partition $\lambda$, we define $C_\lambda(n)\in \mathbb Z\mathfrak{S}_n$ as the sum of all permutations in $\mathfrak S_n$ of reduced cyclic type $\lambda$. Note that $C_\lambda(n)=0$ if $|\lambda|+\ell(\lambda)> n$.
Hence, for every $n\geq0$, the family $(C_\lambda(n))_{|\lambda|+\ell(\lambda)\leq n}$ form a basis of the center of the group algebra of $\mathfrak S_n$:
$$Z(\mathbb Z \mathfrak S_n)=\Span_\mathbb Z \{C_\lambda(n), |\lambda|+\ell(\lambda)\leq n\}.$$

\noindent The multiplication in this algebra is given by 

\begin{equation}\label{eq strcuture coef}
    C_\lambda(n) C_\mu(n)=\sum_{|\kappa|+\ell(\kappa)\leq n } \rho^\kappa_{\lambda,\mu}(n) C_\kappa(n),
\end{equation} 
for some structure coefficients $\rho^\kappa_{\lambda,\mu}(n)$. The latter are linked to the coefficients $c^\lambda_{\mu,\nu}$ as follows (see \cite[Proposition 3.1]{GJ96b}): 
 \begin{equation}\label{eq structure coefficients}
  \rho^\kappa_{\lambda,\mu}(n)= \begin{cases}
     c^{\kappa\oplus 1^{n-|\kappa|}}_{\lambda\oplus 1^{n-|\lambda|},\mu\oplus 1^{n-|\mu|}}(0)  & \text{if } \max\left(|\lambda|+\ell(\lambda),|\mu|+\ell(\mu),|\kappa|+\ell(\kappa)\right)\leq n ,\\
      0 & \text{otherwise.} 
  \end{cases}
 \end{equation}
The following proposition is due to Farahat and Higman.
\begin{prop}[\cite{FH59}]\label{prop FH}
The structure coefficients $\rho^\kappa_{\lambda,\mu}$ satisfy the following properties:
\begin{enumerate}
    \item $\rho^\kappa_{\lambda,\mu}=0$ if $|\kappa|>|\lambda|+|\mu|.$
    \item $\rho^\kappa_{\lambda,\mu}$ is independent from $n$ if $|\kappa|=|\lambda|+|\mu|.$
    \item $\rho^\kappa_{\lambda,\mu}$ is a polynomial in $n$ if $|\kappa|<|\lambda|+|\mu|.$
\end{enumerate}
\end{prop}
We are here interested in the structure coefficients $\rho^{\kappa}_{\lambda,\mu}$ in the case $|\kappa|=|\lambda|+|\mu|$, these coefficients are called the \textit{top connection coefficients} of the Farahat--Higman algebra.
To study these coefficients, we consider the graded algebra $\Z_n$ associated to $Z(\mathbb Z\mathfrak S_n)$ with respect to the filtration $\deg(C_\lambda(n))=|\lambda|.$
We denote by $\mathfrak c_\lambda(n)$ the image of $C_\lambda(n)$ in $\Z_n.$
Concretely,
$\Z_n=\bigoplus_{1\leq r\leq n-1}\Z^{(r)}_n,$
where $\Z_n^{(r)}:=\Span_\mathbb{Z}\left\{\cf_\lambda(n) : \lambda \vdash r\text{ and }\ell(\lambda)\leq n-r\right\}$, and  the multiplication in $\Z_n$ is defined by
\[
\cf_\lambda(n) \cf_\mu(n)=\sum_{\kappa\vdash |\lambda|+|\mu|}\rho^{\kappa}_{\lambda,\mu}(n)\cf_\kappa(n)=\sum_{\kappa\vdash |\lambda|+|\mu|}c^{\kappa\oplus 1^{n-|\kappa|}}_{\lambda\oplus 1^{n-|\lambda|},\mu\oplus 1^{n-|\mu|}}(0)\cf_\kappa(n).
\]
Note that compared to \Cref{eq strcuture coef}, we keep only the top degree terms.
The graded algebra $\Z_n$ comes with a linear isomorphism $\phi_n \colon Z(\mathbb Z\mathfrak S_n)\xrightarrow[]{\sim}\Z_n,$ that sends $C_\lambda(n)$ to $\cf_\lambda(n)$ (which is obviously not an algebra morphism). 
 Since the structure coefficients in $\Z_n$ are independent from $n$ (see \cref{prop FH} item 2), we can define a family of $\mathbb Z$-algebra morphisms:
\begin{align*}
\psi_n \colon \Z_{n+1}\longrightarrow &\Z_n \\
\cf_\lambda(n+1)\longmapsto & \begin{cases}
     \cf_\lambda(n)& \text{if }|\lambda|+\ell(\lambda)\leq n,  \\
     0& \text{otherwise.}
\end{cases}
\end{align*}
Let $\Z_\infty:=\varprojlim \Z_n$ be the projective limit of the $\Z_n$'s, and let the limit $\cf _\lambda:=\varprojlim \cf_\lambda(n)$ in $\Z_\infty$.
We also define $\mathcal{Z}_\infty^{(r)}:=\Span _\mathbb Z\{\cf_\lambda : \lambda \vdash r\}$, hence $\Z_\infty=\bigoplus_{r\geq 1}\Z^{(r)}_\infty$ (see \cite[Example 24, page 131]{Mac} for further details about the construction of the algebra $\Z_\infty$).  

\noindent For every $r \geq 1$, we set 
$\ff_r(n):=\sum_{\lambda\vdash r}\cf_\lambda(n),$
and for every partition $\mu$,
$\ff_\mu(n):=\prod_i\ff_{\mu_i}(n).$
We also define  
$\mathfrak g_\nu(n):=\cf_{\nu-\mathbf{1}}(n)\ff_{\ell(\nu)}(n)$, for every partition $\nu$.
Note that $$\deg(\ff_\nu(n))=\deg(\gf_\nu(n))=|\nu|.$$ Finally we define the limits $\ff_\mu:=\varprojlim \ff_\mu(n)$ and $\gf_\nu:=\varprojlim \gf_\nu(n)$ in $\Z_\infty.$
We have the following theorem due to Farahat and Higman.
\begin{thm}[\cite{FH59}]\label{thm FH}
For every $r\geq0$, $(\ff_\mu)_{\mu\vdash r}$ is a $\mathbb Z$-basis of $\Z_\infty^{(r)}$.
\end{thm}




The following proposition relates the matrix $\mathcal{Q}^{(r)}$ defined in \Cref{sec top coef} to the graded Farahat--Higman algebra $\Z_\infty$.
\begin{prop}\label{prop Q tr mat} For every partitions $\lambda,\mu\vdash r\geq 0$, we have $\tc^\lambda_\mu=[\cf_{\lambda}]\gf_{\mu}.$ In other terms, for every $r> 0$, the matrix $(\mathcal{Q}^{(r)})^{T}$ is the matrix of $(\gf_\mu)_{\mu \vdash r}$ in the basis $(\cf_\lambda)_{\lambda \vdash r}.$

\end{prop}

Hence, our goal is to prove the following theorem that implies \Cref{thm Qinv}:
\begin{thm}\label{thm g}
For every $r\geq0$, the family $(\gf_\mu)_{\mu\vdash r}$ is a $\mathbb Z$-basis for $\Z^{(r)}_\infty$.
\end{thm}
The proof of \Cref{thm g} involves studying triangularity properties of change-of-basis matrices in the algebra $\mathcal{Z}_\infty$. The indices of the different bases should be considered with some particular orders on partitions that are not detailed here. We explain here the different steps of the proof on examples for small values of $r$, the full proof is given in \cite{BD21b}.
The following diagram illustrates the different basis of $\mathcal{Z}^{(r)}_\infty$ involved in the proof of \Cref{thm g}, and the associated transition matrices.
\begin{center}


     
 \begin{tikzcd}    
 
 (\cf_\lambda)_{\lambda\vdash r}\arrow[dd,swap,"\mathcal{M}^{(r)}"] \ar[ddrr,bend right=10,"\mathcal{L}^{(r)}" near end]  &&(\gf_\lambda)_{\lambda\vdash r}\arrow[ll,swap,"{(Q^{(r)})^T}"]  \arrow[lldd,"\mathcal{N}^{(r)}" near start,bend right=25]\\
 \\
   (\ff_\lambda)_{\lambda\vdash r}    &&(\mf_\lambda)_{\lambda\vdash r}\arrow{ll}{\mathcal{U}^{(r)}}\\
 \end{tikzcd}
 \end{center}

In order to prove that $(\gf_\lambda)$ is a $\mathbb{Z}$ basis of $\Z_\infty$, we consider its matrix $\mathcal N$ in the basis $(\ff_\lambda)$. With elementary manipulations of the definitions, we can see that this matrix is block upper triangular, when the partitions indexing the bases are considered with some particular orders.
\begin{exe}\label{ex N}
We give here the matrix $\mathcal{N}^{(r)}$ for $r=5$ (the diagonal blocks are colored in gray).
\definecolor{mygray}{gray}{0.8}
\[
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
  \ff\backslash \gf  & [1^5]  & [2,1^3] & [2^2,1] & [3,1^2] &  [3,2] &  [4,1]   & [5]\\ \hline
     [5]    & \cellcolor{mygray}1& 0 & 0& 0& 0 &  0 & 0 \\ \hline
     [4,1]  &  & \cellcolor{mygray}1 & 0& 0&  0& 0 & -4\\ \hline
     [3,2]  &  &   &\cellcolor{mygray} 3 &\cellcolor{mygray}-1&-12& 3 &  0\\ \hline
     [3,1^2]&  &   &\cellcolor{mygray} -2&\cellcolor{mygray} 1&  0&  0 &  4 \\ \hline
     [2^2,1]&  &   &  &  &\cellcolor{mygray} 10&\cellcolor{mygray}-3& 2 \\ \hline
     [2,1^3]&  &   &  &  & \cellcolor{mygray}-3&\cellcolor{mygray}1 & -4\\ \hline
     [1^5]  &  &   &  &  &   &  & \cellcolor{mygray} 1\\ \hline
\end{array}
\]
\end{exe}
We need to prove that each one of the diagonal blocks of this matrix has determinant $\pm 1$. To this purpose, we prove that these diagonal blocks are South-East blocks of the matrix $\mathcal M^{(i)}$, the matrix of $(\cf_\lambda)_{\lambda\vdash i}$ in $(\ff_\lambda)_{\lambda\vdash i}$, where $i\leq r$. 
\begin{exe}\label{Ex M}
For $r=3$, 
\[
    \text{$\mathcal{M}^{(3)}$ is given by } \;
\begin{array}{|c|c|c|c|} \hline
     \ff \backslash \cf& [1^3] & [2,1] &[3] \\\hline
     [3]  & 10  & -12 &  3 \\\hline
     [2,1] & -7 & 10 &  -3 \\\hline
     [1^3] & 2 & -3 & 1  \\\hline
\end{array}
\; \text{ and $\mathcal{M}^{(2)}$ by } \;
\begin{array}{|c|c|c|} \hline
     \ff\backslash \cf & [1^2] &[2] \\\hline
     [2]  & 3 &  -1 \\\hline
     [1^2]  & -2 & 1  \\\hline
\end{array}.
\]
Note that the third diagonal block of the matrix $\mathcal{N}^{(3)}$ given in \Cref{ex N} is equal to the matrix $\mathcal{M}^{(2)}$ and its fourth diagonal block is a South-East diagonal block of  $\mathcal{M}^{(3)}$.
\end{exe}
We need to show that the East-South blocks of $\mathcal{M}^{(r)}$ have determinant 1. We show that the matrix $\mathcal M^{(r)}$ has a decomposition $\mathcal M^{(r)}=\mathcal{U}^{(r)}\mathcal{L}^{(r)}$ where $\mathcal{U}^{(r)}$ (respectively $\mathcal{L}^{(r)}$) is an upper (respectively lower) triangular matrix, with coefficients equal to 1 on the diagonal. This decomposition is obtained by considering an intermediate basis $(\mf_\lambda)$, defined as the evaluation of the monomial symmetric functions in the Jucys--Murphy elements. Indeed, this basis has the property that its transition matrices to both bases $(\cf_\lambda)$ and $(\ff_\lambda)$ are triangular (we use a result of Matsumoto and Novak \cite{MN13} and some basic properties on symmetric functions). Finally, we note that this decomposition of the matrix $\mathcal{M}^{(r)}$ induces a similar decomposition for every one of its South-East block, and hence these blocks have determinant 1.

\begin{exe}
For $r=3$, we have the decomposition $\mathcal{M}^{(3)}=\mathcal{U}^{(3)}\mathcal{L}^{(3)},$ where
\[
\mathcal{U}^{(3)} \text{ is given by } \;
    \begin{array}{|c|c|c|c|} \hline
     \ff \backslash \mf &  [1^3] & [2,1] &[3] \\\hline
     [3]  & 1  & -3 &  3 \\\hline
     [2,1] & 0 & 1  &  -3 \\\hline
     [1^3] & 0 & 0 & 1  \\\hline
\end{array}
\; \text{ and $\mathcal{L}^{(3)}$ by } \;
\begin{array}{|c|c|c|c|} \hline
     \mf \backslash \cf &  [1^3] & [2,1] &[3] \\\hline
     [3]  & 1  & 0 & 0  \\\hline
     [2,1] & -1 & 1  &  0 \\\hline
     [1^3] & 2 & -3 & 1  \\\hline
\end{array}.
\]
\end{exe}

\acknowledgements{The author would like to thank his advisors Valentin Féray and Guillaume Chapuy for many interesting discussions and for reviewing this paper several times.
He also thanks Guillaume Chapuy and Maciej Do\l{}{\k{e}}ga for suggesting to consider the multiplicativity property in order to deduce properties of the coefficients $c^\lambda_{\mu,\nu}$.

This is an extended abstract of \texorpdfstring{\cite{BD21b}}{}.}

                                                                                                                                                                                                                                                                                                
\printbibliography
\end{document}

                                                                                                                                                                                                                                                                                                                  

                                                                                                                                                                                                                                                
