# Increasing subsequences of linear size in random permutations and the Robinson–Schensted tableaux of permutons

Victor Dubach

► To cite this version:

Victor Dubach. Increasing subsequences of linear size in random permutations and the Robinson–Schensted tableaux of permutons. Random Structures and Algorithms, 2024, 65 (3), pp.488-534. 10.1002/rsa.21223 . hal-05046063

HAL Id: hal-05046063

https://hal.science/hal-05046063v1

Submitted on 24 Apr 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Increasing subsequences of linear size in random permutations and the Robinson–Schensted tableaux of permutons

Victor Dubach*

*Université de Lorraine, IECL, Nancy, France

## Abstract

The study of longest increasing subsequences (LIS) in permutations led to that of Young diagrams via Robinson–Schensted’s (RS) correspondence. In a celebrated paper, Vershik and Kerov obtained a limit theorem for such diagrams and found that the LIS of a uniform permutation of size $n$ behaves as $2\sqrt{n}$. Independently and much later, Hoppen et al. introduced the theory of permutons as a scaling limit of permutations. In this paper, we extend in some sense the RS correspondence of permutations to the space of permutons. When the “RS-tableaux” of a permuton are non-trivial, we show that the RS-tableaux of random permutations sampled from this permuton exhibit a linear behavior, in the sense that their first rows and columns have lengths of linear order. In particular, the LIS of such permutations behaves as a multiple of $n$. We also prove some large deviation results for these convergences. Finally, by studying asymptotic properties of Fomin’s algorithm for permutations, we show that the RS-tableaux of a permuton satisfy a partial differential equation.

**Keywords:** random permutations, permutons, longest increasing subsequence, Robinson–Schensted correspondence, Fomin’s local rules

## 1 Background

### 1.1 The theory of permutons and sampled permutations

A Borel probability measure $\mu$ on $[0, 1]^2$ is called a *permuton* when each of its marginals is uniform, i.e. for any $0 \le x \le y \le 1$:

$$ \mu([x, y] \times [0, 1]) = \mu([0, 1] \times [x, y]) = y - x. $$

The theory of permutons was first studied in [HKM+13], named in [GGKK15], and is now widely studied (see e.g. [KP13, Muk15, BBF+18, BBF+22] and references therein). It serves as a scaling limit model for permutations: if $\sigma$ is a permutation of size $n \in \mathbb{N}^*$, one can associate it with the permuton $\mu_\sigma$ having density

$$ n \sum_{i=1}^{n} 1_{[\frac{i-1}{n}, \frac{i}{n}]} \times [\frac{\sigma(i)-1}{n}, \frac{\sigma(i)}{n}] $$

with respect to Lebesgue measure on $[0, 1]^2$. Putting weak convergence topology on the space of permutons, this gives a meaning to the convergence of a sequence of permutations towards a limit permuton. This convergence is notably characterized by the asymptotics of pattern densities, cementing the theory of permutons within the general framework of sampling limit theory (see e.g. [LS06] for dense graphs, [Jan11] for posets, [ET22] and [Grü23] for trees).

Fundamental to permuton theory is the fact that each permuton gives rise to a model of random permutations. Consider points $Z_1, \dots, Z_n$ in the unit square $[0, 1]^2$ whose $x$-coordinates and $y$-coordinates are all distinct. One can then naturally define a permutation $\sigma$ of size $n$ in the following way: for any $1 \le i, j \le n$, let $\sigma(i) = j$ whenever the point with $i$-th lowest $x$-coordinate has $j$-th lowest $y$-coordinate. We denote by $\text{Perm}(Z_1, \dots, Z_n)$ this permutation; see Figure 1 for an example. When $\mu$ is a permuton and $Z_1, \dots, Z_n$ are random i.i.d. points distributed under $\mu$, we write $\text{Sample}_n(\mu)$ for the law of this random permutation. Since the marginals of $\mu$ are continuous, this permutation is almost surely well defined.
<figure><img src="image_2.png" /></figure>

$$ \mathrm{Perm}(Z_1, Z_2, Z_3, Z_4, Z_5, Z_6, Z_7) = 4 \ 2 \ 7 \ 6 \ 1 \ 3 \ 5 $$

<caption>Figure 1: The permutation $\sigma$ associated to a family of points, written in one-line notation. Here $\sigma(1) = 4$ because the first point from the left, $Z_3$, is the fourth point from the bottom, and so on.</caption>

**Theorem 1.1 ([HKM$^{+}$13])**. Let $\mu$ be a permutation and $(\sigma_n)_{n \in \mathbb{N}^*}$ be a sequence of random permutations such that for each $n \in \mathbb{N}^*$, $\sigma_n \sim \mathrm{Sample}_n(\mu)$. Then the following weak convergence holds almost surely:

$$ \mu_{\sigma_n} \xrightarrow{n \to \infty} \mu. $$

Note that this model can be generalized to more than just permutations. As in [Dub23] we say that a Borel probability measure on $[0, 1]^2$ is a pre-permutation when none of its marginals have any atom; then the law $\mathrm{Sample}_n(\mu)$ is still well defined. This notion has the advantage of being stable by induced sub-measures, which is why we use it for some results. Going from pre-permutations to permutations and conversely is fairly easy: one can associate any pre-permutation $\mu$ with a unique permutation $\hat{\mu}$ such that random permutations sampled from $\mu$ or $\hat{\mu}$ have the same law (see e.g. Remark 1.2 in [BDMW24]). Moreover this is done via a transformation of the unit square which is nondecreasing in each coordinate, hence most quantities defined in later sections have the same values on pre-permutations as on their associated permutations.

## 1.2 Longest increasing subsequences and Robinson–Schensted’s correspondence

Let $w = w_1 \dots w_n$ be a finite word with positive integer letters. We say that a subset of indices $\{i_1 < \dots < i_\ell\}$ is an increasing subsequence of $w$ if $w_{i_1} < \dots < w_{i_\ell}$. The maximum length of such a sequence is called length of the longest increasing subsequence of $w$ and denoted by $\mathrm{LIS}(w)$. More generally for $k \in \mathbb{N}^*$, define the length of the longest $k$-increasing subsequence of $w$ as

$$ \mathrm{LIS}_k(w) := \max_{I_1, \dots, I_k} |I_1 \cup \dots \cup I_k| $$

where the maximum is taken over all families $I_1, \dots, I_k$ (not necessarily disjoint) of increasing subsequences of $w$. Also define $\mathrm{LDS}_k$ similarly by replacing “increasing” with “decreasing” in the previous definition. The study of longest increasing subsequences is intimately related to a bijective map called Robinson–Schensted’s correspondence, which we present next.

A (Young) diagram is a visual representation of an integer partition: it consists of a sequence of left-justified rows, containing nonincreasing numbers of boxes. A (Young) tableau is a filling of a diagram, called its shape, with positive integers. When the filling is nondecreasing (resp. increasing) in each row and increasing in each column, we call the tableau semistandard (resp. standard). Robinson–Schensted’s (RS) correspondence is a map between words and pairs of tableaux sharing the same shape, see Figure 2. The first tableau, called the P-tableau, is semistandard and filled with the letters of $w$, while the second one, called the Q-tableau, is standard and filled with the integers from 1 to the length of $w$. If $\sigma$ is a permutation, seen as a word via one-line notation, then its P-tableau is standard.

There are many ways to define this correspondence, for which we refer the reader to [Ful96]. Below we recall its equivalent description given by Greene’s theorem. For any word $w$, define

$$ \mathrm{sh}(w) = (\mathrm{sh}^{\mathrm{row}}(w), \mathrm{sh}^{\mathrm{col}}(w)) := ((\mathrm{LIS}_k(w) - \mathrm{LIS}_{k-1}(w))_{k \in \mathbb{N}^*}, (\mathrm{LDS}_k(w) - \mathrm{LDS}_{k-1}(w))_{k \in \mathbb{N}^*}) $$
$$ P(\sigma) = \begin{bmatrix} 1 & 3 & 5 \\ 2 & 6 \\ 4 & 7 \end{bmatrix}, \quad Q(\sigma) = \begin{bmatrix} 1 & 3 & 7 \\ 2 & 4 \\ 5 & 6 \end{bmatrix}, \quad \mathrm{sh}(\sigma) = \begin{bmatrix} \multicolumn{3}{c}{\phantom{XX}} \\ \multicolumn{3}{c}{\phantom{XX}} \\ \multicolumn{3}{c}{\phantom{XX}} \end{bmatrix} $$

Figure 2: The standard tableaux associated with the permutation $\sigma = 4276135$, and their common shape. The first row has length 3, and indeed $\mathrm{LIS}(\sigma) = 3$ (attained e.g. with the increasing subsequence $235$). The second row has length 2, and indeed $\mathrm{LIS}_2(\sigma) = 3+2=5$ (attained e.g. with the 2-increasing subsequence $42635$). Finally, the shape has a total of three rows, and indeed $\sigma$ is 3-increasing (one can e.g. decompose it into $46, 27$, and $135$). Greene's theorem can also be checked for the column lengths.

with convention $\mathrm{LIS}_0(w) = \mathrm{LDS}_0(w) = 0$.

**Theorem 1.2 ([Gre74]).** For any word $w$, the sequences $\mathrm{sh}^{\mathrm{row}}(w)$ and $\mathrm{sh}^{\mathrm{col}}(w)$ are respectively the row lengths and column lengths of the RS-shape of $w$. In particular, those sequences are nonincreasing.

Note that the definition of $\mathrm{sh}$ is redundant, as the sequence of row lengths can be deduced from the sequence of column lengths and vice versa (these are usually called *conjugate partitions*). However we shall see that this property is lost in the permutation limit.

Greene's theorem can also be used to define the RS-tableaux. A standard tableau of size $n$ can be equivalently defined as an increasing sequence of $n$ diagrams, where the $k$-th diagram is the shape of the sub-tableau containing the boxes with values at most $k$. For example in Figure 2, the 4-th diagram defining $P(\sigma)$ has row lengths $(2, 1, 1)$ and the 4-th diagram defining $Q(\sigma)$ has row lengths $(2, 2)$.

Let $\sigma$ be a permutation of $\{1, \dots, n\}$. For any $1 \le i, j \le n$ define its sub-word $\sigma^{i,j}$ as the sequence of letters $\sigma(h)$ with $h \le i$ and $\sigma(h) \le j$. One can see that for each $1 \le k \le n$, the RS-shape of $\sigma^{n,k}$ is the $k$-th diagram defining $P(\sigma)$ and the RS-shape of $\sigma^{k,n}$ is the $k$-th diagram defining $Q(\sigma)$. This motivates the following alternative definition of Robinson-Schensted's tableaux:

$$ \mathrm{RS}(\sigma) := (\lambda^{\sigma}(n, \cdot), \lambda^{\sigma}(\cdot, n)) \qquad (1) $$

where, for any $1 \le i, j \le n$,

$$ \lambda^{\sigma}(i, j) = (\lambda_{k}^{\sigma}(i, j))_{k \in \mathbb{N}^{*}} := \mathrm{sh}^{\mathrm{row}}(\sigma^{i, j}). $$

## 1.3 LIS and RS-shapes of random permutations

Ulam formulated the following question in the 60's: consider for each $n \in \mathbb{N}^*$ a uniformly random permutation $\sigma_n$ of size $n$, and write

$$ \ell_n := \mathbb{E}[\mathrm{LIS}(\sigma_n)]. $$

Then what can we say about the asymptotic behavior of $\ell_n$ as $n \to \infty$? The study of longest increasing subsequences has since then been a surprisingly fertile research subject with unexpected links to diverse areas of mathematics; see [Rom15] for a nice introduction to this topic.

A solution to Ulam's problem was found by Vershik and Kerov through the use of Robinson-Schensted's correspondence. More precisely they encoded diagrams $\lambda$ by some continuous functions $\omega_{\lambda}: \mathbb{R} \to \mathbb{R}$ and established the following limit theorem (also simultaneously proved in [LS77]). See Figure 3 for an illustration.

**Theorem 1.3 ([VK77]).** For each integer $n$, let $\sigma_n$ be a uniformly random permutation of size $n$ and write

$$ \omega_n(\cdot) := \frac{\omega_{\mathrm{sh}(\sigma_n)}(\sqrt{n}\cdot)}{\sqrt{n}}. $$

Then the sequence $(\omega_n)_{n \in \mathbb{N}^*}$ converges uniformly in probability to some explicit limit curve.

By Theorem 1.2 this convergence corresponds to explicit non-trivial limits as $n$ goes to infinity for $\frac{1}{n}\mathrm{LIS}_{\alpha\sqrt{n}}(\sigma_n)$, $\alpha \in [0, 2]$. This also implies $\liminf \frac{1}{\sqrt{n}}\ell_n \ge 2$, and with an additional argument for the upper bound we can deduce:
<figure><img src="image_3.png" /><figcaption>Figure 3: The RS-tableaux of a size 20000 uniformly random permutation. Higher values in the tableaux are represented by brighter colors.</figcaption></figure>

**Corollary 1.4 ([VK77]).** For each $n$, let $\sigma_n$ be a uniformly random permutation of size $n$ and write $\ell_n := \mathbb{E}[\text{LIS}(\sigma_n)]$. Then

$$ \frac{1}{\sqrt{n}} \ell_n \xrightarrow{n \to \infty} 2. $$

The study of $\ell_n$ later culminated with the work of Baik, Deift and Johansson [BDJ99], who found its second-order asymptotics.

One can then naturally ask: is it possible to obtain similar asymptotics for sampled random permutations? One of the first advances on this question was obtained by Deuschel and Zeitouni who proved:

**Theorem 1.5 ([DZ95]).** Let $\mu_\rho$ be a permuton with a $C_b^1$ density $\rho$ which is bounded below on $[0, 1]^2$. If for each integer $n$, $\sigma_n \sim \text{Sample}_n(\mu_\rho)$, then:

$$ \frac{1}{\sqrt{n}} \text{LIS}(\sigma_n) \xrightarrow{n \to \infty} K_\rho $$

in probability, for some positive constant $K_\rho$ defined by a variational problem.

This question of generalization is still an active research subject. In the recent paper [Sjö23], the author studies the $\sqrt{n}$ scaling limit for the RS-shape of sampled permutations when the sampling permuton is absolutely continuous.

The goal of this paper is to extend in some sense the function LIS, as well as the first rows and columns of RS-shape and tableaux, to the space of permutons. This will allow us to deduce linear asymptotics of these quantities for sampled permutations; therefore our results are different in nature from the $\sqrt{n}$ regime of [DZ95, Sjö23], and yield non-trivial asymptotics for certain types of permutons displaying a singular part with respect to the Lebesgue measure on $[0, 1]^2$. We introduce the RS-shape of permutons in Section 2.1 and present these asymptotics. Then in Section 2.2 we investigate large deviation principles related to those convergences, exhibiting a difference of behavior between the upper and lower tails. In Section 2.3 we define the RS-tableaux of a permuton and explain how a discrete algorithm translates in this continuous setting, then in Section 2.4 we present a few results about the injectivity of permutons' RS-tableaux. Finally, we illustrate these objects with several examples in Section 2.5.

# 2 Our results

## 2.1 The RS-shape of (pre-)permutons

Throughout the paper we denote by $M_{\text{unif}} \subset M_{\text{cont}} \subset M_{\text{prob}} \subset M_{\text{fin}}$ the sets of permutons, pre-permutons, probability measures and finite measures on $[0, 1]^2$. Say a subset $A \subset [0, 1]^2$ is nondecreasing (resp. nonincreasing) if

$$ \text{for any } (x_1, y_1), (x_2, y_2) \in A, \quad (x_2 - x_1)(y_2 - y_1) \ge 0 \quad (\text{resp. } (x_2 - x_1)(y_2 - y_1) \le 0) $$
and for any $k \in \mathbb{N}^*$, say A is k-nondecreasing (resp. k-nonincreasing) if it can be written as a union of k (not necessarily disjoint) nondecreasing (resp. nonincreasing) subsets of $[0, 1]^2$. Denote by $\mathcal{P}_K^{k\nearrow}([0, 1]^2)$ and $\mathcal{P}_K^{k\searrow}([0, 1]^2)$ respectively the sets of closed k-nondecreasing and k-nonincreasing subsets, and define for any $\mu \in \mathcal{M}_{\text{fin}}$:

$$ \widetilde{\text{LIS}}_k(\mu) := \sup_{A \in \mathcal{P}_K^{k\searrow}([0,1]^2)} \mu(A), \quad \widetilde{\text{LDS}}_k(\mu) := \sup_{A \in \mathcal{P}_K^{k\nearrow}([0,1]^2)} \mu(A). $$

When $k=1$ we may drop the subscript $k$. By convention we set $\widetilde{\text{LIS}}_0(\mu) = \widetilde{\text{LDS}}_0(\mu) := 0$.

**Proposition 2.1.** For any $\mu \in \mathcal{M}_{\text{fin}}$, the supremum in the definition of $\widetilde{\text{LIS}}_k(\mu)$ is reached. Moreover the function $\widetilde{\text{LIS}}_k$ is upper semi-continuous on $\mathcal{M}_{\text{prob}}$, i.e. for any sequence $(\mu_n)_{n \in \mathbb{N}}$ weakly converging to $\mu$ in $\mathcal{M}_{\text{prob}}$ one has $\limsup \widetilde{\text{LIS}}_k(\mu_n) \le \widetilde{\text{LIS}}_k(\mu)$. The same holds for $\widetilde{\text{LDS}}_k$.

The functions $\widetilde{\text{LIS}}_k$ are not continuous: for instance, one can check that the permutations $\mu_\sigma$ defined in Section 1.1 satisfy $\widetilde{\text{LIS}}(\mu_\sigma) = 0$ for all permutations $\sigma$, although this family is dense in $\mathcal{M}_{\text{prob}}$ by Theorem 1.1.

The next result, along with Lemma 3.5 used to prove it, justifies the idea that $\widetilde{\text{LIS}}_k$, $\widetilde{\text{LDS}}_k$ are generalizations of $\text{LIS}_k$, $\text{LDS}_k$ to the space of (pre-)permutations:

**Proposition 2.2.** Let $\mu \in \mathcal{M}_{\text{cont}}$ and $(\sigma_n)_{n \in \mathbb{N}^*}$ be such that for each $n \in \mathbb{N}^*$, $\sigma_n \sim \text{Sample}_n(\mu)$. For any $k \in \mathbb{N}^*$, the following convergences hold almost surely:

$$ \frac{1}{n}\text{LIS}_k(\sigma_n) \xrightarrow{n \to \infty} \widetilde{\text{LIS}}_k(\mu) \quad ; \quad \frac{1}{n}\text{LDS}_k(\sigma_n) \xrightarrow{n \to \infty} \widetilde{\text{LDS}}_k(\mu). $$

This result does not hold for any sequence of permutations $\sigma_n$ such that $\mu_{\sigma_n}$ converges to $\mu$. For example, it is easy to construct a sequence of permutations with sublinear LIS that converges towards the diagonal permutation. We could expect this result to hold under appropriate regularity assumptions on the sequence $(\sigma_n)$, similar to the ones exhibited in [Muk15] for the study of small cycles, but such assumptions remain to be discovered.

We can then extend the notion of RS-shape to the space of permutations by analogy with Greene's theorem. For any $\mu \in \mathcal{M}_{\text{fin}}$, define:

$$ \tilde{\text{sh}}(\mu) = (\tilde{\text{sh}}^{\text{row}}(\mu), \tilde{\text{sh}}^{\text{col}}(\mu)) := \left( (\widetilde{\text{LIS}}_k(\mu) - \widetilde{\text{LIS}}_{k-1}(\mu))_{k \in \mathbb{N}^*}, (\widetilde{\text{LDS}}_k(\mu) - \widetilde{\text{LDS}}_{k-1}(\mu))_{k \in \mathbb{N}^*} \right). $$

An immediate consequence of Proposition 2.2 is the convergence of sampled permutations' shapes towards the sampling permutation's shape, component-wise. Another one is that this quantity belongs to the Thoma simplex, which appears in the limit theory of integer partitions (see e.g. [FMN20] and references therein):

**Proposition 2.3.** Define the Thoma simplex $\Omega$ as

$$ \Omega := \left\{ \left( (\alpha_1 \ge \alpha_2 \ge \dots \ge 0), (\beta_1 \ge \beta_2 \ge \dots \ge 0) \right) : \sum_{i \ge 1} \alpha_i + \sum_{j \ge 1} \beta_j \le 1 \right\}. $$

Then for any $\mu \in \mathcal{M}_{\text{cont}}$, $\tilde{\text{sh}}(\mu) \in \Omega$.

**Remark 1.** Propositions 2.2 and 2.3 can be related to a law of large numbers for random partitions due to Vershik and Kerov. Let $(\alpha, \beta) \in \Omega$ and $\gamma := 1 - \sum_i \alpha_i - \sum_i \beta_i$. In [VK81] the authors defined a measure $M_{\alpha, \beta, \gamma}^n$ on Young diagrams of size $n$ and proved that $\alpha_i$ (resp. $\beta_i$) is the asymptotic proportion of boxes in the $i$-th row (resp. column). In [VK86] they showed that this measure could be interpreted as the RS-shape of some random word. For this, fix an alphabet $\mathbb{L} = \{a_1, a_2, \dots\} \sqcup \{b_1, b_2, \dots\} \sqcup [0, 1]$ where $a_i$'s are called row letters, $b_i$'s are called column letters, and elements of $[0, 1]$ are neutral letters. Define a measure $m_{\alpha, \beta, \gamma}^n$ on words of length $n$ by choosing independently each letter with a probability $\alpha_i$ of being $a_i$, $\beta_i$ of being $b_i$, and $\gamma$ of being uniform in $[0, 1]$. Adapt Robinson-Schensted's algorithm on such words by requiring that each row of the P-tableau contains each column letter at most once, and each column of the P-tableau contains each row letter at most once (but rows may contain one row letter multiple times and columns may contain one column letter multiple times). Then the measure $M_{\alpha, \beta, \gamma}^n$ is the push-forward by RS-shape of $m_{\alpha, \beta, \gamma}^n$. Equivalently, it is possible to interpret random diagrams under $M_{\alpha, \beta, \gamma}^n$ as the RS-shapes of certain sampled
<figure><img src="image_4.png" /><figcaption>Figure 4: The permutation $\mu_{\alpha,\beta,\gamma}$ when the alphabet $\mathbb{L}$ puts the order of $\mathbb{N}$ on row letters, the order of $-\mathbb{N}$ on column letters, and row letters are lower than neutral letters which are lower than column letters. In this example the parameters are $\alpha = (1/4, 1/8, 1/12, 1/24)$, $\beta = (1/6, 1/12)$, $\gamma = 1/4$. This alphabet is called the “jeu de taquin alphabet” in [Śni14].</figcaption></figure>

permutations. For this, associate each row letter $a_i$ with an upward diagonal of mass $\alpha_i$ and each column letter $b_i$ with a downward diagonal of mass $\beta_i$, then place them in $[0, 1]^2$ and interpose uniform mass according to the order on $\mathbb{L}$. This defines a permutation $\mu_{\alpha,\beta,\gamma}$ whose sampled permutations are standardizations of words under $m_{\alpha,\beta,\gamma}^n$ (see e.g. Section 3.7 in [Śni14] for a definition), hence their RS-shapes follow the law $M_{\alpha,\beta,\gamma}^n$ and we can recover with Proposition 2.2 the asymptotics of [VK81]. See Figure 4 for a representation of the permutation $\mu_{\alpha,\beta,\gamma}$.

