Random sorting networks: edge limit

The main object in this article is the uniformly random sorting network which we abbreviate as RSN. Let us start by giving basic definitions. Consider the permutation group of $n$ elements $\mathfrak{S}_{n}$. We use the one-row notation for the elements of $\mathfrak{S}_{n}$ representing them as sequences $(a_{1}\ a_{2}\ ...\ a_{n})$. We let $\tau_{k}$ be the adjacent swap $(k,k+1)$, $1\leq k\leq n-1$, so that

A sorting network of size $n$ is a shortest sequence of swaps, whose product equals the reverse permutation $(n\ n-1\ ...\ 2\ 1)$. By counting inversions in permutations, one shows that the length $N$ of such shortest sequence is $N=\binom{n}{2}$. Let $\Omega_{n}$ denote the set of all sorting networks of size $n$. Thus, elements of $\Omega_{n}$ are sequences $(s_{1},\dots,s_{N})$ such that

Sorting networks can be drawn as wiring diagrams, see Figure 1. Whenever $s_{t}=k$, we say that swap $(k,k+1)$ occurs at time $t$; in the wiring diagram this corresponds to two wires intersecting at the point $(t,k+\tfrac{1}{2})$.

The study of sorting networks is a fruitful topic, with the first mathematical results going back to [S] where Stanley computed the number of elements in $\Omega_{n}$:

A recent point of interest is the study of uniformly random sorting networks initiated by Angel, Holroyd, Romik, and Virag in [AHRV]. The probabilistic results can be split into two groups: global and local. On the global side, [AHRV] proved that the density of swaps approximates the semi-circle law¹¹1There is no known direct connection to the Wigner semi-circle law of the random matrix theory and the match seems coincidental. as $n\to\infty$; [AHRV] predicted and [DVi, D] proved (among other results) that individual trajectories in the wiring diagram become (random) sine curves; see also [K, RVV] for related results.

Our paper belongs to the second group of results, [AGH, R, ADHV, GR], which studies local limits. The most basic local characteristic of the sorting network is spacing in row $k$, which is a distance between two occurrences of the same swap $s_{i}=k$ in the sorting network, cf. Figure 1. [R] and [GR] discovered a link between the asymptotic laws of spacings as $n\to\infty$ and random matrix theory. Namely, [R] matched the asymptotic law of the spacing in row $1$ with the distance between two eigenvalues of $2\times 2$ matrix of Gaussian Orthogonal Ensemble (GOE) of real symmetric random matrices. [GR] dealt with spacings in row $\alpha n$ with $0<\alpha<1$ and showed that after proper rescaling they converge to the Gaudin–Mehta law, which is the universal asymptotic law for spacings between eigenvalues of real symmetric matrices of very large sizes.

Comparing the results of [R] and [GR], we see that the former links the spacings in the extreme row (i.e. at the end-point of the edge) to $2\times 2$ real symmetric matrices, while the latter links the spacings in the bulk rows to the real symmetric matrices of infinite sizes. The observed gap in the asymptotics between $2\times 2$ and $\infty\times\infty$ matrices motivated the central question of our paper: we would like to understand, whether distributions related to $k\times k$ random matrices can be also found in the asymptotic laws for random sorting networks.

The answer presented in this text is both Yes and No. On one side, we are so far unable to find any connections of sorting networks to eigenvalues of real symmetric $k\times k$ matrices (which would be the most direct interpolation between [R] and [GR]). On the other hand, by slightly adjusting our point view, we find that the law of the asymptotic spacing in row $k$ can be expressed in terms of the eigenvalues of $2k\times 2k$ random anti-symmetric Gaussian matrices — they are known in the literature as aGUE, since their analysis reveals connections to the tools used for the Gaussian Unitary Ensemble²²2However, up to multiplication by $\mathbf{i}$, matrix elements of aGUE are real, rather than complex., see [M, Chapter 13] and [FN].

Here is the precise definition of the random matrix object appearing in our asymptotic results.

Note that the eigenvalues of $M_{\ell}$ are real and come in pairs: $\lambda$ is an eigenvalue if and only if so is $-\lambda$. When $\ell$ is odd, $M_{\ell}$ is necessary degenerate, i.e. it has a zero eigenvalue; for even $\ell$, zero is not an eigenvalue almost surely.

We also would like to deal with eigenvalues of all $M_{\ell}$ together.

