Asymptotic free independence and entry permutations for Gaussian random matrices.
Part II: infinitesimal freeness

Mihai Popa Department of Mathematics
University of Texas at San Antonio
One UTSA Circle San Antonio
Texas 78249, USA
and “Simon Stoilow” Institute of Mathematics of the Romanian Academy
P.O. Box 1-764
014700 Bucharest, Romania [email protected] , Kamil Szpojankowski Wydział Matematyki i Nauk Informacyjnych
Politechnika Warszawska
ul. Koszykowa 75
00-662 Warszawa, Poland. [email protected] and Pei-Lun Tseng Department of Mathematics
New York University Abu Dhabi
Saadiyat Marina District, Abu Dhabi, United Arab Emirates [email protected]

Abstract.

We study asymptotic infinitesimal distributions of Gaussian Unitary Ensembles with permuted entries. We show that for a uniformly random permutation the asymptotically permuted GUE matrix has a null infinitesimal distribution. Moreover, we show that asymptotically different permutations of the same GUE matrix are infinitesimally free. Besides this we study a particular example of entry permutation - the transpose, and we show that while a GUE matrix is asymptotically free from its transpose it is not infinitesimally free from it.

KSz: This research was funded in part by National Science Centre, Poland WEAVE-UNISONO grant BOOMER 2022/04/Y/ST1/00008.
For the purpose of Open Access, the authors have applied a CC-BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission.

1. Introduction

Free probability introduced by D. Voiculescu [28, 30] is a non–commutative analogue of classical probability theory, where classical random variables are replaced by non–commutative operators. This theory was introduced in connection to some fundamental problems from the theory of operator algebras (such as the Free Group Factors isomorphism problem), however very quickly (see [29]) it was noticed that the novel theory has deep connections with the random matrix theory. Since then, the connections between free probability and random matrices have become a very active field with many advances in recent years (see [15, 3, 4]). A rough explanation of the phenomenon behind is as follows – big unitarily invariant and independent random matrices are asymptotically free. By this we mean that for two sequences of random matrices the quantity $\tfrac{1}{N}E\left(\textrm{Tr}(P(A_{N},B_{N}))\right)$ , for a non-commutative polynomial $P$ converges, as matrix size $N$ goes to infinity, to $\varphi\left(P(a,b)\right)$ where $a,b$ are free random variables with respect to $\varphi$ , and $a,b$ have distributions equal to the weak limits of the expected empirical eigenvalue distributions of $A_{N}$ and $B_{N}$ respectively.

In recent years some attention was given to $1/N$ correction in the convergence above (see e.g. [25]), i.e. to look not only at $\varphi$ but also consider another functional $\varphi^{\prime}$ which satisfies

(1)

\displaystyle\frac{1}{N}E\left(\textrm{Tr}(P(A_{N},B_{N}))\right)=\varphi(P(a,b))+\frac{1}{N}\varphi^{\prime}(P(a,b))+o\left(\frac{1}{N}\right)\mbox{ as }N\to\infty.

The special interest from non-commutative probability point of view is the case when $a,b$ are infinitesimally free with respect to the pair of functionals $\left(\varphi,\varphi^{\prime}\right)$ (we state the precise definition of infinitesimal freeness in the next section). This notion, under in the framework free probability of type B, was introduced in [6] and the infinitesimal freeness interpretation was found in [5], see also [11] for combinatorial developments related to infinitesimal freeness. As mentioned above asymptotic freeness connects directly to random matrix theory and several classes of random matrices have been proved to be asymptotically infinitesimally free [17, 8, 23] and many related properties have been discovered [11, 26, 27, 7, 10, 12].

Another recent development in random matrix theory is that freeness emerges also when one looks at different entry permutations of a given random matrix. In order to explain this phenomenon let us fix some notation. For any $N\geq 1$ let $A_{N}=(a_{i,j})$ be an $N\times N$ matrix and $\sigma_{N}:[N]^{2}\to[N]^{2}$ be a bijection; that is, $\sigma_{N}$ is a permutation on $[N]^{2}:=\{1,\dots,N\}^{2}$ . By $A_{N}^{\sigma_{N}}$ we denote the permuted matrix, that is we have $[A_{N}^{\sigma_{N}}]_{i,j}=a_{\sigma(i,j)}$ . Among permutations there are many interesting mappings such as partial transposes, which are of interest in quantum information theory [1, 2, 13], and the mixed map in quantum physics [9, 16]. The connection between matrix permutation and free probability were also explored in [18, 19, 20, 24, 22, 21]. In [24] the author showed that for a given sequence of Gaussian random matrices $(G_{N})_{N}$ , and two sequences of permutations of these matrices $\left(G^{\sigma_{N}}_{N}\right)_{N}$ and $\left(G^{\tau_{N}}_{N}\right)_{N}$ the permuted matrices are asymptotically (as $N\to\infty$ ) circular and asymptotically free, whenever pairs of permutation sequences $(\sigma_{N})_{N}$ and $(\tau_{N})_{N}$ satisfy certain conditions. Moreover, following these developments in [22], the authors proved that such conditions occurs with probability one, which means that $G^{\sigma_{N}}_{N}$ and $G^{\tau_{N}}_{N}$ are asymptotically circular and asymptotically free for almost all pairs of independent permutation sequences $(\sigma_{N})_{N}$ and $(\tau_{N})_{N}$ .

In the present paper we show that the framework described above gives not only the asymptotic freeness but also asymptotic infinitesimal freeness. More precisely we show that:

•

Asymptotically the infinitesimal distribution of a randomly permuted (with uniformly chosen permutation of entries) growing GUE matrix is zero.
•

Independent permutations of a sequence of growing GUE matrices are asymptotically infinitesimally free.
•

a GUE matrix and its transpose are not asymptotically infinitesimally free, even though they are asymptotically free [18], but we can explicitly compute their joint infinitesimal distribution.

Moreover we show that the phenomenon described above does not hold for any sequence of matrix permutations, namely we show that the sequence of GUE matrices is not asymptotically infinitesimally free from its transposes, although asymptotic freeness takes place as it was shown in [18].

The paper is organized as follows. We review the framework and properties of infinitesimal freeness in Section 2. In addition, some notation and a basic lemma on permuted Gaussian matrices are also included in Section 2. The infinitesimal distribution of the generic permuted Gaussian matrix is considered in Section 3.

In Section 4, we consider pairs of independent sequences of random permutations $(\sigma_{N})_{N}$ and $(\tau_{N})_{N}$ , such that that $\sigma_{N}$ and $\tau_{N}$ are uniformly distributed random permutations from $S([N]^{2})$ for each $N$ . We discuss the joint infinitesimal distribution of $G_{N},G_{N}^{\sigma_{N}},$ and $G_{N}^{\tau_{N}}$ . From [22] and [24] one can deduce that almost surely $G_{N}^{\sigma_{N}}$ and $G_{N}^{\tau_{N}}$ are asymptotically circular and asymptotically free. Here we show that that they have zero infinitesimal distribution. Moreover we prove that $\{G_{N},G_{N}^{\sigma_{N}},G_{N}^{\tau_{N}}\}$ are asymptotically infinitesimally free.

Recall that Gaussian random matrix $G_{N}$ and its transpose $G_{N}^{\top}$ are asymptotically free [18]. However, $G_{N}$ and its transpose $G_{N}^{\top}$ is not asymptotically infinitesimally free. Indeed, we find the asymptotic joint infinitesimal law of $G_{N}$ and $G_{N}^{\top}$ in Section 5. More precisely, we show that the asymptotic values (as $N\rightarrow\infty$ ) of the infinitesimally free joint cumulants of $G_{N}$ and $G_{N}^{\top}$ are (here each $\varepsilon_{j}$ is either the identity or the matrix transpose):

\displaystyle\lim_{N\rightarrow\infty}\kappa^{\prime}_{p}(G_{N}^{\varepsilon_{1}},G_{N}^{\varepsilon_{2}},\dots,G_{N}^{\varepsilon_{p}})=\left\{\begin{array}[]{ll}1&\textrm{ if }p=2m,\varepsilon_{1}\neq\varepsilon_{m+1},\varepsilon_{m}\neq\varepsilon_{2m},\\ &\textrm{ and }\varepsilon_{s}\neq\varepsilon_{2m+1-s}\textrm{ for }s=2,\dots,m-1\\ 0&\textrm{ otherwise. }\end{array}\right.

Which shows that $G_{N}$ and $G_{N}^{\top}$ are not asymptotically infinitesimally free, but have very regular joint infinitesimal free cumulants.

2. Preliminaries

In this section, we first introduce the framework of infinitesimal freeness, then we review the notion of Gaussian matrices and establish the notation that we use for studying permuted Gaussian matrices.

2.1. Infinitesimal Free Probability

Let us begin by recalling some notions in free probability theory. We say that $(\mathcal{A},\varphi)$ is a non-commutative probability space (ncps for short) whenever $\mathcal{A}$ is a unital $*$ -algebra over $\mathbb{C}$ , and $\varphi:\mathcal{A}\to\mathbb{C}$ is a linear functional such that $\varphi(1)=1$ and $\varphi(a^{*}a)\geq 0$ for all $a\in\mathcal{A}$ . We say unital subalgebras $\mathcal{A}_{1},\dots,\mathcal{A}_{s}$ are free if $a_{1},\dots,a_{n}\in\mathcal{A}$ with $\varphi(a_{j})=0$ for each $j=1,\dots,n$ and $a_{j}\in\mathcal{A}_{i_{j}}$ with $i_{1}\neq i_{2}\neq\cdots\neq i_{n-1}\neq i_{n}$ we have

\varphi(a_{1}\cdots a_{n})=0.

If $(\mathcal{A},\varphi)$ is a ncps with an additional linear functional $\varphi^{\prime}:\mathcal{A}\to\mathbb{C}$ such that $\varphi^{\prime}(1)=0$ and $\varphi^{\prime}(a^{*})=\overline{\varphi^{\prime}(a)}$ for all $a\in\mathcal{A}$ , then we call the triple $(\mathcal{A},\varphi,\varphi^{\prime})$ an infinitesimal probability space.

The natural framework of an infinitesimal probability space for algebras of random matrices was considered in [5, 25].

Denote by $\mathbb{C}\langle X_{1},\dots,X_{k}\rangle$ the complex unital algebra of polynomials in $k$ non-commuting indeterminates. Assume that $(A_{N}^{(1)},\dots,A_{N}^{(k)})_{N}$ is a sequence of $k$ -tuples of random matrices such that each $A_{N}^{(1)},\dots,A_{N}^{(k)}$ are $N\times N$ random matrices, and consider the sequence of linear maps $(\varphi_{N})_{N}$ on $\mathbb{C}\langle X_{1},\dots,X_{k}\rangle$ defined by

\varphi_{N}(P)=\frac{1}{N}(E\circ Tr)\left(P(A_{N}^{(1)},\dots,A_{N}^{(k)})\right).

We say that the sequence $(A_{N}^{(1)},\dots,A_{N}^{(k)})_{N}$ has asymptotic distribution if the limit $\displaystyle\varphi(P):=\lim_{N\to\infty}\varphi_{N}(P)$ exists for all $P\in\mathbb{C}\langle X_{1},\dots,X_{k}\rangle$ . Furthermore, if

\varphi^{\prime}(P):=\lim_{N\to\infty}N[\varphi_{N}(P)-\varphi(P)]

exists for all $P$ , then $\{A_{N}^{(1)},\dots,A_{N}^{(k)}\}$ is said to have the asymptotic infinitesimal distribution. We say that $\{A_{N}^{(1)},\dots,A_{N}^{(k)}\}$ are asymptotically infinitesimally free when asymptotically their joint moments with respect to to the pair of functionals $(\varphi,\varphi^{\prime})$ are calculated according to the rule defined below.

Definition 2.1.

Suppose that $(\mathcal{A},\varphi,\varphi^{\prime})$ is an infinitesimal probability space. We say that unital subalgebras $\mathcal{A}_{1},\dots,\mathcal{A}_{s}$ are infinitesimally free if for every $n$ and for all $a_{1},\dots,a_{n}\in\mathcal{A}$ with $\varphi(a_{j})=0$ for each $j=1,\dots,n$ and $a_{j}\in\mathcal{A}_{i_{j}}$ with $i_{1}\neq i_{2}\neq\cdots\neq i_{n-1}\neq i_{n}$ we have

	$\displaystyle\varphi(a_{1}\cdots a_{n})$	$\displaystyle=$	$\displaystyle 0;$
(2)		$\displaystyle\varphi^{\prime}(a_{1}\cdots a_{n})$	$\displaystyle=$	$\displaystyle\sum\limits_{j=1}^{n}\varphi^{\prime}(a_{j})\varphi(a_{1}\cdots a_{j-1}a_{j+1}\cdots a_{n}).$

It is easy to see that the condition (2.1) in the definition of infinitesimal freeness is equivalent to (see [11] for a detailed explanation)

	$\displaystyle\varphi^{\prime}(a_{1}\cdots a_{n})$
		$\displaystyle=$	$\displaystyle\left\{\begin{array}[]{lr}\varphi(a_{1}a_{n})\varphi(a_{2}a_{n-1})\cdots\varphi(a_{(n-1)/2}a_{(n+3)/2})\varphi^{\prime}(a_{(n+1)/2})\\ \ \mbox{if}\ n\ \mbox{is odd and}\ i_{1}=i_{n},i_{2}=i_{n-1}\dots,i_{(n-1)/2}=i_{(n+1)/2}\\ 0\ \mbox{otherwise}\end{array}.\right.$

Fix a unital algebra $\mathcal{A}$ and sequences of multilinear functionals $\{f_{n}:\mathcal{A}^{n}\to\mathbb{C}\}_{n\geq 1}$ and $\{f_{n}^{\prime}:\mathcal{A}^{n}\to\mathbb{C}\}_{n\geq 1}$ . For a given partition $\pi\in NC(n)$ , we define

f_{\pi}(a_{1},\dots,a_{n})=\prod_{V\in\pi}f_{|V|}(a_{1},\dots,a_{n}\mid V)

where $(a_{1},\dots,a_{n}|V)=(a_{i_{1}},\dots,a_{i_{s}})$ whenever $V=\{i_{1}<\cdots<i_{s}\}$ .

Moreover, we define $\partial f_{\pi}$ by

\partial f_{\pi}(a_{1},\dots,a_{n})=\sum_{V\in\pi}\partial f_{\pi,V}(a_{1},\dots,a_{n})

where

\partial f_{\pi,V}(a_{1},\dots,a_{n})=f^{\prime}_{|V|}(a_{1},\dots,a_{n}\mid V)\prod_{W\in\pi,\ W\neq V}f_{|W|}(a_{1},\dots,a_{n}\mid W).

Definition 2.2.

Let $(\mathcal{A},\varphi,\varphi^{\prime})$ be an infinitesimal probability space, the free cumulants $\{\kappa_{n}:\mathcal{A}^{n}\to\mathbb{C}\}_{n}$ and infinitesimal free cumulants $\{\kappa^{\prime}_{n}:\mathcal{A}^{n}\to\mathbb{C}\}_{n}$ are sequences of multilinear functionals are defined inductively via

	$\displaystyle\varphi(a_{1}\cdots a_{n})$	$\displaystyle=$	$\displaystyle\sum\limits_{\pi\in NC(n)}\kappa_{\pi}(a_{1},\dots,a_{n}),\text{ and }$
(4)		$\displaystyle\varphi^{\prime}(a_{1}\cdots a_{n})$	$\displaystyle=$	$\displaystyle\sum\limits_{\pi\in NC(n)}\partial\kappa_{\pi}(a_{1},\dots,a_{n}).$

In [11] the authors showed that the infinitesimal freeness can be characterized by the vanishing of $(\kappa_{n},\kappa_{n}^{\prime})_{n\geq 1}$ . For reader’s convenience we recall here the precise statement.

Theorem 2.3.

Suppose that $(\mathcal{A},\varphi,\varphi^{\prime})$ is an infinitesimal probability space, and $\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ are unital subalgebras. Then the following statement are equivalent.

(i)

$\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ are infinitesimally free;
(ii)

For each $s\geq 2$ and $i_{1},\dots,i_{s}\in[n]$ which are not all equal, and for $a_{1}\in\mathcal{A}_{i_{1}},\dots,a_{s}\in\mathcal{A}_{i_{s}}$ , we have

$\kappa_{s}(a_{1},\dots,a_{n})=\kappa^{\prime}_{s}(a_{1},\dots,a_{n})=0.$

2.2. Permutations for Gaussian Random Matrices

In this subsection we recall some notation and relevant facts about matrices with permuted entries. In particular we review results from [24] and [22] and we refer to these two papers for proofs.

Definition 2.4.

By an $N\times N$ Gaussian random matrix we will understand a matrix $G=[g_{ij}]_{1\leq i,j\leq N}$ whose entries satisfy the following conditions:

(i)

$g_{i,j}=\overline{g_{j,i}}$ for all $i,j\in[N]$ ;
(ii)

$\{g_{i,j}:1\leq i\leq j\leq N\}$ is a family of independent, identically distributed complex $($ if $i\neq j)$ or real $($ if $i=j)$ Gaussian random variables of mean 0 and variance $\displaystyle\frac{1}{N}$ .

If $n$ is a positive integer, we shall denote by $[n]$ the ordered set $\{1,2,\dots,n\}$ . The set of pair partitions of $[n]$ is denoted by $P_{2}(n)$ . In particular, if $n$ is odd, then $P_{2}(n)=\emptyset$ .

The set of all permutations of $[N]\times[N]$ will be denoted by $\mathcal{S}([N]^{2})$ . For $(i,j)\in[N]\times[N]$ , we denote by $\top$ the transpose, i.e. we have $\top(i,j)=(j,i)$ .

In addition, for a given $\sigma\in\mathcal{S}([N]^{2})$ , we define

\sigma(A)=\{\sigma(i,j):(i,j)\in A\}\text{ for }A\subset[N]\times[N].

Recall that for an $N\times N$ Gaussian random matrix $G_{N}$ and $\sigma\in\mathcal{S}([N]^{2})$ , we denote $G_{N}^{\sigma}$ to be the random matrix whose $(i,j)$ -entry equals the $\sigma(i,j)$ -entry of $G_{N}$ ; i.e.

[G_{N}^{\sigma}]_{i,j}=g_{\sigma(i,j)}.

Assume that for each positive integer $N$ and each $k=1,2,\dots,m$ , $\sigma_{k,N}$ is a permutation from $\mathcal{S}([N]^{2})$ . With these notations, we have that

	$\displaystyle E\circ\mathrm{tr}\Big{(}G_{N}^{\sigma_{1,N}}\cdot G_{N}^{\sigma_{2,N}}\cdots G_{N}^{\sigma_{m,N}}\Big{)}$	$\displaystyle=$
	$\displaystyle\sum_{1\leq i_{1},\dots,i_{m}\leq N}$	$\displaystyle\frac{1}{N}E\big{(}[G_{N}^{\sigma_{1,N}}]_{i_{1},i_{2}}\cdot[G_{N}^{\sigma_{2,N}}]_{i_{2},i_{3}}\cdots[G_{N}^{\sigma_{m,N}}]_{i_{m},i_{1}}\big{)}$

As shown in [24], using Wick’s formula (see [14]) for the right-hand side of the equation above, with the identification $i_{m+1}=i_{1}$ , we obtain

(5)

\displaystyle E\circ\mathrm{tr}\Big{(}G_{N}^{\sigma_{1,N}}\cdot G_{N}^{\sigma_{2,N}}\cdots G_{N}^{\sigma_{m,N}}\Big{)}=\sum_{\pi\in P_{2}(m)}\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)

where we use short-hand notation $\overrightarrow{\sigma_{N}}=(\sigma_{1,N},\sigma_{2,N},\dots,\sigma_{m,N})$ and

\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)=\frac{1}{N}\sum_{1\leq i_{1},\dots,i_{m}\leq N}\prod_{(k,l)\in\pi}E\big{(}[G_{N}^{\sigma_{k,N}}]_{i_{k},i_{k+1}}\cdot[G_{N}^{\sigma_{l,N}}]_{i_{l},i_{l+1}}\big{)}.