**Remark 2.** Our results also have some connections to graphon theory. This theory was introduced in [LS06] for the study of dense graph sequences and is arguably the primary motivation for the introduction of permutation theory in [HKM$^+$13] and [GGKK15]. These two theories share several similarities as well as a formal link; the inversion graph of permutations (see e.g. Section 1.2 in [BBD$^+$22] for a definition) can naturally be extended into a continuous map $\widetilde{\text{inv}}$ from permutations to graphons. The function $\widetilde{\text{LIS}}$ is then analogous to the independence number $\tilde{\alpha}$, which was proved to be upper semi-continuous in [HR20]. Moreover the counterpart of Proposition 2.2 for $k = 1$, i.e. the a.s. convergence of $\alpha(\text{Sample}_n(W))/n$ towards $\tilde{\alpha}(W)$, was established in [BBD$^+$22]. These convergence results allow to see that $\widetilde{\text{inv}}$ indeed maps $\widetilde{\text{LIS}}$ to $\tilde{\alpha}$.

The results of this section are proved in Sections 3.1 and 3.2. From now on we will focus on the study of $\widetilde{\text{LIS}}_k$, since results on $\widetilde{\text{LDS}}_k$ can be deduced by mirroring the permutation:

$$ \mu^{\text{rev}} := \psi_* \mu \quad \text{where for any } (x, y) \in [0, 1]^2, \quad \psi(x, y) := (1-x, y). $$

Since $\psi$ exchanges nonincreasing subsets with nondecreasing ones, we have for any $k \in \mathbb{N}^*$ and $(x, y) \in [0, 1]^2$:

$$ \widetilde{\text{LIS}}_k (\mu^{\text{rev}}|_{[0,x] \times [0,y]}) = \widetilde{\text{LDS}}_k (\mu|_{[1-x,1] \times [0,y]}). $$

## 2.2 Large deviation principles

In this section we present partial large deviation principles concerning the convergences of Proposition 2.2. First we state an upper tail in Theorem 2.4: the simple idea is that long increasing subsequences are formed when many points appear in a maximal increasing subset of the permutation. However this idea does not work for a lower tail, since having few points in a maximal increasing subset does not prevent long increasing subsequences from forming somewhere else: this difference of behavior is made formal in Proposition 2.8. In the $\sqrt{n}$ regime when the permutation has a regular density, this asymmetry translates into a change of speed between the upper and lower tails [DZ99]. Here in the linear regime, we prove in Theorem 2.7 that if there exists a lower tail large deviation then the speed is the same as for the upper tail.
For any $p \in [0, 1]$, define the Legendre transform of the Bernoulli law $Ber(p)$ as:

$$ \text{for any } q \in [0, 1], \quad \Lambda_p^*(q) := q \log \frac{q}{p} + (1-q) \log \frac{1-q}{1-p} \quad \in [0, +\infty]. $$

Cramér’s theorem (recalled in Theorem 3.7) states that this is the good rate function for the large deviation principle of binomial laws. We show that this is also the rate function for the following upper tail:

**Theorem 2.4.** Let $\mu \in \mathcal{M}_{\text{unif}}$, $k \in \mathbb{N}^*$, and $\sigma_n \sim \text{Sample}_n(\mu)$ for each $n \in \mathbb{N}^*$. Then for any $\alpha \in (\widetilde{\text{LIS}}_k(\mu), 1]$:

$$ \frac{1}{n} \log \mathbf{P}(\widetilde{\text{LIS}}_k(\sigma_n) \ge \alpha n) \underset{n \to \infty}{\longrightarrow} -\Lambda_{\widetilde{\text{LIS}}_k(\mu)}^*(\alpha). $$

In particular when $\alpha = 1$ and $k = 1$ we get the following convergence:

**Corollary 2.5.** For any permutation $\mu$ and $\sigma_n \sim \text{Sample}_n(\mu)$:

$$ \mathbf{P}(\sigma_n = \text{id}_n)^{1/n} \underset{n \to \infty}{\longrightarrow} \widetilde{\text{LIS}}(\mu). $$

For the lower tail we restrict our study to LIS for convenience, but this could be generalized to $\widetilde{\text{LIS}}_k$. We begin with an upper bound in the same flavor as in Theorem 2.4:

**Proposition 2.6.** Let $\mu \in \mathcal{M}_{\text{unif}}$ and $\sigma_n \sim \text{Sample}_n(\mu)$ for each $n \in \mathbb{N}^*$. Then for any $\beta \in (0, \widetilde{\text{LIS}}(\mu))$:

$$ \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\widetilde{\text{LIS}}(\sigma_n) < \beta n) \le - \sup_{j \ge 1, j \beta < \widetilde{\text{LIS}}_j(\mu)} \Lambda_{\widetilde{\text{LIS}}_j(\mu)}^*(j\beta). $$

This upper bound is in general better than the simpler one $\Lambda_{\widetilde{\text{LIS}}_k(\mu)}^*(\beta)$; take for example $\mu$ such that $\widetilde{\text{LIS}}_2(\mu) = 2\widetilde{\text{LIS}}(\mu) > 0$. Since it is non-zero whenever $\widetilde{\text{LIS}}(\mu) > 0$, it implies that the $n$ speed for a lower tail is not “too fast”. Conversely the following result states that, except in trivial cases, this speed is not “too slow” either:

**Theorem 2.7.** Let $\mu \in \mathcal{M}_{\text{unif}}$ and $\sigma_n \sim \text{Sample}_n(\mu)$ for each $n \in \mathbb{N}^*$. Let $\beta \in (0, 1]$ and $k \in \mathbb{N}^*$ satisfying $\frac{1}{k+1} < \beta \le \frac{1}{k}$. Then the following assertions are equivalent:

$$ (i) \liminf \frac{1}{n} \log \mathbf{P}(\widetilde{\text{LIS}}(\sigma_n) < \beta n) = -\infty; $$

$$ (ii) \text{ For all } n \in \mathbb{N}^*, \mathbf{P}(\widetilde{\text{LIS}}(\sigma_n) \ge \beta n) = 1; $$

$$ (iii) \quad \widetilde{\text{LIS}}_k(\mu) = 1. $$

Unfortunately the upper bound of Proposition 2.6 is not sharp. We actually show that a rate function for this lower tail can not be expressed as a function of $\widetilde{\text{sh}}(\mu)$:

**Proposition 2.8.** There exist $\mu_1, \mu_2 \in \mathcal{M}_{\text{unif}}$ satisfying $\widetilde{\text{sh}}(\mu_1) = \widetilde{\text{sh}}(\mu_2)$ and

$$ \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\widetilde{\text{LIS}}(\tau_n) < \beta n) < \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\widetilde{\text{LIS}}(\sigma_n) < \beta n) $$

for some $\beta < \widetilde{\text{LIS}}(\mu_1)$, where $\sigma_n \sim \text{Sample}_n(\mu_1)$ and $\tau_n \sim \text{Sample}_n(\mu_2)$.

We believe a lower tail rate function could be expressed with the help of $\widetilde{\text{RS}}(\mu)$ or $\tilde{\lambda}^\mu$ defined in Section 2.3, but this question remains unanswered. The results of this section are proved in Sections 3.3 to 3.5.

**Remark 3.** A large deviation principle for the sequence of sampled permutations $(\sigma_n)$ was recently obtained in [BDMW24, Theorem 1.6]. By semi-continuity of $\widetilde{\text{LIS}}_k$ (Proposition 2.1), we can deduce large deviation inequalities for the sequence $(\widetilde{\text{LIS}}_k(\sigma_n))$ by a variant of the contraction principle (the standard contraction principle carries large deviation results over continuous functions, see e.g. [DZ98]). This actually yields the same inequalities as if we apply the same “semi-contraction principle” directly to Sanov’s theorem, the latter being done in Corollary 3.9. We do not know whether these bounds are optimal are not. We do not use this approach for Theorem 2.4, and instead opt for a self-contained proof. However, we use the lower tail bound of Corollary 3.9 in the proof of Theorem 2.7.

**Remark 4.** The counterpart of Corollary 2.5 for graphs was proved in [CKP22], and it is likely that Theorem 2.4 would also hold in that context. However our study of the lower tail in Theorem 2.7 seems rather specific to permutations, as it hinges on the fact that any permutation $\sigma$ of size $n$ satisfies $\widetilde{\text{LIS}}(\sigma)\widetilde{\text{LDS}}(\sigma) \ge n$. The analog of this property for graphs is not true in general; note that inversion graphs of permutations are perfect graphs.
## 2.3 The RS-tableaux of (pre-)permutons

By analogy with (1), define the RS-tableaux of any $\mu \in \mathcal{M}_{\text{fin}}$ as

$$ \widetilde{\text{RS}}(\mu) := (\tilde{\lambda}^{\mu}(1, \cdot), \tilde{\lambda}^{\mu}(\cdot, 1)) $$

where for any $(x, y) \in [0, 1]^2$, we write $\mu|_{[0,x] \times [0,y]}$ for the measure obtained by restricting $\mu$ to $[0, x] \times [0, y]$ and:

$$ \tilde{\lambda}^{\mu}(x, y) = (\tilde{\lambda}_{k}^{\mu}(x, y))_{k \in \mathbb{N}^{*}} := \tilde{\text{sh}}^{\text{row}}(\mu|_{[0,x] \times [0,y]}) = (\widetilde{\text{LIS}}_{k}(\mu|_{[0,x] \times [0,y]}) - \widetilde{\text{LIS}}_{k-1}(\mu|_{[0,x] \times [0,y]}))_{k \in \mathbb{N}^{*}} $$

In the continuity of Proposition 2.2, we deduce in Section 4.1 linear asymptotics for the RS-tableaux of sampled permutations:

**Proposition 2.9.** Let $\mu \in \mathcal{M}_{\text{unif}}$ and for each $n \in \mathbb{N}^*$, $\sigma_n \sim \text{Sample}_n(\mu)$. For each $k \in \mathbb{N}^*$, the function $\tilde{\lambda}_k^\mu$ is nondecreasing and 1-Lipschitz in each variable. Moreover we have the following almost sure uniform convergence on $[0, 1]^2$:

$$ \frac{1}{n} \lambda_k^{\sigma_n} (\lfloor \cdot \rfloor, \lfloor \cdot \rfloor) \xrightarrow{n \to \infty} \tilde{\lambda}_k^{\mu}. $$

The RS-tableaux of a permutation can be constructed via an algorithm known as Fomin's local rules, see Section 4.2. Its usual version works by labeling the vertices of a grid with diagrams, as in [Sag01, Section 5.2], but it is equivalently possible to label the edges of this grid with integers [Vie18]. This edge version is well adapted to our framework, since labels then correspond to increment indices of $\lambda^\sigma$. The direct algorithm recursively constructs each $\lambda^\sigma(i+1, j+1)$ from $\lambda^\sigma(i+1, j)$, $\lambda^\sigma(i, j+1)$, $\lambda^\sigma(i, j)$ and $\sigma$. Its reciprocal recursively constructs each $\lambda^\sigma(i, j)$ from $\lambda^\sigma(i+1, j)$, $\lambda^\sigma(i, j+1)$ and $\lambda^\sigma(i+1, j+1)$.

It is then natural to wonder if there exists a continuous version of this algorithm, translating as a partial differential equation on $\tilde{\lambda}^\mu$. It is indeed the case for the inverse local rules, as stated in the following result:

**Theorem 2.10.** Suppose $\mu$ is a permutation satisfying $\widetilde{\text{LIS}}_r(\mu) = 1$ for some $r \in \mathbb{N}^*$. Let $(x, y) \in (0, 1]^2$ be such that the left-derivatives

$$ \alpha_k := \partial_x^{-} \tilde{\lambda}_k^{\mu}(x, y) \quad \text{and} \quad \beta_k := \partial_y^{-} \tilde{\lambda}_k^{\mu}(x, y) $$

for $1 \le k \le r$ all exist. Fix $s, t \ge 0$. Then we have the following directional semi-derivatives for each $1 \le k \le r$:

$$ \lim_{\epsilon \to 0^+} \frac{\tilde{\lambda}_k^\mu(x, y) - \tilde{\lambda}_k^\mu(x - t\epsilon, y - s\epsilon)}{\epsilon} = \phi((t\alpha_i)_{k \le i \le r}, (s\beta_i)_{k \le i \le r}) \quad (2) $$

where $\phi$ is a continuous function defined in Proposition 4.12.

The proof of Theorem 2.10 comes in several steps and introduces methods that might be interesting on their own. The general idea is to study Fomin's inverse local rules on $\sigma_n \sim \text{Sample}_n(\mu)$ and exhibit their asymptotic behavior, yielding properties of $\tilde{\lambda}^\mu$. To this aim, we see sequences of edge labels as words, for which we introduce an appropriate equivalence relation. Surprisingly enough, this equivalence relation is implied by the Knuth equivalence of words (see Section 4.4 and Proposition 4.9). Along with the derivability condition of Theorem 2.10 this allows us to show in Section 4.6 that edge labels of $\sigma_n$ behave, locally and asymptotically, as if they were ordered in a deterministic way. This behavior yields the function $\phi$ introduced and studied in Section 4.5. We refer to the discussion at the end of Section 4.2 for more details.

A few comments on this theorem are in order:

* It is possible to generalize this result to pre-permutons, using the associated permutation and the chain rule.

* If $s = 0$ then the left-hand side of Equation (2) is $t\alpha_k$ by definition, and indeed one can check with Equations (40) and (41) that $\phi((t\alpha_i)_{k \le i \le r}, (0)) = t\alpha_k$. By symmetry, an analogous remark holds when $t = 0$.

* When $k = r$, the left-hand side of Equation (2) depends only on the “last row derivatives” $\alpha_r$ and $\beta_r$, and equals $\phi((t\alpha_r), (s\beta_r)) = \max(t\alpha_r, s\beta_r)$. When $k < r$, the $k$-th to $r$-th rows intervene in an intricate way through the function $\phi$.
* Unfortunately we have not been able to establish a continuous version of Fomin's direct algorithm, as the dependence on permutation points makes the asymptotic study more difficult. It seems likely that Theorem 2.10 could be generalized in this direction, but this question is left open.

* It would also be interesting to get rid of the hypothesis $\overline{\text{LIS}}_r(\mu) = 1$; more precisely we would like to weaken it to $\overline{\text{LIS}}_\infty(\mu) = 1$ with the notation of Section 2.4. We can always assume that this is satisfied thanks to Theorem 2.12. However we could neither extend $\phi$ to infinite sequences nor make our techniques work when Fomin's edge labels are unbounded.

* Equation (2) can be related to the “hydrodynamical approach” used by Aldous and Diaconis in [AD95] for the study of LIS in the uniform case. When $\sigma_n$ is a uniform permutation of size $n$, Hammersley [Ham72] studied the function $\lambda_1^{\sigma_n}$ (a very similar one actually) and used the subadditive ergodic theorem to obtain the asymptotic equivalence $\mathbb{E}[\text{LIS}(\sigma_n)] \sim c\sqrt{n}$ for some constant $c > 0$. In [AD95], the authors investigated Hammersley's process in more depth, provided some heuristics as to why $c = 2$, and proved it in this framework. The general idea is that for any $y$, the counting process $x \mapsto \lambda_1^{\sigma_n}(x, y)$ should approximate a Poisson process. Under this hypothesis, one can argue that $\frac{1}{\sqrt{n}}\mathbb{E}[\lambda_1^{\sigma_n}(x, y)]$ should asymptotically satisfy a PDE whose solution is $2\sqrt{xy}$. Therefore Equation (2) can be interpreted as an analog of this, in the $n$ scaling limit for non-uniform permutations and for the first rows and columns of the shape. It could be interesting to try this approach in the case of a permuton with “regular” density, in a context similar to that of [DZ95] and [Sjö23].

We end this section with an interesting consequence of Proposition 2.9 and Theorem 2.10, proved in Section 4.6.

**Corollary 2.11.** Let $\mu$ be a permuton satisfying $\overline{\text{LIS}}_r(\mu) = 1$ for some $r \in \mathbb{N}^*$. Then for all $1 \le k \le r$, for almost every $(x, y) \in (0, 1)^2$, $\tilde{\lambda}_k^\mu$ is differentiable at $(x, y)$ and satisfies $\partial_x \tilde{\lambda}_k^\mu(x, y) \cdot \partial_y \tilde{\lambda}_k^\mu(x, y) = 0$. In other words, the gradient of $\tilde{\lambda}_k^\mu$ is a.e. directed along the $x$- or along the $y$-axis.

## 2.4 Injectivity of pre-permuton Robinson-Schensted

Recall that Robinson-Schensted's correspondence is injective on permutations. This begins the question of what information about a (pre-)permuton $\mu$ we can deduce from the knowledge of $\overline{\text{RS}}(\mu)$. To this end, we introduce a useful decomposition of pre-permutons. Define $\overline{\text{LIS}}_\infty := \lim_{k \to \infty} \uparrow \overline{\text{LIS}}_k$ and $\overline{\text{LDS}}_\infty := \lim_{k \to \infty} \uparrow \overline{\text{LDS}}_k$ on $M_{\text{fin}}$.

**Theorem 2.12.** Let $\mu \in M_{\text{cont}}$. There exists a unique triple $(\mu^{\text{incr}}, \mu^{\text{decr}}, \mu^{\text{sub}}) \in M_{\text{fin}}^3$ satisfying:

