Harold Widom’s work in random matrix theory

Abstract

This is a survey of Harold Widom’s work in random matrices. We start with his pioneering papers on the sine-kernel determinant, continue with his and Craig Tracy’s groundbreaking results concerning the distribution functions of random matrix theory, touch on the remarkable universality of the Tracy–Widom distributions in mathematics and physics, and close with Tracy and Widom’s remarkable work on the asymmetric simple exclusion process.

1. Introduction

The distributions of random matrix theory govern the statistical properties of a wide variety of large systems which do not obey the usual laws of classical probability. Such systems appear in many different areas of applied science and technology, including heavy nuclei, polymer growth, high-dimensional data analysis, and certain percolation processes. The four distribution functions play a particularly important role in the mathematical apparatus of random matrices. The first one describes the emptiness formation probability in the bulk of the spectrum of a large random matrix, and it is explicitly given in terms of the sine-kernel Fredholm determinant. The second, the third, and the forth distributions are given in terms of the Airy kernel Fredholm determinant, and they describe the edge fluctuations of the eigenvalues in the large size limit of the matrices taken from the three classical Gaussian ensembles, unitary (GUE), orthogonal (GOE), and symplectic (GSE). The last three of these distributions are known now as the Tracy–Widom distribution functions.

A key analytical observation concerning the distribution functions of random matrix theory, which was made on many occasions in the papers 567101112, is that they satisfy certain nonlinear integrable PDEs. This property, which generalizes the first result of this type established in JMMS for the sine-kernel determinant, follows in turn from a remarkable Fredholm determinant representation for the random matrix distributions. The existence of such representations in several important examples beyond the sine-kernel case was also first shown in the above-mentioned papers.

What follows is an overview of the principal contributions of Harold Widom to random matrix theory. We start with his papers 3 and 9 on the sine-kernel determinant, which brought mathematical rigor to the theory of this, the first universal distribution function of random matrix theory.

2. The sine-kernel determinant

Let $J = \bigcup _{k=0}^{n}J_k = \bigcup _{k=0}^{n}(a_k, b_k)$ be a union of $n+1$ disjoint intervals in $\mathbb{R}$. Consider the Fredholm determinant

$$\begin{equation*} P_x= \det \left( 1 - K_{\text{sine}}\right), \end{equation*}$$

where $K_{\text{sine}}$ is the trace class operator in $L_2\Bigl (J; dz\Bigr )$ with kernel

$$\begin{equation*} K_{\text{sine}}(z,z') = \frac{\sin x(z-z')}{\pi (z-z')}. \end{equation*}$$

The determinant $P_x$ plays a central role in random matrix theory. Indeed, it is the probability of finding no eigenvalues in the union of intervals $\frac{xJ}{\pi } \coloneq \bigcup _{k=0}^{n}\left(\frac{xa_k}{\pi }, \frac{xb_k}{\pi }\right)$ for a random Hermitian matrix chosen from the Gaussian unitary ensemble (GUE), in the bulk scaling limit with mean spacing 1 (see Meh and Figure 1). Moreover, in the one interval case, the second derivative of $P_x$ describes the distribution of normalized spacings of eigenvalues of large random GUE matrices (see, e.g., Dei1). The determinant $P_x$ also appears in quantum and statistical mechanics. For instance, it describes the emptiness formation probability in the one-dimensional impenetrable Bose gas Len and the gap probability in the one-dimensional Coulomb gas, at inverse temperature $\beta = 2$ (see, e.g., Dys1). The key analytical issue related to $P_x$ is its large $x$ behavior, i.e., the large gap asymptotics. Harold Widom made major contributions to the resolution of this question.

In the one interval case, $n =0$, after rescaling and translation, we may assume $J = (-1, 1)$. For this case, in 1973, des Cloizeaux and Mehta dCM showed that as $x\to \infty$,

$$\begin{equation} \ln P_x=-{x^2\over 2} -{1\over 4}\ln x+ c_0 +o(1), {\tag{2.1}} \end{equation}$$

for some constant $c_0$. In 1976 Dyson Dys2 showed that $P_x$ in fact has a full asymptotic expansion of the form

$$\begin{equation} \ln P_x=-{x^2\over 2} -{1\over 4}\ln x+ c_0 +{a_1\over x}+ {a_2\over x^2}+\cdots . {\tag{2.2}} \end{equation}$$

Dyson identified all the constants $c_0$, $a_1$, $a_2$, $\dots$. Of particular interest is the constant $c_0$, which he found to be

$$\begin{equation} c_0={1\over 12}\ln 2+ 3\zeta '(-1), {\tag{2.3}} \end{equation}$$

where $\zeta (z)$ is the Riemann zeta-function. It should be noted that Dyson obtained this result using one of the early results of Widom 1 on the asymptotics of Toeplitz determinants with symbols supported on circular arcs.

The results in dCM and Dys2 were not fully rigorous. In 3, using an adaptation of Szegő’s classical method to the continuous analogues of orthogonal polynomials (the so-called Krein functions), Widom gave the first rigorous proof of the leading asymptotics in 2.1 in the form

$$\begin{equation} \ln P_x=-{x^2\over 2}(1+o(1)) \tag{2.4} \end{equation}$$

as $x \to \infty$. Actually, Widom proved a slightly stronger result,

$$\begin{equation*} \frac{d}{dx}\ln P_x = -x + O(1) \end{equation*}$$

as $x \to \infty$. In addition, Widom computed the leading asymptotics of the quantity $\operatorname {tr}\left( (1- K_{\text{sine}})^{-1}K_{\text{sine}}\right)$, which is the ratio of the probability that there is at most one eigenvalue in the interval $\left(\frac{-x}{\pi }, \frac{x}{\pi }\right)$ to $P_x$. In the subsequent paper 9, Widom considered the multi-interval case, $n > 0$, and showed that as $x \to \infty$,

$$\begin{equation*} \frac{d}{dx}\ln P_x = c_1 x + c_2(x) + o(1), \end{equation*}$$

where $c_1$ is a negative constant and $c_2(x)$ is a certain bounded oscillatory function of $x$, which was described up to the solution of a Jacobi inversion problem.⁠¹ The method of 9 is a further development of the approach in 3. As in 3, Widom also computes the leading asymptotics of $\operatorname {tr}\left( (1- K_{\text{sine}})^{-1}K_{\text{sine}}\right)$.

¹

An explicit formula for $c_2(x)$, in terms of the Riemann theta-function, was obtained later in DIZ.

✖

The formula 2.3 for $c_0$ in Dys2 was in the form of conjecture: A rigorous proof of 2.3 was only given in 2004. In fact, two proofs of this formula were given independently in Kra and Ehr. It is remarkable that the proof of 2.3 in Kra again uses (in conjunction with the nonlinear steepest descent method) Widom’s computation in 1.

3. The Tracy–Widom distribution functions

The joint probability densities of the eigenvalues of random matrices from the GOE, GUE, and GSE ensembles are given by

$$\begin{equation} P_{N\beta }(\lambda _1, \dots , \lambda _N) = Z^{-1}_{N\beta }\,e^{-\frac{1}{2}\beta \sum _{j=1}^{N}\lambda ^{2}_j} \prod _{j<k}|\lambda _j - \lambda _k|^{\beta }, {\tag{3.1}} \end{equation}$$

where $Z_{N\beta }$ is a normalization constant (or partition function) and

$$\begin{equation*} \beta \coloneq \begin{cases} 1 & \text{for GOE},\\ 2 & \text{for GUE},\\ 4 & \text{for GSE}. \end{cases} \end{equation*}$$

The famous Tracy–Widom distribution functions, commonly denoted as $F_{\beta }(t)$, describe the edge fluctuation of the eigenvalues in the large $N$ limit. They are defined via the scaling limits,

$$\begin{equation} F_{\beta }(t) = \lim _{N\to \infty }\operatorname {Prob} \bigl ((\lambda _{\max } -\sqrt {2N})2^{1/2}N^{1/6} \leq t\bigl ), {\tag{3.2}} \end{equation}$$

where $\lambda _{\max }$ is the largest eigenvalue drawn from the ensembles with density 3.1. The central theme of the series of papers 5671012 is the following analytical description of these distributions, which links them to the theory of integrable systems.

Let $K_{\text{Airy}}$ be the trace-class operator in $L_2\bigl ((t, \infty ); dz\bigr )$ with kernel

$$\begin{equation} K_{\text{Airy}}(z, z') = \frac{\operatorname {Ai}(z)\operatorname {Ai}'(z') - \operatorname {Ai}'(z)\operatorname {Ai}(z')}{z - z'}, {\tag{3.3}} \end{equation}$$

where $\operatorname {Ai}(z)$ is the Airy function,

$$\begin{equation*} \operatorname {Ai}(z) = \frac{1}{2\pi }\int _{-\infty }^{\infty }e^{-\frac{i}{3}s^3 - izs}ds. \end{equation*}$$

Then, the $\beta =2$ Tracy–Widom distribution, $F_{2}(t)$, is given by the Airy-kernel Fredholm determinant (see For),

$$\begin{equation} F_{2}(t) = \det \left(1 - K_{\text{Airy}}\right). {\tag{3.4}} \end{equation}$$

Moreover, as shown in 6, the following formula is valid for the Fredholm determinant on the right-hand side of 3.4:

$$\begin{equation} \det (1 - K_{\text{Airy}}) = \exp \left\{ - \int _{t}^{\infty }(s-t)u^2(s)ds\right\}, {\tag{3.5}} \end{equation}$$

where $u(x)$ is the Hastings–McLeod solution of the second Painlevé equation, i.e., the solution of the ODE

$$\begin{equation} u_{tt} = tu +2u^3, {\tag{3.6}} \end{equation}$$

uniquely determined by the boundary condition,

$$\begin{equation} u(t) = \frac{1}{2\sqrt {\pi }}t^{-1/4}e^{-\frac{2}{3}t^{3/2}}(1 + o(1)), \quad t \to +\infty . {\tag{3.7}} \end{equation}$$

Similar Painlevé representations for the other two Tracy–Widom distribution functions (see 10) have the form

$$\begin{equation} F_{1}(t) = F_{2}^{1/2}(t)E(t), \quad F_{4}(t) = \frac{1}{2}\left\{E(t) + \frac{1}{E(t)}\right\}F_{2}^{1/2}(t), {\tag{3.8}} \end{equation}$$

where

$$\begin{equation*} E(t) = \exp \left\{ - \frac{1}{2}\int _{t}^{\infty }u(s)ds\right\}, \end{equation*}$$

and $u(x)$ is the same Hastings–McLeod solution to the second Painlevé transcendent.⁠² Painlevé equations are integrable in the sense of Lax pairs, which, in particular, implies that their solutions admit a Riemann–Hilbert (RH) representation. A Riemann–Hilbert representation can be viewed as the nonabelian analogue of the familiar integral representations of the classical special functions, such as the Bessel functions, the Airy function, etc. A key consequence of the RH representation is that the Painlevé functions possess one of the principal features of a classical special function—a mechanism, viz. the nonlinear steepest descent method, to evaluate explicitly relevant asymptotic connection formulae (see, e.g., FIKN). Specifically, in the case of the Hastings–McLeod solution, the integrability of the second Painlevé equation underlies the fact that, in addition to the asymptotic behavior 3.7 at $t = +\infty$, one also knows the asymptotic behavior of $u(t)$ at $t = -\infty$, which is described in HaMc⁠³ as

²

A similar representation for the sine-kernel determinant (involving, this time, a special solution of the fifth Painlevé equation) was given earlier in JMMS.

✖

³

Hastings and McLeod derived 3.9 using the inverse scattering transform which was a precursor of the Riemann–Hilbert method.

✖

$$\begin{equation} u(t) = \sqrt {-\frac{t}{2}} + O\Bigl ((-t)^{-5/2}\Bigr ), \quad t \to -\infty . {\tag{3.9}} \end{equation}$$

Herein lies the importance of the Tracy–Widom formulae 3.5 and 3.8—they provide the key distribution functions of random matrix theory with explicit representations that are amenable to detailed asymptotic analysis.

An immediate corollary of formula 3.5 (and the known asymptotics 3.9 of the Painlevé function) is an explicit formula for the large negative $t$ behavior of the distribution function $F_{2}(t)$:

$$\begin{equation} \ln F_2(t) = \frac{t^3}{12} - \frac{1}{8}\ln (- t )+ c_0 + o(1), \quad t \to -\infty . {\tag{3.10}} \end{equation}$$

The value of the constant $c_0$ was conjectured by Tracy and Widom in the paper 6 to be the same as for the sine-kernel determinant, which is given by

$$\begin{equation} c_0 = \frac{1}{24}\ln 2 + \zeta '(-1), {\tag{3.11}} \end{equation}$$

where $\zeta (s)$ is the Riemann zeta-function.⁠⁴

⁴

This conjecture was independently proved in DIK and BBD. Also, in BBD, similar asymptotic results were established for the other two Tracy–Widom distributions.

✖

Another important advantage of the Tracy–Widom formula 3.8 is that it makes it possible to design, using the exact connection formula 3.7, 3.8, 3.9, a very efficient scheme (see Die, DBT) for the numerical evaluation⁠⁵ of the distribution functions $F_{\beta }$.

⁵

It should be noted that the Hastings–McLeod solution is very unstable; indeed, a small change in the pre-exponential numerical factor in the normalization condition 3.7 yields a completely different type of behavior of $u(x)$ for negative $x$, including the appearance of singularities (e.g., see again FIKN). Herein lies the importance of the knowledge of the behavior 3.9 in order to adjust the numerical procedure appropriately. Said differently, knowledge of the connection formulae makes it possible to transform an unstable ODE initial value problem into a stable ODE boundary value problem.

✖

The appearance of the Painlevé equations in the Tracy–Widom formulae is not accidental. As follows from results in 7, the connection to integrable systems is already encoded in the determinant formula 3.4. Indeed, the Airy-kernel integral operator belongs to a class of integral operators with kernels of the form

$$\begin{equation} K(z,z') = \frac{\phi (z)\psi (z') - \psi (z)\phi (z') }{z-z'}, {\tag{3.12}} \end{equation}$$

acting in $L_{2}(J)$, where $J$ is a union of intervals,

$$\begin{equation*} J = \bigcup _{k=1}^{l}[a_{2k-1}, a_{2k}], \end{equation*}$$

and $\phi (z)$, $\psi (z)$ are $C^{1}$-functions. This class of integral operators has appeared frequently in many applications related to random matrices and statistical mechanics.⁠⁶ In 7, it is shown that if the functions $\phi (z)$ and $\psi (z)$ satisfy a linear differential equation,

⁶

An integral operator with kernel 3.12 is a special case of a so-called integrable Fredholm operator, i.e., an integral operator whose kernel is of the form

$$\begin{equation*} K(z,z') = \frac{\sum _{j=1}^{m}f_j(z)h_{j}(z')}{z-z'}, \quad z, z' \in C, \end{equation*}$$

with some functions $f_{j}(z)$ and $h_{j}(z)$ defined on a contour $C$. This type of integral operator was singled out as a distinguished class in IIKS (see also Dei2; in a different context, unrelated to integrable systems, these operators were also studied in the earlier work Sak). A crucial property of a kernel 3.13 is that the associated resolvent kernel is again an integrable kernel. Moreover, the functions “$f$” and “$h$” corresponding to the resolvent are determined via an auxiliary matrix Riemann–Hilbert problem whose jump-matrix is explicitly constructed in terms of the original $f, h$-functions.

✖

$$\begin{equation*} \frac{d}{dz}\begin{pmatrix} \phi (z)\\ \psi (z)\end{pmatrix} =\Omega (z)\begin{pmatrix} \phi (z)\\ \psi (z)\end{pmatrix}, \end{equation*}$$

where

$$\begin{equation*} \Omega (z) = \frac{1}{m(z)}\begin{pmatrix} A(z)&B(z)\\ C(z)&-A(z)\end{pmatrix}, \end{equation*}$$

and $m(z)$, $A(z)$, $B(z)$, and $C(z)$ are polynomials, then the Fredholm determinant, $\det (1 - K)$, can be expressed in terms of the solution to a certain system of nonlinear partial differential equations with the end points $a_j$ as independent variables. This system is integrable in the sense of Lax,⁠⁷ and in the case of the Airy kernel it reduces to a single ODE—the second Painlevé equation.

⁷

The Lax-integrability of the Tracy–Widom system associated with the kernel 3.12 was proven in Pal, where this system was identified as a special case of isomonodromy deformation equations and the Fredholm determinant $\det (1-K)$ was identified as the corresponding $\tau$-function.

✖

In 8, the results of 7 were extended to the general $m\times m$ case, that is, to the kernels of the form

$$\begin{equation} K(z,z') = \frac{\sum _{j,i=1}^{m}c_{ij}\phi _j(z)\phi _{i}(z')}{z-z'}, {\tag{3.13}} \end{equation}$$

acting in $L_{2}(J)$. Here, $J$ is, as before, a union of intervals, the constant matrix $C \equiv \{c_{ij}\}$ is antisymmetric, and $\phi _j(z)$ are $C^{1}$-functions satisfying the linear differential equation

$$\begin{equation} m(z)\frac{d\phi (z)}{dz} = \Omega (z)\phi (z), \quad \phi (z) \coloneq \begin{pmatrix} \phi _1(z)\\ \phi _2(z)\\ .\\ .\\ .\\ \phi _m(z)\end{pmatrix}, {\tag{3.14}} \end{equation}$$

where $m(z)$ is a scalar polynomial while $\Omega (z)$ is a matrix with polynomial entries connected to the matrix $C$ by

$$\begin{equation*} \Omega ^{T}(z)C + C\Omega (z) =0. \end{equation*}$$

The main result of 8 is the derivation, for such operators $K$, of a system of PDEs, with the $a_j$ as independent variables, whose solution determines the logarithmic derivatives of $\det (1-K)$ with respect to $a_j$.

Figure 2.

Harold and his wife, Linda Larkin, at Lake Sonoma in 2013. Photo courtesy of Craig Tracy.

4. Universality of the Tracy–Widom distributions

A remarkable fact is that the Tracy–Widom distribution functions $F_{\beta }(z)$ appear in a large and growing number of applications in random matrix theory as well as in areas beyond random matrices. In this section we will describe some of these applications.

4.1. General invariant ensembles and the Wigner ensembles

The GUE, GOE, and GSE ensembles are, respectively, particular examples of unitary (UE), orthogonal (OE), and symplectic (SE) ensembles of random matrix theory. The joint probability density of the eigenvalues for these ensembles are given by (cf. 3.1)

$$\begin{equation} P_{N \beta }(\lambda _1, \dots , \lambda _N) = Z^{-1}_{N\beta }\,e^{-\eta _{\beta }\sum _{j=1}^{N}V(\lambda _j)} \prod _{j<k}|\lambda _j - \lambda _k|^{\beta }, {\tag{4.1}} \end{equation}$$

where $\eta _{1}=1$, $\eta _{2} = 1$, $\eta _4 = 2$ (this reflects the fact that the eigenvalues of self-dual Hermitian matrices come in pairs), and the potential $V(\lambda )$ is a polynomial with even leading term,

$$\begin{equation} V(\lambda ) = \sum _{k=1}^{2m}t_k\lambda ^k, \quad t_{2m} > 0. {\tag{4.2}} \end{equation}$$

(More general potential functions are also allowed.) GUE, GOE, and GSE correspond to the choice $V(\lambda ) = \lambda ^2$. Consider again the upper edge fluctuations of the spectrum. Edge-universality states that for a given polynomial potential $V(\lambda )$ there exist scalars $z_N^{(\beta )}$ and $s_{N}^{(\beta )}$ such that

$$\begin{equation} \lim _{N\to \infty }\operatorname {Prob}\left(\frac{\lambda _{\text{max}} -z^{(\beta )}_N}{s^{(N)}_{N}} \leq t\right) = F_{\beta }(t), {\tag{4.3}} \end{equation}$$

where $F_{\beta }(t)$, $\beta = 1, 2, 4$ are exactly the same Tracy–Widom distribution functions as in 3.2. For $\beta = 2$ this result was obtained in DKMVZ1DKMVZ2 and for $\beta = 1, 4$ in DeGi1DeGi2. It should be noted that the authors of DeGi1DeGi2 based their analysis on Widom’s papers 1112 where important relations between symplectic, orthogonal, and unitary ensembles were established for finite $N$. These relations allowed the authors of DeGi1DeGi2 to use, in the symplectic and orthogonal cases, the asymptotic estimates previously obtained in DKMVZ2 for the unitary ensembles. There are also a variety of universality results for eigenvalues in the bulk of the spectrum (see, e.g., Dei3 and references therein) for UE, OE, and SE.

Complementary to the invariant ensembles (UE, OE, and SE) are the so-called Wigner matrix ensembles, i.e., random matrices with independent identically distributed entries. Tracy–Widom edge universality for these ensembles is also valid, and this important fact was proved by Soshnikov Sos. In addition, universality in the bulk of the spectrum for the Wigner ensembles is now established; see, e.g., Erd for a comprehensive survey of the results and a historical review.

The Tracy–Widom distribution appears also in Hermitian matrix models with varying weights. These are unitary ensembles with the potential $V(\lambda )$ in 4.1 replaced by $NV(\lambda )$. Universality results of the form 4.3 are also true for such scaled potentials (see, e.g., DKMVZ1, Dei3 and the references therein). For potentials $NV(\lambda )$ a key issue is the large $N$ asymptotics of the partition functions

$$\begin{equation} Z_N = \int _{-\infty }^{\infty }\cdots \int _{-\infty }^{\infty }e^{-N\sum _{j=1}^{N}V(\lambda _j)} \prod _{j<k}(\lambda _j - \lambda _k)^{2}d\lambda _1\cdots d\lambda _N. {\tag{4.4}} \end{equation}$$

Under certain regularity conditions, the leading large $N$ behavior of the partition function is described by the relation Joh1

$$\begin{equation} Z_N \sim e^{-N^2F_0},\quad N \to \infty , {\tag{4.5}} \end{equation}$$

where $F_0$ is the free energy of the model, and is given explicitly in terms of the equilibrium measure corresponding to the potential $V(\lambda )$. The equilibrium measure is the unique probability measure $\nu _{\text{eq}}$ which minimizes the energy functional

$$\begin{equation*} I_{V}(\nu ) = -\int \int _{\mathbb{R}^2}\ln |\lambda -\lambda '|d\nu (\lambda )d\nu (\lambda ') + \int _{\mathbb{R}}V(\lambda )d\lambda . \end{equation*}$$

The formula for the free energy reads

$$\begin{equation*} F_0 = I_{V}(\nu _{\text{eq}}). \end{equation*}$$

As shown in DKM, in the case that $V(\lambda )$ is real analytic and $\frac{V(\lambda )}{\ln |\lambda |} \to + \infty$ as $|\lambda | \to \infty$, the equilibrium measure is absolutely continuous and is supported on a finite number of intervals. The derivative of $\nu _{\text{eq}}$ coincides with the mean limiting density of eigenvalues of the associated UE. If the support of the equilibrium measure consists of one interval, then one can prove (see EM and also BI) the existence of a full asymptotic expansion,

$$\begin{equation} \ln \frac{Z_{N}}{Z_{N}^{\text{Gauss}}} \sim -N^2e_0 + \sum _{g=1}^{\infty }\frac{e_{g}}{N^{2g-2}}, \quad N \to \infty , {\tag{4.6}} \end{equation}$$

where $Z_{N}^{\text{Gauss}}$ stands for the partition function of GUE ( $V(\lambda ) = \lambda ^2$). Since 1980 the expansion 4.6 has played a prominent role in the application of random matrices to enumerative topology. This role was first recognized in BIZ together with the discovery of its deep connections to the counting of graphs on Riemann surfaces (see EM for more details).

The number of intervals in the support of the equilibrium measure depends on the values of the parameters $t_1, \dots , t_{2m}$ in 4.2. It is of great interest to study the transition regimes; i.e., regimes involving values of $t_j$ near critical values when the number of the intervals in the support of the equilibrium measure changes. The first example where one can observe this important critical phenomenon is the even quartic potential $V(\lambda ) = t_4\lambda ^4 + t_2\lambda ^2$. Up to a trivial renormalization, the potential $V$ can be chosen in the form

$$\begin{equation} V(\lambda ) = \frac{1}{4t^2}\lambda ^4 + \left(1-\frac{2}{t}\right)\lambda ^2. {\tag{4.7}} \end{equation}$$

For $t>1$ the support of the equilibrium measure corresponding to this potential consists of one interval. Moreover, as shown in BI, all the coefficients $e_{g}(t)$ of the asymptotic series 4.6, as functions of $t$, are real analytic on $[1, \infty )$. If $t <1$, the support becomes two intervals. At the critical value, $t = 1$, the support consists of one interval but the density function has a double zero inside the support at $\lambda =0$. The relevant double scaling limit near the critical point $t =1$ is prescribed by the scaling condition

$$\begin{equation} \Bigl |(t-1)N^{2/3}\Bigr | < C. {\tag{4.8}} \end{equation}$$

As $N \to \infty$ and $t \to 1$ satisfying 4.8, the partition function admits the following asymptotic representation BI:

$$\begin{equation} \frac{Z_N(t)}{Z^{\text{Gauss}}} = F_2\Bigl ((t-1)2^{2/3}N^{2/3}\Bigr )Z^{\text{reg}}_{N}(t)\Bigl (1 + O(N^{-1/3 + \epsilon })\Bigr ),\quad \epsilon >0, {\tag{4.9}} \end{equation}$$

where $\ln Z^{\text{reg}}_{N}$ is the sum of the first two terms of the series 4.6, i.e.,

$$\begin{equation*} Z^{\text{reg}}_{N}(t) = e^{-N^2e_0(t) + e_1(t)}, \end{equation*}$$

and $F_2(x)$ denotes, as before, the second Tracy–Widom distribution. Thus we see that in this context $F_2$ appears not as a distribution function but rather as a special factor describing the transition between the one interval and two interval asymptotic regime in the large $N$ limit of these partition functions. This gives $F_2$ added meaning in the realm of enumerative topology, not just probability. Although not yet proven, it is expected that equation 4.9 is universal.

4.2. Random permutations

Let $\pi = (\pi (1), \pi (2), \dots , \pi (N))$ be a permutation of the numbers $1, 2, \dots , N$. If $1 \leq i_1 < i_2 < \dots < i_k \leq N$ and $\pi ( i_1) < \pi ( i_2) < \dots < \pi (i_k)$, we say that $\pi ( i_1), \pi ( i_2), \dots ,\pi (i_k)$ is an increasing subsequence in $\pi$ of length $k$. Denote by $l_{N}(\pi )$ the maximal length of all of the increasing subsequences in $\pi$. Suppose that the permutations are random and uniformly distributed. The principal interest is in the limiting statistics of the random variable $l_{N}(\pi )$. This is a subject with a long history (see, e.g., AD) which started in the early 1960s with Ulam’s problem: prove that the following limit exists

$$\begin{equation} \lim _{N\to \infty }\frac{{\mathbb{E}}(l_N)}{\sqrt {N}} = c, {\tag{4.10}} \end{equation}$$

where ${\mathbb{E} (\cdot )}$ means mathematical expectation, and compute $c$. The proof of this result was obtained independently in VeKe and LoSh: It turns out that $c=2$. Further progress was obtained only after 22 years in BDJ, where it was shown that the random variable $\chi _{N} \coloneq \frac{l_N - 2\sqrt {N}}{N^{1/6}}$ converges in distribution to the second Tracy–Widom distribution $F_2(x)$, i.e.,

$$\begin{equation} \lim _{N \to \infty }\operatorname {Prob}\left(\frac{l_N - 2\sqrt {N}}{N^{1/6}} \leq t\right) = F_2(t) \quad \forall t \in {\mathbb{R}}. {\tag{4.11}} \end{equation}$$

In addition, the authors of BDJ proved convergence of moments:

$$\begin{equation} \lim _{N\to \infty }{\mathbb{E}}\Bigl (\chi _{N}^{m}\Bigr ) = {\mathbb{E}}\Bigl (\chi ^{m}\Bigr ) \quad \forall m = 1, 2, \dots \,. {\tag{4.12}} \end{equation}$$

It is worth noting that Harold Widom suggested in 14 an alternative proof of the convergence of the moments 4.12 based on the Borodin–Okounkov Fredholm determinant formula for Toeplitz determinants. The latter was first derived in BoOk, and has been proven extremely useful in the theory and application of Toeplitz determinants. There are now several different proofs of this formula and the first one (after the original proof of Borodin and Okounkov) was again suggested by Harold Widom jointly with Estelle Basor in 13. It is remarkable that this proof in turn is again based on one of the old papers of Widom 2. We also refer to the article by Basor, Böttcher, and Ehrhardt BBE in this volume for more details on the Borodin–Okounkov formula and its history and connection with Widom’s work on Toeplitz determinants. It is important to note that the Borodin–Okounkov formula was in fact discovered earlier by Geronimo and Case in GeCa, but its significance was overlooked at the time.

Random permutations appear in an enormous array of problems. Some of the most fundamental connections are with measures on Young diagrams, random growth processes, interacting particle systems, last passage percolation models, and with various tiling problems. Formula 4.11 and its generalizations for more complex types of permutations, which involve $F_{\beta }$ with $\beta = 1$ and $4$ as well (see BaRa), paved the way that brought the Tracy–Widom distribution functions into many areas of physics, mathematics, and engineering. We refer to the surveys Dei3Cor4 for a discussion of a wide variety of examples and a historical review.

We close this section by mentioning one remarkable generalization of the Ulam problem. Consider $N$-independent standard one-dimensional Brownian motions $B_1(t),B_2(t),\ldots , B_N(t)$, for $t\geq 0$. For $0\leq a<b$ let $B_i(a,b) = B_i(b)-B_i(a)$ denote the increment of the $i$th Brownian motion on the time interval $[a,b]$. Define the last passage time $M^N_t$ through the environment of Brownian motions by

$$\begin{equation*} M^N_t \coloneq \max _{0\leq s_1\leq \cdots \leq s_{N-1}\leq t} \left(B_1(0,s_1)+B_2(s_1,s_2)+\cdots + B_{N}(s_{N-1},t)\right). \end{equation*}$$

In joint work 4 with Janko Gravner and Craig Tracy, Harold Widom proved that $M^N_t/\sqrt {t}$ has the same distribution as the largest eigenvalue of an $N\times N$ GUE matrix. In fact, in their work, they also study some discrete generalizations of the Ulam problem which are related to growth models and last passage problems such as above.

5. The asymmetric simple exclusion process. Harold Widom’s papers 151617

The asymmetric simple exclusion process (ASEP) was introduced (in the probability literature) in Spitzer’s 1970 work Spi. It is a continuous-time Markov process of interacting particles on the integer lattice ${\mathbb{Z}}$. A particle at a location $x$ waits an exponential time with parameter one (independently of all other particles). When that time has elapsed, the particle flips a coin and with probability $p$ attempts to jump one position to the right, and with probability $q=1-p$ attempts to jump one position to the left. These jumps are achieved only if the destination site is unoccupied at that time. Due to the memoryless property of the exponential distribution, this defines a Markov process. See Figure 3 for an illustration of ASEP. Since its appearance, the ASEP model has attracted immense attention in both the mathematics and physics communities, due to the fact that this is one of the simplest nontrivial processes modeling nonequilibrium phenomena.

When $p=0$, the model is known as TASEP, with the $T$ standing for “totally” since now particles only march to the left. In the paper Joh2, building on BDJ, an important relation of the particle probabilities of the totally asymmetric process (TASEP, $p=0$) to the distribution function of the largest eigenvalue in the Laguerre unitary random matrix ensemble was discovered. Relying on tools from random matrix theory (namely, orthogonal polynomials and Fredholm determinants) Joh2 shows that the limiting particle distribution in TASEP is given by the Tracy–Widom $\beta =2$ distribution (see also PrSp). The decade after BDJ saw incredible developments in the analysis of models like TASEP and the longest increasing subsequence whose analysis reduces to studying asymptotics of determinants (these models are called “determinantal”; see Bor1).

The extension of this result to ASEP when $q\neq p>0$ posed an enormous challenge since ASEP, as opposed to TASEP, is not determinantal and a direct relationship to random matrices is no longer available. The extraordinary series of papers 151617, nevertheless provides this extension by building on the relationship between ASEP and the Heisenberg XXZ spin chain and exploiting the ideas of the coordinate Bethe ansatz.⁠⁸ These works broke new ground as the first instance of a nondeterminantal model for which the Tracy–Widom distributions was demonstrated.

⁸

This method dates back to the 1931 work of Hans Bethe Bet in studying the Heisenberg XXX spin chain Hei.

✖

The starting point for Tracy and Widom’s work on ASEP is an exact formula for the transition probability of the $N$-particle ASEP. For $N\in {\mathbb{N}}$, consider a system of $N$ particles on ${\mathbb{Z}}$. For two vectors of ordered integers, $\vec{x} = \{x_1<\cdots < x_N\}$ and $\vec{y} = \{ y_1<\cdots < y_N\}$, let $P_{\vec{y}}(\vec{x};t)$ denote the probability that ASEP starts in state $\vec{y}$ at time zero, and is in state $\vec{x}$ at time $t$. This function solves the Master equation (or Kolmogorov forward equation). When $N=1$, this equation reads

$$\begin{equation*} \frac{d}{dt}P_{y}(x;t) = \Delta _{p,q} P_{y}(x;t), \qquad P_{y}(x;0)=\mathbf{1}_{x=y}, \end{equation*}$$

where $\Delta _{p,q}$ acts in the $x$ variable as $\Delta _{p,q}f(x) = pf(x-1) + qf(x+1)-f(x)$. This equation can be solved explicitly using the Fourier transform, yielding

$$\begin{equation*} P_{y}(x;t) = \frac{1}{2\pi i} \int \xi ^{x-y-1} e^{\epsilon (\xi )t} d\xi ,\qquad \epsilon (\xi ) = p\xi ^{-1} +q \xi -1, \end{equation*}$$

where $\xi$ is integrated along the complex unit circle centered at $0$.

When $N\geq 2$, the Master equation becomes more complicated. When the $x_i$ are well-spaced (at least distance two apart), the right-hand side becomes the sum of $N$ terms, each involving $\Delta _{p,q}$ acting on each of the $x_i$ variables. However, when the $x_i$ neighbor each other, certain terms need to be excluded (corresponding to the excluded jumps in ASEP). Thus, the system becomes nonconstant coefficient and nonseparable and so there is no a priori reason to expect such a simple contour integral formula as above.

There is hope, however. The generator of ASEP (the operator on the right-hand side of the Master equation) is related by a similarity transform to the Hamiltonian of the XXZ quantum spin chain, itself a special limit of the six-vertex model. These models have a long history in the realm of exactly solvable models in statistical mechanics (e.g., Bax), and it was known since Lieb that the coordinate Bethe ansatz can be used to diagonalize the six-vertex model transfer matrix. For the six-vertex model and XXZ spin chain, one has to assume boundary conditions (e.g., work on a torus). However, since the generator of ASEP is stochastic, one can work directly on the full space ${\mathbb{Z}}$. This actually leads to a significant simplification to the Bethe ansatz—there are no longer complicated Bethe equations! Instead, one has to develop an analogue of the classical Plancherel theory, now for the Bethe ansatz eigenfunctions. This is essentially accomplished by 15 as well as BCPS.

Figure 4.

Harold Widom with his long-time collaborator, Craig Tracy at Oberwolfach in May 2009. Seen on the blackboard are calculations related to their work on ASEP. Photo courtesy of the Archives of the Mathematisches Forschungsinstitut Oberwolfach.

The following formula was proved in 15. The $N=2$ case had previously appeared in work of Rákos and Schütz RaSc. Provided $p\neq 0$,

$$\begin{equation} P_{\vec{y}}(\vec{x};t) = \sum _{\sigma \in S_N} \frac{1}{(2\pi i)^N}\int \cdots \int A_{\sigma } \prod _{j=1}^{N} \xi _{\sigma (j)}^{x_j-y_{\sigma (j)}-1} e^{\epsilon (\xi _j)t} d\xi _j. {\tag{5.1}} \end{equation}$$

Here, the sum $\sigma \in S_N$ is taken over all permutations $\sigma$ on $N$ elements; the $\xi _j$ variables are complex and integrated over contours which are assumed to be circles around the origin with radii small enough so as not to contain any poles of the $A_\sigma$ term; this $A_{\sigma }$ term is given by the formula

$$\begin{equation*} A_{\sigma } = \prod \left\{S_{\alpha \beta }:\{\alpha ,\beta \}\text{ is an inversion of }\sigma \right\},\qquad S_{\alpha \beta } = - \frac{p+q \xi _{\alpha } \xi _{\beta } - \xi _{\alpha }}{p+q \xi _{\alpha } \xi _{\beta } - \xi _{\beta }}, \end{equation*}$$

where the product is of terms $S_{\alpha \beta }$ over all pairs $1\leq \alpha <\beta \leq N$ such that $\sigma (\alpha )>\sigma (\beta )$.

This sum over the symmetric group may seem reminiscent of the expansion formula for determinants. In the special case when $p=1$ (which is the same at taking $p=0$, up to some symmetry), there is factorization and $A_\sigma = (-1)^{\sigma } \prod _{j=1}^{N} (1-\xi _{\sigma (j)})^{\sigma (j)-j}$. This implies that for $p=1$,

$$\begin{equation*} P_{\vec{y}}(\vec{x};t)=\det \left(\frac{1}{2\pi i} \int (1-\xi )^{j-i} \xi ^{x_i-y_j-1}e^{\epsilon (\xi )t} d\xi \right)_{i,j=1}^{N}, \end{equation*}$$

which recovers one aspect of the determinantal structure for TASEP; see Sch.

Returning to 5.1, just as in random matrix eigenvalue measures, the challenge now becomes how to extract large $N$ asymptotics for marginals of this measure on point configurations. Random matrix methods, though informative to this aim, were not directly applicable. The paper 15 extracted summation formulas for the marginal distribution of $x_m$ for general $N$ and initial data $\vec{y}$. Taking $y_i=i$ and then taking $N$ to infinity led Tracy and Widom to study step initial conditions for ASEP in which initially every positive integer site is occupied. The paper 15 closed with an infinite summation formula for the marginal distribution of the location of the $m$th left-most particle at time $t$, for any $m$. This formula was further manipulated in 16 into an integral transform of a Fredholm determinant. They had discovered a hidden determinantal structure in this model—one which would then allow them to extract asymptotics in 17. It should be remarked that the analysis of the Fredholm determinant in 17 was itself quite novel, requiring a number of ingenious operator manipulations.

Let us now record the main result of the asymptotics performed in 17. In fact, in 18, a more general class of initial data was considered in which sites in ${\mathbb{N}}$ are inititally occupied according to independent Bernoulli coin flips with probability $\rho \in (0,1]$ of having a particle. The case $\rho =1$ recovers the step initial data.

Assume that $0\leq p < q$ and put $\gamma \coloneq q-p$. Denote also $\sigma = m/t \leq 1$ and define the constants,

$$\begin{equation*} c_1 \coloneq -1 + 2\sqrt {\sigma }, \quad c_2 \coloneq \sigma ^{-1/6}\Bigl (1 - \sqrt {\sigma }\Bigr )^{2/3}. \end{equation*}$$

Then 1718 shows that (cf. 4.3 and 4.11),

$$\begin{equation} \lim _{t \to \infty }\operatorname {Prob}\left(\frac{x_m\Bigl (t/\gamma \Bigr ) - c_1t}{c_2t^{1/3}} \leq s\right) = F_2(s), \quad \text{when}\quad 0 < \sigma < \rho ^2, {\tag{5.2}} \end{equation}$$

and

$$\begin{equation} \lim _{t \to \infty }\operatorname {Prob}\left(\frac{x_m\Bigl (t/\gamma \Bigr ) - c_1t}{c_2t^{1/3}} \leq s\right) = F_1(s)^2, \quad \text{when}\quad \sigma = \rho ^2, \quad \rho < 1. {\tag{5.3}} \end{equation}$$

We emphasize again that ASEP is not a determinantal process and hence none of the usual integrable techniques—such as the orthogonal polynomial approach, the Riemann–Hilbert method, the Borodin–Okounkov formula, or the theory of integrable Fredholm operators—are readily applicable. In spite of the absence of such tools, the Tracy–Widom distributions still arise!

Besides demonstrating that the Tracy–Widom distribution is universal for ASEP regardless of the choice of parameters (provided $p\neq q$), the work in 151617 demonstrated that nondeterminantal models could still be solved, albeit with different techniques.

Over the decade or so since Tracy and Widom’s initial work on ASEP, there have been a number of developments in the field of integrable probability in this direction. This is too vast a subject to try to survey here, so we simply refer to a few existing surveys ABWBor2BoGoBoPe1BoPe2BoWhCor1Cor2Cor3Cor4OConQuSpZyg and mention some general topics: Kardar–Parisi–Zhang universality class, replica method, Markov duality, quantum Toda Hamiltonian, Macdonald processes (and limits to Whittaker, Jack, Hall–Littlewood, or Schur processes), stochastic vertex models, spin $q$-Whittaker and Hall–Littlewood functions. The list goes on, as does the influence of Tracy and Widom’s work on ASEP and random matrices.

Figure 1.

The eigenvalues of a large ($2000\times 2000$) GUE matrix. The full point process sits on the bottom of the figure, and the histogram records the density of points (approximating the Wigner semicircle). Inlaid is a zoom-in of the point process. As the size of the GUE matrix goes to infinity, this converges to $\beta =2$ sine process whose gap probabilities are discussed here.

Figure 3.

In the ASEP, particles jump left and right according to exponential clocks with rates $q$ and $p$. All jumps are independent, and those that would lead to collisions are excluded (the grey $\times$).