One possible sorting network or evolution of the particles in the oriented swap process. Here N = 4, and U 4 is the vector (t 4 , t 6 , t 5 ).
time t i we swap adjacent numbers σ (s i ) and σ (s i + 1), which means that τ (s i ) is appended to the product on the right. As a result, we get a permutation-valued, continuous-time, process (σ t ) t≥0 , which can be interpreted as the evolution of a system of particles with labels (or colors) 1, . . . , N interacting on the discrete interval [N ] = {1, . . . , N}, where σ t (k) is the label of the particle in position k at time t. The initial condition σ 0 is the identity permutation 12 . . . N.
The random pair of sequences {s i } (swap positions) and {t i } (swap times) are generated inductively as follows: let k , k = 1, . . . , N -1 denote N -1 independent exponential clocks (rate 1 Poisson point processes), and let i = 1 and t 0 = 0. When the clock k is the first among the clocks for which σ t i-1 (k) < σ t i-1 (k + 1) to ring at some time t > t i-1 , we set t i equal to t, set s i = k, and increase i by 1.
The particle system interpretation of this definition is: whenever one of the Poisson clocks k rings, check the current labels of the particles at positions k and k + 1. If the one at k + 1 has a smaller label, then nothing happens. Otherwise, swap the labels of the particles at positions k and k + 1. Clearly, after an almost surely finite time we will make all possible swaps and arrive at the reverse permutation N . . . 21.
The authors of [4] proved many results about the oriented swap process and its asymptotic behavior as the size N of the system goes to infinity. Among the quantities they considered were certain random times at which different aspects of the process terminate. Specifically, define the (N -1)-dimensional vector U N = (U N (1), . . . , U N (N -1)), where for each 1 ≤ k ≤ N -1, U N (k) is the last time t i at which the swap s i = k happens. We refer to this random variable as the last swap time associated with positions k, k + 1; see Figure 1. THEOREM 1.1 ([4]). Let a sequence k = k(N), N = 1, 2, . . . , be given such that ε < k/N < 1ε for some fixed ε > 0 and all sufficiently large N . Denote γ y = 1 + 2 √ y(1y), and let F 2 denote the β = 2 Tracy-Widom distribution. Then we have the convergence in distribution
We recall that the distribution F 2 is the universal scaling limit for the largest eigenvalues of random complex Hermitian matrices of growing sizes.
We proceed further by considering the kth particle finishing time Z N (k), which is the last time at which the particle with label k moved. It can be related to last swap times through
, Theorem 1.6, shows that (1.1) implies exactly the same limiting behavior for Z N (k).
Among the times U n (k) and Z n (k), perhaps the most important one is the absorbing time:
which is the time at which the very last swap in the oriented swap process occurs and we reach the reverse permutation N . . . 21. Theorem 1.1 implies that T OSP N ≈ 2N as N → ∞ (the maximum is attained for k ≈ N/2, since y → γ y takes its maximum value of 2 at y = 1/2). However, the authors of [4] could not identify the size of the fluctuations of T OSP N around 2N or their distributional limit; they stated this as an open problem in [4], Section 8. The problem is also mentioned as a "five coffee cup" exercise in [22], Exercise 5.22(e), page 331.
The following theorem settles this problem, and is our main result.
THEOREM 1.2. Let F 1 be the β = 1 Tracy-Widom distribution. We have
We recall that the distribution F 1 is the universal scaling limit for the largest eigenvalues of random real symmetric matrices of growing sizes.
Our proof of Theorem 1.2 belongs to a recent circle of ideas (see [8,10,14,17,19]) on the hidden symmetries in models of integrable probability and their universal limits. In this text we demonstrate how these ideas can be efficiently used to answer asymptotic questions about complicated stochastic systems.
A starting point for the current work is a distributional identity conjectured recently in [8], which relates the random vector U N to a certain random statistic defined in terms of the last passage percolation model with exponential weights. Specifically one defines a random vector V N = (V N (1), . . . , V N (N -1)) of last passage times in an oriented percolation model (the definition is given in (3.6) below), which turns out to be related to U N . CONJECTURE 1.3 ([8]). We have the equality in distribution of random vectors
We remark that the interplay between particle systems and passage times in percolation is well known; in particular, the equality in distribution of one-dimensional marginals U N (k) d = V N (k) for any 1 ≤ k ≤ N -1 follows easily from standard facts, and it was precisely that connection that enabled the authors of [4] to deduce Theorem 1.1 through an application of asymptotic results due to Johansson [21] on the limiting behavior of last passage percolation times. However, Conjecture 1.3 goes much further than this well-understood connection, and does not seem to follow in a straightforward way from any known bijections. In addition to formulating the conjecture, the authors of [8] gave a computer-assisted verification of the distributional identity (1.3) for the initial values 2 ≤ N ≤ 6, which provides good evidence of its validity for general values of N .
Simultaneously, [8] observed that Conjecture 1.3 can be combined with known asymptotic results to yield (1.2). We do not prove Conjecture 1.3 in this text, as the generality of our present method seems to go in a slightly different direction.
Instead, we consider the maximal coordinate of the vector V N :
Below we represent T LPP N in terms of a multicolored version of the TASEP, use the ideas of [4], which relate the TASEP dynamics on finite and infinite lattices, and add to them a recently discovered shift-invariance phenomenon [14] for the colored six-vertex model (which can be degenerated into multispecies/colored TASEP and thereby related to the oriented swap process). The ultimate result is the following equality in distribution of random variables for any N ≥ 2:
(1.4)
The identity (1.4), which can be thought of as a weakened version of Conjecture 1.3, allows us to use the known asymptotic results for T LPP N to deduce Theorem 1.2.
An important technical ingredient of our proof is the shiftinvariance for the colored (or multispecies) TASEP, which we now describe.
We deal with the colored TASEP on Z. By definition, this is a time-dependent assignment ζ t of integer labels (or colors) to points of Z. At time 0 we have
. Then the clock is restarted and we proceed further. We refer to [4], Section 3, for the description of how the process ζ t , t ≥ 0 can be constructed using the graphical representation.
Let us remark that if we fix some k and identify the colors ≤ k calling them "particles" and identify the colors > k calling them "holes" by setting ν k t (x) = 1 ζ t (x)≤k , then ν k t becomes the usual TASEP with particles jumping to the right at rate 1. The initial configuration ν k 0 (x) = 1 x≤k is then known as the step initial condition. In this way, the colored TASEP becomes a coupling of a countable system of ordinary TASEPs, each one started from a (shifted) step initial condition.
We study ζ t through its height functions, which are a collection of random variables parameterized by A, B ∈ Z. We define
In words, h ≤A→≥B counts the number of colors ≤ A at positions ≥ B at time t. Note that h ≤A→≥B can take arbitrary large (but almost surely finite) values. Let us also introduce another set of height functions for the convenience of matching the notation of [14]:
LEMMA 2.1. We have an almost sure identity
PROOF. At time 0 with the notation (u) + = max(u, 0), we have
Hence, (2.2) holds at t = 0. Next, note that both h ≤A→≥B (t) and H ≥A+1 TASEP (t, B -1/2) + (A -B + 1) are monotone functions of t ≥ 0. They both increase by 1 whenever at time t we have a swap, interchanging a color ≤ A at B -1 with a color ≥ (A + 1) at B. We conclude that (2.2) holds at all times.
We can now state the shift-invariance result for the colored TASEP. THEOREM 2.2. Choose an index ι ≥ 1, color cutoff levels k 1 . . . , k n ∈ Z, a time t ≥ 0 and a collection of observation points y 1 , . . . , y n ∈ Z + 1 2 . Set
Then the distribution of the vector of height functions PROOF. By shifting the coordinate system, if necessary, we can assume without loss of generality that k 1 ≥ 0. Then a version of Theorem 2.2 for the colored stochastic six-vertex model was proven in [14], Theorem 1.2 (see also [19], Theorem 1.5). The latter model is an assignment of configurations (six types of vertices) to the points of the positive quadrant Z ≥0 × Z ≥0 by a sequential stochastic rule, which can be thought of as a multiparameter discrete time asymmetric simple exclusion process. There exists a limit transition from the stochastic vertex model to TASEP, which was noticed for the colorless model in [11], Section 2.2, and proved in detail and greater generality in [1], see also [15], Section 12.3, for the colored case.
Let us explain how the limit transition works in the situation of our interest. In the notation of [14], Figure 4, we assume that the hopping probabilities b 1 and b 2 are homogeneous (do not depend on the lattice point) and set
In this situation the colored stochastic six-vertex model on the (x, y) plane (see [14], Figure 3) turns into a discrete version of the colored TASEP, in which τ = x + y takes the role of time and z = yx is the space coordinate. We now recast the stochastic update rule of [14], Section 1.2, in (τ, z) coordinate system. At fixed time τ the configuration of the model is a configuration of particles of the colors 1, 2, 3, . . . on the lattice Z (there is one particle for each color, except for color 0, which we treat as an absence of any particles). At time 0 the particle of color i is at position i for each i > 0 and all other positions are occupied by particles of color 0. The transition from time τ to time τ + 1 depends on the oddity of τ . If τ is even then for each even z ≤ τ we make the following procedure: If both z and z + 1 are occupied with particles of color 0, then we do nothing. Otherwise, suppose that there is a particle of color i at z and a particle of color j at z + 1. If i > j, then we do nothing. If i < j, then we swap these two particles with probability ε and do nothing with probability 1ε (all the choices are independent over z). For odd times τ we do the same procedure for all odd positions z ≤ τ .
The above description makes it immediate that in the limit as ε → 0 and τ → ∞ in such a way that 2ετ → t we converge to the colored TASEP (in which we glued all negative colors into color 0, which is not important for the heights function (2.3) and (2.4), since we assumed k 1 ≥ 0). In particular, returning to the notation of [14], the height function of the colored stochastic six-vertex model, which we denote by H ≥k 6v (•, •), converges in distribution to that of a TASEP height function:
(2.5)
This is to be understood in the sense that the convergence in (2.5) holds for the distributions of finite (arbitrary) collections of values of (k, t, y). Given this relation, the statement of Theorem 2.2 is a direct consequence of [14], Theorem 1.2.
REMARK 2.3. At first, it might seem that [14], Theorem 1.2, ought to imply a more general statement than the one we formulated: indeed, that theorem allowed shifts in the situation when the observation points (x j , y j ) are not restricted to a single line-in the case of the TASEP, an analogous statement would mean accessing the heights at different values of the time parameter t. However, [14], Theorem 1.2, required certain ordering inequalities for the points (x j , y j ), and the only way for these inequalities to be satisfied in the limit (2.5) is by making all times equal, as in (2.3)-(2.4). That is one reason why at this point we are unable to give a full proof of Conjecture 1.3-we will only prove in the next section its particular case corresponding to all equal times in TASEP. At the same time, since the results of [8] support the full validity of the conjecture in its stronger form, one can wonder if Theorem 2.2 might also have as yet unknown extensions involving unequal times.
We end this section by restating a particular case of Theorem 2.2 in terms of the height functions h ≤A→≥B (t) of (2.1). COROLLARY 2.4. Fix N ∈ Z ≥1 . We have a distributional identity of (N -1)-dimensional vectors
PROOF. Given the identity (2.2), this follows by repeated applications of Theorem 2.2 with n = N -1. Indeed, the (N -1)st coordinates of the vectors in (2.6) are the same. The (N -2)nd coordinate is h ≤N-2→≥3 (t) for the left-hand side and h ≤N-1→≥4 (t) for the right-hand side. Hence, we can shift one into another by Theorem 2.2 with ι = n -1 = N -2. Next, we apply Theorem 2.2 twice for ι = n -2 = N -3, shifting h ≤N-3→≥4 (t) into h ≤N-1→≥6 (t). Continuing in this way for smaller values of ι, we reach (2.6).
In this section we prove Theorem 1.2.
We need to gather some facts from [4] about the connection between the oriented swap process and the colored TASEP on Z.
We start by defining the colored TASEP on the finite set [N] = {1, 2, . . . , N}. It is defined in exactly the same way as the colored TASEP on Z, but all the particles stay in [N]: the swaps (0, 1) and (N, N + 1) are prohibited. Clearly, this is just a particular representation of the oriented swap process from the Introduction. In particular, the system stops at the random absorbing time t N 2 = T OSP N . Following [4], Section 3, we introduce a coupling of the colored TASEP on Z (which we continue to denote by ζ t as in Section 2) with its counterpart on [N], which we will denote by ζ N t (x). The coupling proceeds as follows: in order to construct the process on Z we need clocks (Poisson processes) attached to each edge (k, k + 1)-whenever the clock rings, particles at k and k + 1 attempt to swap (and succeed only if the particle at k + 1 had a larger label). For the process on [N ] we are going to use exactly the same N -1 clocks as the N -1 clocks of the process on Z corresponding to the edges (1, 2), (2, 3), . . . , (N -1, N). Now consider, for fixed k ∈ Z,
Then ν k t is a realization of the usual TASEP on Z (with particles given by 1's and jumping to the right) started from a step initial condition: at time 0 the particles are at (. . . , k -2, k -1, k).
Similarly, we can define
and observe that ν k,N t is a realization of a TASEP on [N], with no particles entering from the left and particles prohibited from exiting on the right, that is, swaps along both edges (0, 1) and (N, N + 1) are blocked. Assuming 1 ≤ k ≤ N , in ν k,N 0 the particles occupy positions 1, 2, . . . , k.
Note that all of the processes ν k t for different values of k almost surely take values in the subset of the space of colorless TASEP configurations {0, 1} Z consisting of configurations with only a finite number of 1's to the right of the origin. We make use of the following result. PROPOSITION 3.1 ([4], Lemma 3.3). Define two combinatorial operators acting on : the "cutoff" operator R k keeps only the rightmost k particles in a (potentially infinite) system of particles. The "push-back" operator B n pushes all the particles into the ray (-∞, n], preserving their order (and moving all particles by the minimal possible distances to the left). Then we have an almost sure identity
holding simultaneously for all 1 ≤ k ≤ N , and all t.
The colored TASEP on Z N and its height functions. Define
≤ N, and note that these are the height functions associated with the colored TASEP on Z N . PROPOSITION 3.2. Under the coupling of colored TASEPs on different subsets of Z of Section 3.1, we have an almost sure identity holding for all t 1 , . . . , t N-1 ≥ 0: ). Then we have
Simultaneously (cf. [4], equations ( 4) and ( 5)),
For the first equality in the last formula, notice that since we deal with min(•, i), we can ignore all the particles beyond the first i; for the second equality, notice that for i-particle configurations, B N does not change the number of particles to the right of Ni, since we have i free spots to the right from Ni; these are N + 1i, N + 2i, . . . , N.
Applying (3.3), (3.4), and (3.1) to each coordinate of the vector (3.2), we get the desired identity.
Let T OSP N be the absorbing time, that is, the time when the colored TASEP on [N] stops. The definition, identity (3.2), and Corollary 2.4 imply that
Proof of Theorem 1.2. Using the coupling from Section 3.1, the event
appearing on the right-hand side of (3.5) has the following interpretation: given a colorless TASEP started from the step initial condition with particles occupying the positions N -1, N -2, N -3, . . . at time 0, A N-1 t is the event that at time t the first particle is at or to the right of position 2N -2, the second particle is at or to the right of position 2N -4, . . . , the (N -1)th particle is at or to the right of position 2.
We can now reinterpret this event in terms of last passage percolation (LPP) with exponential weights, using the well-known correspondence between the TASEP and LPP with such weights. We summarize this relationship between the two processes; for a more detailed explanation, see, for example, the discussion around Figure 4 in [13], or [22], Section 4.7.
In short, we treat the configuration of the TASEP as a broken line interface with particles representing segments of slope -1 and holes (i.e., the absence of a particle at some location) representing segments of slope 1, as in Figure 2. Then the time evolution of the TASEP becomes the growth of the line interface, and the growth follows the rule that each inner corner FIG. 2. Left panel: a step initial condition in the TASEP corresponds to the wedge-type broken line interface. The shape of the interface after time t can be computed using last passage times: the time when a box (i, j ) is added to the interface is L(i, j ). In particular, L( 2 is filled with a unit square after an exponential waiting time (independent of all other waiting times). These waiting times, in turn, form the array of weights for the last passage percolation model.
Making the idea more precise and applying it to our particular situation, we take a quadrant filled with i.i.d. exponential mean 1 random variables w ij , i, j = 1, 2, . . . and draw it in Russian notation, as on the left panel of Figure 2. For i, j ≥ 1, we define the last passage time L(i, j ) associated with the square with coordinates (i, j ) by
where m = i + j -1 and the maximum is taken over all monotone lattice paths joining (1, 1) with (i, j ) (i.e., paths with b ), (1, 0)} for all k). The last passage time L(i, j ) represents the time when the unit square with coordinates (i, j ) was filled; in the TASEP picture (with our particular step initial condition offset by N -1 units from the usual one), this corresponds to the time it took the particle that started out in position Ni to arrive at position Ni + j . Now, the vector V N appearing in (1.3) was defined in [8] in terms of the last passage percolation times as (3.6) V N = L(1, N -1), L(2, N -2), . . . , L(N -1, 1) .
Moreover, with the correspondence described above, we now see that the event A N-1 t is the same as the event L(1, N -1) ≤ t, L(2, N -2) ≤ t, . . . , L(N -1, 1) ≤ t .
Hence, we conclude that (3.5) implies the equality in law with 1 ≤ i ≤ i , 1 ≤ j ≤ j , and the maximum being taken over all monotone lattice paths joining (i, j ) to (i , j ). Using the correspondence between TASEP and last passage percolation again, one can then identify the latter maximum with the first time the height at 0 for the TASEP started from a so-called flat initial condition reaches the value N ; see the right panel of Figure 2. From this perspective, the asymptotic computation leading to the Tracy-Widom distribution F 1 goes back to [24], [12]. In a wider context, the first appearance of the F 1 distribution in a closely related framework dates to [7].