$$ 
\left\{ 
\begin{array}{l}
\mu = \mu^{\text{incr}} + \mu^{\text{decr}} + \mu^{\text{sub}}; \\
\overline{\text{LIS}}_{\infty}(\mu^{\text{incr}}) = \mu^{\text{incr}}([0, 1]^2) = \overline{\text{LIS}}_{\infty}(\mu); \\
\overline{\text{LDS}}_{\infty}(\mu^{\text{decr}}) = \mu^{\text{decr}}([0, 1]^2) = \overline{\text{LDS}}_{\infty}(\mu).
\end{array}
\right. 
$$

Moreover the following properties hold:

(i) the measures $\mu^{\text{incr}}$, $\mu^{\text{decr}}$, $\mu^{\text{sub}}$ are pairwise singular;

(ii) for all $k \in \mathbb{N}^*$, $\overline{\text{LIS}}_k(\mu^{\text{incr}}) = \overline{\text{LIS}}_k(\mu)$ and $\overline{\text{LDS}}_k(\mu^{\text{decr}}) = \overline{\text{LDS}}_k(\mu)$;

(iii) $\overline{\text{LIS}}(\mu^{\text{decr}}) = \overline{\text{LIS}}(\mu^{\text{sub}}) = \overline{\text{LDS}}(\mu^{\text{sub}}) = \overline{\text{LDS}}(\mu^{\text{incr}}) = 0$;

(iv) $\tilde{\lambda}^\mu = \tilde{\lambda}^{\mu^{\text{incr}}}$.

Notice that Property (iv) of Theorem 2.12 allows to lift the hypothesis $\overline{\text{LIS}}_r(\mu) = 1$ in Theorem 2.10 to the more general one $\overline{\text{LIS}}_r(\mu) = \overline{\text{LIS}}_\infty(\mu)$. Indeed, consider a permuton $\mu$ that satisfies $\overline{\text{LIS}}_r(\mu) = \overline{\text{LIS}}_\infty(\mu)$. Its submeasure $\mu^{\text{incr}}$ is a priori not a permuton, but can be mapped to a pre-permuton $\delta\mu^{\text{incr}}$ by dilatation. This pre-permuton satisfies $\overline{\text{LIS}}_r(\delta\mu^{\text{incr}}) = 1$, so we can apply Theorem 2.10 using the chain rule. Thanks to Property (iv) of Theorem 2.12, this finally yields a partial differential equation on $\tilde{\lambda}^\mu$.

**Conjecture 2.13.** Let $\mu, \nu \in M_{\text{cont}}$ such that $\overline{\text{RS}}(\mu) = \overline{\text{RS}}(\nu)$. Then $\mu^{\text{incr}} = \nu^{\text{incr}}$.
<figure><img src="image_5.png" /><figcaption>Figure 5: Representation of some of the examples of Section 2.5. From left to right: the locally affine function $f: [0, 1]^2 \to [0, 1]$ constructed in (i) (brighter colors indicate higher values), the permuton of (d), and the permuton of (e). For the last two: $\tilde{\lambda}_1^\mu$ is not differentiable on the dashed blue lines, and $\tilde{\lambda}_2^\mu$ is not differentiable on the dashed orange lines.</figcaption></figure>

Recall that $\tilde{\mathbb{R}}\mathbb{S}(\mu)$ is defined using only the nondecreasing subsets of $\mu$. These “row-tableaux” capture no information about the submeasure $\mu^{\text{decr}}$, since $\tilde{\mathbb{R}}\mathbb{S}(\mu^{\text{decr}})$ is null. An analog of Conjecture 2.13 for nonincreasing subsets could be stated by replacing $\mu$ with $\mu^{\text{rev}}$ (see the discussion at the end of Section 2.1).

We believe that Theorem 2.10 could help establish Conjecture 2.13. In most “regular” examples, the PDE of Theorem 2.10 seems to be satisfied everywhere on $(0, 1]^2$ (note that $\tilde{\lambda}_k^\mu$ is in general not differentiable everywhere). We would then hope for the uniqueness of their solution $\tilde{\lambda}^\mu$ with boundary condition $\tilde{\mathbb{R}}\mathbb{S}(\mu)$, using Corollary 2.11 and the form taken by Equation (2) at the points of non-differentiability of $\tilde{\lambda}_k^\mu$. This is further discussed in Section 2.5, item (i). However we could not make this idea work, and instead we present more elementary results: an injectivity property of $\mu \mapsto \tilde{\lambda}^\mu$, and a positive answer to Conjecture 2.13 when the pre-permutons contain at most one nondecreasing subset.

**Proposition 2.14.** Let $\mu, \nu \in \mathcal{M}_{\text{cont}}$ such that $\tilde{\lambda}^\mu = \tilde{\lambda}^\nu$. Then $\mu^{\text{incr}} = \nu^{\text{incr}}$.

**Proposition 2.15.** Let $\mu, \nu \in \mathcal{M}_{\text{cont}}$ such that $\tilde{\mathbb{L}}\mathbb{S}_\infty(\mu) = \tilde{\mathbb{L}}\mathbb{S}_1(\mu)$ and $\tilde{\mathbb{R}}\mathbb{S}(\mu) = \tilde{\mathbb{R}}\mathbb{S}(\nu)$. Then $\mu^{\text{incr}} = \nu^{\text{incr}}$.

The results of this section are proved in Section 4.7.

## 2.5 Examples

In this section, we illustrate our results with several examples. Some of them are represented in Figure 5. If $x, y \in \mathbb{R}$, we use the standard notation $x \wedge y := \min(x, y)$ and $x \vee y := \max(x, y)$.

(a) Let $\text{Leb}_{[0,1]^2}$ be the uniform permuton, i.e. the Lebesgue measure on $[0, 1]^2$. It is easy to check that for any nondecreasing $A$, we have $\text{Leb}_{[0,1]^2}(A) = 0$. Thus $\tilde{\mathbb{L}}\mathbb{S}(\text{Leb}_{[0,1]^2}) = 0$, and likewise $\tilde{\mathbb{L}}\mathbb{D}\mathbb{S}(\text{Leb}_{[0,1]^2}) = 0$. This is consistent with the fact that the longest monotone subsequences of uniform permutations have sublinear asymptotics.

More generally, let $\mu$ be a pre-permuton with a density with respect to $\text{Leb}_{[0,1]^2}$. By absolute continuity, we again have $\tilde{\mathbb{L}}\mathbb{S}(\mu) = \tilde{\mathbb{L}}\mathbb{D}\mathbb{S}(\mu) = 0$. In particular, with the notation of Theorem 2.12: $(\mu^{\text{incr}}, \mu^{\text{decr}}, \mu^{\text{sub}}) = (0, 0, \mu)$. Our definitions are vacuous in this case, and our techniques are not suited to the study of such pre-permutons.

(b) Let $\mu = \text{Leb}_\Delta$ be the permuton that puts uniform mass on the diagonal $\Delta$ of $[0, 1]^2$. Then $\tilde{\mathbb{L}}\mathbb{S}(\mu) = 1$ and $\tilde{\mathbb{L}}\mathbb{D}\mathbb{S}(\mu) = 0$, and in particular $\tilde{\mathbb{S}}(\mu) = ((1, 0, \dots), (0, \dots))$. Also, $\tilde{\lambda}_1^\mu(x, y) = x \wedge y$ for any $(x, y) \in [0, 1]^2$, and $\tilde{\lambda}_k^\mu(x, y) = 0$ for all $k \ge 2$. The RS-tableaux of $\mu$ are $\tilde{\mathbb{R}}\mathbb{S}(\mu) = ((\text{id}_{[0,1]}, 0, \dots), (\text{id}_{[0,1]}, 0, \dots))$.

(c) Let $\mu$ be the permuton that puts uniform mass on the antidiagonal of $[0, 1]^2$. Then $\tilde{\mathbb{L}}\mathbb{S}(\mu) = 0$, $\tilde{\mathbb{L}}\mathbb{D}\mathbb{S}(\mu) = 1$, but with our definition $\tilde{\mathbb{R}}\mathbb{S}(\mu) = ((0, \dots), (0, \dots))$. This is because in this paper, we defined the RS-tableaux of a permuton via its row-shapes, and not its column-shapes. As discussed at the end of Section 2.1, it would be more relevant in this case to apply our definitions to the mirrored permuton $\mu^{\text{rev}} = \text{Leb}_\Delta$.
(d) Let $\mu$ be the only permuton with support $\{y = 2x\} \cup \{y = 2x - 1\}$ in $[0, 1]^2$. This permuton has row-shape $\tilde{\text{sh}}^{\text{row}}(\mu) = (1/2, 1/2, 0, \dots)$ and trivial column-shape. In particular $\mu = \mu^{\text{incr}}$. We can compute:

$$ \tilde{\lambda}_1^\mu(x, y) = \begin{cases} x \wedge (y/2) & \text{if } x \in [0, 1/2]; \\ y/2 & \text{if } x \in [1/2, 1]; \end{cases} $$

and

$$ \tilde{\lambda}_2^\mu(x, y) = \begin{cases} 0 & \text{if } x \in [0, 1/2]; \\ (x - 1/2) \wedge (y/2) & \text{if } x \in [1/2, 1]. \end{cases} $$

The function $\tilde{\lambda}_1^\mu$ is not differentiable on $\{y = 2x\}$, and $\tilde{\lambda}_2^\mu$ is not differentiable on $\{x = 1/2\} \cup \{y = 2x - 1\}$.

(e) Let $\mu$ be the only permuton with support $\{y = x + 1/2\} \cup \{y = x - 1/2\}$ in $[0, 1]^2$. This permuton has the same RS-shape as the previous one, but different RS-tableaux. We can compute:

$$ \tilde{\lambda}_1^\mu(x, y) = \begin{cases} 0 & \text{if } (x, y) \in [0, 1/2]^2; \\ x \wedge (y - 1/2) & \text{if } (x, y) \in [0, 1/2] \times [1/2, 1]; \\ (x - 1/2) \wedge y & \text{if } (x, y) \in [1/2, 1] \times [0, 1/2]; \\ (x - 1/2) \vee (y - 1/2) & \text{if } (x, y) \in [1/2, 1]^2; \end{cases} $$

and

$$ \tilde{\lambda}_2^\mu(x, y) = \begin{cases} 0 & \text{if } (x, y) \notin [1/2, 1]^2; \\ (x - 1/2) \wedge (y - 1/2) & \text{if } (x, y) \in [1/2, 1]^2. \end{cases} $$

The function $\tilde{\lambda}_1^\mu$ is not differentiable on $\{x \le y, y = 1/2\} \cup \{y = x + 1/2\} \cup \{y \le x, x = 1/2\} \cup \{y = x - 1/2\} \cup \{y = x, y \ge 1/2\}$, and $\tilde{\lambda}_2^\mu$ is not differentiable on $\{x \le y, x = 1/2\} \cup \{y \le x, y = 1/2\} \cup \{y = x, y \ge 1/2\}$.

Now let us illustrate Theorem 2.12 with some examples of permutons having non-trivial decompositions.

(f) The permuton $\mu_{\alpha, \beta, \gamma}$ defined in Remark 1 has RS-shape $(\alpha, \beta)$ by construction. The decomposition of Theorem 2.12 is what one would expect: $\mu_{\alpha, \beta, \gamma}^{\text{incr}}$ is the restriction of $\mu_{\alpha, \beta, \gamma}$ to the upward diagonals of its support, $\mu_{\alpha, \beta, \gamma}^{\text{decr}}$ is its restriction to the downward diagonals, and $\mu_{\alpha, \beta, \gamma}^{\text{sub}}$ is the remaining uniform mass.

(g) Let $f: [0, 1] \to [0, 1]$ and define a measure $\mu_f$ as the push-forward of $\text{Leb}_{[0,1]}$ by the mapping $x \mapsto (x, f(x))$. If $f$ preserves the Lebesgue measure then $\mu_f$ is a permuton, called a push-forward permuton in [FRL23]. A few examples of push-forward permutons are the permutons (b), (d), (e) here; the skew Brownian permutons [Bor23]; and the recursive separable permutons [FRL23]. The RS-shapes and tableaux of push-forward permutons are not easy to compute in general, and may even be trivial (this is e.g. the case for the Brownian separable permuton, by [BBD+22, Theorem 1.10]). However if $f$ is a smooth function (not necessarily Lebesgue-preserving) such that the set $\{f' = 0\}$ has empty interior in $[0, 1]$, then $\mu_f$ is a pre-permuton with a simple decomposition: $\mu_f^{\text{incr}}$ is the restriction of $\mu_f$ to $\{(x, f(x)) : f'(x) > 0\}$ and $\mu_f^{\text{decr}}$ is the restriction of $\mu_f$ to $\{(x, f(x)) : f'(x) < 0\}$. Other examples of “unidimensional” pre-permuton can be constructed by putting uniform masses on unions of curves in $[0, 1]^2$, under the assumption that those curves do not have any horizontal or vertical parts.

(h) Several permutons with non-trivial decompositions have been observed in the recent literature, and we list some of them here. For the runsort permuton $\mathbf{R}$ found in [ADK22], $\mathbf{R}^{\text{incr}}$ is supported on a smooth increasing curve and $\mathbf{R}^{\text{sub}}$ has a density above this curve. The limit of square permutations [BS20] satisfies $\mu^{\text{sub}} = 0$, and its (random) RS-shape has two rows and two columns. Almost square permutations with a sublinear number of internal points have a similar limit [BDS21], and [Bor21, Conjecture 5.1.4] suggests that a linear number of internal points yields a permuton with non-trivial components $\mu^{\text{sub}}$ (uniform mass inside some domain), $\mu^{\text{incr}}$ and $\mu^{\text{decr}}$ (supported on the boundary of this domain). A similar observation can be made for record-biased permutations [ABNP16]: simulations suggest that, in an adequate regime, there is a permuton limit $\mu$, with $\mu^{\text{incr}}$ being supported on an increasing curve and $\mu^{\text{sub}}$ attributing uniform mass under this curve.

This last example further discusses a potential proof strategy for Conjecture 2.13, mentioned in Section 2.4.
(i) Take again $\mu = \text{Leb}_\Delta$. Conjecture 2.13 would imply that this is the only (pre-)permuton with $\overline{\text{RS}}(\mu) = ((\text{id}_{[0,1]}, 0, \dots), (\text{id}_{[0,1]}, 0, \dots))$ (this is actually true thanks to Proposition 2.15, but let us ignore this for the sake of the example). As mentioned earlier, a plausible approach would be to solve the PDE (2) with boundary condition $\overline{\text{RS}}(\mu)$. In this example, we aim to illustrate that this approach should rely on the behavior of $\tilde{\lambda}_1^\mu$ at its points of non-differentiability. More precisely, $\tilde{\lambda}_1^\mu(x, y) = x \wedge y$ is not the only function $f : [0, 1]^2 \to [0, 1]$ such that:

* $f$ is Lipschitz and nondecreasing in both variables;

* $f$ is differentiable a.e. and satisfies $D_{(x,y)}f(s,t) = \phi((t\partial_x f(x,y)), (s\partial_y f(x,y)))$ at its points of differentiability (this equation is equivalent to $\partial_x f(x,y) \cdot \partial_y f(x,y) = 0$ at its points of differentiability, as proved in Corollary 2.11);

* $f(1, \cdot) = f(\cdot, 1) = \text{id}_{[0,1]}$.

To show this, construct $f$ as follows: for any $z \in [0, 1]$, $f$ takes the value $z$ on the broken line which goes from $(z, 1)$ to $(z, \frac{z+1}{2})$, to $(\frac{z+1}{2}, \frac{z+1}{2})$, to $(\frac{z+1}{2}, z)$, to $(1, z)$. Also, set $f = 0$ on $[0, 1/2]^2$. Then $f$ is differentiable outside $\{y = \frac{x+1}{2}\} \cup \{y = x, x \ge 1/2\} \cup \{x = \frac{y+1}{2}\} \cup \{y = 1/2, x \le 1/2\} \cup \{x = 1/2, y \le 1/2\}$, and on this domain it is locally either a function of $x$, or a function of $y$. Hence $f$ satisfies a.e. the same PDE as $\tilde{\lambda}_1^\mu$, and the same boundary condition. See Figure 5 for a representation.

# 3 Proofs of the results in Sections 2.1 and 2.2

## 3.1 Topological preliminaries

Write $d$ for the Euclidean distance on the plane. If $A \subseteq [0, 1]^2$ and $\delta > 0$, define the $\delta$-halo of $A$ by:

$$A^\delta := \{y \in [0, 1]^2 : d(y, x) \le \delta \text{ for some } x \in A\}.$$

Note that if $A$ is a closed subset of $[0, 1]^2$ then $A^\delta$ is closed as well. We then define the Hausdorff distance by

$$\text{for all } A, B \subseteq [0, 1]^2, \quad d_H(A, B) := \inf \{\delta > 0 : A \subseteq B^\delta \text{ and } B \subseteq A^\delta\}.$$

It is well known that the space $\mathcal{P}_K([0, 1]^2)$ of closed subsets of the unit square, equipped with the distance $d_H$, is compact. Moreover, one can easily see that its subsets $\mathcal{P}_K^\perp([0, 1]^2)$ are $\mathcal{P}_K^\perp([0, 1]^2)$ are closed, and hence compact. The following two lemmas may be well known, but we include a short proof.

**Lemma 3.1.** Let $\mu \in \mathcal{M}_{\text{fin}}$. The function $A \in \mathcal{P}_K([0, 1]^2) \mapsto \mu(A) \in [0, 1]$ is upper semi-continuous for the Hausdorff distance.

*Proof.* Let $(A_n)_{n \in \mathbb{N}}$ be a sequence converging to $A$ in $\mathcal{P}_K([0, 1]^2)$. Our goal is to establish $\mu(A) \ge \limsup \mu(A_n)$. For this, fix $\varepsilon > 0$. By monotony and since $\bigcap_{\delta>0} A^\delta = A$, there exists $\delta > 0$ satisfying $\mu(A^\delta) \le \mu(A) + \varepsilon$. Let $n_0$ be such that for any $n$ greater than $n_0$, $A^\delta$ contains $A_n$. Then:

$$\limsup_{n \to \infty} \mu(A_n) \le \mu(A^\delta) \le \mu(A) + \varepsilon$$

which concludes this proof, as it holds for any $\varepsilon > 0$. $\square$

**Lemma 3.2.** For any $k \in \mathbb{N}^*$, the union map $\cup$ from $\mathcal{P}_K([0, 1]^2)^k$ to $\mathcal{P}_K([0, 1]^2)$ is continuous.

*Proof.* By associativity, it suffices to consider the case $k = 2$. Let $(A_n), (B_n)$ be two sequences converging to $A, B$ respectively in $\mathcal{P}_K([0, 1]^2)$. Our goal is to prove the convergence of $(A_n \cup B_n)$ to $A \cup B$. For this, fix $\varepsilon > 0$ and take $n_0$ such that:

$$\text{for all } n > n_0, \quad A_n \subseteq A^\varepsilon \text{ and } A \subseteq A_n^\varepsilon \text{ and } B_n \subseteq B^\varepsilon \text{ and } B \subseteq B_n^\varepsilon.$$

Hence:

$$\text{for all } n > n_0, \quad A_n \cup B_n \subseteq (A^\varepsilon) \cup (B^\varepsilon) \text{ and } A \cup B \subseteq (A_n^\varepsilon) \cup (B_n^\varepsilon).$$

As it is immediate to check the equality $(A^\varepsilon) \cup (B^\varepsilon) = (A \cup B)^\varepsilon$ for any closed subsets of $[0, 1]^2$, this concludes the proof. $\square$
**Corollary 3.3.** For any $k \in \mathbb{N}^*$, the space $\mathcal{P}_K^{k\uparrow}([0, 1]^2)$ equipped with the distance $d_H$ is compact.

Now we have all the necessary tools to prove Proposition 2.1.

*Proof of Proposition 2.1.* Let $\mu \in \mathcal{M}_{\text{fin}}$ and $k \in \mathbb{N}^*$. According to Lemma 3.1, the map $\mu$ defined from $\mathcal{P}_K^{k\uparrow}([0, 1]^2)$ to $[0, 1]$ is upper semi-continuous. It is well-known that any upper semi-continuous function defined on a compact set reaches its maximum. Hence, by Corollary 3.3, the definition of $\widetilde{\text{LIS}}_k(\mu)$ is actually a maximum.

Now let us turn to the semi-continuity of $\widetilde{\text{LIS}}_k$ on the space $\mathcal{M}_{\text{prob}}$. Let $(\mu_n)_{n \in \mathbb{N}}$ be a sequence of probability measures weakly converging to some $\mu$. We aim to prove:

$$ \widetilde{\text{LIS}}_k(\mu) \geq \limsup_{n \to \infty} \widetilde{\text{LIS}}_k(\mu_n). \qquad (3) $$

Up to extraction, suppose the right hand side is an actual limit. For each $n \in \mathbb{N}$, fix $A_n \in \mathcal{P}_K^{k\uparrow}([0, 1]^2)$ such that $\widetilde{\text{LIS}}_k(\mu_n) = \mu_n(A_n)$. Once again using Corollary 3.3, up to extraction (which does not change the right hand side limit in (3)), suppose the sequence $(A_n)_{n \in \mathbb{N}}$ converges to some $A$ in $\mathcal{P}_K^{k\uparrow}([0, 1]^2)$. Fix an arbitrary $\varepsilon > 0$. Recalling the definition of $d_H$, we have:

$$ \lim_{n \to \infty} \widetilde{\text{LIS}}_k(\mu_n) = \lim_{n \to \infty} \mu_n(A_n) \leq \limsup_{n \to \infty} \mu_n(A^\varepsilon) \leq \mu(A^\varepsilon) $$

where in the fourth inequality we used Portmanteau theorem and the fact that $A^\varepsilon$ is closed. Since this holds for any $\varepsilon > 0$ and $\mu(A^\varepsilon) \xrightarrow{\varepsilon \to 0} \mu(A)$, we deduce

$$ \lim_{n \to \infty} \widetilde{\text{LIS}}_k(\mu_n) \leq \mu(A) \leq \widetilde{\text{LIS}}_k(\mu). $$

This concludes the proof of (3), and thus of Proposition 2.1. The study of $\widetilde{\text{LIS}}_k$ is completely similar. $\square$

## 3.2 Convergence of shapes

To prove Proposition 2.2, we associate each permutation $\sigma \in \mathfrak{S}_n$ with a permuton that is appropriate to the study of longest increasing subsequences. The permuton $\mu_\sigma$ defined in Section 1.1 satisfies $\widetilde{\text{LIS}}(\mu_\sigma) = 0$, so we need to introduce a different one. If $a \leq b$ are integers, we use the notation $\llbracket a, b \rrbracket$ for the set $\{a, a+1, \dots, b\}$. For any $i, j \in \llbracket 1, n \rrbracket$, let

$$ C_{i,j} := \left[ \frac{i-1}{n}, \frac{i}{n} \right] \times \left[ \frac{j-1}{n}, \frac{j}{n} \right] $$

and $\Delta_{i,j}$ be the diagonal of $C_{i,j}$. Then define a permuton by putting uniform mass on these diagonals:

$$ \mu_{\sigma}^{\uparrow} := \frac{1}{n} \sum_{i=1}^{n} \text{Leb}_{\Delta_{i, \sigma(i)}} $$

where $\text{Leb}_{\Delta_{i, \sigma(i)}}$ denotes the normalized Lebesgue probability measure on $\Delta_{i, \sigma(i)}$. Since the Wasserstein distance between $\mu_\sigma^\uparrow$ and $\mu_\sigma$ is a $O(1/n)$, Theorem 1.1 implies:

**Lemma 3.4.** Let $\mu \in \mathcal{M}_{\text{unif}}$ and $\sigma_n \sim \text{Sample}_n(\mu)$ for each $n \in \mathbb{N}^*$. Then $\mu_{\sigma_n}^\uparrow \xrightarrow{n \to \infty} \mu$ almost surely.

Notice that this almost sure convergence holds regardless of the joint distribution of $\sigma_n$'s, as this is the case in Theorem 1.1.

Instead of these permutons, we could use the empirical measures of i.i.d. points distributed under $\mu$ (see Section 3.4) to prove Proposition 2.2. One advantage of introducing $\mu_\sigma^\uparrow$ is to also obtain an appropriate embedding of the set of permutations into the space of permutons. This embedding is adapted to the study of longest increasing subsequences, as stated in the following lemma:

**Lemma 3.5.** Let $\sigma \in \mathfrak{S}_n$. Then for any $k \in \mathbb{N}^*$:

$$ \widetilde{\text{LIS}}_k(\mu_{\sigma}^{\uparrow}) = \frac{\text{LIS}_k(\sigma)}{n}. $$
Proof. First, let $I_1, \dots, I_k$ be increasing subsequences of $\sigma$ such that $\text{LIS}_k(\sigma) = |I_1 \cup \dots \cup I_k|$. Then define for each $j \in [1, k]$:

$$A_j := \bigcup_{i \in I_j} \Delta_{i, \sigma(i)}.$$

Since $I_j$ is an increasing subsequence of $\sigma$, $A_j$ is in $\mathcal{P}_K^{\uparrow}([0, 1]^2)$. As $\mu_{\sigma}^{\uparrow}$ puts mass $1/n$ on each diagonal of its support, one has:

$$\frac{\text{LIS}_k(\sigma)}{n} = \frac{|I_1 \cup \dots \cup I_k|}{n} = \mu_{\sigma}^{\uparrow}(A_1 \cup \dots \cup A_k) \le \widetilde{\text{LIS}}_k(\mu_{\sigma}^{\uparrow}). \quad (4)$$

Next, using Proposition 2.1, let $B_1, \dots, B_k$ be closed nondecreasing subsets of $[0, 1]^2$ such that:

$$\widetilde{\text{LIS}}_k(\mu_{\sigma}^{\uparrow}) = \mu_{\sigma}^{\uparrow}(B_1 \cup \dots \cup B_k).$$

Then define for each $i \in [1, k]$:

$$J_i := \{j \in [1, n] : B_i \cap \Delta_{j, \sigma(j)} \neq \emptyset\}.$$

Since $B_i$ is nondecreasing, $J_i$ is an increasing subsequence of $\sigma$. Hence:

$$\widetilde{\text{LIS}}_k(\mu_{\sigma}^{\uparrow}) = \mu_{\sigma}^{\uparrow}(B_1 \cup \dots \cup B_k) \le \frac{|J_1 \cup \dots \cup J_k|}{n} \le \frac{\text{LIS}_k(\sigma)}{n}. \quad (5)$$

The lemma follows from Equations (4) and (5). $\square$

Proof of Proposition 2.2. First notice that if $\mu$ is a pre-permuton, its corresponding permuton $\hat{\mu}$ satisfies $\text{sh}(\hat{\mu}) = \text{sh}(\mu)$ and for each $n \in \mathbb{N}^*$, $\text{Sample}_n(\hat{\mu}) = \text{Sample}_n(\mu)$ (see e.g. Remark 1.2 in [BDMW24]). Thus we can assume for this proof that $\mu$ is a permuton.

On the one hand, using Lemmas 3.4 and 3.5 and Proposition 2.1:

$$\limsup_{n \to \infty} \frac{1}{n} \text{LIS}_k(\sigma_n) = \limsup_{n \to \infty} \widetilde{\text{LIS}}_k(\mu_{\sigma_n}^{\uparrow}) \le \widetilde{\text{LIS}}_k(\mu) \quad \text{almost surely.} \quad (6)$$

On the other hand, using Proposition 2.1, let $A$ be a closed $k$-nondecreasing subset of $[0, 1]^2$ such that $\widetilde{\text{LIS}}_k(\mu) = \mu(A)$. Let $\sigma_n := \text{Perm}(Z_1, \dots, Z_n)$ where $Z_1, \dots, Z_n$ are random i.i.d. points distributed under $\mu$, and define $S_n$ as the number of $Z_i$'s lying in $A$. Since $A$ is $k$-nondecreasing, those $S_n$ points can be written as a union of $k$ nondecreasing subsets. Hence:

$$\text{LIS}_k(\sigma_n) \ge S_n. \quad (7)$$

However $S_n$ follows a binomial law of parameter $(n, \mu(A))$, so the law of large numbers imply

$$\frac{S_n}{n} \xrightarrow{n \to \infty} \mu(A) = \widetilde{\text{LIS}}_k(\mu) \quad \text{almost surely.} \quad (8)$$

We point out the fact that this law of large numbers comes along with exponential concentration inequalities, so almost sure convergence holds regardless of the joint distribution of $S_n$'s. Using (7) and (8), we get:

$$\liminf_{n \to \infty} \frac{1}{n} \text{LIS}_k(\sigma_n) \ge \widetilde{\text{LIS}}_k(\mu) \quad \text{almost surely.} \quad (9)$$

Inequalities (6) and (9) conclude the proof for $\text{LIS}_k$. The proof of the analogous convergence for $\text{LDS}_k$ works the same, replacing $\mu_{\sigma}^{\uparrow}$ with a similar permuton $\mu_{\sigma}^{\downarrow}$ putting mass on antidiagonals. $\square$

To conclude this section, we explain how to derive Proposition 2.3 from Proposition 2.2. While the quantity $\text{sh}(\sigma)$ for $\sigma \in \mathfrak{S}_n$ does not quite belong to the Thoma simplex, this becomes the case in the $n \to \infty$ limit:

**Lemma 3.6.** For each $n \in \mathbb{N}^*$ consider a permutation $\sigma_n$ of size $n$, and define for all $k \in \mathbb{N}^*$:

$$\alpha_k := \limsup_{n \to \infty} \frac{\text{LIS}_k(\sigma_n) - \text{LIS}_{k-1}(\sigma_n)}{n} \quad \text{and} \quad \beta_k := \limsup_{n \to \infty} \frac{\text{LDS}_k(\sigma_n) - \text{LDS}_{k-1}(\sigma_n)}{n}.$$

Then the sequences $\alpha := (\alpha_k)_{k \ge 1}$ and $\beta := (\beta_k)_{k \ge 1}$ satisfy $(\alpha, \beta) \in \Omega$.
*Proof.* The monotony condition is a consequence of Theorem 1.2. To prove the sum condition, we fix an arbitrary $k \in \mathbb{N}^*$ and show the following:

$$ \sum_{i=1}^{k} \alpha_i + \sum_{j=1}^{k} \beta_j \le 1. \qquad (10) $$

For each $n \in \mathbb{N}^*$, denote by $A_{k,n}$ the number of boxes shared by the first $k$ rows and first $k$ columns of $\sigma_n$'s RS-shape. By Theorem 1.2, $\text{LIS}_k(\sigma_n)$ and $\text{LDS}_k(\sigma_n)$ are respectively the numbers of boxes in the first $k$ rows and columns of this diagram. Therefore by inclusion-exclusion:

$$ \text{LIS}_k(\sigma_n) + \text{LDS}_k(\sigma_n) \le n + A_{k,n}. $$

Moreover $A_{k,n}/n \le k^2/n \xrightarrow{n \to \infty} 0$, so inequality (10) follows. Since this holds for any integer $k$, the lemma is proved. $\square$

Finally, Proposition 2.3 is a direct consequence of Proposition 2.2 and Lemma 3.6.

### 3.3 Upper tail large deviation

The proof of Theorem 2.4 heavily hinges on the following celebrated result:

**Theorem 3.7** ([Cra38, DZ98]). Fix $p \in [0, 1]$ and consider for each $n \in \mathbb{N}^*$ a random variable $S_n$ following a binomial law of parameter $(n, p)$. Then for any $q \in (p, 1]$:

$$ \frac{1}{n} \log \mathbf{P}(S_n \ge nq) \xrightarrow{n \to \infty} -\Lambda_p^*(q) $$

with the notation of Section 2.2. Likewise for any $q \in [0, p)$:

$$ \frac{1}{n} \log \mathbf{P}(S_n < nq) \xrightarrow{n \to \infty} -\Lambda_p^*(q). $$

*Proof of Theorem 2.4.* If $\overline{\text{LIS}}_k(\mu) = 1$, there is nothing to prove. Now suppose $\overline{\text{LIS}}_k(\mu) < 1$. To prove the lower bound, let $A$ be a closed $k$-nondecreasing subset of $[0, 1]^2$ such that $\overline{\text{LIS}}_k(\mu) = \mu(A)$. Let $\sigma_n := \text{Perm}(Z_1, \dots, Z_n)$ where $Z_1, \dots, Z_n$ are random i.i.d. points distributed under $\mu$, and define $S_n$ as the number of $Z_i$'s lying in $A$. Since $S_n$ follows a binomial law of parameter $(n, \overline{\text{LIS}}_k(\mu))$, by Theorem 3.7 and inclusion of events:

$$ \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}_k(\sigma_n) \ge \alpha n) \ge \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(S_n \ge \alpha n) \ge -\Lambda_{\overline{\text{LIS}}_k(\mu)}^*(\alpha). $$

Next, let us prove the upper bound. The general idea is that if sampled permutations have a large $\text{LIS}_k$ then a lot of points were sampled in a large $k$-increasing subset of $\mu$. To find such a subset and make it deterministic, we condition on this rare event and extract a limit. Define

$$ x := - \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}_k(\sigma_n) \ge \alpha n) \in [0, +\infty] $$

and suppose, up to extraction, that this $\limsup$ is an actual limit. Our goal is to prove

$$ x \ge \Lambda_{\overline{\text{LIS}}_k(\mu)}^*(\alpha). \qquad (11) $$

If $x = +\infty$ this is trivial. Now suppose $x < +\infty$, which implies the existence of $n_0 \in \mathbb{N}^*$ such that for all $n \ge n_0$, $\mathbf{P}(\text{LIS}_k(\sigma_n) \ge \alpha n) > 0$. Thus for any $n \ge n_0$, we can consider random variables $Z_1^{(n)}, \dots, Z_n^{(n)}$ i.i.d. under $\mu$ conditioned to satisfy

$$ \text{LIS}_k(Z_1^{(n)}, \dots, Z_n^{(n)}) \ge \alpha n, $$
where the notation $\text{LIS}_k(Z_1^{(n)}, \dots, Z_n^{(n)})$ is shortcut for $\text{LIS}_k(\text{Perm}(Z_1^{(n)}, \dots, Z_n^{(n)}))$. Let $A_n$ be the maximal $k$-nondecreasing subset of $\{Z_1^{(n)}, \dots, Z_n^{(n)}\}$ (if there are several such subsets, choose one with an arbitrary rule). Then denote by $\nu_n$ the law of $A_n$ in $\mathcal{P}_K^{k\uparrow}([0, 1]^2)$. Up to extraction, the sequence $(\nu_n)_{n \ge n_0}$ weakly converges to some probability measure $\nu$ on $\mathcal{P}_K^{k\uparrow}([0, 1]^2)$. Let $B_0$ be an arbitrary element in the support of $\nu$ and $\ell \in (\widetilde{\text{LIS}}_k(\mu), \alpha)$. Since $\mu(B_0) \le \widetilde{\text{LIS}}_k(\mu) < \ell$, by monotone continuity there exists $\varepsilon > 0$ such that:

$$ \mu(B_0^\varepsilon) < \ell. \qquad (12) $$

Then by Portmanteau theorem and the fact that $B_0$ is in the support of $\nu$, we get:

$$ \liminf_{n \to \infty} \nu_n \left( \{B \in \mathcal{P}_K^{k\uparrow}([0, 1]^2) : d_H(B, B_0) < \varepsilon\} \right) \ge \nu \left( \{B \in \mathcal{P}_K^{k\uparrow}([0, 1]^2) : d_H(B, B_0) < \varepsilon\} \right) > 0. \quad (13) $$

However:

$$ \begin{aligned} & \nu_n \left( \{B \in \mathcal{P}_K^{k\uparrow}([0, 1]^2) : \text{dist}(B, B_0) < \varepsilon\} \right) \\ & \le \nu_n \left( \{B \in \mathcal{P}_K^{k\uparrow}([0, 1]^2) : B \subseteq B_0^\varepsilon\} \right) \\ & = \mathbf{P}_{\mu^{\otimes n}} \text{ (the maximal } k\text{-nondecreasing subset of } Z_1, \dots, Z_n \text{ is contained in } B_0^\varepsilon \mid \text{LIS}_k(Z_1, \dots, Z_n) \ge \alpha n \} \\ & \le \mathbf{P}_{\mu^{\otimes n}} \text{ (at least } \alpha n \text{ points among } Z_1, \dots, Z_n \text{ are in } B_0^\varepsilon \mid \text{LIS}_k(Z_1, \dots, Z_n) \ge \alpha n \} \end{aligned} $$

thus, writing $S_n$ for a binomial random variable of parameter $(n, \mu(B_0^\varepsilon))$:

$$ \nu_n \left( \{B \in \mathcal{P}_K([0, 1]^2) : \text{dist}(B, B_0) < \varepsilon\} \right) \le \frac{\mathbf{P}(S_n \ge \alpha n)}{\mathbf{P}(\text{LIS}_k(Z_1, \dots, Z_n) \ge \alpha n)}. $$

Now consider another binomial random variable $S'_n$ of parameter $(n, \ell)$. By (12), stochastic domination, Theorem 3.7 and the fact that $\ell < \alpha$:

$$ \frac{1}{n} \log \mathbf{P}(S_n \ge \alpha n) \le \frac{1}{n} \log \mathbf{P}(S'_n \ge \alpha n) \xrightarrow{n \to \infty} -\alpha \log \frac{\alpha}{\ell} - (1-\alpha) \log \frac{1-\alpha}{1-\ell}. $$

Then, using Equation (13) for the first equality:

$$ \begin{aligned} 0 &= \lim_{n \to \infty} \frac{1}{n} \log \nu_n \left( \{B \in \mathcal{P}_K([0, 1]^2) : \text{dist}(B, B_0) < \varepsilon\} \right) \\ &\le \lim_{n \to \infty} \frac{1}{n} \log \mathbf{P}(S'_n \ge \alpha n) - \lim_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}_k(Z_1, \dots, Z_n) \ge \alpha n) \\ &= x - \alpha \log \frac{\alpha}{\ell} - (1-\alpha) \log \frac{1-\alpha}{1-\ell}. \end{aligned} $$

Since this holds for any $\ell \in (\widetilde{\text{LIS}}_k(\mu), \alpha)$, we deduce (11) as desired. $\square$

## 3.4 Lower tail speed

The goal of this section is to establish Proposition 2.6 and Theorem 2.7 stating that, except in trivial cases, a lower tail large deviation principle for $\text{LIS}(\sigma_n)/n$ where $\sigma_n \sim \text{Sample}_n(\mu)$ should indeed have speed $n$.

*Proof of Proposition 2.6.* Let $j \ge 1$ and $A_j$ be a maximal $j$-nondecreasing subset for $\mu$. Notice that all permutations $\sigma$ satisfy $\text{LIS}_j(\sigma) \le j\text{LIS}(\sigma)$ by union bound. We can then write:

$$ \mathbf{P}(\text{LIS}(\sigma_n) < \beta n) \le \mathbf{P}(\text{LIS}_j(\sigma_n) < j\beta n) \le \mathbf{P}_{\mu^{\otimes n}} \text{ (less than } j\beta n \text{ points are in } A_j) = \mathbf{P}(S_n < j\beta n) $$

where $S_n$ is a binomial random variable of parameter $(n, \widetilde{\text{LIS}}_j(\mu))$. If $j$ satisfies $j\beta < \widetilde{\text{LIS}}_j(\mu)$, Theorem 3.7 implies:

$$ \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}(\sigma_n) < \beta n) \le -\Lambda_{\widetilde{\text{LIS}}_j(\mu)}^*(j\beta). $$

Since this bound is valid for all such $j$, Proposition 2.6 follows. $\square$
In order to prove Theorem 2.7 we recall a well known large deviation principle on empirical measures and apply it to our framework. See [DZ98] for a proof and [BDMW24] for another application to permuton theory.

**Theorem 3.8 (Sanov's theorem).** Let $\mu \in \mathcal{M}_{prob}$ and $(Z_i)_{i \in \mathbb{N}^*}$ be a family of i.i.d. random points distributed under $\mu$. Define for each $n \in \mathbb{N}^*$ the empirical measure

$$ \Delta_n := \frac{1}{n}(\delta_{Z_1} + \dots + \delta_{Z_n}) $$

Then the sequence $(\Delta_n)_{n \in \mathbb{N}^*}$ satisfies a large deviation principle

$$ \left\{ \begin{array}{ll} \text{for each open set } E \text{ of } \mathcal{M}_{prob}, & \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\Delta_n \in E) \geq - \inf_{\nu \in E} D(\nu|\mu); \\ \text{for each closed set } F \text{ of } \mathcal{M}_{prob}, & \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\Delta_n \in F) \leq - \inf_{\nu \in F} D(\nu|\mu); \end{array} \right. $$

with good rate function $D(\cdot|\mu)$, called the Kullback-Leibler divergence, defined by:

$$ \text{for all } \nu \in \mathcal{M}_{prob}, \quad D(\nu|\mu) := \begin{cases} \int_{[0,1]^2} \log \left( \frac{d\nu}{d\mu} \right) d\nu & \text{if } \nu \text{ is absolutely continuous with respect to } \mu; \\ +\infty & \text{otherwise.} \end{cases} $$

Let $k \in \mathbb{N}^*$. By upper semi-continuity, for any $\alpha, \beta \in [0, 1]$, $\{\nu \in \mathcal{M}_{prob} : \widetilde{\text{LIS}}_k(\nu) \geq \alpha\}$ is closed and $\{\nu \in \mathcal{M}_{prob} : \widetilde{\text{LIS}}_k(\nu) < \beta\}$ is open. Since $\widetilde{\text{LIS}}_k(\Delta_n) = \text{LIS}_k(Z_1, \dots, Z_n)/n$, we deduce the following corollary:

**Corollary 3.9.** Let $\mu \in \mathcal{M}_{unif}$, $\sigma_n \sim \text{Sample}_n(\mu)$ for each $n \in \mathbb{N}^*$, and $\alpha, \beta \in [0, 1]$. Then:

$$ \left\{ \begin{array}{ll} \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}_k(\sigma_n) < \beta n) \geq - \inf_{\nu \in \mathcal{M}_{prob}; \widetilde{\text{LIS}}_k(\nu) < \beta} D(\nu|\mu); \\ \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}_k(\sigma_n) \geq \alpha n) \leq - \inf_{\nu \in \mathcal{M}_{prob}; \widetilde{\text{LIS}}_k(\nu) \geq \alpha} D(\nu|\mu). \end{array} \right. $$

With the help of Corollary 3.9, we can now prove Theorem 2.7.

**Proof of Theorem 2.7.** We prove both equivalences (i) $\iff$ (ii) and (ii) $\iff$ (iii). Notice that (ii) $\implies$ (i) is immediate.

**Proof of (i) $\implies$ (ii).** We proceed by contraposition, and suppose that $\mathbf{P}(\text{LIS}(\sigma_{n_0}) < \beta n_0) > 0$ for some $n_0 \in \mathbb{N}^*$. By Robinson-Schensted correspondence (or Erdős-Szekeres lemma):

$$ \text{for any } n \in \mathbb{N}^* \text{ and } \sigma \in \mathfrak{S}_n, \text{ } \text{LIS}(\sigma)\text{LDS}(\sigma) \geq n. $$

Hence we get:

$$ \mathbf{P}(\text{LDS}(\sigma_{n_0}) \geq k+1) \geq \mathbf{P}\left(\text{LIS}(\sigma_{n_0}) < \frac{n_0}{k}\right) \geq \mathbf{P}(\text{LIS}(\sigma_{n_0}) < \beta n_0) > 0 $$

which in particular imposes $n_0 \geq k+1$, and then:

$$ \begin{aligned} 0 < \mathbf{P}_{\mu^{\otimes n_0}} \left( \exists i_1 < \dots < i_{k+1}, \{Z_{i_1}, \dots, Z_{i_{k+1}}\} \in \mathcal{P}_K^{\succ}([0, 1]^2) \right) \\ \leq \binom{n_0}{k+1} \mathbf{P}_{\mu^{\otimes k+1}} \left( \{Z_1, \dots, Z_{k+1}\} \in \mathcal{P}_K^{\succ}([0, 1]^2) \right). \end{aligned} $$

Thus, since the marginals of $\mu$ are continuous:

$$ \mathbf{P}_{\mu^{\otimes k+1}} \left( \{Z_1, \dots, Z_{k+1}\} \in \mathcal{P}_{k+1}^{\succ}([0, 1]^2) \right) > 0 $$

where $\mathcal{P}_{k+1}^{\succ}([0, 1]^2)$ denotes the set of nonincreasing subsets of $[0, 1]^2$ of cardinal $k+1$ whose elements share no common x- or y-coordinate. As a consequence, we can define the measure $\mu'$ as the law of $(Z_1, \dots, Z_{k+1})$ under
$\mu^{\otimes k+1}$ conditioned on the event $\{Z_1, \dots, Z_{k+1}\} \in \mathcal{P}_{k+1}^{\succ\succ}([0, 1]^2)$. Now take an element $(z_1, \dots, z_{k+1})$ in the support of $\mu'$. There exists $\varepsilon > 0$ satisfying:

$$ \text{for any } z'_1 \in B_d(z_1, \varepsilon), \dots, z'_{k+1} \in B_d(z_{k+1}, \varepsilon), \quad \{z_1, \dots, z'_{k+1}\} \text{ is nonincreasing.} \quad (14) $$

For all $i \in [1, k+1]$ the point $z_i$ is in the support of $\mu$, therefore $m_i := \mu(B_d(z_i, \varepsilon)) > 0$. Now define a measure $\nu$ as:

$$ \nu(\cdot) := \sum_{i=1}^{k+1} \frac{1}{(k+1)m_i} \mu(B_d(z_i, \varepsilon) \cap \cdot). $$

This probability measure is absolutely continuous with respect to $\mu$, with bounded density

$$ \frac{d\nu}{d\mu} = \sum_{i=1}^{k+1} \frac{1}{(k+1)m_i} \mathbf{1}_{B(z_i, \varepsilon)}. $$

Hence, using the notation of Theorem 3.8, $D(\nu|\mu) < +\infty$. Moreover, by (14) and the fact that $\nu$ puts mass $1/(k+1)$ on each ball of its support, $\widetilde{\text{LIS}}(\nu) \le 1/(k+1) < \beta$. Thus we can conclude with the first inequality of Corollary 3.9:

$$ \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}(\sigma_n) < \beta n) \ge -D(\nu|\mu) > -\infty. $$

Proof of (ii) $\implies$ (iii). Suppose (ii) holds. First let us show that under this hypothesis:

$$ \text{for all } n \in \mathbb{N}^*, \quad \mathbf{P}(\text{LDS}(\sigma_n) \le k) = 1. \quad (15) $$

For this, suppose there exists $n_0 \in \mathbb{N}^*$ such that $\mathbf{P}(\text{LDS}(\sigma_{n_0}) \ge k+1) > 0$. Then necessarily $n_0 \ge k+1$. Thus we can write, as before:

$$ 0 < \mathbf{P}(\text{LDS}(\sigma_{n_0}) \ge k+1) \le \binom{n_0}{k+1} \mathbf{P}(\text{LDS}(\sigma_{k+1}) = k+1) $$

whence $\mathbf{P}(\text{LIS}(\sigma_{k+1}) = 1) > 0$. Since $\beta(k+1) > 1$ this contradicts (ii), and (15) is established. Then by Robinson-Schensted's correspondence, $\mathbf{P}(\text{LIS}_k(\sigma_n) = n) = 1$ for all $n \in \mathbb{N}^*$. Using Proposition 2.2 we deduce:

$$ \widetilde{\text{LIS}}_k(\mu) = \lim_{n \to \infty} \frac{\text{LIS}_k(\sigma_n)}{n} = 1 \quad \text{almost surely.} $$

Proof of (iii) $\implies$ (ii). Suppose $\widetilde{\text{LIS}}_k(\mu) = 1$ and fix $n \in \mathbb{N}^*$. By Proposition 2.1 there exist nondecreasing subsets $A_1, \dots, A_k \in \mathcal{P}_K^{\succ}([0, 1]^2)$ such that $\mu(A_1 \cup \dots \cup A_k) = 1$. Thus if $Z_1, \dots, Z_n$ are i.i.d. random points distributed under $\mu$, by pigeonhole principle there must be at least $n/k$ of them in some $A_i$, implying:

$$ \mathbf{P}(\text{LIS}(\sigma_n) \ge \beta n) \ge \mathbf{P}(\text{LIS}(\sigma_n) \ge n/k) = 1 $$

as desired. $\square$

## 3.5 Lower tail rate function

Before proving Proposition 2.8, we state a simple lemma about conditional concentration of binomial laws.

**Lemma 3.10.** Let $S_n$ be a binomial random variable of parameter $(n, p)$ for some $0 < p < 1$. Then for any $q \in (0, p)$ and $\varepsilon > 0$ such that $q - \varepsilon > 0$, there exists $\delta > 0$ satisfying

$$ \mathbf{P} \left( q - \varepsilon \le \frac{S_n}{n} < q \mid \frac{S_n}{n} < q \right) = 1 - \exp \left( -n\delta + o(n) \right) \quad \text{as } n \to \infty. $$

Likewise for any $q \in (p, 1)$ and $\varepsilon > 0$ such that $q + \varepsilon < 1$, there exists $\delta > 0$ satisfying

$$ \mathbf{P} \left( q \le \frac{S_n}{n} < q + \varepsilon \mid \frac{S_n}{n} \ge q \right) = 1 - \exp \left( -n\delta + o(n) \right) \quad \text{as } n \to \infty. $$
<figure><img src="image_6.png" /><figcaption>Figure 6: Representation of both permutations $\mu_1$ (on the left) and $\mu_2$ (on the right) used to prove Proposition 2.8.</figcaption></figure>

*Proof.* Let us prove the first assertion, as the second one is analogous. Applying Theorem 3.7, we get as $n \to \infty$:

$$ \mathbf{P}(S_n/n < q) = \exp(-n\Lambda_p^*(q) + o(n)) \quad \text{and} \quad \mathbf{P}(S_n/n < q - \varepsilon) = \exp(-n\Lambda_p^*(q - \varepsilon) + o(n)). $$

Since $\Lambda_p^*(q - \varepsilon) > \Lambda_p^*(q)$, the assertion follows directly.

<figure><img src="image_7.png" /></figure>

*Proof of Proposition 2.8.* Define the following diagonals:

$$ \left\{ \begin{array}{l} D_1^1 \text{ from } (0, 0.5) \text{ to } (0.2, 0.7); \\ D_2^1 \text{ from } (0.2, 0) \text{ to } (0.5, 0.3); \\ D_3^1 \text{ from } (0.5, 0.7) \text{ to } (0.8, 1); \\ D_4^1 \text{ from } (0.8, 0.3) \text{ to } (1, 0.5); \end{array} \right. \quad \text{and} \quad \left\{ \begin{array}{l} D_1^2 \text{ from } (0, 0.42) \text{ to } (0.28, 0.7); \\ D_2^2 \text{ from } (0.28, 0) \text{ to } (0.58, 0.3); \\ D_3^2 \text{ from } (0.58, 0.7) \text{ to } (0.88, 1); \\ D_4^2 \text{ from } (0.88, 0.3) \text{ to } (1, 0.42); \end{array} \right. $$

then define $\mu_1$ and $\mu_2$ as the only permutations having support $\cup_{i=1}^4 D_i^1$ and $\cup_{i=1}^4 D_i^2$ respectively. See Figure 6 for a representation. These permutations satisfy $\tilde{\text{LIS}}(\mu_1) = \tilde{\text{LIS}}(\mu_2) = 0.6$, $\tilde{\text{LIS}}_2(\mu_1) = \tilde{\text{LIS}}_2(\mu_2) = 1$, and in particular $\tilde{\text{sh}}(\mu_1) = \tilde{\text{sh}}(\mu_2)$. Now fix $\beta := 0.55$. Our goal is to show that

$$ \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}(\tau_n) < \beta n) < \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}(\sigma_n) < \beta n) $$

where $\sigma_n \sim \text{Sample}_n(\mu_1)$ and $\tau_n \sim \text{Sample}_n(\mu_2)$. Let $n \in \mathbb{N}^*$ and, for each $j \in \{1, 2\}$, $Z_1^j, \dots, Z_n^j$ be random i.i.d. points distributed under $\mu_j$. Also define for each $i \in [1, 4]$, $S_{n,i}^j := |\{Z_1^j, \dots, Z_n^j\} \cap D_i^j|$. This is a binomial random variable of parameter $(n, p_i^j)$, where

$$ (p_1^1, p_2^1, p_3^1, p_4^1) = (0.2, 0.3, 0.3, 0.2) \quad \text{and} \quad (p_1^2, p_2^2, p_3^2, p_4^2) = (0.28, 0.3, 0.3, 0.12). $$

Moreover, these variables satisfy

$$ \text{almost surely for each } j \in \{1, 2\}, \quad \sum_{i=1}^{4} S_{n,i}^{j} = n. \qquad (16) $$

Now for each $j \in \{1, 2\}$, define the events

$$ A^j := \{\text{LIS}(Z_1^j, \dots, Z_n^j) < 0.55n\} \quad \text{and} \quad B^j := \{S_{n,2}^j + S_{n,3}^j < 0.55n\} $$

and notice the inclusion $A^j \subseteq B^j$. Let us study for each $j \in \{1, 2\}$ the probability of $A^j$ conditionally to $B^j$.

**Study of $\mu_1$.** Since $S_{n,2}^1 + S_{n,3}^1$ follows a binomial law of parameter $(n, 0.6)$, Lemma 3.10 implies:

$$ \mathbf{P} \left( 0.53 \le \frac{S_{n,2}^1 + S_{n,3}^1}{n} < 0.55 \mid B^1 \right) = 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty \qquad (17) $$
for some $\delta > 0$ whose value might change along the proof. Moreover, since $S_{n,1}^1 + S_{n,4}^1$ follows a binomial law of parameter $(n, 0.4)$ and $B^1 = \{S_{n,1}^1 + S_{n,4}^1 \ge 0.45n\}$ by (16), Lemma 3.10 also implies:

$$ \mathbf{P}\left(0.45 \le \frac{S_{n,1}^1 + S_{n,4}^1}{n} < 0.47 \mid B^1\right) = 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty. $$

Note that the law of $S_{n,2}^1$ conditional to the variable $S_{n,2}^1 + S_{n,3}^1$ is binomial of parameter $(S_{n,2}^1 + S_{n,3}^1, 0.5)$ (indeed the points appearing in $D_{n,2}^1 \cup D_{n,3}^1$ can be sampled by first determining their number $S_{n,2}^1 + S_{n,3}^1$ and then placing them uniformly at random). We can thus write:

$$ \begin{aligned} & \mathbf{P}\left(0.26 \le \frac{S_{n,2}^1}{n} < 0.28 \mid B^1\right) \\ & \ge \frac{\mathbf{P}\left(0.26 \le \frac{S_{n,2}^1}{n} < 0.28 \text{ and } 0.53 \le \frac{S_{n,2}^1+S_{n,3}^1}{n} < 0.55\right)}{\mathbf{P}(B^1)} \\ & \ge \mathbf{P}\left(\frac{S_{n,2}^1+S_{n,3}^1}{2n} - 0.005 \le \frac{S_{n,2}^1}{n} < \frac{S_{n,2}^1+S_{n,3}^1}{2n} + 0.005 \mid 0.53 \le \frac{S_{n,2}^1+S_{n,3}^1}{n} < 0.55\right) \\ & \quad \times \frac{\mathbf{P}\left(0.53 \le \frac{S_{n,2}^1+S_{n,3}^1}{n} < 0.55\right)}{\mathbf{P}(B^1)} \\ & \ge 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty \end{aligned} $$

for some $\delta > 0$, by Theorem 3.7 and (17). More generally we have:

$$ \left\{ \begin{array}{ll} \text{for } i \in \{2,3\}, & \mathbf{P}\left(0.26 \le \frac{S_{n,i}^1}{n} < 0.28 \mid B^1\right) \ge 1 - \exp(-n\delta + o(n)); \\ \text{for } i \in \{1,4\}, & \mathbf{P}\left(0.22 \le \frac{S_{n,i}^1}{n} < 0.24 \mid B^1\right) \ge 1 - \exp(-n\delta + o(n)); \end{array} \right. \qquad (18) $$

as $n \to \infty$ and for some $\delta > 0$. Under the events of (18), the longest increasing subsequence is formed by the points in $D_2^1$ and $D_3^1$ (see Figure 6). Subsequently:

$$ \mathbf{P}(\text{LIS}(Z_1^1, \dots, Z_n^1) = S_{n,2}^1 + S_{n,3}^1 \mid B^1) \ge 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty, $$

whence, using Equation (17):

$$ \mathbf{P}(A^1|B^1) \ge 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty. $$

Thanks to Theorem 3.7 we finally deduce:

$$ \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\text{LIS}(\sigma_n) < 0.55n) \ge \liminf_{n \to \infty} \frac{1}{n} \log \left( (1 - e^{-n\delta + o(n)}) \mathbf{P}(B^1) \right) = -\Lambda_{0.6}^*(0.55). \quad (19) $$

Study of $\mu_2$. We adapt the previous strategy. However, a key difference here is that the law of $S_{n,1}^2$ conditional to the variable $S_{n,1}^2 + S_{n,4}^2$ is binomial of parameter $(S_{n,1}^2 + S_{n,4}^2, 0.7)$. We get:

$$ \left\{ \begin{array}{ll} \mathbf{P}\left(0.53 \le \frac{S_{n,2}^2+S_{n,3}^2}{n} < 0.55 \mid B^2\right) \ge 1 - \exp(-n\delta + o(n)); \\ \mathbf{P}\left(0.45 \le \frac{S_{n,1}^2+S_{n,4}^2}{n} < 0.47 \mid B^2\right) \ge 1 - \exp(-n\delta + o(n)); \\ \mathbf{P}\left(0.26 \le \frac{S_{n,i}^2}{n} < 0.28 \mid B^2\right) \ge 1 - \exp(-n\delta + o(n)) \quad \text{for } i \in \{2,3\}; \\ \mathbf{P}\left(0.31 \le \frac{S_{n,1}^2}{n} < 0.33 \mid B^2\right) \ge 1 - \exp(-n\delta + o(n)); \\ \mathbf{P}\left(0.13 \le \frac{S_{n,4}^2}{n} < 0.15 \mid B^2\right) \ge 1 - \exp(-n\delta + o(n)); \end{array} \right. $$
as $n \to \infty$, for some $\delta > 0$. Under these events, the longest increasing subsequence is this time formed by the points in $D_1^2$ and $D_3^2$. Subsequently:

$$ \mathbf{P}(\mathrm{LIS}(Z_1^2, \dots, Z_n^2) = S_{n,1}^2 + S_{n,3}^2 \mid B^2) \geq 1 - \exp(-n\delta + o(n)) \quad \text{as } n \to \infty $$

whence

$$ \mathbf{P}(A^2|B^2) \leq \exp(-n\delta + o(n)) \quad \text{as } n \to \infty. $$

From this, (19) and Theorem 3.7 we finally deduce:

$$ \begin{aligned} \limsup_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\mathrm{LIS}(\tau_n) < 0.55n) &\leq \limsup_{n \to \infty} \frac{1}{n} \log (e^{-n\delta + o(n)} \mathbf{P}(B^2)) \\ &= -\delta - \Lambda_{0.6}^*(0.55) < -\Lambda_{0.6}^*(0.55) \leq \liminf_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\mathrm{LIS}(\sigma_n) < 0.55n) \end{aligned} $$

as announced.

□

# 4 Proofs of the results in Sections 2.3 and 2.4

## 4.1 Convergence of tableaux

*Proof of Proposition 2.9.* Recall that for any permutation $\sigma$, its subword $\sigma^{i,j}$ consists of letters with position at most $i$ and value at most $j$. Also recall that $\lambda_k^\sigma(i, j) = \mathrm{LIS}_k(\sigma^{i,j}) - \mathrm{LIS}_{k-1}(\sigma^{i,j})$, and that for any permuton $\mu$, we have $\tilde{\lambda}_k^\mu(x, y) = \tilde{\mathrm{LIS}}_k(\mu|_{[0,x]\times[0,y]}) - \tilde{\mathrm{LIS}}_{k-1}(\mu|_{[0,x]\times[0,y]})$. Let us first establish pointwise convergence. We aim to show that for any fixed $(x, y) \in [0, 1]^2$, almost surely:

$$ \frac{1}{n}\mathrm{LIS}_k\left(\sigma_n^{|nx|,|ny|}\right) \underset{n\to\infty}{\longrightarrow} \widetilde{\mathrm{LIS}}_k\left(\mu|_{[0,x]\times[0,y]}\right). \quad (20) $$

Let $Z_1, \dots, Z_n$ be random i.i.d. points under $\mu$, let $\sigma_n := \mathrm{Perm}(Z_1, \dots, Z_n)$, and define

$$ I := \{i \in \llbracket 1, n \rrbracket : Z_i \in [0, x] \times [0, 1]\} \quad ; \quad J := \{i \in \llbracket 1, n \rrbracket : Z_i \in [0, 1] \times [0, y]\}. $$

Then $\mathrm{Perm}((Z_i)_{i \in I \cap J}) = \sigma_n^{|I|,|J|}$. Moreover, conditional to its size $|I \cap J|$, the permutation $\mathrm{Perm}((Z_i)_{i \in I \cap J})$ follows the law $\mathrm{Sample}_{|I \cap J|}(\nu)$ where $\nu$ is the pre-permuton induced by $\mu$ on $[0, x] \times [0, y]$. As a consequence of Proposition 2.2 and the law of large numbers, we get:

$$ \frac{1}{n}\mathrm{LIS}_k\left(\sigma_n^{|I|,|J|}\right) = \frac{|I \cap J|}{n} \frac{1}{|I \cap J|} \mathrm{LIS}_k\left(\sigma_n^{|I|,|J|}\right) \underset{n \to \infty}{\longrightarrow} \mu([0, x] \times [0, y]) \widetilde{\mathrm{LIS}}_k(\nu) = \widetilde{\mathrm{LIS}}_k\left(\mu|_{[0,x] \times [0,y]}\right) $$

almost surely. Since the words $\sigma_n^{|nx|,|ny|}$ and $\sigma_n^{|I|,|J|}$ differ by at most $||nx|| - |I|| + ||ny|| - |J||$ letters, we have the following rough upper bound:

$$ \left| \mathrm{LIS}_k \left( \sigma_n^{|nx|,|ny|} \right) - \mathrm{LIS}_k \left( \sigma_n^{|I|,|J|} \right) \right| \leq |\lfloor nx \rfloor - |I|| + |\lfloor ny \rfloor - |J||. $$

Using the fact that $\mu$ is a permuton, i.e. that $\mathbf{P}(Z_i \in [0, x] \times [0, 1]) = x$ and $\mathbf{P}(Z_i \in [0, 1] \times [0, y]) = y$, the law of large numbers yields

$$ \frac{|nx| - |I|}{n} \underset{n \to \infty}{\longrightarrow} 0 \quad ; \quad \frac{|ny| - |J|}{n} \underset{n \to \infty}{\longrightarrow} 0 $$

almost surely, and (20) follows.

We can already use this pointwise convergence to deduce properties of $\tilde{\lambda}^\mu$. Let $j \in \llbracket 1, n \rrbracket$ and $i \in \llbracket 1, n-1 \rrbracket$. Since the P-tableau of $\sigma_n^{i+1,j}$ is obtained after Schensted-insertion of at most one letter in the P-tableau of $\sigma_n^{i,j}$, the shape of $\sigma_n^{i,j}$ is included in the shape of $\sigma_n^{i+1,j}$ and they differ by at most one box. This fact is also clear from Fomin's construction described later. Hence for any $k \in \mathbb{N}^*$:

$$ \lambda_k^{\sigma_n}(i, j) \leq \lambda_k^{\sigma_n}(i+1, j) \leq \lambda_k^{\sigma_n}(i, j) + 1. $$
Since for any $k \in \mathbb{N}^*$ and any $(x, y) \in [0, 1]^2$:

$$ \frac{1}{n}\lambda_k^{\sigma_n}([xn], [yn]) \underset{n \to \infty}{\longrightarrow} \tilde{\lambda}_k^{\mu}(x, y) \qquad (21) $$

almost surely by (20), we deduce that $\tilde{\lambda}_k^\mu$ in nondecreasing and 1-Lipschitz in its first variable. The same holds for its second variable.

To obtain uniform convergence, we simply need to adapt the proof of Dini's theorem. Fix $\epsilon > 0$ and $p := \lceil 1/\epsilon \rceil$. Using (21), almost surely for large enough $n$ we have:

$$ \text{for any } i, j \in [0, p], \quad \left| \frac{1}{n}\lambda_k^{\sigma_n}([ni/p], [nj/p]) - \tilde{\lambda}_k^{\mu}(i/p, j/p) \right| \le \epsilon $$

Let $(x, y) \in [0, 1]^2$ and $i, j \in [1, p]$ such that $(i-1)/p \le x \le i/p$ and $(j-1)/p \le y \le j/p$. Then:

$$ \begin{aligned} \tilde{\lambda}_k^{\mu}((i-1)/p, (j-1)/p) - \epsilon &\le \frac{1}{n}\lambda_k^{\sigma_n}([n(i-1)/p], [n(j-1)/p]) \\ &\le \frac{1}{n}\lambda_k^{\sigma_n}([nx], [ny]) \le \frac{1}{n}\lambda_k^{\sigma_n}([ni/p], [nj/p]) \le \tilde{\lambda}_k^{\mu}(i/p, j/p) + \epsilon. \end{aligned} $$

Since $\tilde{\lambda}_k^\mu$ in nondecreasing and 1-Lipschitz in both variables, we deduce:

$$ \left| \frac{1}{n}\lambda_k^{\sigma_n}([nx], [ny]) - \tilde{\lambda}_k^{\mu}(x, y) \right| \le \epsilon + 2/p \le 3\epsilon. $$

We proved that for any $\epsilon > 0$, almost surely

$$ \limsup_{n \to \infty} \left\| \frac{1}{n}\lambda_k^{\sigma_n}([n \cdot], [n \cdot]) - \tilde{\lambda}_k^{\mu} \right\|_{\infty} \le 3\epsilon. $$

By restricting to $\epsilon \in \mathbb{Q}_+^*$ we conclude that almost surely, uniform convergence holds. $\square$

## 4.2 Inverse Fomin dynamics

We start this section by recalling the “edge local rules” construction of Robinson-Schensted’s correspondence, as presented by Viennot in [Vie18]. Let $\sigma \in \mathfrak{S}_n$ and consider the grid $[0, n] \times [0, n]$. For each $1 \le i, j \le n$, fill the cell $c_{i,j} := [i-1, i] \times [j-1, j]$ with a point if and only if $\sigma(i) = j$. The algorithm labels the edges of each cell of the grid with nonnegative integers. Write $S(c), W(c), N(c), E(c)$ for the south, west, north, east edge labels of a cell $c$. We initialize the algorithm with

$$ \text{for each } 1 \le k \le n, \quad S(c_{k,1}) = 0 \quad \text{and} \quad W(c_{1,k}) = 0 $$

and the local rules are the following for each cell $c$:

* if $S(c) = W(c) = 0$ and the cell is empty then $N(c) = E(c) = 0$;

* if $S(c) = W(c) = 0$ and the cell is filled with a point then $N(c) = E(c) = 1$;

* if $S(c) = W(c) > 0$ then $N(c) = E(c) = S(c) + 1$;

* if $S(c) \neq W(c)$ then $N(c) = S(c)$ and $E(c) = W(c)$;

see Figure 7.

These edge rules are equivalent to Fomin’s growth diagrams algorithm, described in Section 5.2 of [Sag01], which labels the vertices of each cell $c$ of the grid with diagrams $SE(c), SW(c), NW(c), NE(c)$. This algorithm starts with empty diagrams on the south and west borders, and uses local rules to deduce for each cell $c$ the diagram $NE(c)$ from the other three diagrams and the presence or not of a permutation point. The local rules for Fomin’s growth diagrams are equivalent to Viennot’s edge local rules, in the sense that the label of an edge is $k > 0$ if and only if the diagrams at
<figure><img src="image_8.png" /><figcaption>Figure 7: Illustration of Fomin's direct local rules.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8: Fomin's rules applied to the permutation $\sigma = 35142$. On the left, diagram labels on vertices are used to represent the shapes of sub-words. On the right, integer labels on edges are used to represent the row length increments. For better readability, each integer label is associated with a color (green for 1, blue for 2, red for 3). We can recover the P- and Q-tableau from the integer labels on the east and north sides of the grid: $P(\sigma)$ contains the letters 1 and 2 in its first row, 3 and 4 in its second row, and 5 in its third row (in this example, $Q(\sigma) = P(\sigma)$ because $\sigma$ is an involution). A rectangle is highlighted for later reference.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 9: Illustration of Fomin's inverse local rules.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 10: Illustration of Property (22).</figcaption></figure>

its endpoints differ by exactly one box in their $k$-th row, and the label is 0 if and only if these diagrams are equal. It is possible to prove [Sag01] that the sequence of diagrams on the north border (resp. east border) of the grid encodes the Q-tableau (resp. P-tableau) of the permutation. Subsequently one can see that the diagram labeling any vertex $(i, j)$ is the RS-shape of the word $\sigma^{i,j}$. See Figure 8 for an example.

We can sum up these observations with our notation: for any $0 \le i \le i' \le n$, $0 \le j \le j' \le n$ and $k \in \mathbb{N}^*$, the number of edges labeled $k$ on any up-right path from $(i, j)$ to $(i', j')$ is equal to $\lambda_k^\sigma(i', j') - \lambda_k^\sigma(i, j)$.

In the previous algorithm, labels on the north and east sides of the grid read $Q(\sigma)$ and $P(\sigma)$, in the sense that the label of the $i$-th top edge (from the left) indicates which row of $Q(\sigma)$ contains the letter $i$, and the label of the $j$-th right edge (from the bottom) indicates which row of $P(\sigma)$ contains the letter $j$. Since Robinson-Schensted's correspondence is bijective, it is possible to retrieve the permutation and the labels on the whole grid from these north and east labels. This is done with the following edge rules, which we will refer to as Fomin's inverse local rules:

* if $N(c) = E(c) = 0$, then $S(c) = W(c) = 0$;

* if $N(c) = E(c) > 0$ then $S(c) = W(c) = N(c) - 1$;

* if $N(c) \neq E(c)$ then $S(c) = N(c)$ and $W(c) = E(c)$;

see Figure 9. This recursively reconstructs the labels on all edges of the grid, and permutation points are exactly in the cells with south/west labels 0 and north/east labels 1.

Let us introduce some formalism related to these rules. We shall study finite words on nonnegative integer letters, representing sequences of labels on vertical or horizontal lines of rectangular grids. For instance if the edges of a rectangular grid $\llbracket i, i' \rrbracket \times \llbracket j, j' \rrbracket$ are labeled with integers then the associated top-word is the "right-to-left" sequence of labels from $(i', j')$ to $(i, j')$. Similarly the associated right-word is the "top-to-bottom" sequence of labels from $(i', j')$ to $(i', j)$. Associated bottom- and left-words are defined analogously. For example on Figure 8 the highlighted rectangle yields top-word 3221, right-word 322, bottom-word 1010 and left-word 001.

Fomin's inverse rules can be interpreted as a map $\mathcal{F} = (\mathcal{F}_{\text{bot}}, \mathcal{F}_{\text{left}})$ with input a pair of top- and right-words and output a pair of bottom- and left-words. In the previous example: $\mathcal{F}(3221, 322) = (1010, 001)$. Notice that the symmetry of Fomin's inverse local rules implies the following property of $\mathcal{F}$:

$$ \text{for any words } w, w', \mathcal{F}(w', w) = (\mathcal{F}_{\text{left}}(w, w'), \mathcal{F}_{\text{bot}}(w, w')). $$
<figure><img src="image_12.png" /><figcaption>Figure 11: The effects of applying one letter to a word.</figcaption></figure>

If $w^{\text{top}}, w^{\text{right}}$ are words we sometimes say that $\mathcal{F}_{\text{bot}}(w^{\text{top}}, w^{\text{right}})$ is obtained by applying $w^{\text{right}}$ to $w^{\text{top}}$. In most reasonings we shall apply $w^{\text{right}}$ to $w^{\text{top}}$ letter by letter. This can be done since

$$ \text{for any } k \in \mathbb{N}, \quad \mathcal{F}_{\text{bot}}(w^{\text{top}}, k \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(\mathcal{F}_{\text{bot}}(w^{\text{top}}, k), w^{\text{right}}), \quad (22) $$

see Figure 10. We can therefore reformulate Fomin's inverse local rules as follows:

* applying the letter 0 to a word does not change it;

* applying a letter $k \ge 1$ to a word containing no $k$ does not change it. Otherwise it changes its first $k$ into a $k-1$, and then applies $k-1$ to the rest of the word;

see Figure 11.

If $w$ is a word and $h \in \mathbb{N}^*$, denote by $\#_h w$ the number of $h$'s in $w$. Since the number of edges labeled $h$ between two vertices does not depend on the up-right path taken, we deduce the following “mass conservation” property of $\mathcal{F}$:

$$ \text{for any words } w^{\text{top}}, w^{\text{right}}, \quad \#_h \mathcal{F}_{\text{left}}(w^{\text{top}}, w^{\text{right}}) + \#_h w^{\text{top}} = \#_h \mathcal{F}_{\text{bot}}(w^{\text{top}}, w^{\text{right}}) + \#_h w^{\text{right}}. \quad (23) $$

This will be useful in Section 4.6. We then define a pseudo-distance between words $w, w'$ by the following formula:

$$ \text{dist}_{\mathcal{F}}(w, w') := \sup_{h \in \mathbb{N}^*} \sup_{w^{\text{right}} \text{ word}} \left| \#_h \mathcal{F}_{\text{bot}}(w, w^{\text{right}}) - \#_h \mathcal{F}_{\text{bot}}(w', w^{\text{right}}) \right|. $$

The symmetry property of $\mathcal{F}$ implies that

$$ \text{dist}_{\mathcal{F}}(w, w') = \sup_{h \in \mathbb{N}^*} \sup_{w^{\text{top}} \text{ word}} \left| \#_h \mathcal{F}_{\text{left}}(w^{\text{top}}, w) - \#_h \mathcal{F}_{\text{left}}(w^{\text{top}}, w') \right|. $$

Let us conclude this section by explaining informally how we shall prove Theorem 2.10. By Proposition 2.9, $\tilde{\lambda}^{\mu}$ is approximated with $\lambda^{\sigma_n}$, whose increments are described by the edge labels of Fomin's construction. Therefore we aim to study the number of each label in the word $\mathcal{F}_{\text{bot}}(w_n^{\text{top}}, w_n^{\text{right}})$ where $w_n^{\text{top}}$ and $w_n^{\text{right}}$ are edge words of $\sigma_n$ on a local rectangle. To do this, our technique is to simplify the top- and right-words without changing “too much” the resulting bottom- and left-words. More precisely, we try to control the pseudo-distance $\text{dist}_{\mathcal{F}}$, whose associated equivalence relation we call “Fomin equivalence”. In Section 4.4 we prove that Fomin equivalence is implied by the well-known Knuth equivalence (for which we refer to Section 2.1 in [Ful96] and Section 3.4 in [Sag01]). This is done by checking that Fomin equivalence is preserved by the elementary Knuth transformations, and we can then use the fundamental fact that Knuth equivalence means equality of the P-tableaux. Independently, thanks to the derivability condition of Theorem 2.10, the labels of $w_n^{\text{top}}$ and $w_n^{\text{right}}$ are well equidistributed. One can see that the P-tableau of a word with bounded, equidistributed letters is similar to the P-tableau of this word's decreasing reordering. We deduce that $w_n^{\text{top}}$ and $w_n^{\text{right}}$ are “almost” Fomin equivalent to their decreasing reorderings; for this we need the regularity property of $\text{dist}_{\mathcal{F}}$ established in Section 4.3. This finally allows us to approximate the local increments of $\lambda^{\sigma_n}$ with the simpler case of decreasing words, studied in Section 4.5, and we conclude the proof of Theorem 2.10 in Section 4.6.
## 4.3 Regularity of inverse Fomin dynamics

In this section we investigate a regularity property of the map $\mathcal{F}$. This will allow us to control how much the output words of Fomin's inverse algorithm can change when the input words are replaced by approximations.

Fix $r \in \mathbb{N}^*$. We call block a (possibly empty) word with nondecreasing integer letters between 0 and $r$. If $\ell \in \mathbb{N}^*$ and $\mathbf{q} := (q_{i,k})_{1 \le i \le \ell, 0 \le k \le r} \in \mathbb{N}^{\ell(r+1)}$ is an array of nonnegative integers, define the word blocks($\mathbf{q}$) as the following concatenation of $\ell$ blocks:

$$ \text{blocks}(\mathbf{q}) := (0^{q_{1,0}} 1^{q_{1,1}} \dots r^{q_{1,r}}) \dots (0^{q_{i,0}} \dots k^{q_{i,k}} \dots r^{q_{i,r}}) \dots (0^{q_{\ell,0}} 1^{q_{\ell,1}} \dots r^{q_{\ell,r}}). $$

Also define a pseudo-distance on such arrays:

$$ \text{for any } \mathbf{q}, \mathbf{q}' \in \mathbb{N}^{\ell(r+1)}, \quad \delta(\mathbf{q}, \mathbf{q}') := \sum_{i=1}^{\ell} \sum_{k=1}^{r} |q_{i,k} - q'_{i,k}| k (8k^2)^{\ell-i}. $$