The determinantal structure for the distribution of eigenvalues of $M_{2k}$ (see [M, Chapter 13] and [FN]) leads to an expression for the distribution of $\mathbf{T}(k)$ as a series, which can be identified with a Fredholm determinant:

where $K^{(k)}$ is a correlation kernel, expressed through the Hermite polynomials $H_{i}(x)$ as

Here we use the “physicist’s normalization”, so that $H_{i}(x)$, $i=0,1,\dots$, is a polynomial of degree $i$ with leading coefficient $2^{i}$ and such that

We can now state our first theorem.

In order to connect the first swaps to the spacings, we are going to use translation invariance of the random sorting networks (cf. [AHRV, Theorem 1, (i)]), which is based on the following combinatorial fact:

Applying Proposition 1.6 one readily proves that for all $1\leq r\leq r+t\leq N$,

which can be used to identify the distribution of a spacing in row $k$. Before doing so, we need to specify the definition of a spacing. In fact, there are two natural definitions, which lead to distinct random variables. For the definition it is convenient to extend a sorting network to a $2N$–periodic $\mathbb{Z}$–indexed sequence:

For instance $(1\,2\,1)\in\Omega_{3}$ is extended to the infinite $\mathbb{Z}$–indexed sequence $(\dots 2\,1\,2\,1\,2\,\dots)$ with $1$s at odd positions and $2$s at even positions. The reason for this particular definition is contained in the following straightforward corollary of Proposition 1.6:

The $n\to\infty$ limit of $\mathrm{Sp}_{k,n}$ turns out to be connected to $\mathbf{T}(k)$ of Definition 1.4.

Here is an alternative definition of the spacing.

Both definitions of the spacing have their own merits. Definition 1.12 is the one preferred in theoretical physics and random matrix literature, and it has been used implicitly in [R], which studies the scaling limit of the spacing of RSN on the $1^{st}$ row. However, a disadvantage of Definition 1.12 is that it is hard to sample or observe $\widehat{\mathrm{Sp}}_{k,n}$, as it fails to be a random variable on the state space of all sorting networks; on the other hand, $\mathrm{Sp}_{k,n}$ is a function of a sorting network, and this is the definition used in [GR] which studies the limiting behavior of RSN in the bulk. The $n\to\infty$ limit of $\widehat{\mathrm{Sp}}_{k,n}$ is still connected to $\mathbf{T}(k)$ of Definition 1.4, but in a slightly different way.

In addition, we present an alternative expression for $\widehat{Z}_{k}$ by identifying it with a marginal of a certain two-dimensional determinantal point process; we refer to [B] and references therein for general discussion of the determinantal point processes.

Here is a sketch of our proof of Theorem 1.5:

• •

  The Edelman-Greene bijection [EG] maps the problem to the study of the asymptotic distribution of the entries of uniformly random standard Young tableau of staircase shape, see Section 4.2.

• •

  We replace standard Young tableau by a continuous version, which we call Poissonized Young tableau. In Section 3.2 we show that the error of this replacement is negligible in our limit regime.

• •

  We use the formula of [GR] for the correlation kernel of the determinantal point process, describing the entries of a Poissonized Young tableau.

• •

  Asymptotic analysis of this formula leads in Theorems 3.5 and 3.6 to the limiting process described in terms of double contour integral formulas for its correlation kernel.

• •

  Expanding the integrals in residues, performing resummations, and using the Gibbs (conditional uniformity) properties of the point processes under consideration, we reveal in Section 3.4 a match to the distribution of eigenvalues of aGUE matrices.

We remark that (in contrast to the results in the bulk, i.e., for $k$ of order $\alpha n$, $0<\alpha<1$, as in [GR, ADHV]) we do not claim any results for the joint asymptotic distribution of several swaps; Theorem 1.5 only deals with one-dimensional marginal distribution. A technical reason is that the Edelman-Green bijection does not have any straightforward continuous version acting on the eigenvalues of aGUE of finite sizes: it seems that one needs to deal simultaneously with aGUE of all sizes, which is not a particularly transparent operation. In future, it would be interesting to find a way to overcome this difficulty.

Theorems 1.11 and 1.14 are proven in Section 4 as corollaries of Theorem 1.5. The central idea is to develop discrete versions of (1.4), (1.5) valid for random sorting networks of finite sizes. In fact, these discrete statements are valid for any periodic point processes and, thus, can be of independent interest, see Proposition 4.2.