Moreover, since $G_{N}$ is Gaussian, $\displaystyle E\big{(}[G_{N}^{\sigma_{k,N}}]_{i_{k},i_{k+1}}\cdot[G_{N}^{\sigma_{l,N}}]_{i_{l},i_{l+1}}\big{)}=\frac{1}{N}\delta_{\sigma_{k,N}(i_{k},i_{k+1})}^{\top\circ\sigma_{l,N}(i_{l},i_{l+1})}.$ Since it is important to keep track of which indices are equal to each other, it is standard to encode this with pair partitions. Therefore for a given $\pi\in P_{2}(m)$ , we denote by $\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}$ such sequences of indices which respect $\overrightarrow{\sigma}_{N}$ and $\pi$ in the sense that they contribute in the sum above. To make the above precise we will view any pair partition as a permutation, where each block becomes a cycle, and we will write $\pi(k)$ , to mean the image of $k$ under the permutation (induced by) $\pi$ . With the identification $i_{m+1}=i_{1}$ we define

	$\displaystyle\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}=\big{\{}(i_{s},j_{s})_{s\in[m]}:\ j_{k}=i_{k+1}\textrm{ and }\sigma_{k,N}(i_{k},j_{k})=\top\circ$	$\displaystyle\sigma_{\pi(k),N}(i_{\pi(k)},j_{\pi(k)})$
		$\displaystyle\textrm{ \ \ \ \ \ for all }k\in[m]\big{\}}$

and

\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}=\log_{N}|\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}|-(\frac{m}{2}+1).

Then (5) can be rewritten as

E\circ\mathrm{tr}\Big{(}G_{N}^{\sigma_{1,N}}\cdot G_{N}^{\sigma_{2,N}}\cdots G_{N}^{\sigma_{m,N}}\Big{)}=\sum_{\pi\in P_{2}(m)}|\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}|N^{-(\frac{m}{2}+1)}=\sum_{\pi\in P_{2}(m)}N^{\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}}.

For $B=\{\beta_{1},\beta_{2},\dots,\beta_{r}\}$ an ordered subset of $[m]$ and $(i_{s},j_{s})_{s\in[m]}\in N^{2m}$ we will be interested in subsequences $(i_{s},j_{s})_{s\in B}$ i.e. $(i_{\beta_{1}},j_{\beta_{1}},\dots,i_{\beta_{r}},j_{\beta_{r}})$ which can be extended to an element from $\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}$ , thus we define

	$\displaystyle\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}(B)=\big{\{}(i_{s},j_{s})_{s\in B}:\ \textrm{ there exists some }$	$\displaystyle(i_{s},j_{s})_{s\in[m]\setminus B}$
		$\displaystyle\textrm{ such that }(i_{s},j_{s})_{s\in[m]}\in\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}\big{\}}$

and let

\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B)=\log_{N}|\mathcal{A}_{\pi,\overrightarrow{\sigma}_{N}}(B)|-|B|+\frac{1}{2}|B^{2}\,_{|\pi}|-1.

where $B^{2}\,_{|\pi}$ can be understand as the range of $\pi$ i.e. we have $B^{2}\,_{|\pi}=\{(k,l)\in B\times B:\ \pi(k)=l\}$ .

The following results are shown in [24] (see Lemmas 2.2 –2.4).

Lemma 2.5.

(i)

If $k\in B$ , then $\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B\cup\{k-1\})\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B)$ and
$\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B\cup\{k+1\})\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B)$ .

In particular, $\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B)\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}$ for all $B\subset[m]$ .
(ii)

If $k\in B$ , then $\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B\cup\{\pi(k)\})\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B).$
(iii)

If $\{k,\pi(k)\}\cap B=\emptyset$ and $\{k-1,k+1\}\subseteq B$ , then
$\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B\cup\{k\})\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}_{N}}(B)-1.$

2.3. Basic probabilistic tools

We will repeatedly use Borel–Cantelli lemma in order to prove almost sure convergence of some statistics of random uniform permutations. We show several similar lemmas, which nevertheless have substantially different proofs. We prove each lemma separately, in each case invoking the following basic fact.

Lemma 2.6.

Let $(X_{N})_{N}$ be a sequence of non-negative random variables, for $X_{N}\stackrel{{\scriptstyle 1}}{{\to}}0$ it suffices to show that for any $\varepsilon>0$ there exist $\delta>0$ and $C>0$ such that $\mathbb{P}(X_{N}>\varepsilon)\leq\tfrac{C}{N^{1+\delta}}$ .

3. The generic permuted Gaussian random matrix has zero infinitesimal distribution

As explained in the previous section, in order to understand the joint moments of a Gaussian matrix with permuted entries it suffices to understand $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)$ for any pairing $\pi$ . In this section we will consider random permutations, and we will consider asymptotic behaviour of $\mathcal{V}_{\overrightarrow{\sigma_{N}}}$ , where we assume that $(\sigma_{N})_{N}$ is a sequence of uniformly random permutations with $\sigma(N)\in\mathcal{S}([N]^{2})$ for each $N\geq 1$ . Note that in $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)$ we integrate with respect to the distribution of entries of the matrix, so the almost sure limits mentioned below are with respect to the sequence of random permutations only. Since a Gaussian matrix after a random permutation most likely is not self-adjoint we have to take care of complex-conjugate together with the matrix permutation. Observe that $(G^{\sigma})^{*}_{(i,j)}=\overline{G_{\sigma(j,i)}}$ and this is exactly the same as $G^{\top\circ\sigma_{N}\circ\top}_{(i,j)}$ , which motivates the notations we introduce below. The goal of this section is to prove the following theorem.

Theorem 3.1.

Let $\big{(}\sigma_{N}\big{)}_{N}$ be a sequence of uniformly random permutations from $\mathcal{S}([N]^{2})$ and $\varepsilon(1),\dots,\varepsilon(m)\in\{1,\ast\}$ . Define

\sigma_{k,N}=\left\{\begin{array}[]{ll}\sigma_{N}&\textrm{ if }\varepsilon(k)=1\\ \top\circ\sigma_{N}\circ\top&\textrm{ if }\varepsilon(k)=\ast.\end{array}\right.

With the notations from Section 2.2, almost surely we have that $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)=o(N^{-1})$ unless $\pi$ is non-crossing and $\varepsilon(k)\neq\varepsilon(\pi(k))$ for all $k\in[m]$ .

In order to prove Theorem 3.1 we need to establish several technical results.

Lemma 3.2.

Let $\big{(}\sigma_{N}\big{)}_{N}$ be a sequence of uniformly random permutations, with each $\sigma_{N}$ from $\mathcal{S}([N]^{2})$ . For any constant $\theta>0$ we have the following almost sure limits:

(i)

$\displaystyle\lim_{N\rightarrow\infty}N^{-(\frac{1}{2}+\theta)}\cdot\big{|}\{(i,j)\in[N]^{2}:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,i)\}\big{|}=0$
(ii)

$\displaystyle\lim_{N\rightarrow\infty}N^{-\theta}\cdot\sup_{1\leq i\leq N}\big{|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(i,j)\in\{\top\circ\sigma_{N}(j,k),\sigma_{N}\circ\top(j,k)\}\}\big{|}=0.$

Proof.

For part (i), for each $i,j\in[N]$ , denote by $I_{i,j}$ the random variable on $\mathcal{S}([N]^{2})$ given by $I_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(i,j)=\top\circ\sigma(j,i)\\ 0&\textrm{ if }\sigma(i,j)\neq\top\circ\sigma(j,i)\end{array}\right.$ and let $\displaystyle X_{N}=\sum_{i,j=1}^{N}I_{i,j}.$

Using Markov’s inequality, we have that $\displaystyle\mathbb{P}(N^{-(\frac{1}{2}+\theta)}X_{N}>\varepsilon)\leq\frac{\mathbb{E}(X_{N}^{2})}{\varepsilon^{2}N^{(1+2\theta)}}$ so from Lemma 2.6 it suffices to show that $\mathbb{E}(X_{N}^{2})$ is bounded.

Since $I_{i,j}=I_{j,i}=I^{2}_{i,j}$ , we have that

\displaystyle\mathbb{E}(X_{N}^{2})=\mathbb{E}\big{(}\big{(}\sum_{i,j=1}^{N}I_{i,j}\big{)}^{2}\big{)}=2\sum_{i,j=1}^{N}\mathbb{E}(I_{i,j})+\sum_{\begin{subarray}{c}1\leq i,j,k,l\leq N\\ (i,j)\notin\{(k,l),(l,k)\}\end{subarray}}\mathbb{E}(I_{i,j}I_{k,l}).

To estimate $\mathbb{E}(I_{i,j})$ , note that if $j\neq j$ and $I_{i,j}(\sigma)\neq 0$ the value of $\sigma(i,j)$ uniquely determines the value of $\sigma(j,i)$ ; there are $N^{2}$ possible choices for $\sigma(i,j)$ and hence $\sigma(j,i)$ and $(N^{2}-2)!$ possibilities for the rest of the values of $\sigma$ . For elements on the diagonal, i.e. when $i=j$ , we have that $I_{i,j}(\sigma)\neq 0$ if and only if $\sigma(j,i)$ is also on the diagonal. Therefore

\displaystyle\sum_{i,j=1}^{N}\mathbb{E}(I_{i,j})=\sum_{i\neq j}\mathbb{E}(I_{i,j})+\sum_{i}\mathbb{E}(I_{i,i})\leq 2{N\choose 2}\frac{N^{2}\cdot(N^{2}-2)!}{N^{2}!}+N\frac{1}{N}\xrightarrow[N\rightarrow\infty]{}2.

Similarly, if $(i,j)\notin\{(k,l),(l,k)\}$ , for $I_{i,j}(\sigma)I_{k,l}(\sigma)\neq 0$ there are $N^{2}$ possible choices for $\sigma(i,j)$ , each uniquely determining at most one possible choice for $\sigma(j,i)$ . Then there are $N^{2}-2$ possible choices for $\sigma(k,l)$ , each determining at most one possible choice for $\sigma(l,k)$ and $N^{2}-4$ possible choices for the rest of the values of the permutation $\sigma$ . Hence

\displaystyle\sum_{\begin{subarray}{c}1\leq i,j,k,l\leq N\\ (i,j)\notin\{(k,l),(l,k)\}\end{subarray}}\mathbb{E}(I_{i,j}I_{k,l})\leq N^{2}(N^{2}-2)\frac{N^{2}\cdot(N^{2}-2)\cdot(N^{2}-4)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

For part (ii) fix $\varepsilon>0$ and observe that using exchangeability of rows and subadditivity, we have that for any fixed $a\in[N]$

	$\displaystyle\mathbb{P}\big{(}\sup_{1\leq i\leq N}\big{\|}\{(j,k)\in[N]^{2}$	$\displaystyle:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}$
	$\displaystyle\leq$	$\displaystyle\sum_{i=1}^{N}\mathbb{P}\big{(}\big{\|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}$
	$\displaystyle=$	$\displaystyle N\cdot\mathbb{P}\big{(}\big{\|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(a,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}.$

Denoting $Y_{N}=\sum_{1\leq i,j\leq N}F_{i,j}$ where each $F_{i,j}$ the random variable on $\mathcal{S}([N]^{2})$ given by $F_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(a,i)=\top\circ\sigma(i,j)\\ 0&\textrm{ if }\sigma(a,i)\neq\top\circ\sigma(i,j)\end{array}\right.$ and applying Markov’s inequality we obtain

\displaystyle\mathbb{P}\big{(}\sup_{1\leq i\leq N}\big{|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,k)\}\big{|}>N^{\theta}\cdot\varepsilon\big{)}\leq N\frac{\mathbb{E}\big{(}Y_{N}^{K}\big{)}}{(N^{\theta}\varepsilon)^{K}},

for any positive integer $K$ , in particular for $K>\frac{3}{\theta}$ .

Since $F_{i,j}^{2}=F_{i,j}$ , we have that $\mathbb{E}\big{(}Y_{N}^{K}\big{)}=\displaystyle\sum_{s=1}^{K}\mathbb{E}\big{(}\sum F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\big{)}$ where the second sum goes over $\{(i_{1},j_{1},\dots,i_{s},j_{s})\in[N]^{2s}:\ (i_{1},j_{1}),\dots,(i_{s},j_{s})\textrm{ distinct}\}.$ So Lemma 2.6 implies that it suffices to show the uniform boundedness in $N$ of the expression $\displaystyle\mathbb{E}\big{(}\sum_{D}F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\big{)}$ where $s$ is some positive integer and

\displaystyle D=\{(i_{1},j_{1},\dots,i_{s},j_{s})\in[N]^{2s}:\ (i_{1},j_{1}),\dots,(i_{s},j_{s})\textrm{ distinct }\}.

We write D as a disjoint union $D=D_{1}\sqcup D_{2}$ , where

	$\displaystyle D_{1}$	$\displaystyle=\{(i_{1},j_{1},\dots,i_{s},j_{s})\in D:\ (i_{k},j_{k})=(a,a)\textrm{ for some }k\in[s]\}$
	$\displaystyle D_{2}$	$\displaystyle=\{(i_{1},j_{1},\dots,i_{s},j_{s})\in D:\ (i_{k},j_{k})\neq(a,a)\textrm{ for all }k\in[s]\}.$

$\bullet$

$(i_{1},j_{1},\ldots,i_{s},j_{s})\in D_{1}$ if there is $1\leq k\leq s$ such that $(i_{k},j_{k})=(a,a)$ (in particular, since the pairs of indices in $D$ are distinct, there can be at most one such $k$ ).
$\bullet$

$(i_{1},j_{1},\ldots,i_{s},j_{s})\in D_{2}$ if for all $1\leq k\leq s$ we have $(i_{k},j_{k})\neq(a,a)$ .

Under the condition $F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\neq 0$ , for each $(i_{1},j_{1},\ldots,i_{s},j_{s})\in D_{2}$ there are at most $\frac{N^{2}!}{(N^{2}-s)!}$ possible choices for the $s$ -tuple $(\sigma(a,i_{1})\dots,\sigma(a,i_{s}))$ each of them determining at most one possible choice for the $s$ -tuple $(\sigma(i_{1},j_{1})\dots,\sigma(i_{s},j_{s}))$ and $(N^{2}-2s)!$ possible choices for the rest of values of $\sigma$ . Furthermore, for each $(i_{1},j_{1},\ldots,i_{s},j_{s})\in D_{1}$ there are at most $N$ choices for the value of $\sigma(a,a)$ and at most $\frac{(N^{2}-1)!}{(N^{2}-s)!}$ for the values of all other $\sigma(a,i_{k})$ such that $F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\neq 0$ ; each such choice determines at most one possible choice for $(\sigma(i_{1},j_{1})\dots,\sigma(i_{s},j_{s}))$ and at most $(N^{2}-2s)!$ possible choices for the rest of values of $\sigma$ . Also, since $(i_{k},j_{k})=(a,a)$ for a unique $k\in[s]$ , we have at most $N^{2s-1}$ choices for the $2s$ -tuple $(i_{1},j_{1},\ldots,i_{s},j_{s})\in D_{2}$ .

Therefore

	$\displaystyle\mathbb{E}\big{(}\sum_{D}F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\big{)}\leq$	$\displaystyle N^{2s}\cdot\frac{1}{N^{2}!}\cdot\frac{N^{2}!}{(N^{2}-s)!}\cdot 1\cdot(N^{2}-2s)!$
	$\displaystyle+$	$\displaystyle N^{2s-1}\cdot\frac{1}{N^{2}!}\cdot\frac{N(N^{2}-1)!}{(N^{2}-s)!}\cdot 1\cdot(N^{2}-2s)!\xrightarrow[N\rightarrow\infty]{}1,$

where $N^{2s}$ comes from estimating the number of terms in the sum, hence the conclusion. The argument of the case $\sigma_{N}(i.j)=\sigma_{N}\circ\top(j,k)$ is similar. ∎

Lemma 3.3.

For each positive integer $N$ let $\phi_{N}$ be a fixed map from $[N]\times[N]$ to $[N]$ . Suppose that each $\omega_{s,N}$ , $s\in\{1,2,3\}$ is either the transpose for each $N$ , or the identity for each $N$ and denote $\sigma_{s,N}=\omega_{s,N}\circ\sigma_{N}\circ\omega_{s,N}$ . With this notations, for any $\theta>0$ the following relations hold true almost surely:

(i)

$\displaystyle\lim_{N\rightarrow\infty}N^{-(1+\theta)}\cdot\big{|}\{(i,j,k,l)\in[N]^{4}:\ \sigma_{N}(i,j)=\top\circ\sigma_{1,N}(k,l)\textrm{ and }\\ {}\hskip 184.9429pt\sigma_{2,N}(j,k)=\top\circ\sigma_{3,N}(l,i)\}\big{|}=0.$
(ii)

$\displaystyle\lim_{N\rightarrow\infty}N^{-(\frac{5}{2}+\theta)}\cdot\big{|}\big{\{}(i,j,a,b)\in[N]^{4}:\ \sigma_{N}(a,\phi_{N}(\sigma_{N}(i,j)))=\top\circ\sigma_{1,N}(b,i)\big{\}}\big{|}=0$ .

Proof.

To simplify the writing, $N$ shall be omitted within this proof by writting $\sigma$ , $\sigma_{s}$ , $\omega_{S}$ for $\sigma_{N}$ , $\sigma_{s,N}$ , $\omega_{s,N}$ respectively (where $1\leq s\leq 4$ ).

For part (i), note first that if $i=j$ , then there are at most $N$ possible choices for $i$ , each determining at most one possible choice for $k,l$ , hence

\big{|}\{(i,j,k,l)\in[N]^{4}:\ i=j,\sigma_{N}(i,j)=\top\circ\sigma_{1,N}(k,l),\sigma_{2,N}(j,k)=\top\circ\sigma_{3,N}(l,i)\}\big{|}=o(N).

Similar relations hold true for $k=l$ , for $i=l$ and for $j=k$ . Furthermore, if $i=k$ and $l=j$ , then the equality $\sigma(i,j)=\top\circ\sigma_{1}(k,l)$ gives either $i=j$ if $\omega_{1}=\text{Id}_{N}$ or $\sigma(i,j)=\top\circ\sigma(i,j)$ if $\omega_{1}$ is the transpose. In the last case there are again at most $N$ possible choices for $(i,j)$ as it is in the preimage of the diagonal under $\sigma_{N}$ .

Therefore it remains to prove the statement for $(i,j,k,l)\in D$ , where

\displaystyle D=\big{\{}(i,j,k,l)\in[N]^{4}:\ (i,j),\,\omega_{1}(k,l),\,\omega_{2}(j,k),\,\omega_{3}(l,i)\textrm{ are distinct}\big{\}}.

For each $(i,j,k,l)\in D$ , consider a mapping $I_{i,j,k,l}$ on $\mathcal{S}([N]^{2})$ given by

\displaystyle I_{i,j,k,l}(\sigma)=\begin{cases}1&\mbox{ if condition ($\ast$) holds true }\\ 0&\mbox{ otherwise, }\end{cases}

where condition ( $\ast$ ) is that $\sigma(i,j)=\top\circ\sigma_{1}(k,l)$ and $\sigma_{2}(j,k)=\top\circ\sigma_{4}(l,i)$ .

From Markov’s inequality, we have

\mathbb{P}(\sum_{(i,j,k,l)\in D}I_{i,j,k,l}>\varepsilon N^{1+\theta})\leq\varepsilon^{-1}\cdot\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D}I_{i,j,k,l}\big{)}/N^{1+\theta},

where the (not displayed) argument of $I_{i,j,k,l}$ is an uniformly random permutation on $\mathcal{S}([N]^{2})$ . From Lemma 2.6 it sufficces to show that the expectation above is bounded.

For $I_{i,j,k,l}(\sigma)\neq 0$ , there are $N^{2}$ possible choices for $\sigma(i,j)$ , each giving at most one possible choice for $\sigma(\omega_{1,N}(k,l))$ and $N^{2}-2$ choices for $\sigma(\omega_{2}(j,k))$ , each of them determining at most one possible choice for $\sigma(\omega_{3}(l,i))$ ; finally, there are at most $(N^{2}-4)!$ possible choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D}I_{i,j,k,l}\big{)}<N^{4}\cdot\frac{N^{2}\cdot(N^{2}-2)\cdot(N^{2}-4)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1,

hence the conclusion.

For part (ii), let us denote by ( $\ast\ast$ ) the relation $\sigma(a,\phi_{N}(\sigma(i,j)))=\top\circ\sigma_{1}(b,i)$ .

Remark that it suffices to show the property for tuples $(i,j,a,b)$ such that $a,b,\notin\{i,j\}$ . If $a\in\{i,j\}$ , then there are $N^{2}$ possible choices for the triple $(i,j,a)$ , each determining, via condition ( $\ast\ast$ ), at most one possible value for $b$ . Similarly for $b\in\{i,j\}$ .

Let $D_{1}=\{(i,j,a,b)\in[N]^{4}:\ a,b\notin\{i,j\}\}$ . As before, using the Borel-Cantelli Lemma, it suffices to show that for each $\varepsilon>0$ ,

\displaystyle\sum_{N=1}^{\infty}\mathbb{P}\big{(}\big{|}\{(i,j,a,b)\in D_{1}:\ \textrm{ ($\ast\ast$) holds true}\}\big{|}>\varepsilon\cdot N^{\frac{5}{2}+\theta}\big{)}<\infty,

which holds true if

\displaystyle N^{1+2\theta}\cdot\mathbb{P}\big{(}\big{|}\{(i,j,a,b)\in D_{1}:\ \textrm{ ($\ast\ast$) holds true}\}\big{|}>\varepsilon\cdot N^{\frac{5}{2}+\theta}\big{)}

is uniformly bounded in $N$ .

For each $(i,j,a,b)\in D_{1}$ consider a mapping $F_{i,j,a,b,}$ on $\mathcal{S}([N]^{2})$ given by

\displaystyle F_{i,j,a,b}(\sigma)=\begin{cases}\begin{array}[]{ll}1&\textrm{ if ($\ast\ast$) holds true}\\ 0&\textrm{otherwise}.\end{array}\end{cases}

Markov’s inequality gives that

\displaystyle\mathbb{P}\big{(}\big{|}\{(i,j,a,b)\in D_{1}:\ \textrm{ ($\ast\ast$) holds true}\}\big{|}>\varepsilon\cdot N^{\frac{5}{2}+\theta}\big{)}\leq\frac{\mathbb{E}\big{(}\displaystyle(\sum_{(i,j,a,b)\in D_{1}}F_{i,j,a,b})^{2}\big{)}}{\varepsilon^{2}N^{5+2\theta}}

where the implicit argument of $F_{i,j,a,b}$ is a uniformly random permutation on $\mathcal{S}([N]^{2})$ . So by Lemma 2.6 it suffices to show that

(6)

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\displaystyle(\sum_{(i,j,a,b)\in D_{1}}F_{i,j,a,b})^{2}\big{)}\textrm{ is uniformly bounded in $N$. }

First, note that if $b\neq b^{\prime}$ , then $F_{i,j,a,b}\cdot F_{i,j,a,b^{\prime}}=0$ . since condition ( $\ast\ast$ ) implies that $\top\circ\sigma_{1}(b,i)=\sigma(a,\phi_{N}(\sigma(i,j)))=\top\circ\sigma_{1}(b^{\prime},i)$ . Similarly, if $a\neq a^{\prime}$ , then $F_{i,j,a,b}\cdot F_{i,j,a^{\prime},b}=0$ .

Next, if $(i,j)\neq(i^{\prime},j^{\prime})$ but $(a,\phi_{N}(\sigma_{N}(i,j)))=(a^{\prime},\phi_{N}(\sigma(i^{\prime},j^{\prime})))$ then ( $\ast\ast$ ) gives that $(b,i)=(b^{\prime},i^{\prime})$ .

Denote

	$\displaystyle D_{2}$	$\displaystyle=\{(i,j,a,b,a^{\prime},b^{\prime}):\ a\neq a^{\prime},b\neq b^{\prime}\textrm{ and }(i,j,a,b),(i,j,a^{\prime},b^{\prime})\in D_{1}\}$
	$\displaystyle D_{3}$	$\displaystyle=\{(i,j,j^{\prime},a,b):\ (i,j,a,b),(i,j^{\prime},a,b)\in D_{1}\}$
	$\displaystyle D_{4}$	$\displaystyle=\{(i,j,i^{\prime},j^{\prime},a,b,a^{\prime},b^{\prime}):\ (i,j)\neq(i^{\prime},j^{\prime}),(a,b)\neq(a^{\prime},b^{\prime})\textrm{ and }$
		$\displaystyle\hskip 207.7052pt(i,j,a,b),(i^{\prime},j^{\prime},a^{\prime},b^{\prime})\in D_{1}\}$

Utilizing the observations above and that $F_{i,j,a,b}=F_{i,j,a,b}^{2}$ , we have that

	$\displaystyle\mathbb{E}\big{(}(\sum_{(i,j,a,b)\in D_{1}}F_{i,j,a,b})^{2}\big{)}=\mathbb{E}$	$\displaystyle\big{(}\sum_{D_{1}}F_{i,j,a,b}\big{)}+\mathbb{E}\big{(}\sum_{D_{2}}F_{i,j,a,b}\cdot F_{i,j,a^{\prime},b^{\prime}}\big{)}$
		$\displaystyle+\mathbb{E}\big{(}\sum_{D_{3}}F_{i,j,a,b}\cdot F_{i,j^{\prime},a,b}\big{)}+\mathbb{E}\big{(}\sum_{D_{4}}F_{i,j,a,b}\cdot F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}.$

For $F_{i,j,a,b}(\sigma_{N})=1$ , there are at most $N^{2}$ possible choices for $\sigma(i,j)$ , each giving at most $N^{2}-1$ possible choices for $\sigma(a,\phi_{N}(\sigma(i,j)))$ , each giving at most one possible choice for $\sigma(\omega_{1}(b,i))$ and at most $(N^{2}-3)!$ possible choices for the rest of values of $\sigma$ . Therefore

(7)

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\sum_{D_{1}}F_{i,j,a,b}\big{)}\leq N^{-4}\cdot N^{4}\cdot\frac{N^{2}\cdot(N^{2}-1)\cdot 1\cdot(N^{2}-3)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

For $(i,j,a,b,a^{\prime},b^{\prime})\in D_{2}$ and $F_{i,j,a,b}\cdot F_{i,j,a^{\prime},b^{\prime}}(\sigma)=1$ , there are $N^{2}$ possible choices for $\sigma(i,j)$ , each giving less than $N^{4}$ possible choices for $\sigma(a,\phi_{N}(\sigma(i,j)))$ , $\sigma(a^{\prime},\phi_{N}(\sigma(i,j)))$ each giving at most one choice for $\sigma(\omega_{1}(b,i))$ , $\sigma(\omega_{1}(b^{\prime},i))$ and $(N^{2}-5)!$ possible choices for the rest of values of $\sigma$ . Therefore

(8)

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\sum_{D_{2}}F_{i,j,a,b}\cdot F_{i,j,a^{\prime},b^{\prime}}\big{)}<N^{-4}\cdot N^{6}\cdot\frac{N^{2}\cdot N^{4}\cdot(N^{2}-5)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

For $(i,j,j^{\prime},a,b)\in D_{3}$ and $F_{i,j,a,b}\cdot F_{i,j^{\prime},a,b}=1$ , there are $N^{2}$ possible choices for $\sigma(i,j)$ , each giving less than $N^{2}$ possible choices for $\sigma(a,\phi_{N}(\sigma(i,j)))$ , each giving at most one possible choice for $\sigma(\omega_{1}(b,i))$ and at most $(N^{2}-3)!$ possible choices for the rest of values of $\sigma$ . Therefore

(9)

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\sum_{D_{3}}F_{i,j,a,b}\cdot F_{i,j^{\prime},a,b}\big{)}<N^{-4}\cdot N^{5}\cdot\frac{N^{4}\cdot(N^{2}-3)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

For $(i,j,i^{\prime},j^{\prime},a,b,a^{\prime},b^{\prime})\in D_{4}$ together with $F_{i,j,a,b}\cdot F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}=1$ there are at most $N^{2}$ possible choices for $\sigma(i,j)$ , each giving less than $N^{2}$ possible choices for $\sigma(a,\phi_{N}(\sigma(i,j)))$ , each giving one possible choice for $\sigma(\omega_{1}(b,i))$ , then less than $N^{4}$ possible choices for $\sigma(i^{\prime},j^{\prime})$ , $\sigma(a^{\prime},\phi_{N}(\sigma(i^{\prime},j^{\prime})))$ , each with at most one choice for $\sigma(\omega_{1}(b^{\prime},i^{\prime}))$ and at most $(N^{2}-6)!$ possible choices for the rest of values of $\sigma$ . Therefore

(10)

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\sum_{D_{4}}F_{i,j,a,b}\cdot F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}<N^{-4}\cdot N^{8}\cdot\frac{N^{8}\cdot(N^{2}-6)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

The conclusion follows summing relations (7) - (10).

∎

Proof of Theorem 3.1.

According to Lemma 2.5(i), for any subset $S$ of $[m]$ , we have that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(S)\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}$ . Therefore it suffices to show that there is some $S\subseteq[m]$ and some $\varepsilon>0$ such that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(S)<-1-\varepsilon$ .

Next, we observe that if we remove from $\pi$ any block of $\pi$ of the form $(k,k+1)$ such that $\varepsilon(k)\neq\varepsilon(k+1)$ it does not change the value of $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)$ . Indeed, if $\pi(k)=k+1$ and $\varepsilon(k)\neq\varepsilon(k+1)$ , that is $\sigma_{k+1,N}=\top\circ\sigma_{k,N}\circ\top$ , then the relation $\delta_{\sigma_{k,N}(i_{k},i_{k+1})}^{\top\circ\sigma_{k+1,N}(i_{k+1},i_{k+2})}=1$ is equivalent to $i_{k}=i_{k+2}$ . Hence

	$\displaystyle\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)=$	$\displaystyle\frac{1}{N}\sum_{\begin{subarray}{c}1\leq i_{\nu}\leq N\\ 1\leq\nu\leq m\end{subarray}}\frac{1}{N}\delta_{\sigma_{k,N}(i_{k},i_{k+1})}^{\top\circ\sigma_{k+1,N}(i_{k+1},i_{k+2})}\prod_{\begin{subarray}{c}(s,t)\in\pi\\ s\neq k\neq t\end{subarray}}E\big{(}[G_{N}^{\sigma_{k,N}}]_{i_{s},i_{s+1}}\cdot[G_{N}^{\sigma_{l,N}}]_{i_{t},i_{t+1}}\big{)}$
(11)		$\displaystyle=$	$\displaystyle\sum_{i_{k+1}=1}^{N}\frac{1}{N}\mathcal{V}_{\overrightarrow{\sigma_{N}}^{\prime}}(\pi^{\prime})=\mathcal{V}_{\overrightarrow{\sigma_{N}}^{\prime}}(\pi^{\prime})$

where $\pi^{\prime}$ and $\overrightarrow{\sigma_{N}}^{\prime}$ are obtained by removing $(k,k+1)$ from $\pi$ and removing $\sigma_{k,N}$ and $\sigma_{k+1,N}$ from $\overrightarrow{\sigma_{N}}$ .

Without loss of generality from now on we assume that $\pi$ does not contain a block of the form $(k,k+1)$ such that $\varepsilon(k)\neq\varepsilon(k+1)$ . Observe that non-crossing pairings which at the same time are alternating in $1$ and $*$ always contain such a pair. Next we shall show that for any other pairing (either crossing or non-crossing but non-alternating) we have that $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)$ vanishes asymptotically.

Suppose that $\pi$ has a block of the form $(k,k+1)$ with $\varepsilon(k)=\varepsilon(k+1)$ . Via a circular permutation of the set $[m]$ , we can then assume that $\pi(1)=2$ . If $m=2$ , then the result follows from Lemma 3.2(i). If $m>2$ , then from our first assumption, the restriction of $\pi$ to $\{3,4,\dots,m\}$ either has a crossing or a block of the form $(s,s+1)$ .

For the case $\pi(1)=2$ and $\pi(s)=s+1$ for some $s>2$ (see Figure 1 below), Lemma 3.2(ii) gives that for any $\theta>0$ , almost surely $|\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,2\}))|=o(N^{\theta})$ , therefore $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,2\}))<-1+\theta$ . Hence, taking $B=\{1,\dots,s-1\}$ , part (ii) of Lemma 2.5 gives that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(B)<-1+\theta$ .

Figure 1.

On the other hand, given $(i_{\nu},j_{\nu})_{\nu\in B}\in\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}(B)$ , the component $i_{s}=j_{s-1}$ is fixed, so according to Lemma 3.2 (ii) almost surely there are $o(N^{\theta})$ triples $(i_{s},i_{s+1},j_{s+1})$ such that $\sigma_{s,N}(i_{s},j_{s})=\top\circ\sigma_{s+1,N}(i_{s+1},j_{s+1})$ , that is

\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}(B\cup\{s,s+1\})=o(N^{\theta})\cdot\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}(B).

We get then $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(B\cup\{s,s+1\})<-2+2\theta$ and the conclusion follows from Lemma 2.5(i).

The case $\pi(1)=2$ and the set $\{3,4,\dots,m\}$ contains a crossing of $\pi$ is similar. Suppose that $a,b,c,d$ is such a crossing see Figure 2 below).

Figure 2

As above, Lemma 3.2(ii) and Lemma 2.5(i) give that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([b-1])<-1+\theta$ . Since $\pi(a)=c$ , Lemma 2.5(ii) gives that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([b-1]\cup\{c\})<-1+\theta$ , and furthermore, utilizing again Lemma 2.5(i), we get

\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([c]\setminus\{b\})<-1+\theta.

Finally, applying part (iii) of Lemma 2.5, we get that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([c])<-2+\theta$ , hence the conclusion.

Next we shall analyse the case when $\pi$ does not have any block with consecutive elements and hence it has a crossing. Let $a<b<c<d$ be such that $\pi(a)=c$ , $\pi(b)=d$ and $c-b$ is minimal. Since $\pi$ does not have any block with consecutive elements, the minimality of $c-b$ give that $c=b+1$ . We can also suppose, via a circular permutation of the set $[m]$ , that $a=1$ .

Furthermore, remark that if the set $[d]$ is not invariant under $\pi$ , then the conclusion of the theorem holds true, that is $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)=o(N^{-1})$ . To show it, suppose that there are some $t,s$ with $t<d<s$ and $\pi(t)=s$ . If $b+1<t<d$ , (see Figure 3 below) then $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}(\{1,b+1\})=0$ , so applying parts (i) and (iii) of Lemma 2.5 we get that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([b+1])\leq-1$ .

Figure 3.

On the other hand, part (ii) of Lemma 2.5 gives then that $\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([b+1])\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([b+1]\cup\{d\})$ and another application of parts (i) and (iii) give that

\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([d])\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([d]\setminus\{t\})-1\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{n}}}([b+1]\cup\{d\})-1\leq-2,

hence the conclusion. The argument for the case $1<t<b$ is similar.

We can assume then that $\pi([d])=[d]$ . Furthermore, this allows us to assume that $d=m$ : if $d<m$ , then the restriction of $\pi$ to $[m]\setminus[d]$ has some crossing (since no block has consecutive elements), and again Lemma 2.5 gives that $\mathfrak{a}_{\pi\overrightarrow{\sigma_{N}}}\leq-2$ . Finally, without loss of generality, we can also suppose that $\varepsilon(1)=1$ , that is $\sigma_{1,N}=\sigma_{N}$ .

If $m=4$ , then, putting $\omega_{s,N}\in\{\text{Id}_{N},\top\}$ in part (i) of Lemma 3.3 we obtain that $\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}=o(N^{1+\theta})$ , hence

\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}<1+\theta-|\{1,2,3,4\}|+|\{(1,3),(2,4)\}|-1=-2+\theta.

If $m>4$ , then applying part (ii) of Lemma 3.3 for $(i,j,a,b)=(i_{1},i_{b},i_{b+1},i_{m})$ , $\omega_{s,N}\in\{\text{Id}_{N},\top\}$ and $\phi_{N}$ one of the canonical projections, we obtain that

\mathcal{A}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,b,b+1,m\})=o(N^{\frac{5}{2}+\theta}),

hence

\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,b,b+1,m\})<\frac{5}{2}+\theta-4+2-1=-\frac{1}{2}+\theta.

On the other hand, since $m>4$ and $\pi$ does not have any blocks with consecutive elements, then either the sets $\{2,3\dots,b-1\}$ and $\{b+2,b+3,\dots,m-1\}$ are invariant under $\pi$ and at least one of them is nonvoid, or there are some $t,s$ with $\pi(t)=s$ and $1<t<b$ and $b+1<s<m$ .

Let us suppose that the set $\{2,3,\dots,b-1\}$ is nonvoid and invariant under $\pi$ . Since $\pi$ does not have any blocks with consecutive elements, the restriction of $\pi$ to the set $\{2,3,\dots,b-1\}$ contains at least one crossing, $(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ (see Figure 4 below).

Figure 4.

Applying parts (i), then (ii) of Lemma 2.5, we have that:

\displaystyle\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,b,b+1,m\})\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([a^{\prime}]\cup\{b,b+1,m\})\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([a^{\prime}]\cup\{c^{\prime},b,b+1,m\}).

Denoting $B=[c^{\prime}]\cup\{b,b+1,m\}$ and applying again Lemma 2.5(i), we have further obtain

\displaystyle\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(B\setminus\{b^{\prime}\})\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([a^{\prime}]\cup\{c^{\prime},b,b+1,m\}),

and another application of Lemma 2.5(iii) gives that

\displaystyle\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(B)\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(B\setminus\{b^{\prime}\})-1\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,b,b+1,m\})-1<-\frac{3}{2}+\theta,

hence the conclusion. The case when $\{b+2,b+2,\dots,m-1\}$ is nonvoid is similar.

Finally, let us suppose that there are some $t,s$ with $\pi(t)=s$ and $1<t<b$ and $b+1<s<m$ (see Figure 5 below).

Figure 5.

Applying part(i), then part (iii) of the Lemma 2.5 we obtain that

\displaystyle-\frac{1}{2}+\theta>\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}(\{1,b,b+1,m\})\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([b+1]\setminus\{t\}\cup\{m\})

respectively that

\displaystyle\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([b+1]\setminus\{t\}\cup\{m\})\geq\mathfrak{a}_{\pi,\overrightarrow{\sigma_{N}}}([b+1]\cup\{m\})+1,

hence the conclusion.

∎

4. Asymptotic Infinitesimal Freeness Relations

In [24], it is shown that $G_{N}^{\sigma_{N}}$ and $G_{N}^{\tau_{N}}$ are asymptotically circular and asymptotically free whenever the pair of permutation sequences $(\sigma_{N})_{N}$ and $(\tau_{N})_{N}$ satisfies certain conditions. Similar properties for Haar matrices were studied in [22] where we also allowed that the sequences of permutations are random. One of the consequences of [22] (not stated explicitly anywhere) is that conditions from [24] hold almost surely, which implies that for almost all pairs of permutation sequences $(\sigma_{N})_{N}$ and $(\tau_{N})_{N}$ , we have $G_{N}^{\sigma_{N}}$ and $G_{N}^{\tau_{N}}$ are asymptotically circular and asymptotically free.

In this section, we show that the property also holds on the level of infinitesimal distributions. More precisely, we show the following theorem:

Theorem 4.1.

Suppose that $G_{N}$ is a Gaussian random matrix for each positive integer $N$ . Moreover assume that sequences of uniformly random permutations $\big{(}\sigma_{N}\big{)}_{N}$ and $\big{(}\tau_{N}\big{)}_{N}$ from $\mathcal{S}([N]^{2})$ are independent from each other and independent from the sequence $(G_{N})_{N}$ . We have almost surely that $G_{N}^{\sigma_{N}}$ and $G_{N}^{\tau_{N}}$ are asymptotically circular with zero infinitesimal distribution and infinitesimally free from each other and from $G_{N}$ .

Remark 4.2.

Let us clarify what we mean by the ”almost sure” statement above. We consider asymptotic freeness with respect to sequence of functionals $(1/N)\mathbb{E}\circ\textrm{Tr}$ i.e. we take the expectation of the normalized trace. We will study as in the previous section the quantity $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)$ defined as in equation (5), which becomes a random variable when we let $\overrightarrow{\sigma_{N}}$ be a sequence of random permutations. Hence the almost sure limit here refers to the limit with probability one with respect to an uniformly random permutation.

The proof of the theorem above is very similar to the argument from the previous section. More precisely, in equation (5) we consider that each $\sigma_{k,N}$ is one of the following permutations: $\text{Id}_{N},\sigma_{N},\top\circ\sigma_{N}\circ\top,\tau_{N},\top\circ\tau_{N}\circ\top$ and prove a results similar to the ones from Section 3.

Lemma 4.3.

Suppose that $\big{(}\omega_{N}\big{)}_{N}$ is a given sequence of permutations with $\omega_{N}\in\mathcal{S}([N]^{2})$ for each $N$ . If $\theta>0$ is a constant, then for almost all $(\sigma_{N})_{N}$ we have that:

(i)

$\displaystyle\lim_{N\rightarrow\infty}N^{-(\frac{1}{2}+\theta)}\cdot|\{(i,j)\in[N]^{2}:\ \omega_{N}(i,j)=\sigma_{N}(j,i)\}|=0$
(ii)

$\displaystyle\lim_{N\rightarrow\infty}N^{-\theta}\cdot\sup_{1\leq i\leq N}\big{|}(j,k)\in[N]^{2}:\ \omega_{N}(i,j)=\sigma_{N}(j,k)\}\big{|}=0.$

Proof.

For part (i), given $i,j\in[N]$ , denote by $I_{i,j}$ the random variable on $\mathcal{S}([N]^{2})$ given by $I_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(i,j)=\omega_{N}(j,i)\\ 0&\textrm{ if }\sigma(i,j)\neq\omega_{N}(j,i).\end{array}\right.$

As in the proof of Lemma 3.2(i), it suffices to show that the sums $\displaystyle\sum_{i,j=1}^{N}\mathbb{E}(I_{i,j})$ and $\displaystyle\sum_{\begin{subarray}{c}1\leq i,j,k,l\leq N\\ (i,j)\notin\{(k,l),(l,k)\}\end{subarray}}\mathbb{E}(I_{i,j}I_{k,l})$ are bounded in $N$ .

For $I_{i,j}(\sigma)\neq 0$ there is only one possible choice for $\sigma_{N}(j,i)$ and $(N^{2}-1)!$ possiblilities for the rest of the values of $\sigma$ , therefore

\displaystyle\sum_{i,j=1}^{N}\mathbb{E}(I_{i,j})\leq N^{2}\frac{1\cdot(N^{2}-1)!}{N^{2}!}=1.

If $(i,j)\notin\{(k,l),(l,k)\}$ , for $I_{i,j}(\sigma)I_{k,l}(\sigma)\neq 0$ there is only one possible choice for $\sigma(j,i)$ and for $\sigma(l,k)$ and $(N^{2}-2)!$ possible choices for the rest of the values of $\sigma$ , therefore

\displaystyle\sum_{\begin{subarray}{c}1\leq i,j,k,l\leq N\\ (i,j)\notin\{(k,l),(l,k)\}\end{subarray}}\mathbb{E}(I_{i,j}I_{k,l})\leq N^{2}(N^{2}-2)\frac{1\cdot(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1,

and the conclusion follows.

For part (ii), for a fixed $a\in[N]$ denote by $F_{i,j}$ the random variable on $\mathcal{S}([N]^{2})$ given by $F_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(i,j)=\omega_{N}(a,i)\\ 0&\textrm{ if }\sigma(i,j)\neq\omega_{N}(a,i)\end{array}\right.$ and, as in the proof of Lemma 3.2(ii), it suffices to show the boundedness (as $N\rightarrow\infty$ ) of the expression

\mathbb{E}\big{(}\sum_{D}F_{i_{1},j_{1}}\cdots F_{i_{s},j_{s}}\big{)}

where $s$ is some positive integer and again

\displaystyle D=\{(i_{1},j_{1},\dots,i_{s},j_{s})\in[N]^{2s}:\ (i_{1},j_{1}),\dots,(i_{s},j_{s})\textrm{ distinct }\}.

If $F_{i_{t},j_{t}}\neq 0$ for each $1\leq t\leq s$ , we need that the $s$ -tuple $(\sigma(i_{1},j_{1}),\dots,\sigma(i_{s},j_{s}))$ coincides to the $s$ -tuple $(\omega_{N}(a,i_{1}),\dots,\omega_{N}(a,i_{s}))$ and there are at most $(N^{2}-s)!$ choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\mathbb{E}\big{(}\sum_{D}F_{j_{1},k_{1}}\cdots F_{i_{s},j_{s}}\big{)}\leq\frac{1}{N^{2}!}\cdot N^{2s}\cdot(N^{2}-s)!\xrightarrow[N\rightarrow\infty]{}1

hence the conclusion. ∎

Lemma 4.4.

Let $\theta$ be a constant. The following relations hold true almost surely for sequences $\big{(}\sigma_{N}\big{)}_{N}$ with each $\sigma_{N}$ an uniformly random permutation from $\mathcal{S}([N]^{2})$ :

(i)

if $(f_{N})_{N},(g_{N})_{N}$ are two given sequences of maps, $f_{N},g_{N}:[N]^{2}\rightarrow[N]^{2}$ , then

$\displaystyle\lim_{N\rightarrow\infty}N^{-(1+\theta)}\cdot\big{|}\{(i,j):\ \sigma_{N}(f_{N}(i,j))=g_{N}(i,j)\}\big{|}=0$

(ii)

if $(\phi_{N})_{N},(\psi_{N})_{N}$ are sequences of maps, $\phi_{N},\psi_{N}:[N]^{3}\rightarrow[N]^{2}$ , such that $(i,a,b)=(i^{\prime},a^{\prime},b^{\prime})$ whenever $\phi_{N}(i,j,a)=\phi_{N}(i^{\prime},j^{\prime},a^{\prime})$ and $\psi_{N}(i,j,b)=\psi_{N}(i^{\prime},j^{\prime},b^{\prime})$ , then

\displaystyle\lim_{n\rightarrow\infty}N^{-(\frac{5}{2}+\theta)}\cdot\big{|}\{(i,j,a,b):\ \sigma_{N}(\phi_{N}(i,j,a))=\psi_{N}(i,j,b)\}\big{|}=0.

Proof.

Considering the random variable $I_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(f_{N}(i,j))=g_{N}(i,j)\\ 0&\textrm{ otherwise }\end{array}\right.$ and using Markov’s inequality, we have that

\displaystyle\mathbb{P}\big{(}\big{|}\{(i,j):\ \sigma_{N}((f_{N}(i,j))=g_{N}(i,j)\}\big{|}>\varepsilon\cdot N^{1+\theta}\big{)}<\frac{\mathbb{E}\big{(}\displaystyle\sum_{i,j\in[N]}I_{i,j}\big{)}}{\varepsilon\cdot N^{1+\theta}}

so by Lemma 2.6 it suffices to show that $\displaystyle\mathbb{E}\big{(}\sum_{i,j\in[N]}I_{i,j}\big{)}=O(N^{0})$ .

For $I_{i,j}(\sigma)=1$ , there is at most one possible choice for $\sigma(f_{N}(i,j))$ and at most $(N^{2}-1)!$ possible choices for the rest of the values of $\sigma$ , hence

\displaystyle\mathbb{E}\big{(}\sum_{i,j\in[N]}I_{i,j}\big{)}\leq N^{2}\cdot\frac{1\cdot(N^{2}-1)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

Similarly, for part (ii) considering the random variable

I_{i,j,a,b}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(\phi_{N}(i,j,a))=\psi_{N}(i,j,b)\\ 0&\textrm{ otherwise }\end{array}\right.

and applying again Markov’s inequality, we have that

\displaystyle\mathbb{P}\big{(}\big{|}\{(i,j,a,b):\sigma_{N}(\phi_{N}(i,j,a))=\psi_{N}(i,j,b)\}\big{|}>\varepsilon\cdot N^{\frac{5}{2}+\theta}\big{)}<\frac{\displaystyle\mathbb{E}\big{(}(\sum_{i,j,a,b}I_{i,j,a,b})^{2}\big{)}}{\varepsilon^{2}\cdot N^{5+2\theta}}

so by Lemma 2.6 it suffices to show that $\displaystyle\mathbb{E}\big{(}(\sum_{i,j,a,b}I_{i,j,a,b})^{2}\big{)}=O(N^{4})$ .

For $I_{i,j,a,b}(\sigma)=1$ there is only one possible choice for $\sigma(\phi_{N}(i,j,a))$ and $(N^{2}-1)!$ possible choices for the other values of $\sigma$ , therefore

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{i,j,a,b}I_{i,j,a,b}^{2}\big{)}=\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{i,j,a,b}I_{i,j,a,b}\big{)}\leq\frac{1}{N^{4}}\cdot N^{4}\cdot\frac{(N^{2}-1)!}{N^{2}}\xrightarrow[N\rightarrow\infty]{}0.

Denote $D=\{(i,j,a,b,i^{\prime},j^{\prime},a^{\prime},b^{\prime}):\ (i,a,b)\neq(i^{\prime},a^{\prime},b^{\prime})\}$ . From the property of $\phi_{N}$ and $\psi_{N}$ , it follows that if $(i,j,a,b,i^{\prime},j^{\prime},a^{\prime},b^{\prime})\in D$ and $\phi_{N}(i,j,a)=\phi_{N}(i^{\prime},j^{\prime},a^{\prime})$ then $I_{i,j,a,b}I_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}=0$ . Hence, if $(i,j,a,b,i^{\prime},j^{\prime},a^{\prime},b^{\prime})\in D$ and the relation $I_{i,j,a,b}\cdot I_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}(\sigma)\neq 0$ holds true, then there is one possible choice for $\sigma(\phi_{N}(i,j,a))$ and $\sigma(\phi_{N}(i^{\prime},j^{\prime},a^{\prime}))$ and $(N^{2}-2)!$ possible choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{D}I_{i,j,a,b}I_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}\leq\frac{1}{N^{4}}\cdot N^{8}\cdot\frac{(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

On the other hand, for $I_{i,j,a,b}\cdot I_{i,j^{\prime},a,b}(\sigma)\neq 0$ , there is one possible choice for $\sigma(\phi_{N}(i,j,a))$ and at most $(N^{2}-1)!$ possible choices for the other values of $\sigma$ , hence

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{i,a,b,j,j^{\prime}}I_{i,j,a,b}\cdot I_{i,j^{\prime},a,b}\big{)}\leq\frac{1}{N^{4}}\cdot N^{5}\cdot\frac{(N^{2}-1)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0,

and property (ii) follows. ∎

Lemma 4.5.

The following relations hold true almost surely for sequences $\big{(}\sigma_{N}\big{)}_{N}$ with each $\sigma_{N}$ a permutation from $\mathcal{S}([N]^{2})$ :

(i)

Suppose that $(f_{N})_{N}$ , $(g_{N})_{N}$ are two given sequences of maps and $(\eta_{N})_{N}$ is a sequence of permutations such that $f_{N},g_{N}:[N]^{2}\rightarrow[N]^{2}$ and $\eta_{N}\in\mathcal{S}([N]^{2}).$ Then

	$\displaystyle\lim_{N\rightarrow\infty}N^{-(1+\theta)}\cdot\big{\|}\{(i,j)\in[N]^{2}:\ f_{N}(i,$	$\displaystyle j)\neq g_{N}(i,j)$
	and	$\displaystyle\sigma_{N}(f_{N}(i,j))=\eta_{N}\circ\sigma_{N}(g_{N}(i,j))\}\big{\|}=0.$

(ii)

Suppose that $(h_{N})_{N}$ is a sequence of maps and $(\omega_{N})_{N}$ , $(\eta_{N})_{N}$ are sequences of permutations, $h_{N}:[N]^{2}\rightarrow[N]$ and $\omega_{N},\eta_{N}\in\mathcal{S}([N]^{2})$ with $(\omega_{N})_{N}$ either the identity permutation or the matrix transpose. Then

	$\displaystyle\lim_{N\rightarrow\infty}N^{-(\frac{5}{2}+\theta)}\cdot\big{\|}\{(i,j,a,b)\in[N]^{4}:\$	$\displaystyle\omega_{N}(b,i)\neq(a,h_{N}(i,j))\textrm{ and }$
		$\displaystyle\sigma_{N}(a,h_{N}(i,j))=\eta_{N}\circ\sigma_{N}\circ\omega_{N}(b,i)\}\big{\|}=0$

Proof.

For part (i), denote $D=\{(i,j)\in[N]^{2}:\ f_{N}(i,j)\neq g_{N}(i,j)\}$ and consider the random variable on $\mathcal{S}([N]^{2})$ given by

I_{i,j}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{if }\sigma(f_{N}(i,j))=\eta_{N}\circ\sigma(g_{N}(i,j))\\ 0&\textrm{otherwise}.\end{array}\right.

Via Markov’s inequality and Lemma 2.6 it suffices to show that $\displaystyle\mathbb{E}\big{(}\sum_{(i,j)\in D}I_{i,j}\big{)}=O(N^{0})$

For $I_{i,j}(\sigma)=1$ , there are $N^{2}$ possible for $\sigma_{N}(f_{N}(i,j))$ , each giving one possible choice for $\sigma_{N}(g_{N}(i,j))$ and $(N^{2}-2)!$ possible choices for the rest of values of $\sigma$ . Therefore:

\displaystyle\mathbb{E}\big{(}\sum_{(i,j)\in D}I_{i,j}\big{)}<N^{2}\cdot\frac{N^{2}\cdot(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1,

hence the conclusion.

For part (ii), denote $V=\{(i,j,a,b)\in[N]^{4}:\ \omega_{N}(b,i)\neq(a,h_{N}(i,j))\}$ and consider the random variable on $\mathcal{S}([N]^{2})$ given by

\displaystyle F_{i,j,a,b}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(a,h_{N}(i,j))=\eta_{N}\circ\sigma\circ\omega_{N}(b,i)\\ 0&\textrm{ otherwise. }\end{array}\right.

With these notations, it suffices to show that $\displaystyle\mathbb{E}\big{(}(\sum_{V}F_{i,j,a,b})^{2}\big{)}=O(N^{4})$ .

To simplify the writing, we shall use the notations $\vec{v}$ (respectively $\vec{v}^{\prime}$ ) for $(i,j,a,b)$ (respectively $(i^{\prime},j^{\prime},a^{\prime},b^{\prime})$ ); also, let $Z(\vec{v})=\{(a,h_{N}(i,j)),\omega_{N}(b,i)\}$ and introduce the sets $W=\{(\vec{v},\vec{v}^{\prime})\in V\times V:\ \vec{v}\neq\vec{v}^{\prime}\}$ , and, for $s=0,1,2$ , let

\displaystyle W_{s}=\{(\vec{v},\vec{v}^{\prime})\in W:\ \big{|}Z(\vec{v})\cap Z(\vec{v}^{\prime}))\big{|}=s\}.

We have that

	$\displaystyle\mathbb{E}\big{(}(\sum_{V}F_{i,j,a,b})^{2}\big{)}$	$\displaystyle=\mathbb{E}\big{(}\sum_{V}F_{i,j,a,b}^{2}\big{)}+\mathbb{E}\big{(}\sum_{W}F_{i,j,a,b}F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}$
		$\displaystyle=\mathbb{E}\big{(}\sum_{V}F_{i,j,a,b}\big{)}+\sum_{s=0}^{2}\mathbb{E}\big{(}\sum_{W_{s}}F_{i,j,a,b}F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}.$

Since the random variables $F_{i,j,a,b}$ are identically distributed,

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{V}F_{i,j,a,b}\big{)}=\big{|}V\big{|}\cdot\frac{1}{N^{4}}\mathbb{E}\big{(}F_{i,j,a,b}\big{)}<N^{4}\cdot\frac{1}{N^{4}}=1.

If $(\vec{v},\vec{v}^{\prime})\in W_{0}$ , then there are at most $N^{2}$ possible choices for $\sigma(a,h_{N}(i,j))$ , each giving one possible choice for $\sigma(\omega_{N}(b,i))\big{)}$ , less than $N^{2}$ possible choices for the pair $\big{(}\sigma(a^{\prime},h_{N}(i^{\prime},j^{\prime})),\sigma(\omega_{N}(b^{\prime},i^{\prime}))\big{)}$ and at most $(N^{2}-4)!$ possible choices for the rest of the values of $\sigma$ . Therefore:

\displaystyle\frac{1}{N^{4}}\cdot\mathbb{E}\big{(}\sum_{W_{0}}F_{i,j,a,b}F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}\leq\frac{1}{N^{4}}\cdot N^{8}\cdot\frac{N^{4}\cdot(N^{2}-4)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

If $(\vec{v},\vec{v}^{\prime})\in W_{1}$ then there are at most $N^{2}$ possible choices for $\sigma(a,h_{N}(i,j))$ each giving one choice for $\sigma(Z(\vec{v})\cup Z(\vec{v}^{\prime})$ and at most $(N^{2}-3)!$ possible choices for the rest of values of $\sigma$ . Also, since $\omega_{N}$ is either the identity of the matrix transpose, we have that $|W_{1}|\leq N^{7}$ . Therefore

\displaystyle\frac{1}{N^{4}}\cdot\mathbb{E}\big{(}\sum_{W_{1}}F_{i,j,a,b}F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}\leq\frac{1}{N^{4}}\cdot N^{7}\cdot\frac{N^{2}\cdot(N^{2}-3)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

If $(\vec{v},\vec{v}^{\prime})\in W_{2}$ then there are at most $N^{2}$ possible choices for $\sigma(a,h_{N}(i,j))$ each giving one choice for $\sigma(Z(\vec{v})\cup Z(\vec{v}^{\prime})$ and at most $(N^{2}-2)!$ possible choices for the rest of values of $\sigma$ . Moreover, if $(a,h_{N}(i,j))=(a^{\prime},h_{N}(i^{\prime},j^{\prime}))$ and $\omega_{N}(b,i)=\omega_{N}(b^{\prime},i^{\prime})$ , then $(a,b,i)=(a^{\prime},b^{\prime},i^{\prime})$ , and $|W_{2}|\leq N^{5}$ . If $(a,h_{N}(i,j))=\omega_{N}(b^{\prime},i^{\prime})$ and $\omega_{N}(b,i)=(a^{\prime},h_{N}(i^{\prime},j^{\prime}))$ , then $a=b^{\prime}$ and $b=a^{\prime}$ when $\omega_{N}$ is the identity, respectively $a=i^{\prime}$ and $i=a^{\prime}$ when $\omega_{N}$ is the matrix transpose. Hence $|W_{2}|\leq N^{6}$ . We have that

\displaystyle\frac{1}{N^{4}}\cdot\mathbb{E}\big{(}\sum_{W_{2}}F_{i,j,a,b}F_{i^{\prime},j^{\prime},a^{\prime},b^{\prime}}\big{)}\leq\frac{1}{N^{4}}\cdot N^{6}\cdot\frac{N^{2}\cdot(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1

and the conclusion follows. ∎

Lemma 4.6.

Suppose that $(\eta_{1,N})_{N},(\eta_{2,N})_{N},(\omega_{N})_{N}$ are given sequences of permutations such that $\omega_{N}$ is either the identity or the matrix transpose. Then, almost surely for $(\sigma_{N})_{N}$ we have that

	$\displaystyle\lim_{N\rightarrow\infty}N^{-(\frac{5}{2}+\theta)}\cdot\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\ (a,k)\neq$	$\displaystyle\omega_{N}(k,l)\textrm{ and }\sigma_{N}(a,k)=\eta_{1}(b,i),$
		$\displaystyle\sigma_{N}(\omega_{N}(k,l))=\eta_{2}(i,j)\}\big{\|}=0.$

Proof.

As in the proof of the preceding Lemma 4.5(ii), we use the notation $\vec{v}=(i,j,k,l,a,b)$ , $\vec{v}^{\prime}=(i^{\prime},j^{\prime},k^{\prime},l^{\prime},a^{\prime},b^{\prime})$ , and we let $Z(\vec{v})=\{(a,k),\omega_{N}(k,l)\}$ and $Z(\vec{v}^{\prime})=\{(a^{\prime},k^{\prime}),\omega_{N}(k^{\prime},l^{\prime})\}$ . Consider the sets ( $s=0,1,2$ ):

	$\displaystyle V=\{(i,j,k,l,a,b)\in[N]^{6}:\ (a,k)\neq\omega_{N}(k,l)\}$
	$\displaystyle W=\{(\vec{v},\vec{v}^{\prime})\in V^{2}:\ \vec{v}\neq\vec{v}^{\prime}\}$
	$\displaystyle W_{s}=\{(\vec{v},\vec{v}^{\prime})\in W:\ \|Z(\vec{v})\cap Z(\vec{v}^{\prime})\|=s\}$

Next, consider the random variable $F^{a,b}_{i,j,k,l}$ on $\mathcal{S}([N]^{2})$ given by

\displaystyle F^{a,b}_{i,j,k,l}(\sigma)=\left\{\begin{array}[]{ll}1,&\textrm{ if }\sigma(a,k)=\eta_{1}(b,i)\textrm{ and }\sigma(\omega_{N}(k,l))=\eta_{2}(i,j)\\ 0,&\textrm{ otherwise. }\end{array}\right.

Using Lemma 2.6 and Markov Inequality, it suffices to show that

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}(\sum_{V}F_{i,j,k,l}^{a,b})^{2}\big{)}=O(N^{0}).

For $F^{a,b}_{i,j,k,l}(\sigma)\neq 0$ , with $(i,j,k,l,a,b)\in V$ , there is at most one possible choice for $\sigma(a,k)$ and $\sigma(\omega_{N}(k,l))$ and $(N^{2}-2)!$ possible choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{V}(F_{i,j,k,l}^{a,b})^{2}\big{)}=\frac{1}{N^{4}}\mathbb{E}\big{(}F_{i,j,k,l}^{a,b}\big{)}\leq\frac{1}{N^{4}}\cdot N^{6}\cdot\frac{(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

If $(\vec{v},\vec{v}^{\prime})\in W_{s}$ , then for $F^{a,b}_{i,j,k,l}F^{a^{\prime},b^{\prime}}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}(\sigma)\neq 0$ there is at most one possible choice for $\sigma\big{(}Z(\vec{v})\cup Z(\vec{v}^{\prime})\big{)}$ and $(N^{2}-|Z(\vec{v})\cup Z(\vec{v}^{\prime})|)!$ possible choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\frac{1}{N^{4}}\mathbb{E}\big{(}\sum_{W_{s}}F^{a,b}_{i,j,k,l}F^{a^{\prime},b^{\prime}}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\big{)}\leq\frac{|W_{s}^{\ast}|}{N^{4}}\cdot\frac{(N^{2}-|Z(\vec{v})\cup Z(\vec{v}^{\prime})|)!}{N^{2}!}

where $W_{s}^{\ast}=\{(\vec{v},\vec{v}^{\prime})\in W_{s}:F^{a,b}_{i,j,k,l}F^{a^{\prime},b^{\prime}}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\neq 0\}$ . Hence it suffices to show that

(12)

\displaystyle|W_{s}^{\ast}|\leq N^{4+2|Z(\vec{v})\cup Z(\vec{v}^{\prime})|}=N^{12-2|Z(\vec{v})\cap Z(\vec{v}^{\prime})|}.

For $s=0$ , relation (12) is trivially verified, as $W_{0}^{\ast}\subset V\times V\subseteq[N]^{12}$ . If $s\geq 1$ , then either $(a,k)\in Z(\vec{v}^{\prime})$ or $\omega_{N}(k,l)\in Z(\vec{v}^{\prime})$ . Suppose that $(a,k)\in Z(\vec{v}^{\prime})$ . If $(a,k)=(a^{\prime},k^{\prime})$ , then $F^{a,b}_{i,j,k,l}F^{a^{\prime},b^{\prime}}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\neq 0$ gives that $\eta_{1}(b,i)=\eta_{1}(b^{\prime},i^{\prime})$ , so $(b,i)=(b^{\prime},i^{\prime})$ . It follows that $(\vec{v},\vec{v}^{\prime})$ is uniquely determined by $(i,j,k,l,a,b,l^{\prime},a^{\prime})$ , that is $|W_{s}^{\ast}|\leq N^{8}$ , which implies (12). If $(a,k)=\omega_{N}(k^{\prime},l^{\prime})$ then again $F^{a,b}_{i,j,k,l}F^{a^{\prime},b^{\prime}}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\neq 0$ gives that $\eta_{1}(b,i)=\eta_{2}(i^{\prime},j^{\prime})$ so $(i^{\prime},j^{\prime})=\eta_{2}^{-1}\circ\eta_{1}(b,i)$ . It folows that $(\vec{v},\vec{v}^{\prime})$ is uniquely determined by $(i,j,k,l,a,b,a^{\prime},b^{\prime})$ , that is $|W_{s}^{\ast}|\leq N^{8}$ , which implies (12).

The case $\omega_{N}(k,l)\in Z(\vec{v}^{\prime})$ is similar. ∎

Proof of Theorem 4.1 .

From Theorem 3.1, we can assume that $G_{N}^{\sigma_{N}}$ and $G_{N}^{\tau_{N}}$ are both asymptotically circular with individually zero infinitesimal $*$ -distribution. Then, using the free moment-cumulant expansion, if suffices to show that $\mathcal{V}_{\overrightarrow{\sigma_{N}}}(\pi)=o(N^{-1})$ unless $\pi$ is non-crossing and $\sigma_{k,N}=\top\circ\sigma_{l,N}\circ\top$ whenever $\pi(k)=l$ .

As in the proof of Theorem 3.1, eventually by modifying $m$ , we can assume that $\pi$ does not have any blocks of the type $(k,k+1)$ such that $\sigma_{k,N}=\top\circ\sigma_{l,N}\circ\top$ . Next, using Lemma 4.3 in the same way Lemma 3.2 was used in the proof of Theorem 3.1, we can furthermore assume that $\pi$ does not have any blocks with consecutive elements. It follow that $\pi$ must have at least one crossing, and, as shown in the proof of Theorem 3.1, we can suppose without loss of generality that there is some $b\in[m-2]$ such that $\pi(1)=b+1$ and $\pi(b)=m$ .

Let us denote $S=\{(\sigma_{N})_{N},(\top\circ\sigma_{N}\circ\top)_{N}\}$ , $T=\{(\tau_{N})_{N},(\top\circ\tau_{N}\circ\top)_{N}\}$ and $T_{1}=\{(\text{Id}_{N})_{N}\}\cup T$ .

Suppose first that $m=4$ . It suffices to show that the following result holds true for any sequences $(\sigma_{s,N})_{N}\in S\cup T_{1}$ , $s=1,\dots,4$ :

(13)		$\displaystyle\big{\|}\{(i,j,k,l)\in[N]^{4}:\ \sigma_{1,N}(i,j)=\top\circ$	$\displaystyle\sigma_{3,N}(k,l)\textrm{ and }$
		$\displaystyle\sigma_{2,N}(j,k)=\top\circ\sigma_{4,N}(l,i)\}\big{\|}=o(N^{2}).$

Moreover, at least one of the sequences $(\sigma_{s,N})_{N}$ should be from the set $S$ and at least one from the set $T_{1}$ , so it suffices to show (13) for the following three cases:

(a)

one of the $(\sigma_{s,N})_{N}$ is from the set $S$ and three are from $T_{1}$
(b)

two of the $(\sigma_{s,N})_{N}$ are from the set $S$ and two are from $T_{1}$
(c)

three of the $(\sigma_{s,N})_{N}$ are from the set $S$ and one is $(\text{Id}_{N})_{N}$ .

For case (a), via a circular permutation of the set $\{1,2,3,4\}$ , we can suppose that $(\sigma_{2,N})_{N}\in S$ . Then, for

	$\displaystyle f_{N}(i,j)$	$\displaystyle=\left(j,(\pi_{1}\circ\sigma_{3,N}^{-1}\circ\top\circ\sigma_{1,N})(i,j)\right)$
	$\displaystyle g_{N}(i,j)$	$\displaystyle=\top\circ\sigma_{4,N}\left(\pi_{2}\circ\sigma_{3,N}^{-1}\circ\top\circ\sigma_{1,N})(i,j),i\right)$

Lemma 4.4(i) gives that (13) holds true for any $(\tau_{N})_{N}$ and almost surely for $(\sigma_{N})_{N}$ .

For case (b), note first that it suffices to show (13) when $\{i,k\}\cap\{j,l\}=\emptyset$ . Indeed, if $i=j$ , then there are at most $N$ possible choices for the pair $(i,j)$ , each determining at most one possible choice for $(k,l)=\sigma_{3,N}^{-1}\circ\top\circ\sigma_{1,N}(i,j)$ ; the other cases are similar.

Next, without loss of generality, we can further assume that $(\sigma_{1,N})_{N}\in T_{1}$ and $(\sigma_{2,N})_{N}\in S$ .

Suppose that $(\sigma_{4,N})_{N}\in S$ , Hence $\sigma_{4,N}=\omega_{N}\circ\sigma_{N}\circ\omega_{N}$ , with $\omega_{N}$ either identity or matrix transpose. Let

	$\displaystyle f_{N}(i,j)=(j,k)=\left(j,\pi_{1}\circ\sigma_{3,N}^{-1}\circ\top\circ\sigma_{1,N}(i,j)\right)$
	$\displaystyle g_{N}(i,j)=\omega_{N}(l,i)=\omega_{N}\left((\pi_{2}\circ\sigma_{3,N}^{-1}\circ\top\circ\sigma_{1,N})(i,j),i\right)$
	$\displaystyle\eta_{N}=\top\circ\omega_{N}$

Lemma 4.5(i) gives that (13) holds true if $f(i,j)\neq g(i,j)$ , so it suffices to show (13) for $(i,j,k,l)$ such that $(j,k)=\omega_{N}(l,i)$ , which, since $i\neq j$ implies $\omega_{N}=\text{Id}_{N}$ , $i=k$ and $j=l$ . It suffices then to show that

(14)

\displaystyle\big{|}\{(i,j)\in[N]^{2}:\ \sigma_{1,N}(i,j)=\top\circ\sigma_{3,N}(i,j)\}|=o(N^{2})

holds true almost surely for $(\sigma_{1,N})_{N},(\sigma_{3,N})_{N}\in\{(\text{Id}_{N})_{N},(\tau_{N})_{N}\}$ .

If one of $(\sigma_{1,N})_{N},(\sigma_{3,N})_{N}$ is $(\tau_{N})_{N}$ , and the other is $(\text{Id}_{N})_{N}$ , then the conclusion follows from Lemma 4.3(i). If $\sigma_{1,N}=\sigma_{3,N}$ , then equation (14) gives that $(i,j)\in\sigma_{3,N}^{-1}(\{(t,t):t\in[N]\})$ , hence there are at most $N$ possible choices for $(i,j)$ , and the conclusion follows.

Finally, suppose that $(\sigma_{3,N})_{N}\in S$ . Then let $\sigma_{3,N}=\omega_{N}\circ\sigma_{N}\circ\omega_{N}$ with $(\omega_{N})_{N}$ either the identity permutation or the matrix transpose. For tuples $(i,j,k,l)$ with $j=l$ , according to Lemma 4.3, the condition $\sigma_{1,N}(i,j)=\sigma_{3,N}(k,l)$ is satisfied by $o(N^{2})$ tuples for any $(\sigma_{1,N})_{N}$ almost surely $(\sigma_{N})_{N}$ .

Let $D_{1}=\{(i,j,k,l)\in[N]^{4}:\ \{i,k\}\cap\{j,l\}=\emptyset\textrm{ and }j\neq l\}$ and define the random variable

\displaystyle I_{i,j,k,l}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{if }\sigma(i,j)=\top\circ\omega_{N}\circ\sigma\circ\omega_{N}(k,l)\textrm{ and }\sigma(j,k)=\top\circ\sigma_{4,N}(l,i)\\ 0&\textrm{otherwise}.\end{array}\right.

Using Markov Inequality and Lemma 2.6, the result is implied by

\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D_{1}}I_{i,j,k,l}\big{)}=O(N^{0}).

On the other hand, for $I_{i,j,k,l}(\sigma)=1$ , there is one possible choice for $\sigma(\omega_{N}(k,l))$ and $\sigma(j,k)$ and $(N^{2}-2)!$ possible choices for the rest of the values of $\sigma$ . Therefore

\displaystyle\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D_{1}}I_{i,j,k,l}\big{)}<N^{4}\cdot\frac{(N^{2}-2)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

For case (c), we can suppose, without loss of generality, that $\sigma_{1,N}=\text{Id}_{N}$ and $\sigma_{3,N}=\sigma_{N}$ . I.e. we have to show that

(15)

\displaystyle\big{|}\{(i,j,k,l):\ \sigma_{N}(k,l)=(j,i)\textrm{ and }\sigma_{2,N}(j,k)=\top\circ\sigma_{4,N}(l,i)\}\big{|}=o(N^{2})

holds true almost surely for $(\sigma_{N})_{N}$ where ( $s=1,2$ ) $\sigma_{s,N}=\omega_{s,N}\circ\sigma_{N}\circ\omega_{s,N}$ and $(\omega_{s,N})_{N}$ is either identity transforms or matrix transposes.

As discussed above, (15) is trivially verified if $i=j$ , $j=k$ or $i=l$ . Furthermore, if $k=i$ , or $l=j$ , then (15) follows applying Lemma 4.3(i) for the condition $\sigma_{N}(k,l)=(j,i)$ . Hence, denoting $D_{2}=\{(i,j,k,l)\in[N]^{4}:\ i,j,k,l\textrm{ distinct}\}$ it suffices to show that (15) holds true for $(i,j,k,l)\in D_{2}$ ,

Define the random variable on $\mathcal{S}([N]^{2})$ :

\displaystyle J_{i,j,k,l}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(k,l)=(j,i)\textrm{ and }\sigma_{1,N}(j,k)=t\circ\sigma_{2,N}(l,i)\\ 0&\textrm{ otherwise }\end{array}\right.

where $\sigma_{s,N}=\omega_{s,N}\circ\sigma\circ\omega_{s,N}$ for $s=1,2$ .

As before it suffices to show that $\displaystyle\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D_{2}}J_{i,j,k,l}\big{)}=O(N^{0})$ .

Note that if $(i,j,k,l)\in D_{2}$ , then $(k,l)$ , $\omega_{1,N}(j,k)$ and $\omega_{2,N}(l,i)$ are distinct. Hence, for $J_{i,j,k,l}\neq 1$ , there is one possible choice for $\sigma(k,l)$ , $N^{2}-1$ possible choices for $\sigma(\omega_{1,N}(j,k))$ , one possible choice for $\sigma(\omega_{2,N}(l,i))$ and $(N^{2}-3)!$ possible choices for the rest of values of $\sigma$ . Therefore

\displaystyle\mathbb{E}\big{(}\sum_{(i,j,k,l)\in D_{2}}J_{i,j,k,l}\big{)}<N^{4}\cdot\frac{(N^{2}-1)\cdot(N^{2}-3)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}1.

Next, suppose that $m>4$ . As in the proof of Theorem 3.1, it suffices to show that $\mathfrak{a}(\{1,b,b+1,m\})<0$ , i.e. that the following result holds true for any $(\sigma_{s,N})_{N}\in S\cup T_{1}$ , where $s\in\{1,b,b+1,m\}$ :

(16)		$\displaystyle\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\ \sigma_{1,N}(i,j)=$	$\displaystyle\top\circ\sigma_{b+1,N}(k,l)\textrm{ and }$
		$\displaystyle\sigma_{b,N}(a,k)=\top\circ\sigma_{m,N}(b,i)\}\big{\|}=o(N^{3}).$

We shall prove the statement above by analysing the same cases (a), (b) and (c) as in the setting $m=4$ .

For case (a), via a circular permutation of the set $[m]$ and taking adjoints, we can suppose that $(\sigma_{b,N})_{N}=(\sigma_{N})_{N}$ . Putting

	$\displaystyle\phi(i,j,a)$	$\displaystyle=(a,k)=(a,\pi_{1}\circ\sigma_{b+1,N}^{-1}\cdot\top\cdot\sigma_{1,N}(i,j))$
	$\displaystyle\psi(i,j,b)$	$\displaystyle=\sigma_{m,N}(b,i)$

note that $\phi(i,j,a)=\phi(i^{\prime},j^{\prime},a^{\prime})$ and $\psi(i,j,b)=\psi(i^{\prime},j^{\prime},b^{\prime})$ implies $(i,a,b)=(i^{\prime},a^{\prime},b^{\prime})$ , and the conclusion follows from Lemma 4.4(ii).

For case (b) we can assume, without loss of generality, that $(\sigma_{1,N})_{N}\in T_{1}$ and $(\sigma_{b,N})_{N}\in S$ . It suffices to distinguish two subcases, when $(\sigma_{b+1,N})_{N}\in S$ , respectively when $(\sigma_{m,N})_{N}\in S$ .

Suppose that $(\sigma_{m,N})_{N}\in S$ , that is $\sigma_{m,N}=\omega_{N}\circ\sigma_{N}\circ\omega_{N}$ with $\omega_{N}$ either the identity or the matrix transpose. Applying Lemma 4.5(ii) for $h(i,j)=k=\pi_{1}\circ\sigma_{b+1,N}^{-1}\circ\sigma_{1,N}(i,j)$ , we obtain that relation (16) with the extra condition $(a,k)\neq\omega_{N}(b,i)$ is satisfied for all $(\sigma_{1,N})_{N},(\sigma_{b+1,N})_{N}\in T_{1}$ and almost surely for $(\sigma_{N})_{N}\in S$ .

Assume that $(a,k)=\omega_{N}(b,i)$ . If $\omega_{N}=\text{Id}_{N}$ , then the equality $\sigma_{b,N}(a,k)=t\circ\sigma_{m,N}(b,i)$ gives that $\sigma_{N}(a,k)=t\circ\sigma_{N}(a,k)$ , hence $(a,k)\in\sigma_{N}^{-1}\{(s,s):s\in[N]\}$ so there are at most $N^{2}$ possible choices for $(a,k,l)$ , which uniquely determines $(i,j,k,l,a,b)$ . If $\omega_{N}$ is the matrix transpose, then the equality $\sigma_{b,N}(a,k)=\top\circ\sigma_{m,N}(b,i)$ gives that $\sigma_{N}(a,k)=\sigma_{N}(k,a)$ , that is $a=k$ , so again there are at most $N^{2}$ possible choices for the triple $(a,k,l)$ .

Suppose that $(\sigma_{b+1,N})_{N}\in S$ , that is $\sigma_{b+1,N}=\omega_{N}\circ\sigma_{N}\circ\omega_{N}$ with $\omega_{N}$ either the identity or the matrix transpose. Applying Lemma 4.6, we obtain that relation (16) with the extra condition $(a,k)\neq\omega_{N}(k,l)$ is satisfied for all $(\sigma_{1,N})_{N},(\sigma_{b+1,N})_{N}\in T_{1}$ and almost surely for $(\sigma_{N})_{N}\in S$ .

Assume that $(a,k)=\omega_{N}(k,l)$ . Then $(a,k,l)$ is uniquely determined by $(a,k)$ . But $(i,j,k,l,a,b)$ is uniquely detemined by $(a,k,l)$ , so (16) follows.

For case (c), we can assume that $\sigma_{1,N}=\text{Id}_{N}$ and $\sigma_{b+1,N}=\sigma_{N}$ . I.e. we have to show that the following relation holds true almost surely for $(\sigma_{N})_{N}$ :

(17)		$\displaystyle\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\ \sigma_{N}(k,l)=(j,i)\textrm{ and }\sigma_{b,N}(a,k)=\top\circ\sigma_{m,N}($	$\displaystyle b,i)\}\big{\|}$
		$\displaystyle=o(N^{3})$

where $\sigma_{b,N}=\omega_{1,N}\circ\sigma_{N}\circ\omega_{1,N}$ and $\sigma_{m,N}=\omega_{2,N}\circ\sigma_{N}\circ\omega_{2,N}$ with $(\omega_{s,N})_{N}$ either the identity permutation or the matrix transpose.

Note that given $(\sigma_{N})_{N}$ , the tuple $(i,j,k,l,a,b)$ is uniquely determined by either of the triples $(k,l,a)$ and $(k,l,b)$ hence property (17) is verified under one of the extra conditions $(k,l)\in\{\omega_{1,N}(a,k),\omega_{2,N}(b,i)\}$ .

If $\omega_{1,N}(a,k)=\omega_{2,N}(b,i)=(u,v)$ , then $\sigma_{2,N}(a,k)=\top\circ\sigma_{4,N}(b,i)$ gives that $\omega_{1,N}(\sigma_{N}(u,v))=\top\circ\omega_{2,N}(\sigma_{N}(u,v))$ , so either $\omega_{1,N}=\top\circ\omega_{2,N}$ or $\top\circ\sigma_{N}(u,v)=\sigma_{N}(u,v)$ . But $\omega_{1,N}=\top\circ\omega_{2,N}$ , gives $(k,a)=(b,i)$ , so $(i,j,k,l,a,b)$ is uniquely determined by $(k,l)$ . Also, if $\top\circ\sigma_{N}(u,v)=\sigma_{N}(u,v)$ , then there are at most $N$ possible choices for $\sigma(u,v)$ , that is for $(a,k)$ so there are at most $N^{2}$ possible choices for $(k,l,a)$ .

Denote $V=\{(i,j,k,l,a,b)\in[N]^{6}:\ (k,l),\omega_{1,N}(a,k),\omega_{2,N}(b,i)\textrm{ distinct}\}$ .

Consider the random variable

\displaystyle J^{a,b}_{i,j,k,l}(\sigma)=\left\{\begin{array}[]{ll}1&\textrm{ if }\sigma(k,l)=(j,i)\textrm{ and }\sigma_{1}(a,k)=\top\circ\sigma_{2}(b,i)\\ 0&\textrm{ otherwise }\end{array}\right.

where $\sigma_{1}=\omega_{1}\circ\sigma\circ\omega_{1}$ and $\sigma_{2}=\omega_{2}\circ\sigma\circ\omega_{2}$ , and applying Markov Inequality and Lemma 2.6, it suffices to show that

(18)

\displaystyle N^{-4}\mathbb{E}\big{(}(\sum_{V}J_{i,j,k,l}^{a,b})^{2}\big{)}=O(N^{0}).

For $J^{a,b}_{i,j,k,l}(\sigma)\neq 0$ there is one possible choice for $\sigma(k,l)$ , less than $N^{2}$ possible choices for $\sigma(\omega_{1,N}(a,k))$ , one choice for $\sigma(\omega_{2,N}(b,i))$ and $(N^{2}-3)!$ possible choices for the other values of $\sigma$ . Therefore

\displaystyle N^{-4}\cdot\mathbb{E}\big{(}\sum_{V}(J_{i,j,k,l}^{a,b})^{2}\big{)}=N^{-4}\cdot\mathbb{E}\big{(}\sum_{V}J_{i,j,k,l}^{a,b}\big{)}<N^{-4}\cdot N^{6}\frac{N^{2}\cdot(N^{2}-3)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0.

To simplify the writing, let us denote by $\vec{v}=(i,j,k,l,a,b)$ , $\vec{v}^{\prime}=(i^{\prime},j^{\prime},k^{\prime},l^{\prime})$ , $Z(\vec{v})=\{(k,l),\omega_{1,N}(a,k),\omega_{2,N}(b,i)\}$ and $Z(\vec{v}^{\prime})=\{(k^{\prime},l^{\prime}),\omega_{1,N}(a^{\prime},k^{\prime}),\omega_{1,N}(b^{\prime},i^{\prime})\}$ . Note that if $Z(\vec{v})=Z(\vec{v}^{\prime})$ , then $(k,l,a)=(k^{\prime},l^{\prime},a^{\prime})$ , so $\vec{v}=\vec{v}^{\prime}$ .

Denoting

	$\displaystyle W=\big{\{}(\vec{v},\vec{v}^{\prime})\in V^{2}:\ \vec{v}\neq\vec{v}^{\prime}\big{\}}$
	$\displaystyle W_{1}=\big{\{}(\vec{v},\vec{v}^{\prime})\in W:\ Z(\vec{v})\cap Z(\vec{v}^{\prime})=\emptyset\big{\}}$
	$\displaystyle W_{2}=\big{\{}(\vec{v},\vec{v}^{\prime})\in W:\ \|Z(\vec{v})\cap Z(\vec{v}^{\prime})\|=1\big{\}}$
	$\displaystyle W_{3}=\big{\{}(\vec{v},\vec{v}^{\prime})\in W:\ \|Z(\vec{v})\cap Z(\vec{v}^{\prime})\|=2\big{\}}$

it follows that

\displaystyle\mathbb{E}\big{(}\sum_{W}J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}})=\sum_{s=1}^{3}\mathbb{E}\big{(}\sum_{W_{s}}J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}}\big{)}

Let us remind that, as discussed above, for $J^{a,b}_{i,j,k,l}(\sigma)\neq 0$ , there are at most $N^{2}$ possible choices for $\sigma(Z(\vec{v}))$ . So, for $J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}}(\sigma)\neq 0$ there are at most $N^{4}$ possible choices for $\sigma(Z(\vec{v})\cup Z(\vec{v}^{\prime}))$ and at most $(N^{2}-|Z(\vec{v})\cup Z(\vec{v}^{\prime})|)!$ possible choices for the rest of the values of $\sigma$ , therefore

\displaystyle\mathbb{E}\big{(}\sum_{W_{s}}J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}}\big{)}\leq|W_{s}|\cdot N^{-4}\cdot\frac{N^{4}\cdot(N^{2}-|Z(\vec{v})\cup Z(\vec{v}^{\prime})|)!}{N^{2}!}

but $|Z(\vec{v})\cup Z(\vec{v}^{\prime})|=6-|Z(\vec{v})\cap Z(\vec{v}^{\prime})|$ , so it suffices to show that

(19)

\displaystyle\log_{N}|W_{s}|<12-2|Z(\vec{v})\cap Z(\vec{v}^{\prime})|.

For $s=1$ , we have that $W_{1}\in V\times V\in[N]^{12}$ , so (19) holds true. For $s=2$ , since $|Z(\vec{v})\cap Z(\vec{v}^{\prime})|=1$ , at least two components of $\vec{v}$ are equal to two components of $\vec{v}^{\prime}$ , hence $|W_{2}|\leq N^{10}$ , which implies (19).

If $s=3$ , note that all subsets with two elements of $Z(\vec{v})$ contain four components of $\vec{v}$ , thus (19) being satisfied, except for $\{(k,l),\omega_{1,N}(a,k)\}$ If $\{(k,l),\omega_{1,N}(a,k)\}=\{(k^{\prime},l^{\prime}),\omega_{1,N}(a^{\prime},k^{\prime})\}$ , then, for $J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}}(\sigma)\neq 0$ , there are at most $N^{2}$ possible choices for $\sigma(Z(\vec{v}))$ , each giving one possible choice for $\sigma(\{(k,l),\omega_{1,N}(a,k)\})$ , Hence for $\sigma(Z(\vec{v}^{\prime}))$ and $(N^{2}-4)!$ possible choices for the rest of the values of $\sigma$ . Therefore, denoting $W_{4}=\big{\{}(\vec{v},\vec{v}^{\prime})\in W:\ \{(k,l),(a,k)\}=\{(k^{\prime},l^{\prime}),(a^{\prime},k^{\prime})\}\big{\}}$ , we have that

\displaystyle\mathbb{E}\big{(}\sum_{W_{4}}J_{i,j,k,l}^{a,b}\cdot J_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}^{a^{\prime},b^{\prime}}\big{)}<N^{9}\cdot N^{-4}\cdot\frac{N^{2}\cdot(N^{2}-4)!}{N^{2}!}\xrightarrow[N\rightarrow\infty]{}0,

and the conclusion follows. ∎

5. Joint Infinitesimal Distribution of a Gaussian Random Matrix and its Transpose

In this section, we investigate the their joint infinitesimal distribution of Gaussian random matrix and its transpose, we describe their joint infinitesimal free cumulants in the following theorem. In particular, we show that Gaussian random matrix and its transpose are not asymptotically infinitesimally free.

Theorem 5.1.

For each positive integer $N$ , consider $G_{N}$ a complex Gaussian random matrix and $G_{N}^{\top}$ its matrix transpose. The asymptotic values (as $N\rightarrow\infty$ ) of the infinitesimally free joint cumulants of $G_{N}$ and $G_{N}^{\top}$ are computed according to the following rule (here each $\varepsilon_{j}$ is either the identity or the matrix transpose):

\displaystyle\lim_{N\rightarrow\infty}\kappa^{\prime}_{p}(G_{N}^{\varepsilon_{1}},G_{N}^{\varepsilon_{2}},\dots,G_{N}^{\varepsilon_{p}})=\left\{\begin{array}[]{ll}1&\textrm{ if }p=2m,\varepsilon_{s}\neq\varepsilon_{m+s},\textrm{ for }s\in[m]\\ 0&\textrm{ otherwise. }\end{array}\right.

Before proceeding with the proof of the Theorem above, notice that simple computations give the following particular cases of Lemmata 4.4, 4.5, 4.6.

Remark 5.2.

Suppose that for $1\leq s\leq 4$ , $\sigma_{s,N}$ is either the identity or the matrix transpose in $\mathcal{S}([N]^{2})$ and denote

	$\displaystyle C_{1}(\sigma_{1},\dots,\sigma_{4})=\big{\|}\{(i,j,k,l)\in[N]^{4}:\,$	$\displaystyle\sigma_{1}(i,j)=\top\circ\sigma_{3}(k,l),$
		$\displaystyle\sigma_{2}(j,k)=\top\circ\sigma_{4}(l,i)\}\}\big{\|}$
	$\displaystyle C_{2}(\sigma_{1},\dots,\sigma_{4})=\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\,$	$\displaystyle\sigma_{1}(i,j)=\top\circ\sigma_{3}(k,l),$
		$\displaystyle\sigma_{2}(a,k)=\top\circ\sigma_{4}(b,i)\}\big{\|}.$

Then

\displaystyle C_{1}(\sigma_{1},\dots,\sigma_{4})=\left\{\begin{array}[]{ll}N^{2}&\textrm{ if }\sigma_{1}\neq\sigma_{3}\textrm{ and }\sigma_{2}\neq\sigma_{4}\\ N&\textrm{ otherwise,}\end{array}\right.

and

\displaystyle C_{2}(\sigma_{1},\dots,\sigma_{4})=\left\{\begin{array}[]{ll}N^{3}&\textrm{ if }\sigma_{1}\neq\sigma_{3}\textrm{ and }\sigma_{2}\neq\sigma_{4}\\ N^{2}&\textrm{ otherwise.}\end{array}\right.

Proof.

Since the identity commutes with the transpose, for $1\leq s,t\leq 4$ , we have that $\sigma_{s}^{-1}\circ\top\circ\sigma_{t}(i,j)=\left\{\begin{array}[]{ll}(i,j)&\textrm{ if }\sigma_{s}\neq\sigma_{t}\\ (j,i)&\textrm{ if }\sigma_{s}=\sigma_{t}.\end{array}\right.$ . So, if $\sigma_{1}\neq\sigma_{3}$ and $\sigma_{2}\neq\sigma_{2}$ , then

	$\displaystyle C_{1}(\sigma_{1},\dots,\sigma_{4})$	$\displaystyle=\big{\|}\{(i,j,k,l)\in[N]^{4}:\ (i,j)=(k,l),\ (j,k)=(l,i)\}\big{\|}$
		$\displaystyle=\big{\|}\{(i,j,k,l)\in[N]^{4}:\ i=k,\ j=l\}\big{\|}=N^{2}$

and

	$\displaystyle C_{2}(\sigma_{1},\dots,\sigma_{4})$	$\displaystyle=\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\ (i,j)=(k,l),\ (a,k)=(b,i)\}\big{\|}$
		$\displaystyle=\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\ i=k,\ j=l,\ a=b\}\big{\|}=N^{3}.$

If $\sigma_{1}=\sigma_{3}$ , then $i=l$ and $j=k$ , hence $\sigma_{2}(j,k)=\sigma_{4}(l,i)$ gives that $i=j=k=l$ , that is $C_{1}(\sigma_{1},\dots,\sigma_{4})=N$ . Also, $\sigma_{2}(a,k)=\sigma_{4}(b,i)$ gives that $(b,i)=\sigma_{4}^{-1}\circ\sigma_{2}(a,j)$ , so $(i,j,k,l,a,b)$ is uniquely determined by $(a,j)$ , that is $C_{2}(\sigma_{1},\dots,\sigma_{4})=N^{2}$ . The argument for the case $\sigma_{2}=\sigma_{4}$ is similar. ∎

Lemma 5.3.

Let $n,N$ be a positive integers and suppose that for each $s\in[n]$ , $\sigma_{s}$ is either the identity or the matrix transpose in $\mathcal{S}([N]^{2})$ . Denote $\overrightarrow{\sigma}=(\sigma_{1},\dots,\sigma_{n})$ , and, with the notations from Section 2, write

\displaystyle\mathbb{E}\circ\mathrm{tr}\big{(}G_{N}^{\sigma_{1}}\cdot G_{N}^{\sigma_{2}}\cdots G_{N}^{\sigma_{n}}\big{)}=\sum_{\pi\in P_{2}(n)}\mathcal{V}_{\overrightarrow{\sigma}}(\pi).

Also, write the set $P_{2}(m)$ as the disjoint union

\displaystyle P_{2}(n)=P_{2}(\overrightarrow{\sigma},0)\cup P_{2}(\overrightarrow{\sigma},1)\cup P_{2}(\overrightarrow{\sigma},2)

where

	$\displaystyle P_{2}(\overrightarrow{\sigma},0)$	$\displaystyle=\{\pi\in P_{2}(n):\ \pi\textrm{ is non-crossing and }\sigma_{s}=\sigma_{\pi(s)}\textrm{ for all }s\in[n]\}$
	$\displaystyle P_{2}(\overrightarrow{\sigma},1)$	$\displaystyle=\{\pi\in P_{2}(n):\ \textrm{ there exists some }B=\{i(1),i(2),\dots,i(2m)\}\subseteq[n]\textrm{ with }$
		$\displaystyle i(1)<\dots<i(2m)\textrm{ such that }\pi(i(s))=i(m+s)\textrm{ and }\sigma_{i(s)}\neq\sigma_{i(m+s)}$
		$\displaystyle\textrm{ and }\sigma_{k}=\sigma_{\pi(k)}\textrm{ whenever }k\in[n]\setminus B\textrm{ and the permutation }\sigma\vee 1_{B}$
		$\displaystyle\textrm{ ( obtained from $\sigma$ by considering $B$ as a block) is non-crossing}\big{\}}$
	$\displaystyle P_{2}(\overrightarrow{\sigma},2)$	$\displaystyle=P_{2}(n)\setminus(P_{2}(\overrightarrow{\sigma},0)\cup P_{2}(\overrightarrow{\sigma},1)).$

With the notations above, we have that:

(23)

\displaystyle\mathcal{V}_{\overrightarrow{\sigma}}(\pi)=\left\{\begin{array}[]{ll}1&\textrm{ if }\pi\in P_{2}(\overrightarrow{\sigma},0)\\ N^{-1}&\textrm{ if }\pi\in P_{2}(\overrightarrow{\sigma},1)\\ O(N^{-2})&\textrm{ if }\pi\in P_{2}(\overrightarrow{\sigma},2).\end{array}\right.

Proof.

As in (3) from the proof of Theorem 3.1, if $\pi(k)=k+1$ and $\sigma_{k}=\sigma_{k+1}$ , then $\mathcal{V}_{\overrightarrow{\sigma}}(\pi)=\mathcal{V}_{\overrightarrow{\sigma}^{\prime}}(\pi^{\prime})$ where $\pi^{\prime}$ and $\overrightarrow{\sigma}^{\prime}$ are obtained by removing $(k,k+1)$ respectively $\sigma_{k},\sigma_{k+1}$ from $\pi$ , respectively $\overrightarrow{\sigma}$ . If $\pi\in P_{2}(\overrightarrow{\sigma},0)$ then iterating (3) $n/2$ times gives the first part of (23). Moreover, if $\pi\notin P_{2}(\overrightarrow{\sigma},0)$ , then, (3) allows us to assume, without loss of generality that $\sigma_{k}\neq\sigma_{k+1}$ whenever $\pi(k)=k+1$ .

Under all the assumptions above, suppose first that $\pi$ is non-crossing. We shall prove (23) by induction on $n$ . If $n=2$ , then $\pi\in P_{2}(\overrightarrow{\sigma},1)$ and

\displaystyle\mathcal{V}_{\overrightarrow{\sigma}}(\pi)=N^{-2}\cdot\big{|}\{(i,j)\in[N]^{2}:\ \sigma_{1}(i,j)=\top\circ\sigma_{1}\circ\top(j,i)\}\big{|}=N^{-1},

hence (23) holds true.

If $n\geq 4$ , then $\pi\in P_{2}(\overrightarrow{\sigma},2)$ . On the other hand, since $\pi$ is non-crossing, it has at least one block which is a segment. Via a circular permutation of the set $[n]$ , we can suppose without loss of generality that $\pi(n-1)=n$ , which furthermore implies that $\sigma_{n-1}=\top\circ\sigma_{N}$ . Then the condition

\displaystyle\sigma_{n-1}(i_{n-1},j_{n-1})=\sigma_{n}\circ\top(i_{n},j_{n})

gives that $i_{n-2}=i_{n}$ . Therefore, denoting by $\pi^{\prime}$ , respectively by $\overrightarrow{\sigma}^{\prime}$ the restrictions of $\pi$ , respectively of $\overrightarrow{\sigma}$ to the set $[n-2]$ , we then have that

\displaystyle\mathfrak{a}_{\pi^{\prime},\overrightarrow{\sigma}^{\prime}}\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}}([n-2])