**Lemma 4.1.** Let $\mathbf{q} \in \mathbb{N}^{\ell(r+1)}$, $w := \text{blocks}(\mathbf{q})$, and $w^{\text{right}}$ be a word. Then there exists a distinguished $\tilde{\mathbf{q}} \in \mathbb{N}^{\ell(r+1)}$ such that $\mathcal{F}_{\text{bot}}(w, w^{\text{right}}) = \text{blocks}(\tilde{\mathbf{q}})$. With a slight abuse of notation, we denote this by $\mathcal{F}_{\text{bot}}(\mathbf{q}, w^{\text{right}}) = \tilde{\mathbf{q}}$. Moreover for any array $\mathbf{q}' \in \mathbb{N}^{\ell(r+1)}$:

$$ \delta(\mathcal{F}_{\text{bot}}(\mathbf{q}, w^{\text{right}}), \mathcal{F}_{\text{bot}}(\mathbf{q}', w^{\text{right}})) \le \delta(\mathbf{q}, \mathbf{q}'). $$

This last bound means that the pseudo-distance $\delta$ can not increase after applying a word, regardless of this word.

*Proof.* By induction it suffices to prove the lemma when $w^{\text{right}} = k$ is a single positive letter. The word $\mathcal{F}_{\text{bot}}(w, k)$ is obtained from $w$ by changing the first $k$ of some block to $k-1$, the first $k-1$ of another block to $k-2$, and so on. Since each new letter can be seen in the same block as the letter that produced it, this will allow us to write $\mathcal{F}_{\text{bot}}(w, k) = \text{blocks}(\tilde{\mathbf{q}})$ where $\tilde{\mathbf{q}}$ is obtained by doing local changes in $\mathbf{q}$.

Denote by $h$ the number of decrements that happen when applying $k$ to $w$, and by $i_k \le \dots \le i_{k-h+1}$ the block indices of these decrements. Since each block is nondecreasing, two decrements cannot happen in the same block, i.e. we have $i_k < i_{k-1} < \dots < i_{k-h+1}$. We can thus write $\mathcal{F}_{\text{bot}}(w, k) = \text{blocks}(\tilde{\mathbf{q}})$ where $\tilde{\mathbf{q}} \in \mathbb{N}^{\ell(r+1)}$ satisfies

$$ \tilde{q}_{i_k,k} = q_{i_k,k-1}; \quad \tilde{q}_{i_k,k-1} = q_{i_k,k-1}+1; \quad \dots; \quad \tilde{q}_{i_{k-h+1},k-h+1} = q_{i_{k-h+1},k-h+1}-1; \quad \tilde{q}_{i_{k-h+1},k-h} = q_{i_{k-h+1},k-h}+1; $$

and everywhere else $\mathbf{q}$ and $\tilde{\mathbf{q}}$ coincide. This establishes the first assertion of the lemma.

For the second assertion write $w' := \text{blocks}(\mathbf{q}')$ and $\tilde{\mathbf{q}}' := \mathcal{F}_{\text{bot}}(\mathbf{q}', k)$. Then define analogously $h' \in [0, k]$ and $1 \le i'_k < i'_{k-1} < \dots < i'_{k-h+1} \le \ell$. If the decrement indices are the same as for $\mathbf{q}$ i.e. $h' = h$ and $i_k = i'_k$, ..., $i_{k-h+1} = i'_{k-h+1}$, then $\delta(\tilde{\mathbf{q}}, \tilde{\mathbf{q}}') = \delta(\mathbf{q}, \mathbf{q}')$. The only possibility for the indices not to be the same is that some positive letter $j \in [1, k]$ in some block $i \in [1, k]$ of one word was decremented while the same block of the other word did not contain this letter. Suppose this happens and take $i$ minimal for this property. Then

$$ \text{either } \tilde{q}_{i,j} = q_{i,j-1} - 1 \text{ and } \tilde{q}'_{i,j} = q'_{i,j} = 0, \quad \text{or } \tilde{q}'_{i,j} = q'_{i,j-1} - 1 \text{ and } \tilde{q}_{i,j} = q_{i,j} = 0. $$

Only one of these occurs, and by symmetry we might suppose the first one does. Minimality of $i$ means that applying $k$ to $w$ and $w'$ starts with the same dynamics, up until their $i$-th block where the first $j$ of $w$ becomes $j-1$ and $j-1$ is applied to the rest of $w$ while this block in $w'$ remains unchanged and $j$ is applied to the rest of $w'$. These changes in the $i$-th block yield the equations:

$$ |\tilde{q}_{i,j} - \tilde{q}'_{i,j}| = |q_{i,j} - q'_{i,j}| - 1; \quad |\tilde{q}_{i,j-1} - \tilde{q}'_{i,j-1}| \le |q_{i,j-1} - q'_{i,j-1}| + 1. \quad (24) $$

In the following blocks, at most $2(j-1)$ values may change in $\mathbf{q}$ and at most $2j$ may in $\mathbf{q}'$. This yields a family of “disagreement” indices $A \subseteq [i+1, \ell] \times [1, j]$ of size $|A| \le 4j$ and such that:

$$ \text{for any } (i', j') \in [1, \ell] \times [1, r] \setminus (A \cup \{(i, j)\} \cup \{(i, j-1)\}), \quad |\tilde{q}_{i,j} - \tilde{q}'_{i,j}| = |q_{i,j} - q'_{i,j}|. \quad (25) $$

On disagreement indices we use the simple bound:

$$ \text{for any } (i', j') \in A, \quad |\tilde{q}_{i', j'} - \tilde{q}'_{i', j'}| \le |q_{i', j'} - q'_{i', j'}| + 2. \quad (26) $$
Using Equations (24) to (26) we finally deduce that:

$$
\begin{align*}
\delta(\tilde{\mathbf{q}}, \tilde{\mathbf{q}}') &\le \delta(\mathbf{q}, \mathbf{q}') - j(8j^2)^{\ell-i} + (j-1)(8(j-1)^2)^{\ell-i} + 8j \cdot j (8j^2)^{\ell-i-1} \\
&\le \delta(\mathbf{q}, \mathbf{q}') - j(8j^2)^{\ell-i} + (j-1)(8j^2)^{\ell-i} + 8j \cdot j (8j^2)^{\ell-i-1} \le \delta(\mathbf{q}, \mathbf{q}')
\end{align*}
$$

as desired.

<figure><img src="image_13.png" /></figure>

**Corollary 4.2.** Let **q**, **q'** ∈ N<sup>l(r+1)</sup> and w := blocks(**q**), w' := blocks(**q**'). The following holds:

$$
\mathrm{dist}_{\mathcal{F}}(w, w') \leq \delta(\mathbf{q}, \mathbf{q}').
$$

*Proof.* Fix $h \in \mathbb{N}^*$ and $w^{\text{right}}$ a word. Write $\tilde{\mathbf{q}} := \mathcal{F}_{\text{bot}}(\mathbf{q}, w^{\text{right}})$ and $\tilde{\mathbf{q}}' := \mathcal{F}_{\text{bot}}(\mathbf{q}', w^{\text{right}})$. Then:

$$
|\#_h \mathcal{F}_{\text{bot}}(w, w^{\text{right}}) - \#_h \mathcal{F}_{\text{bot}}(w', w^{\text{right}})| = \left| \sum_{i=1}^{\ell} \tilde{q}_{i,h} - \sum_{i=1}^{\ell} \tilde{q}'_{i,h} \right| \le \delta(\tilde{\mathbf{q}}, \tilde{\mathbf{q}}') \le \delta(\mathbf{q}, \mathbf{q}')
$$

where the last inequality is given by Lemma 4.1.

<figure><img src="image_14.png" /></figure>

**4.4 Fomin and Knuth equivalence**

We say that two words w, w' are Fomin equivalent or simply equivalent, denoted w ≡ w', when dist<sub>Γ</sub>(w, w') = 0.
This means that applying any word to w and w' yields resulting words with the same amount of each non-zero label.
In particular two equivalent words have the same number of k's for any k ∈ N*, but not necessarily the same number
of 0's.

**Lemma 4.3.** Let $w, w', w^{\text{right}}$ be words. If $w \equiv w'$ then:

$$
\mathcal{F}_{\text{bot}}(w, w^{\text{right}}) \equiv \mathcal{F}_{\text{bot}}(w', w^{\text{right}}).
$$

*Proof.* It suffices to observe that for any word $w_2^{\text{right}}$:

$$
\mathcal{F}_{\text{bot}}\left(\mathcal{F}_{\text{bot}}(w, w^{\text{right}}), w_2^{\text{right}}\right) = \mathcal{F}_{\text{bot}}\left(w, w^{\text{right}} w_2^{\text{right}}\right)
$$

and likewise with $w'$. The lemma then follows directly from definition.

<figure><img src="image_15.png" /></figure>

**Lemma 4.4.** If $w, w'$ are words and $i \in \mathbb{N}$:

$$
w \equiv w' \implies i \cdot w \equiv i \cdot w' \text{ and } w \cdot i \equiv w' \cdot i
$$

*Proof.* We aim to prove that for any word $w^{\text{right}}$ the following holds: for any pair of equivalent words $w \equiv w'$, any $i \in \mathbb{N}$ and any $h \in \mathbb{N}^*$,

$$
\#_h \mathcal{F}_{\text{bot}}(i \cdot w, w^{\text{right}}) = \#_h \mathcal{F}_{\text{bot}}(i \cdot w', w^{\text{right}}) \quad \text{and} \quad \#_h \mathcal{F}_{\text{bot}}(w \cdot i, w^{\text{right}}) = \#_h \mathcal{F}_{\text{bot}}(w' \cdot i, w^{\text{right}}). \tag{27}
$$

We do this by induction on the length of $w^{\text{right}}$. If $w^{\text{right}}$ is empty, (27) is immediate since equivalent words have the same amount of each positive letter. Now suppose this holds for some word $w^{\text{right}}$ and let us prove it for every word $j \cdot w^{\text{right}}$ with $j \in \mathbb{N}$. Fix $w \equiv w'$ and $i \in \mathbb{N}$.

For the first equality of (27) we distinguish between two cases. If $i = j$ then, using Property (22):

$$
\mathcal{F}_{\text{bot}}(i \cdot w, j \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(i \cdot w, i \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}((i-1)^{+} \cdot \mathcal{F}_{\text{bot}}(w, (i-1)^{+}), w^{\text{right}}) \quad (28)
$$

where we used the standard notation $(i-1)^+ = \max(i-1, 0)$, and likewise for $w'$. See the left part of Figure 12 for a representation. Lemma 4.3 implies $\mathcal{F}_{\text{bot}}(w, (i-1)^+) \equiv \mathcal{F}_{\text{bot}}(w', (i-1)^+)$ and the first part of (27) follows by induction.

Otherwise $i \neq j$ and

$$
\mathcal{F}_{\text{bot}}(i \cdot w, j \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(i \cdot \mathcal{F}_{\text{bot}}(w, j), w^{\text{right}}),
$$
<figure><img src="image_16.png" /><figcaption>Figure 12: Illustration of equalities (28) and (30) used to prove Lemma 4.4.</figcaption></figure>

likewise for $w'$. Lemma 4.3 implies $\mathcal{F}_{\text{bot}}(w, j) \equiv \mathcal{F}_{\text{bot}}(w', j)$ and the first part of (27) follows once again by induction.

For the second equality of (27), observe that applying $j$ to $w \cdot i$ decrements a number of letters in $w$, say $k \in [0, j]$, and then applies $j-k = \mathcal{F}_{\text{left}}(w, j)$ to $i$ (resp. $w', k'$). Therefore

$$ \mathcal{F}_{\text{bot}}(w \cdot i, j) = \mathcal{F}_{\text{bot}}(w, j) \cdot \mathcal{F}_{\text{bot}}(i, j-k) \quad \text{and} \quad \mathcal{F}_{\text{bot}}(w' \cdot i, j) = \mathcal{F}_{\text{bot}}(w', j) \cdot \mathcal{F}_{\text{bot}}(i, j-k'). \quad (29) $$

Since $k$ is a number of decrements, it can be expressed as the sum of all letters of $w$ minus the sum of all letters of $\mathcal{F}_{\text{bot}}(w, j)$. As such:

$$ k = \sum_{h \ge 1} h \, \#_h w - h \, \#_h \mathcal{F}_{\text{bot}}(w, j) = \sum_{h \ge 1} h \, \#_h w' - h \, \#_h \mathcal{F}_{\text{bot}}(w', j) = k' $$

where the second equality is a consequence of $w \equiv w'$. Finally, using (29) and Property (22) (see the right part of Figure 12):

$$ \left\{ \begin{array}{l} \mathcal{F}_{\text{bot}}(w \cdot i, j \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(\mathcal{F}_{\text{bot}}(w, j) \cdot i', w^{\text{right}}); \\ \mathcal{F}_{\text{bot}}(w' \cdot i, j \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(\mathcal{F}_{\text{bot}}(w', j) \cdot i', w^{\text{right}}); \end{array} \right. \qquad (30) $$

where $i' = \mathcal{F}_{\text{bot}}(i, j-k)$, and we conclude by induction. $\square$

**Corollary 4.5.** For any words $w_1, w_2, w'_1, w'_2$ such that $w_1 \equiv w'_1$ and $w_2 \equiv w'_2$, we have $w_1 w_2 \equiv w'_1 w'_2$.

*Proof.* Successive application of Lemma 4.4 yield both $w_1 w_2 \equiv w_1 w'_2$ and $w'_1 w'_2 \equiv w_1 w'_2$, whence the result. $\square$

Using $0 \equiv \emptyset$, this yields the following fact (which was actually quite clear from the beginning):

**Corollary 4.6.** Any word is equivalent to itself without its 0's.

**Lemma 4.7.** For any integers $i < j \le k$, $j i k \equiv j k i$.

*Proof.* If $i = 0$ then this is a direct consequence of Corollary 4.6. Now suppose $i \ge 1$. The strategy is the same as for the proof of Lemma 4.4. We aim to prove that for any word $w^{\text{right}}$ the following holds: for any integers $i < j \le k$ and any $h \in \mathbb{N}^*$,

$$ \#_h \mathcal{F}_{\text{bot}}(j i k, w^{\text{right}}) = \#_h \mathcal{F}_{\text{bot}}(j k i, w^{\text{right}}). \qquad (31) $$

We do this by induction on the length of $w^{\text{right}}$. If $w^{\text{right}}$ is empty, (31) is immediate. Now suppose this holds for some word $w^{\text{right}}$ and let us prove it for every word $m \cdot w^{\text{right}}$ with $m \in \mathbb{N}$.

If $m = i$ then

$$ \mathcal{F}_{\text{bot}}(j i k, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(j i-1 k, w^{\text{right}}); \quad \mathcal{F}_{\text{bot}}(j k i, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(j k i-1, w^{\text{right}}). $$

Since $i-1 < j \le k$, (31) follows by induction.

If $m = j$ then

$$ \mathcal{F}_{\text{bot}}(j i k, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(j-1 i' k, w^{\text{right}}); \quad \mathcal{F}_{\text{bot}}(j k i, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(j-1 k i', w^{\text{right}}) $$
where $i' = i \land (j-2)$. Since $i' < j-1 \le k$, (31) follows by induction.

If $m = k$ we distinguish between two cases. If $j = k$ then $m = j$ and this case was already treated. If $j \le k-1$ then $i \le k-2$ and

$$ \mathcal{F}_{\text{bot}}(jik, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(jik-1, w^{\text{right}}); \mathcal{F}_{\text{bot}}(jki, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(jk-1i, w^{\text{right}}). $$

Since $i < j \le k-1$, (31) follows by induction.

Otherwise $m \notin \{i, j, k\}$ and

$$ \mathcal{F}_{\text{bot}}(jik, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(jik, w^{\text{right}}), $$

likewise for $jki$. (31) follows once again by induction, and this concludes the proof. □

**Lemma 4.8.** For any integers $i \le j < k$, $ikj \equiv kij$.

*Proof.* If $i = 0$ then this is a direct consequence of Corollary 4.6. Now suppose $i \ge 1$. We proceed as before and aim to prove that for any word $w^{\text{right}}$ the following holds: for any integers $i \le j < k$ and any $h \in \mathbb{N}^*$,

$$ \#_h \mathcal{F}_{\text{bot}}(ikj, w^{\text{right}}) = \#_h \mathcal{F}_{\text{bot}}(kij, w^{\text{right}}). \qquad (32) $$

We do this by induction on the length of $w^{\text{right}}$. If $w^{\text{right}}$ is empty, (32) is immediate. Now suppose this holds for some word $w^{\text{right}}$ and let us prove it for every word $m \cdot w^{\text{right}}$ with $m \in \mathbb{N}$.

The cases $m = i, m = j$ and $m \notin \{i, j, k\}$ are handled just like in the proof of Lemma 4.7. The only subtlety comes when $m = k$. In this case, if $i = k-1$ then $j = k-1$ and

$$ \mathcal{F}_{\text{bot}}(ikj, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(k-1k-1k-2, w^{\text{right}}) $$

while

$$ \mathcal{F}_{\text{bot}}(kij, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(k-1k-2k-1, w^{\text{right}}). $$

We can thus apply Lemma 4.7 to get $k-1k-1k-2 \equiv k-1k-2k-1$, and directly conclude. If $i < k-1$ then

$$ \mathcal{F}_{\text{bot}}(ikj, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(ik-1j', w^{\text{right}}); \mathcal{F}_{\text{bot}}(kij, m \cdot w^{\text{right}}) = \mathcal{F}_{\text{bot}}(k-1ij', w^{\text{right}}) $$

where $j' = j \land (k-2)$. Since $i \le j' < k$, (32) follows by induction. □

Lemmas 4.7 and 4.8 together with Corollary 4.5 tell us transforming within a word any triplet $jik$ where $i < j \le k$ into $jki$ or $ikj$ where $i \le j < k$ into $kij$ preserves Fomin equivalence. In other words, two adjacent letters can be switched if they are followed or preceded by an intermediate value, and equality cases are handled by considering that among two letters with the same value, the greatest is the one that comes last in the word. These transformations are known as *elementary Knuth transformations*. Two words are said to be *Knuth equivalent* when they differ by successive elementary transformations. We have thus proved:

**Proposition 4.9.** If two finite words are Knuth equivalent then they are Fomin equivalent.

We have not been able to determine whether the converse is true or not, but we believe this could be an interesting question. Now, we shall use the following well-known result about Knuth equivalence:

**Theorem 4.10** ([Ful96, Sag01]). Two words are Knuth equivalent if and only if they have the same P-tableau.

This theorem is the last puzzle piece we needed to combine our previous results into Proposition 4.11, which shall prove useful in the permutation setting. First we state some key observation.

Fix $r \in \mathbb{N}^*$. Let $w$ be a word on letters between 1 and $r$ and $P(w)$ its P-tableau. For any $i \in [1, r]$ and $k \in [0, r]$, denote by $q_{i,k}(w)$ the number of $k$'s in the $(r-i+1)$-st row of $P(w)$ (notice that $q_{i,k}(w) = 0$ whenever $i > k$). By Theorem 4.10, the array

$$ q(w) = (q_{i,k}(w))_{1 \le i \le r, 0 \le k \le r} \in \mathbb{N}^{r(r+1)} $$

characterizes the Knuth equivalence class of $w$. Moreover Theorem 1.2 allows to describe this array in terms of nondecreasing subsequences of $w$. Indeed, writing $w \le k$ for the sub-word of $w$ consisting of its letters with values at
most k, recall that the P-tableau of $w^{\le k}$ is the restriction of $P(w)$ to its values at most k. Thus $\text{LIS}_i(w^{\le k})$ is the number of boxes with values at most k in the first i rows of $P(w)$, and we deduce:

$$ q_{r-i+1,k}(w) = \text{LIS}_i(w^{\le k}) - \text{LIS}_i(w^{\le k-1}) - \text{LIS}_{i-1}(w^{\le k}) + \text{LIS}_{i-1}(w^{\le k-1}). \quad (33) $$

With the notation of Section 4.2, the word blocks($\mathbf{q}(w)$) is the concatenation of all rows of $P(w)$, from last to first. It is usually called the row word of $P(w)$, and one can see that its P-tableau is $P(w)$ (see Lemma 3.4.5 in [Sag01] or Section 2.1 in [Ful96]). Hence blocks($\mathbf{q}(w)$) is a distinguished word in the Knuth equivalence class of $w$. These facts lead to the following result:

**Proposition 4.11.** Fix $r \in \mathbb{N}^*$, $\gamma_1, \dots, \gamma_r \in \mathbb{N}$ and set $w_{\text{ord}} := r^{\gamma_r} \dots 1^{\gamma_1}$. For $k \in [1, r]$ denote by $\gamma_{(1)}^k \ge \dots \ge \gamma_{(k)}^k$ the weakly decreasing order statistics of $\gamma_1, \dots, \gamma_k$. Let $w$ be a word on letters between 1 and $r$ and define for each $i \in [1, r]$:

$$ \eta_{i,k} := |\gamma_{(1)}^k + \dots + \gamma_{(i)}^k - \text{LIS}_i(w^{\le k})| $$

where $\gamma_{(i)}^k := 0$ if $i > k$. Then we have the following upper bound:

$$ \text{dist}_{\mathcal{F}}(w, w_{\text{ord}}) \le 4r(8r^2)^r \max_{1 \le i, k \le r} \eta_{i,k}. $$

*Proof.* Let $i, k \in [1, r]$. Since any nondecreasing sequence of $w_{\text{ord}}$ can only have one type of letter, it is easy to see that

$$ \text{LIS}_i(w_{\text{ord}}^{\le k}) = \gamma_{(1)}^k + \dots + \gamma_{(i)}^k. $$

Thus Equation (33) yields

$$ |q_{r-i+1,k}(w) - q_{r-i+1,k}(w_{\text{ord}})| \le \eta_{i,k} + \eta_{i,k-1} + \eta_{i-1,k} + \eta_{i-1,k-1}. \quad (34) $$

Since $w$ is Knuth equivalent to blocks($\mathbf{q}(w)$) and likewise for $w_{\text{ord}}$, Proposition 4.9 implies

$$ \text{dist}_{\mathcal{F}}(w, w_{\text{ord}}) = \text{dist}_{\mathcal{F}}(\text{blocks}(\mathbf{q}(w)), \text{blocks}(\mathbf{q}(w_{\text{ord}}))). $$

We can then apply Corollary 4.2 with (34) to obtain:

$$ \text{dist}_{\mathcal{F}}(w, w_{\text{ord}}) \le \delta(\mathbf{q}(w), \mathbf{q}(w_{\text{ord}})) \le 4r(8r^2)^r \max_{1 \le i, k \le r} \eta_{i,k}. \quad \square $$

## 4.5 Study of decreasing labels

For any $r \in \mathbb{N}^*$ and $(\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r} \in \mathbb{N}^r$, define

$$ \phi((\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r}) := \beta_1 + \#_1 \mathcal{F}_{\text{bot}}(r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1}). \quad (35) $$

For example $\phi((\alpha_1), (\beta_1)) = \beta_1 + (\alpha_1 - \beta_1)^+ = \alpha_1 \vee \beta_1$, and

$$ \phi((\alpha_1, \alpha_2), (\beta_1, \beta_2)) = \beta_1 + ((\alpha_1 - (\alpha_2 \wedge \beta_2))^+ + (\alpha_2 \wedge \beta_2) - \beta_1)^+ = \alpha_1 \vee \beta_1 \vee (\alpha_2 \wedge \beta_2). $$

Notice that the index $r$ can be omitted on $\phi$, since

$$ \phi((\alpha_1, \dots, \alpha_r, 0, \dots, 0), (\beta_1, \dots, \beta_r, 0, \dots, 0)) = \phi((\alpha_1, \dots, \alpha_r), (\beta_1, \dots, \beta_r)). $$

This section is devoted to the study of this function and its continuous extension to sequences of real numbers.

**Proposition 4.12.** For each $r \ge 1$, the function $\phi$ has a unique continuous extension from $(\mathbb{N}^r)^2$ to $(\mathbb{R}_+^r)^2$ satisfying the following homogeneity property:

$$ \text{for any } c \in \mathbb{R}_+ \text{ and } (\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r} \in \mathbb{R}_+^r, \quad \phi((c\alpha_k), (c\beta_k)) = c\phi((\alpha_k), (\beta_k)). \quad (36) $$
Proof. For stability reasons, we prove this by studying the dynamics of block words as defined in Section 4.2. Let $r \ge 1$ and $\mathbf{a} = (a_0, \dots, a_r)$, $\mathbf{b} = (b_0, \dots, b_r) \in \mathbb{N}^{r+1}$. Define

$$ \varphi(\mathbf{a}, \mathbf{b}) = (\varphi_0(\mathbf{a}, \mathbf{b}), \varphi_1(\mathbf{a}, \mathbf{b}), \dots, \varphi_{r-1}(\mathbf{a}, \mathbf{b}), \varphi_r(\mathbf{a}, \mathbf{b})) \\ := (a_0 + (a_1 \wedge b_1), (a_1 - b_1)^+ + (a_2 \wedge b_2), \dots, (a_{r-1} - b_{r-1})^+ + (a_r \wedge b_r), (a_r - b_r)^+). \quad (37) $$

One can then see that the following holds:

$$ \left\{ \begin{array}{l} \mathcal{F}_{\text{bot}}(0^{a_0} \dots r^{a_r}, 0^{b_0} \dots r^{b_r}) := 0^{\varphi_0(\mathbf{a}, \mathbf{b})} \dots r^{\varphi_r(\mathbf{a}, \mathbf{b})}; \\ \mathcal{F}_{\text{left}}(0^{a_0} \dots r^{a_r}, 0^{b_0} \dots r^{b_r}) := 0^{\varphi_0(\mathbf{b}, \mathbf{a})} \dots r^{\varphi_r(\mathbf{b}, \mathbf{a})}. \end{array} \right. $$

Now let us study the effect of applying a single block to a sequence of blocks. For any $\ell \in \mathbb{N}^*$ and any array $\mathbf{q} = (q_{i,k})_{1 \le i \le \ell, 0 \le k \le r} \in \mathbb{N}^{\ell(r+1)}$, one has:

$$ \begin{aligned} & \mathcal{F}_{\text{bot}}(0^{q_{1,0}} \dots r^{q_{1,r}} \dots 0^{q_{\ell,0}} \dots r^{q_{\ell,r}}, 0^{b_0} \dots r^{b_r}) \\ &= \mathcal{F}_{\text{bot}}(0^{q_{1,0}} \dots r^{q_{1,r}}, 0^{b_0} \dots r^{b_r}) \cdot \mathcal{F}_{\text{bot}}(0^{q_{2,0}} \dots r^{q_{2,r}} \dots 0^{q_{\ell,0}} \dots r^{q_{\ell,r}}, \mathcal{F}_{\text{left}}(0^{q_{1,0}} \dots r^{q_{1,r}}, 0^{b_0} \dots r^{b_r})) \\ &= 0^{\varphi_0(\mathbf{q}_{1,\mathbf{b}})} \dots r^{\varphi_r(\mathbf{q}_{1,\mathbf{b}})} \cdot \mathcal{F}_{\text{bot}}(0^{q_{2,0}} \dots r^{q_{2,r}} \dots 0^{q_{\ell,0}} \dots r^{q_{\ell,r}}, 0^{\varphi_0(\mathbf{b},\mathbf{q}_{1})} \dots r^{\varphi_r(\mathbf{b},\mathbf{q}_{1})}). \end{aligned} $$

where $\mathbf{q}_1 := (q_{1,k})_{0 \le k \le r}$. We see by induction that this resulting word is yet again a concatenation of $\ell$ blocks. With a slight abuse of notation, define $\varphi(\mathbf{q}, \mathbf{b}) = (\varphi_{i,k}(\mathbf{q}, \mathbf{b}))_{1 \le i \le \ell, 0 \le k \le r} := \mathcal{F}_{\text{bot}}(\mathbf{q}, 0^{b_0} \dots r^{b_r})$ with the notation of Lemma 4.1. Last calculation showed the following recursive formula for $\varphi$:

$$ \left\{ \begin{array}{l} \varphi_{1,\ell}(\mathbf{q}, \mathbf{b}) = \varphi(\mathbf{q}_1, \mathbf{b}) \\ (\varphi_{i,k}(\mathbf{q}, \mathbf{b}))_{2 \le i \le \ell, 0 \le k \le r} = \varphi(\mathbf{q} \setminus \mathbf{q}_1, \varphi(\mathbf{b}, \mathbf{q}_1)) \end{array} \right. \quad (38) $$

where $\mathbf{q} \setminus \mathbf{q}_1 := (q_{i,k})_{2 \le i \le \ell, 0 \le k \le r}$. Finally for any $\ell' \in \mathbb{N}^*$ and $\mathbf{q}' = (q'_{i,k})_{1 \le i \le \ell', 0 \le k \le r} \in \mathbb{N}^{\ell'(r+1)}$, define $\varphi(\mathbf{q}, \mathbf{q}') = (\varphi_{i,k}(\mathbf{q}, \mathbf{q}'))_{1 \le i \le \ell', 0 \le k \le r} := \mathcal{F}_{\text{bot}}(\mathbf{q}, \text{blocks}(\mathbf{q}')).$ Then $\varphi$ satisfies the following recursion if $\ell' \ge 2$:

$$ \varphi(\mathbf{q}, \mathbf{q}') = \varphi(\varphi(\mathbf{q}, \mathbf{q}'_1), \mathbf{q}' \setminus \mathbf{q}'_1). \quad (39) $$

One advantage of this point of view is that Equations (37) to (39) can be used to continuously extend $\varphi$ from $\mathbb{N}^{\ell(r+1)} \times \mathbb{N}^{\ell'(r+1)}$ to $\mathbb{R}_+^{\ell(r+1)} \times \mathbb{R}_+^{\ell'(r+1)}$. Then $\phi$ can be continuously extended to $(\mathbb{R}_+^r)^2$ by letting, for any $r \ge 1$ and $(\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r} \in \mathbb{R}_+^r$:

$$ \phi((\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r}) = \beta_1 + \sum_{i=1}^{r} \varphi_{i,1}(\mathbf{q}_{\alpha}, \mathbf{q}_{\beta}) $$

where $\mathbf{q}_{\alpha}, \mathbf{q}_{\beta} \in \mathbb{R}_+^{r(r+1)}$ are such that $r^{\alpha_r} \dots 1^{\alpha_1} = \text{blocks}(\mathbf{q}_{\alpha})$ and $r^{\beta_r} \dots 1^{\beta_1} = \text{blocks}(\mathbf{q}_{\beta})$. From homogeneity of $\varphi$, seen in (37) and conserved in Equations (38) and (39), we deduce homogeneity of $\phi$ i.e. Property (36).

For the uniqueness claim, observe that Equations (35) and (36) serve to characterize $\phi$ on each $(\mathbb{Q}_+^r)^2$, and continuity implies uniqueness on $(\mathbb{R}_+^r)^2$. $\square$

Many properties of $\phi$ can be extended, by homogeneity and continuity, from $(\mathbb{N}^r)^2$ to $(\mathbb{R}_+^r)^2$. For instance:

$$ \text{for any } \alpha, \beta \in \mathbb{R}_+, \quad \phi((\alpha), (\beta)) = \alpha \vee \beta. \quad (40) $$

One can also see that $\mathcal{F}_{\text{bot}}((r+1)^{\alpha_{r+1}} r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1}) = (r+1)^{\alpha_{r+1}} \cdot \mathcal{F}_{\text{bot}}(r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1})$ and $\mathcal{F}_{\text{bot}}(r^{\alpha_r} \dots 1^{\alpha_1}, (r+1)^{\beta_{r+1}} r^{\beta_r} \dots 1^{\beta_1}) = \mathcal{F}_{\text{bot}}(r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1})$, therefore for any $r \in \mathbb{N}^*$ and any $(\alpha_k)_{1 \le k \le r}, (\beta_k)_{1 \le k \le r} \in \mathbb{R}_+^r$:

$$ \begin{aligned} \phi((\alpha_1, \dots, \alpha_r, \alpha_{r+1}), (\beta_1, \dots, \beta_r, 0)) &= \phi((\alpha_1, \dots, \alpha_r, 0), (\beta_1, \dots, \beta_r, \beta_{r+1})) \\ &= \phi((\alpha_1, \dots, \alpha_r), (\beta_1, \dots, \beta_r)). \end{aligned} \quad (41) $$

We can use the last two properties of $\phi$ to prove a third one which we will use to establish Corollary 2.11.
**Lemma 4.13.** Let $r \in \mathbb{N}^*$. Consider $(\alpha_k)_{1 \le k \le r}$, $(\beta_k)_{1 \le k \le r} \in \mathbb{R}_+^r$ such that

$$ \phi((\alpha_i)_{k \le i \le r}, (\beta_i)_{k \le i \le r}) = \alpha_k + \beta_k \quad (42) $$

for all $1 \le k \le r$. Then $\alpha_k \cdot \beta_k = 0$ for all $1 \le k \le r$.

*Proof.* Let us prove the lemma by induction on $r \in \mathbb{N}$. For $r = 1$, (40) implies $\alpha_1 \lor \beta_1 = \alpha_1 + \beta_1$, i.e. $\alpha_1 \cdot \beta_1 = 0$. Now let $r > 1$ and assume that the lemma holds for $r - 1$. Use Equation (42) for $k = r$ along with (40) to get $\alpha_r \lor \beta_r = \alpha_r + \beta_r$, which implies $\alpha_r \cdot \beta_r = 0$. Then, thanks to (41), Equation (42) becomes

$$ \phi((\alpha_i)_{k \le i \le r-1}, (\beta_i)_{k \le i \le r-1}) = \alpha_k + \beta_k $$

for all $1 \le k \le r - 1$. The proof follows by induction. $\square$

Let us present one last property of $\phi$. Notice that for any $h \in \mathbb{N}^*$, the function $\#_h \mathcal{F}_{\text{bot}}$ does not depend on letters less than $h$ in the input words. Indeed, applying a letter less than $h$ can only decrement letters that are less than $h$. Subsequently for any $r \ge h$ and $(\alpha_k)_{1 \le k \le r}$, $(\beta_k)_{1 \le k \le r} \in \mathbb{N}^r$:

$$ \#_h \mathcal{F}_{\text{bot}} (r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1}) = \#_h \mathcal{F}_{\text{bot}} (r^{\alpha_r} \dots h^{\alpha_h}, r^{\beta_r} \dots h^{\beta_h}). $$

Combined with the following “translation-invariance” property of Fomin’s inverse rules:

$$ \#_h \mathcal{F}_{\text{bot}} (r^{\alpha_r} \dots h^{\alpha_h}, r^{\beta_r} \dots h^{\beta_h}) = \#_1 \mathcal{F}_{\text{bot}} ((r-h+1)^{\alpha_r} \dots 1^{\alpha_h}, (r-h+1)^{\beta_r} \dots 1^{\beta_h}), $$

we deduce that:

$$ \phi((\alpha_k)_{h \le k \le r}, (\beta_k)_{h \le k \le r}) = \beta_h + \#_h \mathcal{F}_{\text{bot}} (r^{\alpha_r} \dots 1^{\alpha_1}, r^{\beta_r} \dots 1^{\beta_1}). \quad (43) $$

## 4.6 Continuous inverse growth rules

The aim of this section is to prove Theorem 2.10 and Corollary 2.11, using all the previously developed tools.

*Proof of Theorem 2.10.* Fix an integer $r \in \mathbb{N}^*$ and a permutation $\mu$ satisfying $\widetilde{\text{LIS}}_r(\mu) = 1$. The function $\tilde{\lambda}^\mu$ is then entirely described by $\tilde{\lambda}_1^\mu, \dots, \tilde{\lambda}_r^\mu$, for which we will omit the exponent. Moreover $\mu$'s sampled permutations are almost surely $r$-increasing, meaning their diagrams consist of at most $r$ rows. The tableaux of $\sigma_n \sim \text{Sample}_n(\mu)$ are then entirely described by the functions $\lambda_1^{\sigma_n}, \dots, \lambda_r^{\sigma_n}$, for which we will also omit the exponent.

Let $(x, y) \in (0, 1]^2$ be such that the left-derivatives

$$ \alpha_k := \partial_x^{-} \tilde{\lambda}_k(x, y) \quad \text{and} \quad \beta_k := \partial_y^{-} \tilde{\lambda}_k(x, y) $$

for $k \in [1, r]$ all exist. Fix $s, t \ge 0$, and $\epsilon > 0$ small enough to have $x - t\epsilon, y - s\epsilon \ge 0$. According to Proposition 2.9, we can and will work on an event where the convergence

$$ \text{for all } k \in [1, r], \quad \left\| \tilde{\lambda}_k - \frac{1}{n} \lambda_k (\lfloor n \rfloor, \lfloor n \rfloor) \right\| = o(1) $$

holds. We can use this convergence along with the derivability condition of $\tilde{\lambda}$ to obtain decent control over the disposition of Fomin’s edge labels. Fix an integer $p \in \mathbb{N}^*$ and define regular subdivisions

$$ x - t\epsilon = x_p < x_{p-1} < \dots < x_0 = x \quad \text{and} \quad y - s\epsilon = y_p < y_{p-1} < \dots < y_0 = y $$

of respective steps $t\epsilon/p$ and $s\epsilon/p$. Then for any $k \in [1, r]$ and $j \in [1, p]$:

$$ \begin{align*} \tilde{\lambda}_k(x_{j-1}, y) - \tilde{\lambda}_k(x_j, y) & = \tilde{\lambda}_k(x, y) - (j-1)t\epsilon\alpha_k/p + \mathop{o}\limits_{\epsilon \to 0} (\epsilon(j-1)/p) - \tilde{\lambda}_k(x, y) + jt\epsilon\alpha_k/p + \mathop{o}\limits_{\epsilon \to 0} (\epsilon j/p) \\ & = \epsilon t\alpha_k/p + \mathop{o}\limits_{\epsilon \to 0} (\epsilon) \end{align*} $$
whence

$$ \lambda_k(\lfloor nx_{j-1} \rfloor, \lfloor ny \rfloor) - \lambda_k(\lfloor nx_j \rfloor, \lfloor ny \rfloor) = n\epsilon t\alpha_k/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). \quad (44) $$

This means that edge labels of $\sigma_n$ on the north side of $\llbracket \lfloor n(x-t\epsilon) \rfloor, \lfloor nx \rfloor \rrbracket \times \llbracket \lfloor n(y-s\epsilon) \rfloor, \lfloor ny \rfloor \rrbracket$ are quite well equidistributed. Denote by $w_{\lambda}^{\text{top}}$, $w_{\lambda}^{\text{right}}$, $w_{\lambda}^{\text{bot}}$, $w_{\lambda}^{\text{left}}$ the words associated with the edge labels of $\sigma_n$ on this rectangular grid, as defined in Section 4.2. Write the top-word as a concatenation $w_{\lambda}^{\text{top}} = w_{(1)}^{\text{top}} \dots w_{(p)}^{\text{top}}$, where each $w_{(j)}^{\text{top}}$ consists of labels from x-coordinate $\lfloor nx_{j-1} \rfloor$ to $\lfloor nx_j \rfloor$. Then (44) translates as:

$$ \#_k w_{(j)}^{\text{top}} = n\epsilon t\alpha_k/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). \quad (45) $$

In particular, by summing (45) over $j \in \llbracket 1, p \rrbracket$:

$$ \#_k w_{\lambda}^{\text{top}} = n\epsilon t\alpha_k + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). \quad (46) $$

Similar statements hold for $w_{\lambda}^{\text{right}}$. Next, let us explain how to relate this property of equidistribution to Proposition 4.11. In what follows, we consider that nondecreasing subsequences can only contain positive letters.

**Claim 1:** For any $i, k \in \llbracket 1, r \rrbracket$ the following holds:

$$ \left| \text{LIS}_i \left( w_{\lambda}^{\text{top}, \le k} \right) - n\epsilon \left( \alpha_{(1)}^k + \dots + \alpha_{(i)}^k \right) \right| \le n\epsilon r^2/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n) $$

with the notation of Proposition 4.11.

To see this, note that a nondecreasing subsequence of $w_{\lambda}^{\text{top}, \le k}$ reads as a subsequence of 1's, followed by a subsequence of 2's, ..., followed by a subsequence of $k$'s. Let $A = A_1 \sqcup \dots \sqcup A_i$ be an $i$-nondecreasing subsequence (i.e. a union of $i$ nondecreasing subsequences, which we can suppose disjoint) of $w_{\lambda}^{\text{top}, \le k}$ with maximum length.

We say $j \in \llbracket 1, p \rrbracket$ is “valid” if for each $h \in \llbracket 1, i \rrbracket$, the nondecreasing subsequence $A_h$ takes letters of at most one value in the subword $w_{(j)}^{\text{top}, \le k}$. In this case, at best, $A$ can thus take the $i$ most represented letters in $w_{(j)}^{\text{top}, \le k}$. Using (45), this allows to bound the number of letters picked up by $A$ in any valid subword $w_{(j)}^{\text{top}, \le k}$ by

$$ n\epsilon t \left( \alpha_{(1)}^k + \dots + \alpha_{(i)}^k \right) / p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). $$

When an index $j \in \llbracket 1, p \rrbracket$ is not valid, it means that some $A_h$ takes letters of at least two different values in $w_{(j)}^{\text{top}, \le k}$. Since each $A_h$ is a nondecreasing subsequence, it can “invalidate” at most $k-1$ subwords. Therefore at most $i(k-1)$ subwords are not valid, and in each of them $A$ can potentially take every letter. This observation, along with the previous analysis, leads to the following upper bound:

$$ \text{LIS}_i \left( w_{\lambda}^{\text{top}, \le k} \right) \le n\epsilon t \left( \alpha_{(1)}^k + \dots + \alpha_{(i)}^k \right) + i(k-1)nt\epsilon/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). $$

Conversely we can construct an $i$-nondecreasing subsequence $B = B_1 \sqcup \dots \sqcup B_{i \wedge k}$ of $w_{\lambda}^{\text{top}, \le k}$ by letting each $B_h$ take all $b_h$'s of $w_{\lambda}^{\text{top}, \le k}$, where $b_h$ is such that $\alpha_{b_h} = \alpha_{(h)}^k$. Subsequently, using (45):

$$ \text{LIS}_i \left( w_{\lambda}^{\text{top}, \le k} \right) \ge n\epsilon t \left( \alpha_{(1)}^k + \dots + \alpha_{(i \wedge k)}^k \right) + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). $$

This concludes the proof of Claim 1.

**Claim 2:** Define $w_{\text{ord}}^{\text{top}} := r^{\lfloor n\epsilon t\alpha_r \rfloor} \dots 1^{\lfloor n\epsilon t\alpha_1 \rfloor}$. There exists a constant $\chi_r > 0$ such that for any word $w^{\text{right}}$ and any $h \in \mathbb{N}^*$:

$$ \left\{ \begin{array}{l} \left| \#_h \mathcal{F}_{\text{bot}}(w_{\lambda}^{\text{top}}, w^{\text{right}}) - \#_h \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w^{\text{right}}) \right| \le \chi_r t\epsilon n/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n); \\ \\ \left| \#_h \mathcal{F}_{\text{left}}(w_{\lambda}^{\text{top}}, w^{\text{right}}) - \#_h \mathcal{F}_{\text{left}}(w_{\text{ord}}^{\text{top}}, w^{\text{right}}) \right| \le \chi_r t\epsilon n/p + n \sum_{\epsilon \to 0} o(\epsilon) + \sum_{n \to \infty} o(n). \end{array} \right. $$
Indeed with the notation of Proposition 4.11, Claim 1 rewrites

$$ \text{for any } i, k \in [1, r], \quad \eta_{i,k} \le \frac{nt\epsilon r^2}{p} + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n) $$

thus, letting $\chi_r := 4r^3(8r^2)^r$:

$$ \mathrm{dist}_{\mathcal{F}}(w_{\lambda}^{\mathrm{top}}, w_{\mathrm{ord}}^{\mathrm{top}}) \le \chi_r \epsilon n/p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n), $$

which is the first desired inequality. For the second inequality, use this first inequality along with Equations (23) and (46):

$$ \begin{aligned} & \left| \#_h \mathcal{F}_{\text{left}}(w_{\lambda}^{\text{top}}, w^{\text{right}}) - \#_h \mathcal{F}_{\text{left}}(w_{\text{ord}}^{\text{top}}, w^{\text{right}}) \right| \\ & \le \left| \#_h \mathcal{F}_{\text{bot}}(w_{\lambda}^{\text{top}}, w^{\text{right}}) - \#_h \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w^{\text{right}}) \right| + \left| \#_h w_{\lambda}^{\text{top}} - \#_h w_{\text{ord}}^{\text{top}} \right| \\ & \le \chi_r \epsilon n/p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n). \end{aligned} $$

This proves Claim 2, and by symmetry the following holds as well:

**Claim 3:** Define $w_{\mathrm{ord}}^{\mathrm{right}} := r^{\lfloor n\epsilon s\beta_r \rfloor} \dots 1^{\lfloor n\epsilon s\beta_1 \rfloor}$. Then for any word $w^{\mathrm{top}}$ and any $h \in \mathbb{N}^*$:

$$ \left\{ \begin{array}{l} \left| \#_h \mathcal{F}_{\text{left}}(w^{\text{top}}, w_{\lambda}^{\text{right}}) - \#_h \mathcal{F}_{\text{left}}(w^{\text{top}}, w_{\text{ord}}^{\text{right}}) \right| \le \chi_r s \epsilon n / p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n); \\ \\ \left| \#_h \mathcal{F}_{\text{bot}}(w^{\text{top}}, w_{\lambda}^{\text{right}}) - \#_h \mathcal{F}_{\text{bot}}(w^{\text{top}}, w_{\text{ord}}^{\text{right}}) \right| \le \chi_r s \epsilon n / p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n). \end{array} \right. $$

We can now finish the proof of Theorem 2.10. Using Claims 2 and 3 we obtain for any $k \in \mathbb{N}^*$:

$$ \begin{aligned} & \left| \#_k \mathcal{F}_{\text{bot}}(w_{\lambda}^{\text{top}}, w_{\lambda}^{\text{right}}) - \#_k \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w_{\text{ord}}^{\text{right}}) \right| \\ & \le \left| \#_k \mathcal{F}_{\text{bot}}(w_{\lambda}^{\text{top}}, w_{\lambda}^{\text{right}}) - \#_k \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w_{\lambda}^{\text{right}}) \right| + \left| \#_k \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w_{\lambda}^{\text{right}}) - \#_k \mathcal{F}_{\text{bot}}(w_{\text{ord}}^{\text{top}}, w_{\text{ord}}^{\text{right}}) \right| \\ & \le (t+s)\chi_r \epsilon n/p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n). \end{aligned} $$

Then using the equality $\lambda_k(\lfloor nx \rfloor, \lfloor ny \rfloor) - \lambda_k(\lfloor n(x-t\epsilon) \rfloor, \lfloor n(y-s\epsilon) \rfloor) = \#_k \mathcal{F}_{\text{bot}}(w_{\lambda}^{\text{top}}, w_{\lambda}^{\text{right}}) + \#_k w_{\lambda}^{\text{right}}$, (46), Proposition 4.12 and Property (43) we get:

$$ \left| \left( \lambda_k(\lfloor nx \rfloor, \lfloor ny \rfloor) - \lambda_k(\lfloor n(x-t\epsilon) \rfloor, \lfloor n(y-s\epsilon) \rfloor) \right) - \phi((n\epsilon t \alpha_i)_{k \le i \le r}, (n\epsilon s \beta_i)_{k \le i \le r}) \right| \\ \le (t+s)\chi_r \epsilon n/p + n \sum_{\epsilon \to 0} (\epsilon) + \sum_{n \to \infty} (n). $$

Dividing by $n$, using Property (36) and taking $n \to \infty$ we deduce:

$$ \left| \left( \tilde{\lambda}_k(x, y) - \tilde{\lambda}_k(x - t\epsilon, y - s\epsilon) \right) - \epsilon \phi((t\alpha_i)_{k \le i \le r}, (s\beta_i)_{k \le i \le r}) \right| \le (t+s)\chi_r \epsilon/p + \sum_{\epsilon \to 0} (\epsilon), $$

whence:

$$ \limsup_{\epsilon \to 0^+} \left| \frac{\tilde{\lambda}_k(x, y) - \tilde{\lambda}_k(x - t\epsilon, y - s\epsilon)}{\epsilon} - \phi((t\alpha_i)_{k \le i \le r}, (s\beta_i)_{k \le i \le r}) \right| \le (t+s)\chi_r/p. $$

Since this holds for any $p \in \mathbb{N}^*$, this concludes the proof of Theorem 2.10. $\square$

<figure><img src="image_17.png" /></figure>

**Proof of Corollary 2.11.** For each $k \in [1, r]$, the function $\tilde{\lambda}_k^\mu$ is Lipschitz according to Proposition 2.9. Thanks to Rademacher's theorem, this implies that $\tilde{\lambda}_k^\mu$ is differentiable almost everywhere on $(0, 1)^2$. If $(x, y)$ is a point at which $\tilde{\lambda}_k^\mu$ is differentiable and if we write $\alpha_k := \partial_x^{-} \tilde{\lambda}_k(x, y)$ and $\beta_k := \partial_y^{-} \tilde{\lambda}_k(x, y)$, then the left-hand side of Equation (2) is simply equal to $t\alpha_k + s\beta_k$, therefore we have $\phi((t\alpha_i)_{k \le i \le r}, (s\beta_i)_{k \le i \le r}) = t\alpha_k + s\beta_k$. Almost everywhere on $(0, 1)^2$, this equation holds for all $k \in [1, r]$. Lemma 4.13 then implies $\alpha_k \cdot \beta_k = 0$ almost everywhere for all $k$, which concludes the proof. $\square$

<figure><img src="image_18.png" /></figure>
## 4.7 Proofs of injectivity results

*Proof of Theorem 2.12.* Let us first prove the existence of a triple satisfying those properties. For each $k \in \mathbb{N}^*$ consider $A_k \in \mathcal{P}^{k\uparrow}([0, 1]^2)$ such that $\mu(A_k) = \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu)$ and $B_k \in \mathcal{P}^{k\downarrow}([0, 1]^2)$ such that $\mu(B_k) = \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_k(\mu)$. Then define:

$$A := \bigcup_{k \in \mathbb{N}^*} A_k, \quad B := \bigcup_{k \in \mathbb{N}^*} B_k, \quad \mu^{\text{incr}} := \mu(A \cap \cdot), \quad \mu^{\text{decr}} := \mu(B \cap \cdot), \quad \mu^{\text{sub}} := \mu((A \cup B)^c \cap \cdot).$$

Clearly one has

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu^{\text{incr}}) = \mu(A) = \mu^{\text{incr}}([0, 1]^2) \quad \text{and} \quad \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_{\infty}(\mu^{\text{decr}}) = \mu(B) = \mu^{\text{decr}}([0, 1]^2)$$

and the measure $\mu^{\text{sub}}$ is singular with respect to both $\mu^{\text{incr}}$ and $\mu^{\text{decr}}$. Then notice that the intersection between a non-decreasing and a nonincreasing subset is entirely contained within the union of a vertical and a horizontal line. Since $\mu$ is a pre-permuton, it puts mass zero to such an intersection. As $A$ (resp. $B$) is a countable union of nondecreasing (resp. nonincreasing) subsets, it implies $\mu(A \cap B) = 0$. Thus (i) holds, and $\mu = \mu^{\text{incr}} + \mu^{\text{decr}} + \mu^{\text{sub}}$.

Now for each $k \in \mathbb{N}^*$, since $\mu^{\text{incr}}$, $\mu^{\text{decr}}$ are sub-measures of $\mu$, one has

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu^{\text{incr}}) \le \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu) \quad \text{and} \quad \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_k(\mu^{\text{decr}}) \le \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_k(\mu).$$

Moreover

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu^{\text{incr}}) \ge \mu^{\text{incr}}(A_k) = \mu(A_k) = \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu) \quad \text{and} \quad \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_k(\mu^{\text{decr}}) \ge \mu^{\text{decr}}(B_k) = \mu(B_k) = \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_k(\mu),$$

hence (ii) holds. Subsequently $\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu^{\text{incr}}) = \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu)$ and $\widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_{\infty}(\mu^{\text{decr}}) = \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_{\infty}(\mu)$.

Now consider a nondecreasing subset $A'$ that is disjoint of $A$. For each $k \in \mathbb{N}^*$ the subset $A_k \cup A'$ is $(k+1)$-nondecreasing, implying

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{k+1}(\mu) \ge \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu) + \mu(A').$$

As a consequence:

$$\mu(A') \le \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{k+1}(\mu) - \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_k(\mu) \xrightarrow{k \to \infty} 0.$$

In particular $\mu^{\text{decr}}(A') = \mu^{\text{sub}}(A') = 0$. Since this holds for any nondecreasing subset disjoint of $A$ and $\mu^{\text{decr}}$, $\mu^{\text{sub}}$ are singular with respect to $\mu^{\text{incr}}$, this implies:

$$\widetilde{\mathcal{L}\mathcal{I}}(\mu^{\text{decr}}) = \widetilde{\mathcal{L}\mathcal{I}}(\mu^{\text{sub}}) = 0$$

and in particular $\tilde{\lambda}^{\mu} = \tilde{\lambda}^{\mu^{\text{incr}}}$. Repeating this argument with nonincreasing subsets, we deduce (iii).

Let us turn to the uniqueness claim. Keep the previous definition of $\mu^{\text{incr}}$, $\mu^{\text{decr}}$, $\mu^{\text{sub}}$ and write $\mu = \nu^{\text{incr}} + \nu^{\text{decr}} + \nu^{\text{sub}}$ where $\nu^{\text{incr}}$, $\nu^{\text{decr}}$, $\nu^{\text{sub}}$ are finite (positive) measures satisfying

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\nu^{\text{incr}}) = \nu^{\text{incr}}([0, 1]^2) = \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu) \quad \text{and} \quad \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_{\infty}(\nu^{\text{decr}}) = \nu^{\text{decr}}([0, 1]^2) = \widetilde{\mathcal{L}\mathcal{D}\mathcal{S}}_{\infty}(\mu).$$

Let $C$ be a countable union of nondecreasing subsets supporting the measure $\nu^{\text{incr}}$. Then:

$$\nu^{\text{incr}}([0, 1]^2) = \nu^{\text{incr}}(C) \le \mu(C) \le \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu).$$

Since the first and last term are equal, we deduce equality of all terms. Hence the sub-measure $\nu^{\text{incr}}$ of $\mu$ is given by the restriction $\nu^{\text{incr}} = \mu(C \cap \cdot)$. Moreover Property (iii) implies

$$\mu^{\text{decr}}(C) = \mu^{\text{sub}}(C) = 0, \qquad (47)$$

thus

$$\widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu) = \mu(C) = \mu^{\text{incr}}(C) \le \mu^{\text{incr}}([0, 1]^2) = \widetilde{\mathcal{L}\mathcal{I}\mathcal{S}}_{\infty}(\mu)$$

from which we deduce

$$\mu^{\text{incr}}(C) = \mu^{\text{incr}}([0, 1]^2). \qquad (48)$$

Equations (47) and (48) together imply

$$\mu^{\text{incr}} = \mu(C \cap \cdot) = \nu^{\text{incr}}$$

as desired. The proof of $\mu^{\text{decr}} = \nu^{\text{decr}}$ works the same, and we finally deduce $\mu^{\text{sub}} = \nu^{\text{sub}}$. $\square$
*Proof of Proposition 2.14.* For any $(x, y) \in [0, 1]^2$:

$$ \widetilde{\text{LIS}}_{\infty}(\mu|_{[0,x]} \times [0,y]) = \mu^{\text{incr}}([0,x] \times [0,y]). $$

Hence $\tilde{\lambda}^{\mu} = \tilde{\lambda}^{\nu}$ implies

$$ \mu^{\text{incr}}([0, x] \times [0, y]) = \nu^{\text{incr}}([0, x] \times [0, y]) $$

for any $(x, y) \in [0, 1]^2$, and therefore $\mu^{\text{incr}} = \nu^{\text{incr}}$.

□

The idea to prove Proposition 2.15 is that while we could not recover $\tilde{\lambda}^{\mu}$ from its PDE together with its boundary condition $\widetilde{\text{RS}}(\mu)$, there is a simple explicit solution for the last row of the tableaux.

**Lemma 4.14.** Let $\mu$ be a pre-permuton satisfying $\widetilde{\text{LIS}}_r(\mu) = 1$ for some $r \in \mathbb{N}^*$. Then for any $(x, y) \in [0, 1]^2$:

$$ \tilde{\lambda}_r(x, y) = \tilde{\lambda}_r(x, 1) \wedge \tilde{\lambda}_r(1, y). $$

*Proof.* Denote by $F = (F_1, F_2)$ the pair of distribution functions of each marginal of $\mu$, so that the push-forward $\hat{\mu} = F_*\mu$ is a permuton. Since $F$ is nondecreasing in each coordinate, we have for any $k \in [1, r]$ and $(x', y') \in [0, 1]^2$:

$$ \widetilde{\text{LIS}}_k(\hat{\mu}|_{[0,F_1(x')]} \times [0,F_2(y')]) = \widetilde{\text{LIS}}_k(\mu|_{[0,x'] \times [0,y']}). $$

Thus $\tilde{\lambda}^{\mu} = \tilde{\lambda}^{\hat{\mu}} \circ F$.

For each $n \in \mathbb{N}^*$ let $\sigma_n \sim \text{Sample}_n(\mu)$. As noted before obtaining Property (43), for any words $w^{\text{top}}$ and $w^{\text{right}}$, the number of $r$'s in $\mathcal{F}_{\text{bot}}(w^{\text{top}}, w^{\text{right}})$ does not depend on letters less than $r$ in $w^{\text{top}}$ and $w^{\text{right}}$. Let $1 \le i \le i' \le n$, $1 \le j \le j' \le n$, and $w_n^{\text{top}}, w_n^{\text{right}}$ be the top- and right-words of $\sigma_n$'s edge labels on $[[i, i')] \times [[j, j]]$. Since these words almost surely only have labels at most $r$, the previous observation yields:

$$ \#_r \mathcal{F}_{\text{bot}}(w_n^{\text{top}}, w_n^{\text{right}}) = \#_r \mathcal{F}_{\text{bot}}(r^{\#_r w_n^{\text{top}}}, r^{\#_r w_n^{\text{right}}}) = (\#_r w_n^{\text{top}} - \#_r w_n^{\text{right}})^{+}. $$

Then

$$ \begin{aligned} \lambda_r^{\sigma_n}(i', j') - \lambda_r^{\sigma_n}(i, j) &= \#_r \mathcal{F}_{\text{bot}}(r^{\#_r w_n^{\text{top}}}, r^{\#_r w_n^{\text{right}}}) + \#_r w_n^{\text{right}} \\ &= \#_r w_n^{\text{top}} \vee \#_r w_n^{\text{right}} \\ &= (\lambda_r^{\sigma_n}(i', j') - \lambda_r^{\sigma_n}(i, j')) \vee (\lambda_r^{\sigma_n}(i', j') - \lambda_r^{\sigma_n}(i, j)), \end{aligned} $$

and in particular when $i' = j' = n$, almost surely:

$$ \lambda_r^{\sigma_n}(i, j) = \lambda_r^{\sigma_n}(i, n) \wedge \lambda_r^{\sigma_n}(n, j). $$

Using Proposition 2.9 we get for any $(x, y) \in [0, 1]^2$:

$$ \lambda_r^{\hat{\mu}}(x, y) = \lambda_r^{\hat{\mu}}(x, 1) \wedge \lambda_r^{\hat{\mu}}(1, y). $$

Using the equality $\tilde{\lambda}^{\mu} = \tilde{\lambda}^{\hat{\mu}} \circ F$ we finally deduce for any $(x, y) \in [0, 1]^2$:

$$ \tilde{\lambda}_r^{\mu}(x, y) = \tilde{\lambda}_r^{\hat{\mu}}(F_1(x), F_2(y)) = \tilde{\lambda}_r^{\hat{\mu}}(F_1(x), 1) \wedge \tilde{\lambda}_r^{\hat{\mu}}(1, F_2(y)) = \tilde{\lambda}_r^{\mu}(x, 1) \wedge \tilde{\lambda}_r^{\mu}(1, y). \quad \square $$

*Proof of Proposition 2.15.* Under the first hypothesis we have $\mu^{\text{incr}}([0, 1]^2) = \widetilde{\text{LIS}}(\mu^{\text{incr}})$. Applying Lemma 4.14 to the renormalization of $\mu^{\text{incr}}$, we deduce for any $(x, y) \in [0, 1]^2$:

$$ \tilde{\lambda}_1^{\mu}(x, y) = \tilde{\lambda}_1^{\mu^{\text{incr}}}(x, y) = \tilde{\lambda}_1^{\mu^{\text{incr}}}(x, 1) \wedge \tilde{\lambda}_1^{\mu^{\text{incr}}}(1, y) = \tilde{\lambda}_1^{\mu}(x, 1) \wedge \tilde{\lambda}_1^{\mu}(1, y). \quad (49) $$

Since $\widetilde{\text{RS}}(\mu) = \widetilde{\text{RS}}(\nu)$ implies

$$ \widetilde{\text{LIS}}_{\infty}(\nu) = \sum_{k \ge 1} \tilde{\lambda}_k^{\nu}(1, 1) = \sum_{k \ge 1} \tilde{\lambda}_k^{\mu}(1, 1) = \tilde{\lambda}_1^{\mu}(1, 1) = \tilde{\lambda}_1^{\nu}(1, 1) = \widetilde{\text{LIS}}_1(\nu), $$

$\nu$ also satisfies Equation (49). Therefore $\tilde{\lambda}^{\mu} = \tilde{\lambda}^{\nu}$, and we conclude with Proposition 2.14.

□
## Acknowledgments

I would like to express my sincere gratitude to my supervisor Valentin Féray for his invaluable guidance and support. I would also like to thank two anonymous reviewers for their suggestions that greatly improved the presentation of this paper; Blaise Colle, Corentin Correia, Emmanuel Kammerer, and Pierrick Sieste for fruitful discussions; and Rémi Maréchal, whose master's thesis laid the foundation of this work by proving Propositions 2.1 and 2.2 when $k = 1$ with a different but essentially equivalent definition of $\tilde{\mathcal{L}}\mathcal{S}_1$. The author is partially supported by the Program "Future Leader" of the Initiative "Lorraine Université d'Excellence" (LUE), and by the Agence Nationale de la Recherche funding CORTIPOM ANR-21-CE40-0019.

## References

[ABNP16] Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, and Carine Pivoteau. Analysis of algorithms for permutations biased by their number of records. In *27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm AOFA 2016*, 2016.

[AD95] David J. Aldous and Persi Diaconis. Hammersley's interacting particle process and longest increasing subsequences. *Probability Theory and Related Fields*, 103(2):199-213, 1995.

[ADK22] Noga Alon, Colin Defant, and Noah Kravitz. The runsort permuton. *Advances in Applied Mathematics*, 139:102361, 2022.

[BBD$^{+}$22] Frédérique Bassino, Mathilde Bouvel, Michael Drmota, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Linear-sized independent sets in random cographs and increasing subsequences in separable permutations. *Combinatorial Theory*, 2(3), 2022.

[BBF$^{+}$18] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, and Adeline Pierrot. The Brownian limit of separable permutations. *The Annals of Probability*, 46(4):2134-2189, 2018.

[BBF$^{+}$22] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Scaling limits of permutation classes with a finite specification: A dichotomy. *Advances in Mathematics*, 405:108513, 2022.

[BDJ99] Jinho Baik, Percy Deift, and Kurt Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. *Journal of the American Mathematical Society*, 12(4):1119-1178, 1999.

[BDMW24] Jacopo Borga, Sayan Das, Sumit Mukherjee, and Peter Winkler. Large deviation principle for random permutations. *International Mathematics Research Notices*, (3):2138-2191, 2024.

[BDS21] Jacopo Borga, Enrica Duchi, and Erik Slivken. Almost square permutations are typically square. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 57(4):1834-1856, 2021.

[Bor21] Jacopo Borga. Random Permutations–A geometric point of view. *Preprint at arXiv:2107.09699*, 2021.

[Bor23] Jacopo Borga. The skew brownian permuton: A new universality class for random constrained permutations. *Proceedings of the London Mathematical Society*, 126(6):1842-1883, 2023.

[BS20] Jacopo Borga and Erik Slivken. Square permutations are typically rectangular. *The Annals of Applied Probability*, 30(5):2196-2233, 2020.

[CKP22] Oliver Cooley, Mihyun Kang, and Oeg Pikhurko. On a question of Vera T. Sós about size forcing of graphons. *Acta Mathematica Hungarica*, 168(1):1-26, 2022.

[Cra38] Harald Cramér. Sur un nouveau théorème-limite de la théorie des probabilités. *Colloque consacré à la théorie des probabilités, Actualités scientifiques et industrielles*, 736:2-23, 1938.

[Dub23] Victor Dubach. Locally uniform random permutations with large increasing subsequences. *Combinatorial Theory*, 3(3), 2023.
[DZ95] Jean-Dominique Deuschel and Ofer Zeitouni. Limiting curves for i.i.d. records. *The Annals of Probability*, 23(2):852–878, 1995.

[DZ98] Amir Dembo and Ofer Zeitouni. *Large Deviations Techniques and Applications*, volume 38 of *Stochastic Modelling and Applied Probability*. Springer Berlin, Heidelberg, 1998.

[DZ99] Jean-Dominique Deuschel and Ofer Zeitouni. On increasing subsequences of i.i.d. samples. *Combinatorics, Probability and Computing*, 8(3):247–263, 1999.

[ET22] Gábor Elek and Gábor Tardos. Convergence and limits of finite trees. *Combinatorica*, 42(6):821–852, 2022.

[FMN20] Valentin Féray, Pierre-Loïc Méliot, and Ashkan Nikeghbali. Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces. *Proceedings of the London Mathematical Society*, 121(4):876–926, 2020.

[FRL23] Valentin Féray and Kelvin Rivera-Lopez. The permuton limit of random recursive separable permutations. *Preprint at arXiv:2306.04278*, 2023.

[Ful96] William Fulton. *Young Tableaux: With Applications to Representation Theory and Geometry*. London Mathematical Society Student Texts. Cambridge University Press, 1996.

[GGKK15] Roman Glebov, Andrzej Grzesik, Tereza Klimošová, and Daniel Král'. Finitely forcible graphons and permutons. *Journal of Combinatorial Theory, Series B*, 110:112–135, 2015.

[Gre74] Curtis Greene. An extension of Schensted's theorem. *Advances in Math.*, 14:254–265, 1974.

[Grü23] Rudolf Grübel. A note on limits of sequences of binary trees. *Discrete Mathematics & Theoretical Computer Science*, 25, 2023.

[Ham72] John M. Hammersley. A few seedlings of research. In *Proc. Sixth Berkeley Symp. Math. Statist. and Probability*, volume 1, pages 345–394, 1972.

[HKM$^{+}$13] Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio. Limits of permutation sequences. *Journal of Combinatorial Theory, Series B*, 103(1):93–113, 2013.

[HR20] Jan Hladký and Israel Rocha. Independent sets, cliques, and colorings in graphons. *European Journal of Combinatorics*, 88:103108, 2020.

[Jan11] Svante Janson. Poset limits and exchangeable random posets. *Combinatorica*, 31(5):529–563, 2011.

[KP13] Daniel Král and Oleg Pikhurko. Quasirandom permutations are characterized by 4-point densities. *Geometric and Functional Analysis*, 23(2):570–579, 2013.

[LS77] Benjamin F. Logan and Larry A. Shepp. A variational problem for random Young tableaux. *Advances in Mathematics*, 26(2):206–222, 1977.

[LS06] László Lovász and Balázs Szegedy. Limits of dense graph sequences. *Journal of Combinatorial Theory, Series B*, 96(6):933–957, 2006.

[Muk15] Sumit Mukherjee. Fixed points and cycle structure of random permutations. *Electronic Journal of Probability*, 21:1–18, 2015.

[Rom15] Dan Romik. *The Surprising Mathematics of Longest Increasing Subsequences*. Institute of Mathematical Statistics Textbooks (4). Cambridge University Press, 2015.

[Sag01] Bruce E. Sagan. *The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions*. Graduate Texts in Mathematics. Springer New York, 2001.

[Sjö23] Jonas Sjöstrand. Monotone subsequences in locally uniform random permutations. *Annals of Probability*, 51(4):1502–1547, 2023.
[Śni14] Piotr Śniady. Robinson-Schensted-Knuth Algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux. *SIAM Journal on Discrete Mathematics*, 28(2):598–630, 2014.

[Vie18] Xavier Viennot. Growth diagrams and edge local rules. In *GASCom 2018 Random and Exhaustive Generation of Combinatorial Structures*, Athens, Greece, 2018.

[VK77] Anatoli M. Vershik and Sergueï V. Kerov. Asymptotics of the Plancherel measure of the symmetric group and the limit form of Young tableaux. *Soviet Math. Dokl.*, 18:527–531, 1977.

[VK81] Anatoli M. Vershik and Sergueï V. Kerov. Asymptotic theory of characters of the symmetric group. *Functional Analysis and its Applications*, 15:246–255, 1981.

[VK86] Anatoli M. Vershik and Sergueï V. Kerov. The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm. *SIAM J. Algebraic Discrete Methods*, 7:116–124, 1986.