Finally, Theorem 1.18 is proven in Section 4 by repeating the arguments of Theorem 1.5 for the sorting networks conditional on the event $\{s_{1}=k\}$. This requires asymptotic analysis of entries of standard Young tableau of a slightly different shape, which is still possible by our methods. Thus, we arrive at the identities of Theorem 1.18 in an indirect way, by showing that the two sides of the identity are $n\to\infty$ limits of the same discrete distributions.

We thank the anonymous referee for helpful comments. The work of V.G. was partially supported by NSF Grants DMS-1664619, DMS-1949820, DMS-2246449, and by the Office of the Vice Chancellor for Research and Graduate Education at the University of Wisconsin–Madison with funding from the Wisconsin Alumni Research Foundation.

A partition is a sequence of non-negative integers $\lambda_{1}\geq\lambda_{2}\geq...\geq 0$ such that $|\lambda|:=\sum_{i=1}^{\infty}\lambda_{i}<\infty$. The length of $\lambda$, denoted by $l(\lambda)$, is the number of strictly positive $\lambda_{i}s$.

We identify a partition $\lambda$ with a collection of $N=|\lambda|$ boxes, such that there are $\lambda_{i}$ boxes in row $i$. We use coordinate $(i,j)$ to denote the j-th box at row i. In other words, the coordinates of boxes are $\{(i,j)\mid 1\leq j\leq\lambda_{i},\,i=1,2,\dots\}$. Such a combinatorial object is named a Young diagram, still denoted as $\lambda$. In particular, we say the Young diagram is of staircase shape and write $\lambda=\Delta_{n}$ for some $n\in\mathbb{Z}_{\geq 2}$, if $\lambda_{i}=n-i$ for $i=1,2,\dots,n$. We also use the diagram $\lambda=\Delta_{n}\setminus(n-k,k)$ for $1\leq k\leq n-1$, which has $\lambda_{i}=n-i$ for $i\neq n-k$ and $\lambda_{n-k}=k-1$.

A standard Young tableau (SYT) of shape $\lambda$ is an insertion of numbers 1,2,…,$|\lambda|$ into boxes of $\lambda$ without repetitions, such that the numbers in each row and column strictly increase from left to right and from top to bottom. The numbers within a SYT are its entries. Fixing the Young diagram $\lambda$, we can get a uniformly random SYT of shape $\lambda$, denoted as $\mathbf{T}_{\lambda}$ by considering a uniform measure on the space of all SYT of shape $\lambda$. See Figure 2 for an example with $\lambda=\Delta_{6}$.

A Poissonized Young tableau (PYT) of shape $\lambda$ is an insertion of $|\lambda|$ real numbers in $[0,1]$ into boxes of $\lambda$, such that the numbers strictly increase along each row and column. We use $\mathrm{PYT}(\lambda)$ to denote the space of all PYT of shape $\lambda$. Note that a given PYT of shape $\lambda$ can be transformed canonically to a SYT of the same shape, by replacing the k-th smallest entry with k. In the opposite direction, we can get a uniformly random PYT of shape $\lambda$, denoted as $\pazocal{T}_{\lambda}$ by the following steps: first generate a uniformly random SYT of shape $\lambda$, then independently sample $|\lambda|$ i.i.d. random variables uniform in [0,1], and replace the entry $k$ with the k-th smallest random variable.

Let $T_{\Delta_{n}}$ denote a standard Young tableau of shape $\Delta_{n}$. We make a change of coordinates $(i,j)\to(l,m)$ for the entries in $T_{\Delta_{n}}$ by letting

We let $T_{\Delta_{n}}(l,m)$ denote the entry of $T_{\Delta_{n}}$ on the $i^{\text{th}}$ row and the $j^{\text{th}}$ column, where $i$ and $j$ are reconstructed from $l$ and $m$ by inverting the above formulas. In more detail, we have

The allowed values for $(i,j)$ are: $i\geq 1$, $j\geq 1$, $i+j\leq n$. The allowed values for $(l,m)$ are $l=2,3,4,\dots,2n-2$ and $m=1,2,\dots,\lfloor\frac{\min(l,2n-l)}{2}\rfloor$. The transformation $(i,j)\to(l,m)$ is essentially a clockwise rotation by 45 degrees, as can be seen in Figure 2.