and

\displaystyle\mathfrak{a}_{\pi,\overrightarrow{\sigma}}\leq\mathfrak{a}_{\pi,\overrightarrow{\sigma}}([n-2])-1

hence (23) follows.

Next, suppose that $\pi$ is crossing. As in the proof of Theorem 3.1, we can assume that $\pi(1)=b+1$ and $\pi(b)=d$ for $1<b<b+1<d\leq n$ . If $d\neq n$ , then $\pi\in P_{2}(\overrightarrow{\sigma},2)$ and, as in the proof on Theorem 3.1, in this case we have that $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}\leq-2$ , so (23) holds true.

If $d=n$ and $\sigma_{1}=\sigma_{b+1}$ or $\sigma_{b}=\sigma_{d}$ , then again $\pi\in P_{2}(\overrightarrow{\sigma},2)$ ; Remark 5.2 and Lemma 2.5 give that $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}\leq-2$ , so (23) holds true.

Suppose that $d=n$ , $\sigma_{1}\neq\sigma_{b+1}$ , $\sigma_{b}\neq\sigma_{d}$ and if $\pi(k)=k+1$ we have that $\sigma_{k}\neq\sigma_{k+1}$ . If $n=4$ , then $\pi\in P_{2}(\overrightarrow{\sigma},1)$ , and Remark 5.2 gives that $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}=-1$ , so (23) holds true in this case. Suppose then that $n>4$ . If there is some $s\in\{2,\dots,b-1\}$ or $s\in\{b+2,\dots,n-1\}$ such that $\pi(s)=s+1$ , then $\pi\in P_{2}(\overrightarrow{\sigma},2)$ ; on the other hand, we assumed that $\sigma_{s}\neq\sigma_{s+1}$ so $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}(\{s,s+1\})=-1$ and Lemma 2.5 gives that $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}\leq-2$ so (23) holds true. The same argument remains valid if there exists $a^{\prime}<b^{\prime}<c^{\prime}<d^{\prime}$ elements either of $\{2,\dots,b-1\}$ or of $\{b+2,\dots,n-1\}$ such that $\pi(a^{\prime})=c^{\prime}$ and $\pi(b^{\prime})=d^{\prime}$ (see Figure 4). So we can further assume that $\pi([b])=[n]\setminus[b]$ , in particular $n=2b$ .

Note that the condition $\pi([b])=[n]\setminus[b]$ gives that $A_{\pi,\overrightarrow{\sigma}}=A_{\pi,\overrightarrow{\sigma}}([b])$ . Furthermore, since $\pi(1)=b+1$ and $\sigma_{1}\neq\sigma_{b+1}$ we have that $i_{b+1}=i_{1}$ , so $A_{\pi,\overrightarrow{\sigma}}([b])=A_{\pi,\overrightarrow{\sigma}}([b-1])$ .

If $\pi\in P_{2}(\overrightarrow{\sigma},1)$ , then

	$\displaystyle A_{\pi,\overrightarrow{\sigma}}$	$\displaystyle=\{(i_{1},i_{2},\dots,i_{2b})\in[N]^{2b}:(i_{s},i_{s}+1)=(i_{m+s},i_{m+s}+1),i_{2b}=i_{1}\}$
		$\displaystyle=\{(i_{1},i_{2},\dots,i_{b})\in[N]^{b}\},$

and since $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}=\log_{N}\big{|}A_{\pi,\overrightarrow{\sigma}}\big{|}-b-1$ it follows that (23) holds true.

Figure 8.

If $\pi\in P_{2}(\overrightarrow{\sigma},2)$ , then the set $\{s\in[b]:\ \pi(s)\neq b+s\textrm{ or }\sigma_{s}\neq\sigma_{b+s}\}$ is non-void. Denote by $t$ its smallest element. Then $\pi(t-1)=m+t-1$ and $\sigma_{t-1}\neq\sigma_{m+t-1}$ so $i_{t}=i_{m+t}$ . Let $v=\pi(m+t)$ . Then $v\in[b-1]\setminus\{t-1\}$ . and $i_{t}=i_{m+t}\in\{i_{v},i_{v+1}\}$ . If $v\neq t$ , then $v\neq t\neq v+1$ . If $v=t$ , using that $\sigma_{t}=\sigma_{m+t}$ we get $i_{t}=i_{t+1}$ . Either way, there is some $w\in[b-1]\setminus\{t\}$ such that $(i_{1},\dots,i_{b})\in A_{\pi,\overrightarrow{\sigma}}([b-1])$ implies that $i_{w}=i_{t}$ , hence $\big{|}A_{\pi,\overrightarrow{\sigma}}([b-1])\big{|}\leq b-1$ , that is $\mathfrak{a}_{\pi,\overrightarrow{\sigma}}\leq-2$ , and the conclusion follows.

∎

Proof of Theorem 5.1.

Since for each $s\leq n$ , we have that the sequence $(\sigma_{s,N})_{N}$ is either the sequence of identity permutations or the sequence of matrix transposes, we can simplify the writing by omitting the index $N$ and writing $\sigma_{s}$ for $\sigma_{s,N}$ . With this convention, it suffices to show that

	$\displaystyle\lim_{N\rightarrow\infty}\big{[}\mathbb{E}\circ\textrm{Tr}(G_{N}^{\sigma_{1}}\cdots G_{N}^{\sigma_{n}})-N\lim_{N\rightarrow\infty}\mathbb{E}\circ\mathrm{tr}(G_{N}^{\sigma_{1}}\cdots G_{N}^{\sigma_{n}})\big{]}$
	$\displaystyle=\sum_{\rho\in NC(n)}\big{[}\sum_{\begin{subarray}{c}B\in\rho\\ B=(i(1),\dots,i(p))\end{subarray}}\kappa^{\prime}_{p}(\sigma_{i(1)},\dots,\sigma_{i(p)})\cdot\prod_{\begin{subarray}{c}D\in\rho\setminus\{B\}\\ D=(j(1),\dots,j(r))\end{subarray}}\kappa_{r}(\sigma_{j(1)},\dots,\sigma_{j(r)})\big{]}$

where

\displaystyle\kappa_{r}(\sigma_{1},\dots,\sigma_{r})=\left\{\begin{array}[]{ll}1&\textrm{ if }r=2\textrm{ and }\sigma_{1}=\sigma_{2}\\ 0&\textrm{ otherwise}\end{array}\right.

and

\displaystyle\kappa^{\prime}_{p}(\sigma_{1},\dots,\sigma_{p})=\left\{\begin{array}[]{ll}1&\textrm{ if }p=2m\textrm{ and }\sigma_{s}\neq\sigma_{m+s}\textrm{ for }s\in[m]\\ 0&\textrm{ otherwise.}\end{array}\right.

On the other hand, from Lemma 5.3, we have that

\displaystyle\mathbb{E}\circ\mathrm{tr}(G_{N}^{\sigma_{1}}\cdots G_{N}^{\sigma_{m}})=\big{|}P_{2}(\overrightarrow{\sigma},0)\big{|}+\frac{1}{N}\big{|}P_{2}(\overrightarrow{\sigma},1)\big{|}+O(N^{-2})

which gives

	$\displaystyle\lim_{N\rightarrow\infty}\big{[}\mathbb{E}\circ\textrm{Tr}(G_{N}^{\sigma_{1}}\cdots G_{N}^{\sigma_{m}})-N\lim_{N\rightarrow\infty}\mathbb{E}\circ\mathrm{tr}(G_{N}^{\sigma_{1}}\cdots G_{N}^{\sigma_{m}})\big{]}$	$\displaystyle=\big{\|}P_{2}(\overrightarrow{\sigma},1)\big{\|}$
		$\displaystyle=\sum_{\rho\in NC(n)}\chi_{P_{2}(\overrightarrow{\sigma},1)}(\rho)$

where $\displaystyle\chi_{P_{2}(\overrightarrow{\sigma},1)}(\rho)=\left\{\begin{array}[]{ll}1&\textrm{ if }\rho\in P_{2}(\overrightarrow{\sigma},1)\\ 0&\textrm{ otherwise.}\end{array}\right.$

But the definition of $P_{2}(\overrightarrow{\sigma},1)$ reads

\chi_{P_{2}(\overrightarrow{\sigma},1)}(\rho)=\sum_{\begin{subarray}{c}B\in\rho\\ B=(i(1),\dots,i(p))\end{subarray}}\kappa^{\prime}_{p}(\sigma_{i(1)},\dots,\sigma_{i(p)})\cdot\prod_{\begin{subarray}{c}D\in\rho\setminus\{B\}\\ D=(j(1),\dots,j(r))\end{subarray}}\kappa_{r}(\sigma_{j(1)},\dots,\sigma_{j(r)})

and the conclusion follows.

∎

Acknowledgement

We would like to thank the anonymous referee for careful reading of the manuscript, and for important remarks which led to an improvement of this paper.

References

[1] G. Aubrun, S. Szarek, and E. Werner. Hastings’s additivity counterexample via dvoretzky’s theorem. Communications in mathematical physics, 305(1):85–97, 2011.
[2] T. Banica and I. Nechita. Asymptotic eigenvalue distributions of block-transposed wishart matrices. Journal of Theoretical Probability, 26(3):855–869, 2013.
[3] S. T. Belinschi, H. Bercovici, and M. Capitaine. On the outlying eigenvalues of a polynomial in large independent random matrices. Int. Math. Res. Not. IMRN, 2021(4):2588–2641, 2021.
[4] S. T. Belinschi, T. Mai, and R. Speicher. Analytic subordination theory of operator-valued free additive convolution and the solution of a general random matrix problem. J. Reine Angew. Math., 732:21–53, 2017.
[5] S. T. Belinschi and D. Shlyakhtenko. Free probability of type b: analytic interpretation and applications. American Journal of Mathematics, 134(1):193–234, 2012.
[6] P. Biane, F. Goodman, and A. Nica. Non-crossing cumulants of type b. Transactions of the American Mathematical Society, 355(6):2263–2303, 2003.
[7] A. Celestino, K. Ebrahimi-Fard, and D. Perales. Relations between infinitesimal non-commutative cumulants. Doc. Math., 26:1145–1185, 2021.
[8] S. Dallaporta and M. Fevrier. Fluctuations of linear spectral statistics of deformed Wigner matrices. arXiv preprint arXiv:1903.11324, 2019.
[9] T. Damour, S. De Buyl, M. Henneaux, and C. Schomblond. Einstein billiards and overextensions of finite-dimensional simple lie algebras. Journal of High Energy Physics, 2002(08):030, 2002.
[10] M. Fevrier. Higher order infinitesimal freeness. Indiana University Mathematics Journal, pages 249–295, 2012.
[11] M. FPei’evrier and A. Nica. Infinitesimal non-crossing cumulants and free probability of type B. Journal of Functional Analysis, 258(9):2983–3023, 2010.
[12] T. Hasebe. Differential independence via an associative product of infinitely many linear functionals. Colloq. Math., 124(1):79–94, 2011.
[13] M. Horodecki, P. Horodecki, and R. Horodecki. Separability of n-particle mixed states: necessary and sufficient conditions in terms of linear maps. Physics Letters A, 283(1-2):1–7, 2001.
[14] S. Janson. Gaussian Hilbert spaces, volume 129 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1997.
[15] C. Male, J. A. Mingo, S. Péché, and R. Speicher. Joint global fluctuations of complex Wigner and deterministic matrices. Random Matrices Theory Appl., 11(2):Paper No. 2250015, 46, 2022.
[16] A. Mandarino, T. Linowski, and K. Lun.Zyczkowski. Bipartite unitary gates and billiard dynamics in the weyl chamber. Physical Review A, 98(1):012335, 2018.
[17] J. A. Mingo. Non-crossing annular pairings and the infinitesimal distribution of the GOE. Journal of the London Mathematical Society, 100(3):987–1012, 2019.
[18] J. A. Mingo and M. Popa. Freeness and the transposes of unitarily invariant random matrices. Journal of Functional Analysis, 271(4):883–921, 2016.
[19] J. A. Mingo and M. Popa. Freeness and the partial transposes of wishart random matrices. Canadian Journal of Mathematics, 71(3):659–681, 2019.
[20] J. A. Mingo and M. Popa. The partial transpose and asymptotic free independence for Wishart random matrices, II. Pacific J. Math., 317(2):387–421, 2022.
[21] J. A. Mingo, M. Popa, and K. Szpojankowski. On the partial transpose of a Haar unitary matrix. Studia Math., 266(3):337–359, 2022.
[22] J. A. Mingo, M. Popa, and K. Szpojankowski. Asymptotic $*$ -distribution of permuted Haar unitary matrices. Indiana Univ. Math. J., 72(3):927–967, 2023.
[23] J. A. Mingo and J. Vazquez-Becerra. The asymptotic infinitesimal distribution of a real wishart random matrix. arXiv preprint arXiv:2112.15231, 2021.
[24] M. Popa. Asymptotic free independence and entry permutations for Gaussian random matrices. Proc. Amer. Math. Soc., 150(8):3379–3394, 2022.
[25] D. Shlyakhtenko. Free probability of type-B and asymptotics of finite-rank perturbations of random matrices. Indiana University Mathematics Journal, 67(2):971–991, 2018.
[26] P.-L. Tseng. Operator-valued infinitesimal multiplicative convolutions. arXiv preprint arXiv:2201.13187, 2022.
[27] P.-L. Tseng. A unified approach to infinitesimal freeness with amalgamation. Internat. J. Math., 34(13):Paper No. 2350079, 26, 2023.
[28] D. Voiculescu. Addition of certain non-commuting random variables. Journal of functional analysis, 66(3):323–346, 1986.
[29] D. Voiculescu. Limit laws for random matrices and free products. Invent. Math., 104(1):201–220, 1991.
[30] D. V. Voiculescu, K. J. Dykema, and A. Nica. Free random variables, volume 1 of CRM Monograph Series. American Mathematical Society, Providence, RI, 1992. A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups.

	$\displaystyle\mathbb{P}\big{(}\sup_{1\leq i\leq N}\big{\|}\{(j,k)\in[N]^{2}$	$\displaystyle:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}$
	$\displaystyle\leq$	$\displaystyle\sum_{i=1}^{N}\mathbb{P}\big{(}\big{\|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(i,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}$
	$\displaystyle=$	$\displaystyle N\cdot\mathbb{P}\big{(}\big{\|}\{(j,k)\in[N]^{2}:\ \sigma_{N}(a,j)=\top\circ\sigma_{N}(j,k)\}\big{\|}>N^{\theta}\cdot\varepsilon\big{)}.$

	$\displaystyle C_{1}(\sigma_{1},\dots,\sigma_{4})=\big{\|}\{(i,j,k,l)\in[N]^{4}:\,$	$\displaystyle\sigma_{1}(i,j)=\top\circ\sigma_{3}(k,l),$
		$\displaystyle\sigma_{2}(j,k)=\top\circ\sigma_{4}(l,i)\}\}\big{\|}$
	$\displaystyle C_{2}(\sigma_{1},\dots,\sigma_{4})=\big{\|}\{(i,j,k,l,a,b)\in[N]^{6}:\,$	$\displaystyle\sigma_{1}(i,j)=\top\circ\sigma_{3}(k,l),$
		$\displaystyle\sigma_{2}(a,k)=\top\circ\sigma_{4}(b,i)\}\big{\|}.$

Asymptotic free independence and entry permutations for Gaussian random matrices. Part II: infinitesimal freeness

Abstract.

1. Introduction

2. Preliminaries

2.1. Infinitesimal Free Probability

Definition 2.1.

Definition 2.2.

Theorem 2.3.

2.2. Permutations for Gaussian Random Matrices

Definition 2.4.

Lemma 2.5.

2.3. Basic probabilistic tools

Lemma 2.6.

3. The generic permuted Gaussian random matrix has zero infinitesimal distribution

Theorem 3.1.

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

Proof of Theorem 3.1.

4. Asymptotic Infinitesimal Freeness Relations

Theorem 4.1.

Remark 4.2.

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

Lemma 4.5.

Proof.

Lemma 4.6.

Proof.

Proof of Theorem 4.1 .

5. Joint Infinitesimal Distribution of a Gaussian Random Matrix and its Transpose

Theorem 5.1.

Remark 5.2.

Proof.

Lemma 5.3.

Proof.

Proof of Theorem 5.1.

Acknowledgement

References

Asymptotic free independence and entry permutations for Gaussian random matrices.
Part II: infinitesimal freeness