Similarly, for standard Young tableau $T_{\Delta_{n}\setminus(n-k,k)}$ we make the same change of coordinates as above and deal with $T_{\Delta_{n}\setminus(n-k,k)}(l,m)$. Formally, the entry at $(l,m)=(2k,1)$ does not exist, because it corresponds to the removed box at $(n-k,k)$, but we can also think about this entry as being $N={n\choose 2}$; in this way $T_{\Delta_{n}\setminus(n-k,k)}$ becomes $T_{\Delta_{n}}$ with the additional restriction $T_{\Delta_{n}}(2k,1)=N$.

For Poissonized Young tableau (PYT) $\pazocal{T}_{\lambda}$ of shapes $\lambda=\Delta_{n}$ or $\lambda=\Delta_{n}\setminus(n-k,k)$, we define the change of coordinate in exactly the same way and use $(m,l)$ coordinate system.

Let $\pazocal{T}_{\lambda}$ be a $\mathrm{PYT}$ of shape $\lambda$. As in Section 2.2, we will focus on the case $\lambda=\Delta_{n}$ or $\lambda=\Delta_{n}\setminus(n-k,k)$, for which we induce a point process on $\mathbb{Z}_{\geq 0}\times\mathbb{R}_{\geq 0}$ from its entries.

By definition, $u=1-\pazocal{T}(l,m)$ is the $m^{\text{th}}$ lowest particle on level $\{l\}\times\mathbb{R}_{\geq 0}$ (except for level $l=2k$ in $\pazocal{T}_{\Delta_{n}\setminus(n-k,k)}$, where $\pazocal{T}(2k,1)$ is missing), and the particles on neighboring levels interlace by the setting of PYT, see Figure 3.

If we take $\pazocal{T}_{\lambda}$ to be uniformly random, then the projection of $\pazocal{T}_{\lambda}$ becomes a point process on $\mathbb{Z}_{\geq 0}\times[0,1]$. Note that this random point configuration is simple almost surely. We also would like to rescale the $u$–coordinate.

We study the asymptotic behavior of $\pazocal{X}_{n}^{{}^{\prime}}$ and $\pazocal{X}^{{}^{\prime}}_{k,n}$ in Section 3.3. Our analysis uses the technique of determinantal point processes with correlation kernels given by double contour integrals, which we present next.

Here’s a brief review of some standard definitions, for a thorough introduction see [B, DVe]. Let $S$ be a locally compact Polish space, say $\mathbb{Z}$ or $\mathbb{R}^{n}$. We consider the space of discrete subsets in $S$, which consists of countable subsets $X$ of $S$ without accumulation points, and identify each such point configuration with the measure $\sum_{x\in X}\delta_{x}$. The topology of this space is given as the weak topology of Radon measures on $S$. We further use Borel $\sigma-$algebra corresponding to this topology.

A point process is a random discrete subset of $S$, and we assume that it is simple a.s, i.e, all the points have distinct positions. A determinantal point process $\pazocal{X}$ on $S$ is a point process with correlation kernel $K:S\times S\rightarrow\mathbb{R}$, and a reference measure $\mu$ on $S$, such that for any $f:S^{k}\rightarrow\mathbb{R}$ with compact support,

Expectations of the form given by the l.h.s. of (2.1) determine the law of $\pazocal{X}$ under mild conditions on $K$, see [Le]. This will always be the case in this text as the correlation kernels we consider will be continuous.

The determinantal point processes appearing in this paper live in space $S=\mathbb{Z}\times[0,1]$ or $S=\mathbb{Z}\times\mathbb{R}_{\geq 0}$, with reference measure being the product of counting measure and Lebesgue measure, denoted by $\#_{\mathbb{Z}}\times\pazocal{L}([0,1])$ or $\#_{\mathbb{Z}}\times\pazocal{L}(\mathbb{R}_{\geq 0})$ resp. We use the following lemma, whose proof we omit, see [DVe], [Le].

When $\mathrm{PYT}$ $\pazocal{T}_{\Delta_{n}}$ and $\pazocal{T}_{\Delta_{n}\setminus(n-k,k)}$ are uniformly random, their projections are point processes on $\mathbb{Z}_{\geq 0}\times[0,1]$, whose correlation functions were computed in [GR]. We restate the result there for our case in the following theorem, which is a stepping stone of the proofs of our main results.

Let us recall a statement from [FN, Theorems 2.9 and 3.3]: