# A geometric approach to conjugation-invariant random permutations

Victor Dubach

► To cite this version:

Victor Dubach. A geometric approach to conjugation-invariant random permutations. Probability Theory and Related Fields, 2025, 194 (1-2), pp.245-298. 10.1007/s00440-025-01449-7. hal-05536092

HAL Id: hal-05536092

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

Submitted on 4 Mar 2026

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 CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

# A geometric approach to conjugation-invariant random permutations

Victor Dubach<fnref n="1" />

Received: 1 March 2024 / Accepted: 4 November 2025 / Published online: 8 November 2025
© The Author(s) 2025

## Abstract

We propose a new approach to conjugation-invariant random permutations. Namely, we explain how to construct uniform permutations in given conjugacy classes from certain point processes in the plane. This enables the use of geometric tools to study various statistics of such permutations. For their longest decreasing subsequences, we prove universality of the $2\sqrt{n}$ asymptotic. For Robinson–Schensted shapes, we prove universality of the Vershik–Kerov–Logan–Shepp limit shape, thus solving a conjecture of Kammoun. For the number of records, we establish a phase transition phenomenon as the number of fixed points grows. For pattern counts, we obtain an asymptotic normality result, partially answering a conjecture of Hamaker and Rhoades.

**Keywords** Random permutations · Conjugation-invariance · Longest increasing subsequences · Robinson-Schensted correspondence · Records · Patterns

**Mathematics Subject Classification** 60C05 · 05A05

# 1 Introduction

## 1.1 Conjugation-invariant random permutations

We say that a random permutation $\tau$ of $[n] := \{1, \dots, n\}$ is conjugation-invariant when for any fixed permutation $\rho$, the conjugate $\rho \circ \tau \circ \rho^{-1}$ follows the same law as $\tau$. Standard examples of conjugation-invariant permutations are uniformly random permutations, random involutions, Ewens random permutations [12], their generalizations [6, 28, 37], and many more.

An equivalent description of conjugation-invariance makes use of the cycle decomposition. Define the *cycle type* of $\tau$ as the sequence $t = (t_1, t_2, \dots, t_n)$ where $t_p$ is the number of $p$-cycles in $\tau$. We also say that $t$ has size $\sum_{p=1}^n pt_p = n$ and that $\tau$ is $t$-cyclic. Since the cycle type is a total invariant for conjugation in the symmetric group,

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

<footnote>Victor Dubach
victor.dubach@outlook.fr</footnote>

<footnote n="1">¹ Uppsala Universitet, Uppsala, Sweden</footnote>
a random permutation $\tau$ is conjugation-invariant if and only if, when conditioned on its cycle type $t$, $\tau$ is a uniform $t$-cyclic permutation. Thus, studying conjugation-invariant random permutations often amounts to studying uniform permutations with given cycle types.

There are reasons to believe in universality phenomena for several statistics of conjugation-invariant permutations, with a dependence on the number of fixed points and sometimes 2-cycles. Recent advances motivate this idea by generalizing asymptotic properties of uniformly random permutations to conjugation-invariant random permutations under certain hypotheses [13, 15, 18, 25]. The aim of this paper is to make further progress in this direction by introducing a “geometric” construction for random permutations in given conjugacy classes, see Lemma 1.3 in Section 1.2. This new point of view allows us to establish asymptotic results on the longest monotone subsequences, Robinson–Schensted shape, number of records, and pattern counts.

**Longest monotone subsequences.** The maximum length of a monotone subsequence in a uniform permutation famously behaves as $2\sqrt{n}$ [38]. Baik and Rains [5] showed similar asymptotics for random involutions, with a dependence on the number of fixed points, and Kammoun [25] proved that the $2\sqrt{n}$ asymptotic holds for conjugation-invariant random permutations with few cycles. In Section 2.1 we extend these results to general conjugation-invariant permutations for their longest decreasing subsequences. Longest increasing subsequences are harder to handle, and we only provide such asymptotics up to a multiplicative constant.

**Robinson–Schensted shape.** The Robinson–Schensted shape of a uniform permutation converges, after suitable rescaling, to a limit curve [30, 38]. Kammoun [25] extended this result to conjugation-invariant permutations with few cycles, and conjectured that this assumption could be lifted. In Section 2.2 we provide a positive answer to this conjecture.

**Records.** The numbers of records in uniform permutations are known to satisfy asymptotic normality. In Section 2.3 we prove a general limit theorem for the number of high records (or left-to-right maxima) in conjugation-invariant permutations, showcasing a phase transition as the number of fixed points grows. More precisely, the number of high records interpolates from logarithmic with Gaussian fluctuations to asymptotically Gamma, when the number of non-fixed points is of order $n/\sqrt{\log n}$. We also find the first order asymptotics
of low records (or left-to-right minima), and their second order asymptotics in some cases.

**Pattern counts.** Janson et al. [24] established asymptotic normality for all pattern counts in uniform permutations. Kammoun [26] and Hamaker and Rhoades [18] extended this to conjugation-invariant permutations, under certain assumptions on their cycles. The authors of [18] conjectured that the (non-degenerate) asymptotic normality of pattern counts holds for all conjugation-invariant permutations, where the asymptotic variance depends on the numbers of fixed points and 2-cycles. In Section 2.4 we partially answer this conjecture, by proving asymptotic normality for all conjugation-invariant permutations, and non-degeneracy in some cases.

Our results can be applied to most models of conjugation-invariant permutations, with virtually no restrictions on their cycle types. For example, they are novel for random permutations with cycle weights, some of which have a lot of cycles [6, 11], and for central virtual permutations, some of which have a macroscopic number of fixed points [37].

## 1.2 A geometric construction

We begin by recalling the notion of standardization: if $(y_1, \dots, y_n)$ is a sequence of pairwise distinct numbers, define $\tau = \text{st}(y_1, \dots, y_n)$ as the unique permutation of $[n]$ such that:

$$ \text{for all } 1 \le i, j \le n, \quad \tau(i) < \tau(j) \Leftrightarrow y_i < y_j. $$

The following two results are classical and easy to check:

**Lemma 1.1** Let $\mu$ be an atomless probability distribution on $\mathbb{R}$, and let $Y_1, \dots, Y_n$ be i.i.d. random variables distributed under $\mu$. Then $Y_1, \dots, Y_n$ are a.s. pairwise distinct, and the permutation $\text{st}(Y_1, \dots, Y_n)$ is uniformly random in $\mathcal{S}_n$.

**Lemma 1.2** Let $t$ be a cycle type of size $n$, and let $s$ be an arbitrary fixed $t$-cyclic permutation. If $\sigma$ is a uniformly random permutation of $\mathcal{S}_n$ then $\sigma \circ s \circ \sigma^{-1}$ is a uniformly random $t$-cyclic permutation.

Now, consider a finite subset $\mathcal{P} = \{Z_1 = (X_1, Y_1), \dots, Z_n = (X_n, Y_n)\}$ of $\mathbb{R}^2$ with no redundant x- or y-coordinates. We can define a permutation $\tau$ of $[n]$ by letting $\tau(i) = j$ when the $i$-th point from the left in $\mathcal{P}$ is the $j$-th point from the bottom; equivalently, $\tau = \text{st}(Y_{(1)}, \dots, Y_{(n)})$ where $Z_{(1)}, \dots, Z_{(n)}$ are ordered such that $X_{(1)} < \dots < X_{(n)}$. We denote by $\tau = \text{Perm}(\mathcal{P})$ this permutation.

By considering adequate planar point processes $\mathcal{P}$, we may obtain random permutations $\tau$ with various laws: for instance if $Z_1, \dots, Z_n$ are i.i.d. Unif([0, 1]$^2$) variables
<figure><img src="image_4.png" /><figcaption>Fig. 2 The dependency graph $\mathcal{L}_t$ associated with the cycle type $t = (2, 1, 2, 0, 1)$</figcaption></figure>

As we explain in Section 2.1 to 2.3, monotone subsequences and records of $\tau = \text{Perm}(\mathcal{P})$ can be read directly on $\mathcal{P}$. This allows us to study these statistics of the permutation by investigating the behavior of the point process in certain regions of the plane. To this aim, a list of useful properties of the geometric construction may be found in Section 3. Regarding pattern counts, we rather use the “weak dependency” of points in $\mathcal{P}$ (see Section 2.4 for more details).

## 1.3 Notation

We denote by $\mathfrak{S}_n$ the set of permutations of $[n]$ and by $\Delta$ the diagonal of $[0, 1]^2$. Throughout this paper we consider the standard partial order on $\mathbb{R}^2$ defined by $(x, y) \le (x', y')$ when $x \le x'$ and $y \le y'$.

Let $t$ be a cycle type of size $n$, and let $\mathcal{P}$ be a geometric construction of $t$. We can decompose it into its cycles $\mathcal{P} = \bigcup_{p \in [n], k \in [t_p]} \mathcal{P}_{p,k}$ where $\mathcal{P}_{p,k} := \{Z_{p,k}^l : l \in [p]\}$. We can also decompose it into $\mathcal{P}_\Delta := \mathcal{P} \cap \Delta$ and $\tilde{\mathcal{P}} := \mathcal{P} \setminus \Delta$, and we write $\tilde{t} := (t_1, t_2, t_3, \dots, t_n)$ for the cycle type of size $\tilde{n} := n - t_1$ with no fixed point. It is straightforward to check that $\tilde{\mathcal{P}}$ is a geometric construction of $\tilde{t}$.

Define a graph $\mathcal{L}_t := (\mathcal{V}_t, \mathcal{E}_t)$ with vertex $\mathcal{V}_t$ and edges between $i$ and $\mathfrak{s}(i)$ for each $i \in \mathcal{V}_t$ (forgetting self-loops). We refer to $\mathcal{L}_t$ as the “dependency graph” associated with $t$. See Figure 2 for an example, and Section 7.1 for an explanation of this name.

Let $(a_n)_{n \in \mathbb{N}}$ be a sequence of positive numbers. We say that a sequence of random variables $(X_n)_{n \in \mathbb{N}}$ is a $\mathcal{O}\mathbf{P}(a_n)$ as $n \to \infty$ if

$$ \sup_{n \in \mathbb{N}} \mathbf{P}(|X_n| > a_n M) \xrightarrow{M \to +\infty} 0. $$

Also, $(X_n)_{n \in \mathbb{N}}$ is a $\mathcal{O}\mathbf{P}(a_n)$ as $n \to \infty$ if $X_n/a_n \xrightarrow{n \to \infty} 0$ in probability. Finally, a sequence $(A_n)_{n \in \mathbb{N}}$ of events happens with high probability (w.h.p.) as $n \to \infty$ if $\mathbf{P}(A_n) \xrightarrow{n \to \infty} 1$.

# 2 Results: universality and beyond

## 2.1 Longest monotone subsequences

Let $\tau$ be a permutation of $[n]$. An increasing subsequence of $\tau$ is a sequence of indices $i_1 < \dots < i_\ell$ such that $\tau(i_1) < \dots < \tau(i_\ell)$, and the maximum length of an increasing
subsequence of $\tau$ is denoted by $\text{LIS}(\tau)$. We may define analogously $\text{LDS}(\tau)$ as the maximum length of a decreasing subsequence of $\tau$.

The study of monotone subsequences in permutations has been an active and capti-
vating field of research; see [33] for an introduction. In particular when $\tau_n$ is uniformly
random, the law of $\text{LIS}(\tau_n)$ (which is the same as that of $\text{LDS}(\tau_n)$ in this case) is now
well-understood: it behaves asymptotically as $2\sqrt{n}$ [38], satisfies a large deviation
principle [10, 35], and admits Tracy-Widom fluctuations of order $n^{1/6}$ [4].

One might expect these results to mostly hold when the law of $\tau_n$ is conjugation-
invariant. The first advance on this question was obtained by Baik and Rains, who
studied random involutions [5]. More recently, Kammoun [25, 27] and Guionnet [17]
could settle the case of conjugation-invariant random permutations with few cycles.
Here we start by stating first order asymptotic results and concentration inequalities
for the longest decreasing subsequences of uniform permutations with given cycle
types and no fixed points.

**Theorem 2.1** For any $\delta > 0$ there exists $c_\delta > 0$ such that the following holds. For each $n$, let $t^{(n)}$ be a cycle type of size $n$ such that $t_1^{(n)} = 0$ and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Then:

$$
\mathbf{P} \left( \frac{1}{\sqrt{n}} \mathrm{LDS}(\tau_n) < 2(1-\delta) \right) \le \exp(-c_\delta n) ;
$$

$$
\mathbf{P} \left( \frac{1}{\sqrt{n}} \mathrm{LDS}(\tau_n) > 2(1+\delta) \right) \le \exp(-c_\delta \sqrt{n}).
$$

In particular $\frac{1}{\sqrt{n}}\mathrm{LDS}(\tau_n) \xrightarrow{n\to\infty} 2$ in probability and in $L^q$ for all $q \ge 1$.

It is not difficult to add fixed points in the previous theorem, and to consider random
cycle types instead of deterministic ones. This yields the following corollary.

**Corollary 2.2** For any $\delta > 0$ there exists $c_\delta > 0$ such that the following holds. Let $(\tau_n)_n$ be a sequence of conjugation-invariant random permutations, where $\tau_n$ has size $n$ and (random) cycle type $t^{(n)}$. Then for any $n$:

$$
\left\{
\begin{array}{l}
\mathbf{P} \left( \text{LDS}(\tau_n) < 2(1-\delta)\sqrt{n-t_1^{(n)}} \right) \le \mathbb{E} \left[ \exp \left( -c_\delta (n-t_1^{(n)}) \right) \right]; \\
\mathbf{P} \left( \text{LDS}(\tau_n) > 2(1+\delta)\sqrt{n-t_1^{(n)}} \right) \le \mathbb{E} \left[ \exp \left( -c_\delta \sqrt{n-t_1^{(n)}} \right) \right].
\end{array}
\right.
$$

In particular if $n - t_1^{(n)} \to \infty$ in probability then $\frac{1}{1 + \sqrt{n - t_1^{(n)}}} \text{LDS}(\tau_n) \to 2$ in probability and in $L^q$ for all $q \ge 1$.

Although increasing and decreasing subsequences share the same distribution in uniformly random permutations, this fact does not hold for conjugation-invariant random permutations. The study of increasing subsequences in this context is trickier, and we were only able to derive their first order asymptotics up to a multiplicative constant. As before, we start by stating our result for uniform permutations with given

<figure><img src="image_5.png" /></figure>
cycle types and no fixed points, and then we generalize it to all conjugation-invariant permutations.

**Proposition 2.3** For any $\delta > 0$ there exists $c_\delta > 0$ such that the following holds. For each $n$, let $t^{(n)}$ be a cycle type of size $n$ such that $t_1^{(n)} = 0$ and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Then:

$$ 
\begin{aligned}
\mathbf{P}\left(\frac{1}{\sqrt{n}}\mathrm{LIS}(\tau_n) < 2(1-\delta)\right) &\le \exp(-c_\delta n) \ ; \\
\mathbf{P}\left(\frac{1}{\sqrt{n}}\mathrm{LIS}(\tau_n) > 2(1+\delta)\sqrt{3}\right) &\le \exp(-c_\delta \sqrt{n}) \cdot
\end{aligned}
$$

**Corollary 2.4** For any $\delta > 0$ there exists $c_\delta > 0$ such that the following holds. Let $(\tau_n)_n$ be a sequence of conjugation-invariant random permutations, where $\tau_n$ has size $n$ and (random) cycle type $t^{(n)}$. Then for any $n$:

$$ 
\left\{
\begin{array}{l}
\mathbf{P}(\mathrm{LIS}(\tau_n) < 2(1-\delta)\sqrt{n}) \le \exp(-c_\delta n); \\
\mathbf{P}(\mathrm{LIS}(\tau_n) > t_1^{(n)} + 2(1+\delta)\sqrt{3(n-t_1^{(n)})}) \le \mathbb{E}\left[\exp(-c_\delta\sqrt{n-t_1^{(n)}})\right].
\end{array}
\right.
$$

In particular if $\frac{1}{\sqrt{n}}t_1^{(n)} \to \alpha \ge 0$ in probability then $\frac{1}{\sqrt{n}}\mathrm{LIS}(\tau_n)$ is asymptotically bounded between 2 and $\alpha + 2\sqrt{3}$ in probability.

Let us briefly explain the techniques used to prove the results of this section. Deuschel and Zeitouni [9] studied the first order asymptotics of longest monotone subsequences in $\mathrm{Perm}(Z_1, \dots, Z_n)$, where $Z_1, \dots, Z_n$ are i.i.d. under certain probability densities on $[0, 1]^2$ (such random permutations are called locally uniform in [36]). This is made possible by the following key observation: increasing and decreasing subsequences of $\tau = \mathrm{Perm}(P)$ correspond to up-right and down-right paths of points in $P$. The authors of [9] then slice the unit square into small rectangles in which the points are almost uniformly distributed, so that they may locally apply the result of [38], and finally stitch these local paths of points into one global path. When studying uniform permutations in given conjugacy classes, the same method can be adapted to the geometric construction of Lemma 1.3.

Finally, we state a reasonable conjecture in the direction of Proposition 2.3 and Corollary 2.4. It was already established for random involutions in [5], and for conjugation-invariant random permutations satisfying certain cycle constraints in [25, Theorem 1.2] and [27, Theorem 3].

**Conjecture 2.5** Let $(\tau_n)_n$ be a sequence of conjugation-invariant random permutations, where $\tau_n$ has size $n$ and (random) cycle type $t^{(n)}$. Suppose that $t_1^{(n)}/\sqrt{n} \to 0$ in probability. Then

$$ \frac{1}{\sqrt{n}}\mathrm{LIS}(\tau_n) \xrightarrow{n\to\infty} 2 $$

in probability.
**Remark 1** Baik and Rains actually proved [5, Theorems 3.2 and 3.4] that if $\tau_n$ is a uniform $t^{(n)}$-cyclic permutation where $t^{(n)} = (t_1^{(n)}, t_2^{(n)}, 0, \dots)$ satisfies $t_1^{(n)}/\sqrt{n} \to \alpha \ge 0$, i.e. if $\tau_n$ is a uniform involution with $\alpha\sqrt{n} + o(\sqrt{n})$ fixed points, then

$$ \frac{1}{\sqrt{n}} \mathrm{LIS}(\tau_n) \underset{n \to \infty}{\longrightarrow} \begin{cases} 2 & \text{if } \alpha \le 1 \\ \alpha + \frac{1}{\alpha} & \text{if } \alpha \ge 1 \end{cases} $$

in probability. We could expect the same first order asymptotics for any sequence of conjugation-invariant random permutations such that $t_1^{(n)}/\sqrt{n} \to \alpha$ in probability. However we chose not to include this refinement of Conjecture 2.5 in its statement, as it might be more speculative.

The results of this section are proved in Section 4.

## 2.2 Robinson-Schensted shape

Let $\tau$ be a permutation of $[n]$. If $x \ge 0$, we call $x$-decreasing subsequence any union of $[x]$ individually decreasing subsequences, and we define $\mathrm{LDS}_x(\tau)$ as the maximal size of an $x$-decreasing subsequence of $\tau$.

The study of $x$-decreasing subsequences in permutations is partly motivated by their fundamental link with the *Robinson-Schensted correspondence*. This is a one-to-one correspondence between permutations and pairs of standard Young tableaux with the same shape. This shape, which is a Young diagram, is called the *RS shape* of the permutation: it appears in several domains, such as integrable probability or representation theory. A well-known theorem of Greene [16] states that for any integer $k$, the number of boxes in the first $k$ columns of the RS shape of $\tau$ equals $\mathrm{LDS}_k(\tau)$. Equivalently, the length of the $k$-th column equals $\mathrm{LDS}_k(\tau) - \mathrm{LDS}_{k-1}(\tau)$. A similar connection can be made between increasing subsequences of $\tau$ and the row lengths of its RS shape.

Historically, studying the asymptotics of $\mathrm{LIS}(\tau_n)$ and $\mathrm{LDS}(\tau_n)$ when $\tau_n$ is uniformly random actually required finding the asymptotics of its entire RS shape. The law of this shape is known as the Plancherel measure, for which Vershik and Kerov and simultaneously Logan and Shepp established the following.

**Theorem 2.6** ([30, 38]) For each $n$, let $\tau_n$ be a uniformly random permutation of $[n]$. Then there exists an explicit nondecreasing, concave function $F_{\mathrm{LSKV}}: \mathbb{R}_+ \to \mathbb{R}_+$ such that for each $r \ge 0$:

$$ \frac{1}{n} \mathrm{LDS}_{r\sqrt{n}}(\tau_n) \underset{n \to \infty}{\longrightarrow} F_{\mathrm{LSKV}}(r) $$

in probability.

According to Greene's theorem, $F_{\mathrm{LSKV}}(r)$ thus describes the asymptotic proportion of boxes in the first $\lfloor r\sqrt{n} \rfloor$ columns of the RS shape of $\tau_n$, and the derivative of $F_{\mathrm{LSKV}}$ describes the limit curve of this shape.

<figure><img src="image_6.png" /></figure>
A classical property of the Robinson–Schensted correspondence is that it induces a bijection between involutions and (single) standard Young tableaux. If ($\tau_n$) is a sequence of uniformly random involutions, the proofs of [30] and [38] can then be adapted to show that Theorem 2.6 still holds (see e.g. Equation (24) in [31] and the discussion below). More generally if ($\tau_n$) is a sequence of conjugation-invariant random permutations, Kammoun proved that Theorem 2.6 still holds under the assumption that the number of cycles in $\tau_n$ is sublinear [25, Theorem 1.8]. He later conjectured that this assumption could be lifted, provided we take into account the proportion of fixed points [27, Conjectures 6 and 7]. The main difficulty is that none of the previous approaches (via hook-length formula [30], representation theory [21, 31], coupling [25]...) work in this wider setting. Here, using our geometric construction, we solve this conjecture.

**Theorem 2.7** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ with no fixed point and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Then for each $r \ge 0$:

$$ \frac{1}{n} \text{LDS}_{r\sqrt{n}}(\tau_n) \xrightarrow{n \to \infty} F_{\text{LSKV}}(r) $$

in probability.

**Corollary 2.8** Let $(\tau_n)_n$ be a sequence of conjugation-invariant random permutations, where $\tau_n$ has size $n$ and (random) cycle type $t^{(n)}$. Suppose that $n - t_1^{(n)} \to \infty$ in probability. Then for each $r \ge 0$:

$$ \frac{1}{n - t_1^{(n)}} \text{LDS}_{r\sqrt{n - t_1^{(n)}}}(\tau_n) \xrightarrow{n \to \infty} F_{\text{LSKV}}(r) $$

in probability.

Let us briefly discuss the strategy of proof. As in Section 2.1, $k$-decreasing subsequences of $\tau = \text{Perm}(\mathcal{P})$ have a nice visual interpretation: they correspond to unions of $k$ down-right paths in $\mathcal{P}$. In the continuity of [9], where the longest monotone subsequences of locally uniform permutations were studied with geometric tools, Sjöstrand [36] recently studied the limit RS shape of locally uniform permutations using more advanced analysis. His approach broadly consisted in computing the “score” associated with a bundle of decreasing curves, by decomposing the unit square into small regions where the sampling density is almost constant and the curves are almost parallel. In Lemma 3.3 we show that the points of our geometric construction, when restricted to any rectangle outside the diagonal of the unit square, are i.i.d. uniform. This simple fact is at the basis of how we apply and adapt the results and methods of [36].

The results of this section are proved in Section 5.

## 2.3 Records

Let $\tau$ be a permutation of $[n]$. We say that a position $i \in [n]$ is a high record (or left-to-right maximum) for $\tau$ if for any $j < i$, we have $\tau(j) < \tau(i)$. We say that it is a
low record (or left-to-right minimum) for $\tau$ if for any $j < i$, we have $\tau(j) > \tau(i)$. We denote by $\text{rec}^{\uparrow}(\tau)$ and $\text{rec}^{\downarrow}(\tau)$ the numbers of high and low records in $\tau$, respectively. Records and their many variants are standard statistics in enumerative combinatorics.

The numbers of low and high records in uniformly random permutations are well-understood: thanks to a classical bijection they follow the same law as the number of cycles (see e.g. [3, Section 1.2]), and this yields the following asymptotic normality (found e.g. in [2, Equation (1.31)]).

**Theorem 2.9** For each $n$, let $\tau_n$ be a uniformly random permutation of $[n]$. Then we have the following convergence in distribution:

$$ \frac{\text{rec}^{\uparrow}(\tau_n) - \log n}{\sqrt{\log n}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, 1). $$

The same holds for $\text{rec}^{\downarrow}(\tau_n)$.

Records can be interpreted nicely when the permutation is obtained from a family of points in the plane. If $\tau = \text{Perm}(\mathcal{P})$, a point $Z = (X, Y) \in \mathcal{P}$ corresponds to a high record in $\tau$ when no other point lies in its up-left corner $[0, X] \times [Y, 1]$. Similarly, $Z$ corresponds to a low record in $\tau$ when no other point lies in its down-left corner $[0, X] \times [0, Y]$. We write $\text{rec}^{\uparrow}(\mathcal{P})$ and $\text{rec}^{\downarrow}(\mathcal{P})$ as shortcuts for $\text{rec}^{\uparrow}(\text{Perm}(\mathcal{P}))$ and $\text{rec}^{\downarrow}(\text{Perm}(\mathcal{P}))$.

There is no more link between the numbers of cycles and records in conjugation-invariant permutations, but the geometric construction enables a new approach. We prove a limit theorem for the number of high records, showcasing a phase transition as the number of fixed points grows. First recall that, for $n \in \mathbb{N}^*$ and $\lambda > 0$, the Gamma $(n, \lambda)$ distribution is defined as the $n$-th convolution power of the Exp $(\lambda)$ distribution. By convention, Gamma $(n, +\infty)$ is the a.s. null distribution.

**Theorem 2.10** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Write $\tilde{n} := n - t_1^{(n)}$ for the number of non-fixed points. Suppose that $\tilde{n} \underset{n \to \infty}{\longrightarrow} \infty$ and that

$$ \frac{\tilde{n}}{n/\sqrt{\log n}} \underset{n \to \infty}{\longrightarrow} \alpha $$

for some $\alpha \in [0, \infty]$. Then we have the following convergence in distribution:

$$ \frac{\text{rec}^{\uparrow}(\tau_n) - \log(\tilde{n})}{t_1^{(n)}/\tilde{n} + \sqrt{\log(\tilde{n})}} \underset{n \to \infty}{\longrightarrow} \frac{\alpha}{\alpha+1}Y + \frac{1}{\alpha+1}\Gamma_2 $$

where $Y$ and $\Gamma_2$ are independent $\mathcal{N}(0, 1)$ and Gamma $(2, 1)$ random variables. In particular if $\tilde{n} = \omega(\frac{n}{\sqrt{\log n}})$ as $n \to \infty$ then:

$$ \frac{\text{rec}^{\uparrow}(\tau_n) - \log n}{\sqrt{\log n}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, 1). $$

<figure><img src="image_7.png" /></figure>
Similar to the case of monotone subsequences, the study of low records in conjugation-invariant random permutations differs from that of high records. This asymmetry is already seen in some regimes for the first order asymptotics, as shown in the following theorem.

**Theorem 2.11** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation.

1. If $t_1^{(n)} = O(\sqrt{n})$ then we have the following convergence in probability:

$$ \frac{\mathrm{rec}^{\downarrow}(\tau_n)}{\log n} \xrightarrow{n \to \infty} 1. $$

2. If $\sqrt{n} \ll t_1^{(n)} \ll n$, i.e. $\sqrt{n} = o(t_1^{(n)})$ and $t_1^{(n)} = o(n)$, then we have the following convergence in probability:

$$ \frac{\mathrm{rec}^{\downarrow}(\tau_n)}{\log n - \log t_1^{(n)}} \xrightarrow{n \to \infty} 2. $$

3. If $t_1^{(n)} = \Theta(n)$ then $\mathrm{rec}^{\downarrow}(\tau_n) = O_P(1)$.

We could not compute fluctuations for the number of low records in general. To simplify the analysis, we restrict ourselves to products of 2-cycles and products of 3-cycles, for which exhibit different fluctuations.

**Proposition 2.12** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ such that $t_1^{(n)} = O(\sqrt{n})$, and let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation.

1. Suppose that $t_1^{(n)} + 2t_2^{(n)} = n$. Then we have the following convergence in distribution:

$$ \frac{\mathrm{rec}^{\downarrow}(\tau_n) - \log n}{\sqrt{\log n}} \xrightarrow{n \to \infty} \mathcal{N}(0, 2). $$

2. Suppose that $t_1^{(n)} + 3t_3^{(n)} = n$. Then we have the following convergence in distribution:

$$ \frac{\mathrm{rec}^{\downarrow}(\tau_n) - \log n}{\sqrt{\log n}} \xrightarrow{n \to \infty} \mathcal{N}(0, 1). $$

It would be interesting to find the interpolation between the two items of Proposition 2.12. However this would notably require understanding the interaction between 2-cycles and other cycles, and its effect on the law of low records, which seems difficult to grasp.

**Remark 2** As in Corollaries 2.2, 2.4, 2.8 and 2.16, the results of this section remain true if $(\tau_n)$ is a sequence of conjugation-invariant random permutations and the hypotheses hold in probability.

The results of this section are proved in Section 6.
## 2.4 Pattern counts

Let $\tau \in \mathfrak{S}_n$ and $I = \{i_1 < \cdots < i_r\}$ be a subset of $[n]$. We may define a permutation $\pi \in \mathfrak{S}_r$ by the following rule: for any $j, k \in [r]$, $\pi(j) > \pi(k)$ if and only if $\tau(i_j) > \tau(i_k)$. We write $\text{pat}(I, \tau)$ for this permutation, and say that this is the pattern induced by $\tau$ on $I$.

Permutation patterns are a natural notion of substructures for permutations, and as such they have attracted a lot of interest. A central question is that of pattern counts: given a permutation $\pi$ of $[r]$, how many subsets of $\tau$ induce $\pi$ as a pattern? In other words, we are interested in the statistic

$$X_{\pi}(\tau) := \sum_{I \in \binom{[n]}{r}} \mathbf{1}_{\text{pat}(I, \tau)=\pi}$$

where $\binom{[n]}{r}$ denotes the subsets of $[n]$ of size $r$. For example, $X_{21}(\tau)$ counts the number of inversions in $\tau$, and $X_{12\dots r}(\tau)$ counts the number of increasing subsequences of length $r$ in $\tau$.

Pattern counts in uniformly random permutations are known to be asymptotically normal since the works of Bóna for monotone patterns [7], and later Janson et al. for all patterns:

**Theorem 2.13** ([24]) For each $n$, let $\tau_n$ be a uniformly random permutation of $[n]$. Then for any $r \in \mathbb{N}^*$:

$$\left( \frac{X_{\pi}(\tau_n) - \binom{n}{r} \frac{1}{r!}}{n^{r-1/2}} \right)_{\pi \in \mathfrak{S}_r} \underset{r \to \infty}{\longrightarrow} \mathcal{N}(0, \Sigma)$$

for some matrix $\Sigma$, of rank $(r-1)^2$ and such that $\Sigma_{\pi,\pi} > 0$ for all $\pi \in \mathfrak{S}_r$ if $r \ge 2$.

The convergence result in this theorem can be established via the method of *dependency graphs*. To prove non-degeneracy, i.e. that $\Sigma_{\pi,\pi}$ is positive, Bóna was able to find a lower bound for the variance of $X_\pi$ by expressing it in terms of covariances, while the authors of [24] used the method of *U-statistics*.

In [13], Féray established a central limit theorem for pattern counts in Ewens random permutations, and conjectured its non-degeneracy. Kammoun [26, Proposition 31] and Hamaker and Rhoades [18, Theorem 8.8] could generalize the non-degenerate asymptotic normality of Theorem 2.13 to conjugation-invariant permutations, under certain conditions on their cycles. It was conjectured in [18, Problem 9.9] that those conditions could be lifted, and that the asymptotic variance would only depend on the proportions of fixed points and 2-cycles.

Here, using the geometric construction of Lemma 1.3, we extend the convergence of Theorem 2.13 to most conjugation-invariant permutations. If $\tau_n$ is a uniform $t$-cyclic permutation then we can write, for any $\pi \in \mathfrak{S}_r$:

$$X_{\pi}(\tau_n) = \sum_{I \in \binom{[n]}{r}} \mathbf{1}_{\text{Perm}(Z_i, i \in I)} = \pi \quad (1)$$

<figure><img src="image_8.png" /></figure>
with the notation of Section 1.2. Thanks to the dependency graph $\mathcal{L}_t$ defined in Section 1.3, we derive a limit theorem for $X_\pi(\tau_n)$. More precisely, Stein's method yields explicit bounds on the speed of convergence. In the following, we denote by $d_K$ the Kolmogorov distance between two probability distributions.

**Theorem 2.14** Let $Y \sim \mathcal{N}(0, 1)$. For each $n$, let $t^{(n)}$ be a cycle type of size $n$ and $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Fix $r \in \mathbb{N}^*$ and $\pi \in \mathfrak{S}_r$. Then for any $n$:

$$d_K \left( \frac{X_\pi(\tau_n) - \mathbb{E}[X_\pi(\tau_n)]}{\sqrt{\mathrm{Var}[X_\pi(\tau_n)]}}, Y \right) \le 42 \frac{r}{(r-1)!^2} \frac{n^{2r-3/2}}{\mathrm{Var}[X_\pi(\tau_n)]} + 72 \frac{r}{(r-1)!^3} \frac{n^{3r-2}}{\mathrm{Var}[X_\pi(\tau_n)]^{3/2}}$$

Furthermore, if $\mathrm{Var}[X_\pi(\tau_n)] = \sigma^2 n^{2r-1} + o(n^{2r-1})$ for some $\sigma \ge 0$ as $n \to \infty$, then

$$\frac{X_\pi(\tau_n) - \mathbb{E}[X_\pi(\tau_n)]}{n^{r-1/2}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, \sigma^2)$$

in distribution, and if $\sigma > 0$ then the previous distance is bounded by $\mathcal{O}(n^{-1/2})$.

Thanks to [18, Proposition 7.2 and Theorem 8.14], the condition $\mathrm{Var}[X_\pi(\tau_n)] = \sigma^2 n^{2r-1} + o(n^{2r-1})$ holds under the simple assumption that $t_1^{(n)}/n$ and $t_2^{(n)}/n$ converge. We may still want to find an explicit formula for $\sigma$, and to understand in which cases $\sigma > 0$. For this we use the method of U-statistics developed by Hoeffding [19], as was done in [24]. Before stating our results, we need a few definitions.

Fix $r \in \mathbb{N}^*$ and $p_1 \in [0, 1]$. Then let $\hat{Z}_1, \dots, \hat{Z}_r$ be i.i.d. variables distributed under $p_1 \mathrm{Leb}_\Delta + (1-p_1) \mathrm{Leb}_{[0,1]^2}$, where $\mathrm{Leb}_\Delta$ denotes the Lebesgue measure on the diagonal $\Delta$ of $[0, 1]^2$. Define, for any $z \in [0, 1]^2$:

$$\psi_{\pi}^{p_1}(z) := \mathbf{P} \left( \mathrm{Perm} \left( \hat{Z}_1, \dots, \hat{Z}_{r-1}, z \right) = \pi \right)$$

and

$$\mu_{\pi}^{p_1} := \mathbf{P} \left( \mathrm{Perm} \left( \hat{Z}_1, \dots, \hat{Z}_r \right) = \pi \right) = \mathbb{E} \left[ \psi_{\pi}^{p_1} \left( \hat{Z}_r \right) \right].$$

**Theorem 2.15** Let $(t^{(n)})_n$ be a sequence of cycle types of size $n$ such that $t_1^{(n)} = np_1 + o(\sqrt{n})$ and $2t_2^{(n)} = np_2 + o(n)$ as $n \to \infty$, for some $p_1, p_2 \in [0, 1]$. For each $n$, let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Then for any $r \in \mathbb{N}^*$, we have the following convergence in distribution:

$$\left( \frac{X_\pi(\tau_n) - \binom{n}{r} \mu_\pi^{p_1}}{n^{r-1/2}} \right)_{\pi \in \mathfrak{S}_r} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, \Sigma^{p_1, p_2})$$
where for any $\pi, \rho \in \mathfrak{S}_r$, if $U, V, W$ are i.i.d. Unif([0, 1]) variables:

$$ (r-1)!^2 \sum_{\pi, \rho} p_1^{p_1} p_2^{p_2} = p_1 \mathrm{Cov} [\psi_{\pi}^{p_1}(U, U), \psi_{\rho}^{p_1}(U, U)] \\ + (1-p_1) \mathrm{Cov} [\psi_{\pi}^{p_1}(U, V), \psi_{\rho}^{p_1}(U, V)] \\ + p_2 \mathrm{Cov} [\psi_{\pi}^{p_1}(U, V), \psi_{\rho}^{p_1}(V, U)] \\ + 2(1-p_1-p_2) \mathrm{Cov} [\psi_{\pi}^{p_1}(U, V), \psi_{\rho}^{p_1}(V, W)]. $$

**Corollary 2.16** Let $(\tau_n)_n$ be a sequence of conjugation-invariant random permutations, where $\tau_n$ has size $n$ and (random) cycle type $t^{(n)}$. Suppose that $t_1^{(n)} = np_1 + o_P(\sqrt{n})$ and $2t_2^{(n)} = np_2 + o_P(n)$ as $n \to \infty$, for some $p_1, p_2 \in [0, 1]$. Then the convergence of Theorem 2.15 holds.

Note that Theorem 2.15 states a joint convergence, rather than the marginal convergence stated in Theorem 2.14. We stress that the true novelty of Theorem 2.15 lies in the computation of the variance, carried out by the method of $U$-statistics, and not in the joint convergence. Indeed, Theorem 2.14 could have been stated for joint convergence, but we chose not to do so for convenience.

The matrix $\Sigma^{p_1, p_2}$ turns out to be rather difficult to study when $p_1 \in (0, 1)$. Without further hypotheses, we could only prove that $X_\pi(\tau_n)$ satisfies non-degenerate asymptotic normality if $\pi$ is an involution.

**Proposition 2.17** If $p_1 < 1$ and $\pi \in \mathfrak{S}_r$, $r \ge 2$ satisfies $\pi = \pi^{-1}$, then $\sum_{\pi, \pi}^{p_1, p_2} > 0$.

When fixed points vanish, i.e. when $p_1 = 0$, Theorem 2.15 greatly simplifies. This allows us to prove non-degeneracy for any non-trivial pattern and to compute the dimension spanned by the limiting Gaussian variable, as in Theorem 2.13 of [24]. We use the notation of Theorem 2.15 and drop the index $p_1$ when it is null.

**Theorem 2.18** Let $(t^{(n)})_n$ be a sequence of cycle types of size $n$ such that $t_1^{(n)} = o(\sqrt{n})$ and $2t_2^{(n)} = np_2 + o(n)$ as $n \to \infty$, for some $p_2 \in [0, 1]$. For each $n$, let $\tau_n$ be a uniform $t^{(n)}$-cyclic permutation. Then for any $r \in \mathbb{N}^*$, we have the following convergence in distribution:

$$ \left( \frac{X_{\pi}(\tau_n) - \binom{n}{r} \frac{1}{r!}}{n^{r-1/2}} \right)_{\pi \in \mathfrak{S}_r} \xrightarrow{n \to \infty} \mathcal{N}(0, \Sigma^{p_2}) $$

where for any $\pi, \rho \in \mathfrak{S}_r$, if $U, V$ are i.i.d. Unif([0, 1]) variables:

$$ (r-1)!^2 \sum_{\pi, \rho} p_2^{p_2} = \mathrm{Cov} [\psi_{\pi}(U, V), \psi_{\rho}(U, V)] + p_2 \mathrm{Cov} [\psi_{\pi}(U, V), \psi_{\rho}(V, U)]. $$

The matrix $\Sigma^{p_2}$ has rank $(r-1)^2$ for any $p_2 < 1$, and rank $r(r-1)/2$ for $p_2 = 1$. Moreover, $\sum_{\pi, \pi}^{p_2} > 0$ for any $p_2 \in [0, 1]$ and $\pi \in \mathfrak{S}_r$, $r \ge 2$.

**Remark 3** In parallel to this work, Féray and Kammoun [14] were able to prove a more general result than Theorem 2.15 and Proposition 2.17, using the method of weighted

<figure><img src="image_9.png" /></figure>
dependency graphs. They could prove non-degeneracy for any (classical) non-trivial pattern, i.e. that $\sum_{\pi, \pi'}^{p_1, p_2} > 0$ for any $p_1 < 1$ and $\pi \in \mathfrak{S}_r$, $r \ge 2$. However, bounds on the speed of convergence as in our Theorem 2.14 seem to be out of reach for their methods.

**Remark 4** Our method of (non-weighted) dependency graphs also allows the application of [23, Theorem 2.1] to Equation 1 for large deviation estimates. Namely, for any $t > 0$:

$$ \mathbf{P}(|X_{\pi}(\tau_n) - \mathbb{E}[X_{\pi}(\tau_n)]| \ge t) \le 2 \exp\left(\frac{-2(r-1)!}{3} \frac{t^2}{n^{2r-1}}\right) $$

**Remark 5** A popular generalization of patterns is that of vincular patterns, where we require some positions of the pattern to be adjacent. Descents, peaks and valleys are classical examples of vincular patterns. Asymptotic normality of vincular pattern counts in uniform permutations was established in [20]. Regarding conjugation-invariant permutations, the convergence results of [14, 18, 26] all hold within the general context of vincular patterns. Unfortunately, it seems unlikely that our methods would work for vincular patterns.

The results of this section are proved in Section 7.

## 3 Properties of the geometric construction

In this section, we present several interesting facts about the geometric construction of Lemma 1.3. These will be essential to prove the results of this paper, generally by reducing the study of conjugation-invariant permutations to uniformly random permutations. We use the notation of Section 1.2 and 1.3.

**Lemma 3.1** Let $t$ be a cycle type of size $n$ such that $t_1 = 0$, and let $\mathcal{P}$ be a geometric construction. Then it can be decomposed into an a.s. disjoint union

$$ \mathcal{P} = \mathcal{P}^{(1)} \cup \mathcal{P}^{(2)} \cup \mathcal{P}^{(3)} $$

where each $\mathcal{P}^{(i)}$ is a family of i.i.d. uniform points in $[0, 1]^2$, of (deterministic) sizes $n_1, n_2, n_3$ bounded between $n/3-1$ and $n/3+1$.

**Proof** The idea is to define the three subsets $\mathcal{P}^{(1)}, \mathcal{P}^{(2)}, \mathcal{P}^{(3)}$ by assigning them the points of each cycle in an alternating order. The rule for ensuring the i.i.d. uniformity property is that whenever some point $Z_{p,k}^l$ lies in $\mathcal{P}^{(i)}$, then the adjacent points $Z_{p,k}^{l \pm 1}$ shall not belong to $\mathcal{P}^{(i)}$. To construct the $\mathcal{P}^{(i)}$'s in a balanced way while satisfying this rule, we do the following:

* For each $p$ such that $p = 0 \mod 3$ and $1 \le k \le t_p$, the points of $\mathcal{P}_{p,k}$ can be put in the three subsets by simply alternating:

$$ Z_{p,k}^1 \in \mathcal{P}^{(1)}, Z_{p,k}^2 \in \mathcal{P}^{(2)}, Z_{p,k}^3 \in \mathcal{P}^{(3)}, Z_{p,k}^4 \in \mathcal{P}^{(1)}, \dots, Z_{p,k}^p \in \mathcal{P}^{(3)}. $$
Then each $\mathcal{P}_{p,k} \cap \mathcal{P}^{(i)}$ has size $p/3$ and contains i.i.d. uniform points.

* For each $p$ such that $p = 1 \mod 3$ and $1 \le k \le t_p$, the points of $\mathcal{P}_{p,k}$ can be put in the three subsets by simply alternating, but then one subset will get a surplus. Thus two of the subsets $\mathcal{P}_{p,k} \cap \mathcal{P}^{(i)}$ have size $(p-1)/3$, the other one has size $1 + (p-1)/3$, and they each contain i.i.d. uniform points. Namely if $(i_1, i_2, i_3)$ is a permutation of $(1, 2, 3)$ then the choice

$$Z_{p,k}^1 \in \mathcal{P}^{(i_1)}, Z_{p,k}^2 \in \mathcal{P}^{(i_2)}, Z_{p,k}^3 \in \mathcal{P}^{(i_3)}, Z_{p,k}^4 \in \mathcal{P}^{(i_1)}, \dots, Z_{p,k}^{p-1} \in \mathcal{P}^{(i_3)}, Z_{p,k}^p \in \mathcal{P}^{(i_2)}$$

yields a surplus for $\mathcal{P}^{(i_2)}$. For each such $(p, k)$ we can choose which subset gets a surplus in order to balance out those surpluses over the $(p, k)$'s. Consequently the sets

$$\bigcup_{p=1 \mod 3, 1 \le k \le t_p} \mathcal{P}_{p,k} \cap \mathcal{P}^{(i)}$$

have sizes of the form $m + \epsilon_i$ for some integer $m$ and $\epsilon_i \in \{0, 1\}, i = 1, 2, 3$.

* For each $p = 2 \mod 3$ and $1 \le k \le t_p$ a similar reasoning can be made, except this time one subset will get a deficit. By balancing out the deficits as before, we can construct the sets

$$\bigcup_{p=2 \mod 3, 1 \le k \le t_p} \mathcal{P}_{p,k} \cap \mathcal{P}^{(i)}$$

in such a way that they each contain i.i.d. uniform points and have sizes of the form $m' - \delta_i$ for some integer $m'$ and $\delta_i \in \{0, 1\}, i = 1, 2, 3$.

In the end, by balancing out the surpluses with the deficits, the subsets $\mathcal{P}^{(i)}$ have sizes $m'' + \eta_i$ for some integer $m''$ and $\eta_i \in \{0, 1\}, i = 1, 2, 3$, and each contain i.i.d. uniform points. The lemma follows. $\square$

Thanks to Lemma 3.1, we can apply Chernoff-type bounds to control the number of points in any zone of the plane. Recall that $\tilde{P} := P \setminus \Delta$ is a geometric construction for $\tilde{t} := (0, t_2, \dots)$ of size $\tilde{n} := n - t_1$.

**Corollary 3.2** Let $t$ be a cycle type of size $n$ and $P$ be a geometric construction. If $C$ is a measurable subset of $[0, 1]^2$ then $|\tilde{P} \cap C|$ is distributed like a (correlated) sum of Binom $(n_i, \text{Leb}(C))$ variables, where $|n_i - \tilde{n}/3| \le 1$ for $i = 1, 2, 3$. In particular for any $\delta > 0$ there exists a constant $c > 0$, which depends only on $\delta$ and $\text{Leb}(C)$, such that:

$$\mathbf{P}\left(\left|\frac{1}{\tilde{n}}\right|\tilde{P} \cap C\right| - \text{Leb}(C)\right| > \delta\right) \le \exp(-c\tilde{n}).$$

The following two lemmas informally state that conjugation-invariant random permutations are, in some sense, “locally uniform”.

<figure><img src="image_10.png" /></figure>
**Lemma 3.3** Let $t$ be a cycle type and $\mathcal{P}$ be a geometric construction. If $I, J$ are two essentially disjoint intervals of $[0, 1]$ then the set $\mathcal{P} \cap (I \times J)$ is a (random-sized) family of i.i.d. uniform points in $I \times J$.

*Proof* It suffices to prove the lemma for each set $\mathcal{P}_{p,k}$. Fix $(p, k)$. Note that if some point $(U_{p,k}^l, U_{p,k}^{l+1})$ is in $I \times J$ then a.s. neither $(U_{p,k}^{l-1}, U_{p,k}^l)$ nor $(U_{p,k}^{l+1}, U_{p,k}^{l+2})$ are in $I \times J$, where all exponents are taken modulo $p$ in $[p]$. Moreover, $(U_{p,k}^l, U_{p,k}^{l+1})$ is independent of

$$ \mathcal{P}_{p,k} \setminus \{(U_{p,k}^{l-1}, U_{p,k}^l), (U_{p,k}^l, U_{p,k}^{l+1}), (U_{p,k}^{l+1}, U_{p,k}^{l+2})\}. $$

Thus for any $l_1, \dots, l_j$, the event

$$ \{ \mathcal{P}_{p,k} \cap (I \times J) = \{(U_{p,k}^{l_1}, U_{p,k}^{l_1+1}), \dots, (U_{p,k}^{l_j}, U_{p,k}^{l_j+1})\} \} $$

is either negligible or essentially rewrites as

$$ \begin{gathered} (U_{p,k}^{l_1}, U_{p,k}^{l_1+1}) \in I \times J, \dots, (U_{p,k}^{l_j}, U_{p,k}^{l_j+1}) \in I \times J, \\ (I \times J) \cap \mathcal{P}_{p,k} \setminus \{(U_{p,k}^{l_1-1}, U_{p,k}^{l_1}, \dots, (U_{p,k}^{l_j-1}, U_{p,k}^{l_j}, \dots)\} = \emptyset. \end{gathered} $$

Conditionally on this event when it is non-negligible, these points are i.i.d. uniform in $I \times J$. This concludes the proof. $\square$

**Lemma 3.4** Let $t$ be a cycle type of size $n$ and $\mathcal{P} = \{(U_i, U_{s(i)}) : i \in V_t\}$ be a geometric construction. Then conditionally given the unordered set $\{U_i : i \in V_t\}$, the following holds a.s.:

1. $\text{Perm}(\mathcal{P})$ is a uniform $t$-cyclic permutation.

2. If $I, J$ are two essentially disjoint intervals of $[0, 1]$ then, conditionally given $|\mathcal{P} \cap (I \times J)|$, the permutation $\text{Perm}(\mathcal{P} \cap (I \times J))$ is uniformly random of size $|\mathcal{P} \cap (I \times J)|$.

*Proof* The conditional law of $\mathcal{P}$ given $\{U_i : i \in V_t\}$ can be a.s. re-described as follows. Sort $\{U_i : i \in V_t\}$ as $U_{(1)} < \dots < U_{(n)}$, let $\rho$ be a uniformly random bijection from $[n]$ to $V_t$, then set $V_i := U_{(\rho^{-1}(i))}$ for any $i \in V_t$, and finally $\mathcal{P} = \{(V_i, V_{s(i)}) : i \in V_t\}$. The first claim then follows from the same argument as in the proof of Lemma 1.3.

For the second claim, notice that $\mathcal{P} \cap (I \times J)$ is a random subset of the finite grid $\{(U_{(i)}, U_{(j)}) : i, j \in [n]\} \cap (I \times J)$. Consider $0 \le m \le n$ and indices $i_1, \dots, i_m, j_1, \dots, j_m \in [n]$ such that for each $r \in [m]$, $U_{(i_r)} \in I$ and $U_{(j_r)} \in J$. The sets of indices $\{i_1, \dots, i_m\}$ and $\{j_1, \dots, j_m\}$ are then a.s. disjoint. Furthermore, the probability

$$ \begin{gathered} \mathbf{P}(\forall r \in [m], (U_{(i_r)}, U_{(j_r)}) \in \mathcal{P}) = \mathbf{P}(\forall r \in [m], \\ (V_{\rho(i_r)}, V_{\rho(j_r)}) \in \mathcal{P} = \mathbf{P}(\forall r \in [m], \rho(j_r) = s(\rho(i_r))) \end{gathered} $$
only depends on $i_1, \dots, i_m, j_1, \dots, j_m$ through $m$. This readily implies that conditionally given $\{U_i, i \in V_t\}$ and $|P \cap (I \times J)|$, the permutation $\text{Perm}(P \cap (I \times J))$ is uniformly random. $\square$

# 4 Proofs of the results on monotone subsequences

## 4.1 Decreasing subsequences

**Proof of Theorem 2.1** Throughout the proof we fix $\delta > 0$ and let $P$ be a geometric construction of $\tau_n$.

**Upper tail bound:** Suppose, without loss of generality, that $\delta = 1/\beta$ for some integer $\beta$. Fix an arbitrary integer $K > 16\beta^2$ and set $\Delta x := 1/K$. Slice $[0, 1]^2$ into a regular grid $(C_{i,j})_{1 \le i, j \le K}$ made of square cells

$$C_{i,j} := [(i-1)\Delta x, i\Delta x] \times [(j-1)\Delta x, j\Delta x].$$

Notice that any down-right path of points can only visit at most one diagonal square cell $C_{i,i}$. Therefore:

$$\text{LDS}(\tau_n) = \text{LDS}(P) \le \text{LDS}(\tilde{P}) + \max_{1 \le i \le K} \text{LDS}(P \cap C_{i,i}) \quad (2)$$

where $\tilde{P}$ is the restriction of $P$ to the cells $C_{i,j}$ with $i \ne j$. For each $i$, Lemma 3.1 asserts that $P \cap C_{i,i}$ is a superposition of three (correlated) random-sized sets of i.i.d. uniform points in $C_{i,i}$. Writing $L_m$ for the LDS of a uniform permutation of size $m$, we obtain:

$$\begin{aligned} \mathbf{P}(\text{LDS}(P \cap C_{i,i}) > 2\delta\sqrt{n}) &\le 3 \max_{1 \le j \le 3} \mathbf{P}(\text{LDS}(P^{(j)} \cap C_{i,i}) > \frac{2\delta}{3}\sqrt{n}) \\ &\le 3 \max_{1 \le j \le 3} \mathbf{P}(L_{|P^{(j)} \cap C_{i,i}|} > \frac{2\delta}{3}\sqrt{n}). \end{aligned}$$

Since each size $|P^{(j)} \cap C_{i,i}|$ is stochastically dominated by $\text{Binom}(n, K^{-2})$ and the variables $L_m$ are stochastically nondecreasing in $m$, this yields:

$$\mathbf{P}\left(\max_{1 \le i \le K} \text{LDS}(P \cap C_{i,i}) > 2\delta\sqrt{n}\right) \le 3K\mathbf{P}\left(L_{\text{Binom}(n, K^{-2})} > \frac{2\delta}{3}\sqrt{n}\right). \quad (3)$$

First off, Chernoff bounds imply

$$\mathbf{P}(\text{Binom}(n, K^{-2}) > 2nK^{-2}) \le \exp(-c_{\delta}n) \quad (4)$$

for some constant $c_{\delta} > 0$ which depends only on $\delta$ and whose value may change throughout the proof. Then, since $2\sqrt{2}K^{-1} < \sqrt{2\delta^2}/8 < 2\delta/3$, [35, Theorem 2] implies
<figure><img src="image_11.png" /><figcaption>Fig. 3 Representation of the down-right sequence of cells (highlighted) encoded by the admissible sequence ((10, 8), (8, 7), (5, 4), (4, 4), (4, 2)), with $K = 5$ and $\beta = 2$</figcaption></figure>

$$ \mathbf{P} \left( L_{2nK^{-2}} > \frac{2\delta}{3}\sqrt{n} \right) \leq \exp(-c_{\delta}\sqrt{n}) \quad (5) $$

for some other $c_{\delta} > 0$. From Equations 3 to 5 we deduce

$$ \mathbf{P} \left( \max_{1 \le i \le K} \mathrm{LDS}(\mathcal{P} \cap C_{i,i}) > 2\delta\sqrt{n} \right) \le \exp(-c_{\delta}\sqrt{n}) $$

for some constant $c_{\delta} > 0$. Then by (2):

$$ \mathbf{P}(\mathrm{LDS}(\tau_n) > 2(1 + 3\delta)\sqrt{n}) \le \mathbf{P}(\mathrm{LDS}(\tilde{\mathcal{P}}) > 2(1 + 2\delta)\sqrt{n}) + \exp(-c_{\delta}\sqrt{n}).(6) $$

To study the remaining term, we can broadly rewrite the proof of [9, Lemma 9]. Set $\Delta y := \Delta x/\beta = 1/(K\beta)$ and slice $[0, 1]^2$ into a thinner grid $(\tilde{C}_{i,j})_{1 \le i \le K, 1 \le j \le K\beta}$ made of rectangular cells

$$ \tilde{C}_{i,j} := [(i-1)\Delta x, i\Delta x] \times [(j-1)\Delta y, j\Delta y]. $$

Say a sequence of indices $(\mathbf{a}, \mathbf{b}) = (a_i, b_i)_{1 \le i \le K}$ is *admissible* if it satisfies $1 \le b_{i+1} \le a_{i+1} \le b_i \le a_i \le K\beta$ for all $i \in [K-1]$. Informally, it encodes a down-right sequence of cells where $a_i$, resp. $b_i$, is the highest, resp. lowest, cell in the $i$-th column. See Figure 3 for a representation. Fix such $(\mathbf{a}, \mathbf{b})$ and write $\tilde{\mathcal{P}}_{(\mathbf{a},\mathbf{b})}$ for the restriction of $\tilde{\mathcal{P}}$ to the cells associated with $(\mathbf{a}, \mathbf{b})$. For each $1 \le i \le K$, write

$$ R_i := [(i-1)\Delta x, i\Delta x] \times [(b_i - 1)\Delta y, a_i \Delta y] $$
for the i-th column of (a, b), and set $h_i := a_i - b_i + 1$. Since (a, b) encodes a down-right path, we can write

$$ \mathrm{LDS}(\tilde{\mathcal{P}}_{(a,b)}) \leq \sum_{i=1}^{K} \mathrm{LDS}(\tilde{\mathcal{P}} \cap R_i). \qquad (7) $$

Furthermore, at most one column $R_i$ can intersect the diagonal square cells $C_{i,i}$. When this happens, write $i_0$ for the corresponding index, and arbitrarily set $i_0 := 1$ otherwise. Now notice that, by the Cauchy–Schwarz inequality:

$$ \sum_{i=1}^{K} \sqrt{h_i \Delta x \Delta y} \leq \sqrt{K \sum_{i=1}^{K} h_i \Delta x \Delta y} \leq \sqrt{K \Delta x \Delta y (K + K\beta)} = \sqrt{1 + \delta} $$

where the middle inequality is obtained by noticing that a down-right path has at most $K + K\beta$ cells. This yields

$$ 1 + 2\delta \geq \delta + \sqrt{1 + \delta} \sum_{i=1}^{K} \sqrt{h_i \Delta x \Delta y}. \qquad (8) $$

Using Equations (7) and 8, we deduce:

$$ \mathbf{P}(\mathrm{LDS}(\tilde{\mathcal{P}}_{(a,b)}) > 2(1 + 2\delta)\sqrt{n}) \leq \mathbf{P}(\exists i \neq i_0, \mathrm{LDS}(\mathcal{P} \cap R_i) > 2\sqrt{1 + \delta}\sqrt{n}h_i \Delta x \Delta y) \\ + \mathbf{P}(\mathrm{LDS}(\tilde{\mathcal{P}} \cap R_{i_0}) > 2\delta\sqrt{n}). \qquad (9) $$

We can decompose the family $\tilde{\mathcal{P}} \cap R_{i_0} = (\mathcal{P} \cap A) \sqcup (\mathcal{P} \cap B)$ into its points above and below $C_{i_0,i_0}$. Since we have $\mathrm{Leb}(A) \leq \Delta x < \delta^2/16$, Corollary 3.2 yields:

$$ \mathbf{P}\left(|\mathcal{P} \cap A| > \frac{\delta^2}{16}n\right) \leq \exp(-c_{\delta}n), $$

and likewise for B. Lemma 3.3 asserts that the sets $\mathcal{P} \cap A$ and $\mathcal{P} \cap B$ consist of i.i.d. uniform points, hence:

$$ \begin{aligned} \mathbf{P}(\mathrm{LDS}(\tilde{\mathcal{P}} \cap R_{i_0}) > 2\delta\sqrt{n}) &\leq \mathbf{P}(L_{|\mathcal{P} \cap A|} > \delta\sqrt{n}) + \mathbf{P}(L_{|\mathcal{P} \cap B|} > \delta\sqrt{n}) \\ &\leq 2\mathbf{P}\left(L_{\frac{\delta^2}{16}n} > \delta\sqrt{n}\right) + \exp(-c_{\delta}n). \end{aligned} $$

Therefore, by [35, Theorem 2]:

$$ \mathbf{P}(\mathrm{LDS}(\tilde{\mathcal{P}} \cap R_{i_0}) > 2\delta\sqrt{n}) \leq \exp(-c_{\delta}\sqrt{n}). \qquad (10) $$
The first term of (9) is handled in a similar way. If $i \neq i_0$, by Corollary 3.2:

$$ \mathbf{P}(|\mathcal{P} \cap R_i| > (1 + \frac{\delta}{2})nh_i \Delta x \Delta y) \leq \exp(-c_{\delta}n). $$

We can then use Lemma 3.3 and [35, Theorem 2] as before:

$$ \begin{aligned} \mathbf{P} (\exists i \neq i_0, \text{LDS}(\mathcal{P} \cap R_i) > 2\sqrt{1+\delta}\sqrt{nh_i \Delta x \Delta y}) & \\ & \leq K \exp(-c_{\delta}n) + K \max_{i \neq i_0} \mathbf{P} (L_{(1+\delta/2)nh_i \Delta x \Delta y} > 2\sqrt{1+\delta}\sqrt{nh_i \Delta x \Delta y}) \\ & \leq \exp(-c_{\delta}\sqrt{n}). \end{aligned} \quad (11) $$

Finally, putting together Equations 9 to 11:

$$ \mathbf{P}(\text{LDS}(\tilde{\mathcal{P}}_{(a,b)}) > 2(1 + 2\delta)\sqrt{n}) \leq \exp(-c_{\delta}\sqrt{n}). $$

Since any down-right path of points defines an admissible sequence and the number of admissible sequences is bounded by $(K\beta)^{2K}$, we deduce:

$$ \mathbf{P}(\text{LDS}(\tilde{\mathcal{P}}) > 2(1 + 2\delta)\sqrt{n}) \leq \exp(-c_{\delta}\sqrt{n}) $$

for some constant $c_{\delta} > 0$ which depends only on $\delta$. Using (6), this concludes the proof of the upper tail bound.

**Lower tail bound:** Define $C := [0, 1/2] \times [1/2, 1]$ and $C^* := [1/2, 1] \times [0, 1/2]$. Then:

$$ \text{LDS}(\mathcal{P}) \geq \text{LDS}(\mathcal{P} \cap C) + \text{LDS}(\mathcal{P} \cap C^*). $$

We can apply Corollary 3.2 to obtain

$$ \mathbf{P}(|\mathcal{P} \cap C| < (1 - \delta/2)^2 n/4) \leq \exp(-2c_{\delta}n) $$

for some $c_{\delta} > 0$. Therefore, by Lemma 3.3 and [10, Theorem 1]:

$$ \begin{aligned} \mathbf{P}(\text{LDS}(\mathcal{P} \cap C) < (1 - \delta)\sqrt{n}) & \leq \exp(-2c_{\delta}n) + \mathbf{P}(L_{(1-\delta/2)^2n/4} < 2(1 - \delta)\sqrt{n/4}) \\ & \leq \exp(-c_{\delta}n) \end{aligned} $$

and likewise for $C^*$. Finally:

$$ \begin{aligned} \mathbf{P}(\text{LDS}(\tau_n) < 2(1 - \delta)\sqrt{n}) & \leq \mathbf{P}(\text{LDS}(\mathcal{P} \cap C) < (1 - \delta)\sqrt{n}) \\ & \quad + \mathbf{P}(\text{LDS}(\mathcal{P} \cap C^*) < (1 - \delta)\sqrt{n}) \leq \exp(-c_{\delta}n) \end{aligned} $$

for some $c_{\delta} > 0$, as desired.
Convergence in probability readily follows from these inequalities. To obtain $L^q$ convergence for all $q \ge 1$ we simply need to prove boundedness in $n$ of $\mathbb{E}[(\text{LDS}(\tau_n)/\sqrt{n})^{q'}]$ for any $q' \ge 1$. This follows from

$$ \mathbb{E}[(\text{LDS}(\tau_n)/\sqrt{n})^{q'}] \le (2+\delta)^{q'} + (n/\sqrt{n})^{q'} \exp(-c_\delta\sqrt{n}) = \mathcal{O}_{n\to\infty}(1) $$

where $\delta > 0$ is arbitrary. This concludes the proof of Theorem 2.1. □

**Proof of Corollary 2.2** We work conditionally given $t^{(n)}$. Then for each $n$, $\tau_n$ is a uniform $t^{(n)}$-cyclic permutation. Let $\mathcal{P}$ be a geometric construction of $\tau_n$ and $\tilde{\mathcal{P}}$ be its points outside the diagonal. Define $\tilde{t}^{(n)}$ as the cycle type $(0, t_2^{(n)}, t_3^{(n)}, \dots)$ of size $\tilde{n} := n - t_1^{(n)}$. Then according to Lemma 1.3, $\tilde{\tau}_n := \text{Perm}(\tilde{\mathcal{P}})$ is a uniform $\tilde{t}^{(n)}$-cyclic permutation. Since fixed points contribute at most 1 to $\text{LDS}(\tau_n)$, we can write:

$$ \text{LDS}(\tilde{\tau}_n) \le \text{LDS}(\tau_n) \le 1 + \text{LDS}(\tilde{\tau}_n). $$

Thus by Theorem 2.1, for any $\delta > 0$ there exists a universal constant $c_\delta > 0$ such that for any $n$:

$$ \begin{aligned} \mathbf{P}(\text{LDS}(\tau_n) > 2(1+\delta)\sqrt{\tilde{n}}) &\le \mathbb{E}[\mathbf{P}(\text{LDS}(\tilde{\tau}_n) > 2(1+\delta)\sqrt{\tilde{n}} \mid t^{(n)})] \\ &\le \mathbb{E}[\exp(-c_\delta\sqrt{\tilde{n}})], \end{aligned} $$

and likewise for the lower tail bound. If $\tilde{n} \to \infty$ in probability then the right-hand side goes to 0 as $n \to \infty$, and this proves convergence in probability. Convergence in $L^q$ follows as in the proof of Theorem 2.1, bounding $\text{LDS}(\tau_n)$ above by $n - t_1^{(n)} + 1$ and using the fact that the previous tail inequalities hold a.s. conditionally given $t^{(n)}$. □

## 4.2 Increasing subsequences

The study of increasing subsequences is subtler than that of decreasing ones in our geometric construction. Indeed, while down-right paths tend to stay away from the diagonal of $[0, 1]^2$, allowing us to use Lemma 3.3, up-right paths tend to stay very close to it. Consequently, we settle for mere bounds here.

**Proof of Proposition 2.3** Fix $\delta > 0$. Let $\mathcal{P}$ be a geometric construction of $\tau_n$ as in Lemma 1.3.

**Lower tail bound:** Set $K = \lceil 2/\delta \rceil$ and let $(C_{i,j})_{1 \le i,j \le K}$ be a regular square grid defined by

$$ C_{i,j} = [(i-1)/K, i/K] \times [(j-1)/K, j/K]. $$

<figure><img src="image_12.png" /></figure>
Then:

$$ \mathrm{LIS}(\tau_n) = \mathrm{LIS}(\mathcal{P}) \geq \sum_{i=1}^{K-1} \mathrm{LIS}(\mathcal{P} \cap C_{i,i+1}). \quad (12) $$

Using Corollary 3.2, there exists $c_\delta > 0$ such that:

$$ \mathbf{P} \left( |\mathcal{P} \cap C_{i,i+1}| < (1 - \delta/2)^2 n / K^2 \right) \leq \exp(-2c_\delta n). $$

Then by [10, Theorem 1] along with Lemma 3.3, denoting by $L_m$ the LIS of a uniform permutation of size $m$:

$$ \mathbf{P} \left( \mathrm{LIS}(\mathcal{P} \cap C_{i,i+1}) < (1 - \delta) \frac{2\sqrt{n}}{K-1} \right) \leq \mathbf{P} \left( L_{(1-\delta/2)^2 n / K^2} < (1 - \delta) \frac{2\sqrt{n}}{K-1} \right) \\ + \exp(-2c_\delta n) \leq \exp(-c_\delta n) $$

since $\frac{1-\delta/2}{K} > \frac{1-\delta}{K-1}$. Finally, using Equation (12):

$$ \mathbf{P} \left( \mathrm{LIS}(\tau_n) < (1 - \delta) 2\sqrt{n} \right) \leq (K-1) \max_{1 \leq i \leq K-1} \mathbf{P} \left( \mathrm{LIS}(\mathcal{P} \cap C_{i,i+1}) < (1 - \delta) \frac{2\sqrt{n}}{K-1} \right) \\ \leq \exp(-c_\delta n) $$

for some $c_\delta > 0$.

**Upper tail bound:** For this, simply use Lemma 3.1 and a rough union bound. Since

$$ \mathrm{LIS}(\tau_n) = \mathrm{LIS}(\mathcal{P}) \leq \mathrm{LIS}(\mathcal{P}^{(1)}) + \mathrm{LIS}(\mathcal{P}^{(2)}) + \mathrm{LIS}(\mathcal{P}^{(3)}), $$

we can use [35, Theorem 2] to deduce

$$ \mathbf{P} \left( \mathrm{LIS}(\tau_n) > (1 + \delta) 2\sqrt{3n} \right) \leq 3\mathbf{P} \left( L_{\lceil n/3 \rceil + 1} > (1 + \delta) 2\sqrt{n/3} \right) \leq \exp(-c_\delta \sqrt{n}). $$

for some $c_\delta > 0$. This concludes the proof. □

**Proof of Corollary 2.4** The method is the same as in the proof of Corollary 2.2, using rather the bounds

$$ \max \left( t_1^{(n)}, \mathrm{LIS}(\check{\tau}_n) \right) \leq \mathrm{LIS}(\tau_n) \leq t_1^{(n)} + \mathrm{LIS}(\check{\tau}_n) $$

and discussing whether $t_1^{(n)} \geq (1 - \delta) 2\sqrt{n}$ for the upper tail bound. □
## 5 Proofs of the results on Robinson-Schensted shapes

In [36], Sjöstrand studied the limit RS shape of so-called locally uniform permutations. The latter are random permutations of the form $\sigma_n = \text{Perm}(\mathcal{P}_n)$ where $\mathcal{P}_n = \{Z_1, \dots, Z_n\}$ are i.i.d. random points distributed under some absolutely continuous distribution $\rho$. In particular, he proved [36, Theorem 10.2] that the limit

$$ \lim_{n \to \infty} \frac{1}{n} \text{LDS}_{r\sqrt{n}}(\sigma_n) $$

exists for any $r \ge 0$. It is denoted by $F_{\max}(r)$, where the dependence in $\rho$ is implicitly understood, and is characterized by some variational problem:

$$ F_{\max}(r) = \sup_{u \in \mathcal{U}_{0,r}((0,1)^2)} F_{\rho}(u). $$

Precise definitions are postponed to Section 5.1. The approach in [36] relies on a shift in point of view: instead of looking for large $r\sqrt{n}$-decreasing subsequences in $\sigma_n$, one looks for suitable functions $w_n \in \mathcal{U}_{r\sqrt{n}}((0,1)^2)$ that “fit” the point set $\mathcal{P}_n$. The quantity $F_{\rho}(u)$ is constructed so that it can be thought of as a “score” associated with $u$, that is, a measurement of how well the function $u$ should fit the decreasing subsequences of $\mathcal{P}_n$ after rescaling. [36, Proposition 4.5] shows that the function $F_{\rho}$ can be used to locally approximate $\text{LDS}_{r\sqrt{n}}(\sigma_n)$; it is also reformulated in handier terms into [36, Lemma 8.2] which yields a global upper bound, and [36, Lemma 6.3] which yields a local lower bound.

The difference between our setting and Sjöstrand’s is that the points of our geometric construction $\mathcal{P}$ are not globally independent. Nonetheless, they are locally i.i.d. thanks to Lemma 3.3, allowing us to use the same techniques as in [36]. Moreover, the local sampling density is constant in our case ($\rho := 1$), thus greatly simplifying several steps of the proof.

This section is organized as follows. First, in Section 5.1, we recall the definitions and results from [36] that will be relevant in our setting. Then, in Section 5.2, we illustrate them with the case of i.i.d. points sampled uniformly inside an arbitrary domain. Our contribution comes in Section 5.3, where we use these results to establish Theorem 2.7, and finally Corollary 2.8.

### 5.1 Preliminaries

Let $\Omega$ be an open subset of $\mathbb{R}^2$. If $u: \Omega \to \mathbb{R}$ is Lebesgue-measurable, write $\|u\|_{1,\Omega} := \int_{\Omega} |u| d\text{Leb}$ for its $L^1$ norm. Recall that we use the partial order on $\mathbb{R}^2$ defined by:

$$ (x, y) \le (x', y') \quad \text{if and only if} \quad x \le x' \text{ and } y \le y'. $$

Then, we call $u$ doubly increasing if $u(x, y) \le u(x', y')$ whenever $(x, y) \le (x', y')$. Denote by $\mathcal{U}(\Omega)$ the set of doubly increasing functions on $\Omega$, and by $\mathcal{U}_{h,r}(\Omega)$ its subset consisting of functions with values in $[h, h+r]$. For any $u \in \mathcal{U}(\Omega)$, define
<figure><img src="image_13.png" /><figcaption>**Fig. 4** Left: a doubly increasing function $u \in \mathcal{U}_{0,r}((0, 1)^2)$ for some $3 \le r < 4$, with its integer level lines. Darker colors indicate greater values of $u$. The set $D(u)$ is highlighted in red. Right: in red, a 3-decreasing point set $P$. The function $\kappa_P$ indeed satisfies $D(\kappa_P) = P$. Its values range from 0 to 3, with lighter colors indicating lower values and darker colors indicating higher values</figcaption></figure>

$$D(u) := \{ (x, y) \in \Omega : u(x, y) \in \mathbb{Z} \text{ and } u(x', y') < u(x, y) \text{ for any } (x', y') \in \Omega \setminus \{(x, y)\} \text{ s.t. } (x', y') \le (x, y) \}.$$

In words, $D(u)$ is the set of “south-west corners” in the integer level lines of $u$. Also, if $P$ is a finite subset of $\Omega$, define $\kappa_P : (x, y) \in \Omega \mapsto \text{LIS}(P \cap ((-\infty, x] \times (-\infty, y]))$. See Figure 4 for an illustration.

It is easy to check that if $u \in \mathcal{U}_{0,r}(\Omega)$ then $D(u)$ is an $|r|$-decreasing subset of $\Omega$, see [36, Lemma 6.2]. Reciprocally, one can also check that if $P$ is a $k$-decreasing subset of $\Omega$ then $\kappa_P$ is in $\mathcal{U}_{0,k}(\Omega)$ and satisfies $D(\kappa_P) = P$, see again [36, Lemma 6.2]. Now, if $P$ is a finite point set in $\Omega$, recall that $\text{LDS}_k(P)$ can be expressed as the maximum of $|P \cap P|$ where $P$ ranges over $k$-decreasing subsets of $\Omega$. Subsequently, by [36, Lemma 6.2]:

$$\text{LDS}_k(P) = \max_{u \in \mathcal{U}_{0,k}(\Omega)} |D(u) \cap P|.$$

We shall use this equation after rescaling, that is:

$$\text{LDS}_{r\sqrt{n}}(P) = \max_{w \in \mathcal{U}_{0,r}(\Omega)} |D(w\sqrt{n}) \cap P|. \quad (13)$$

The main tool that we will use from [36] is a function $F_{\Omega}: \mathcal{U}(\Omega) \to \mathbb{R}_+$ that serves as a “score” associated with $u$: the quantity $F_{\Omega}(u)$ is a limit approximation of $\frac{1}{n}|D(w\sqrt{n}) \cap \sigma_n|$, where $\sigma_n$ is a homogeneous Poisson point process with intensity $n$ on $\Omega$ and $w$ is close to $u$. The definition of $F_{\Omega}$ hinges on the following lemma:

**Lemma 5.1** (Theorem 3.2 in [36]) For $\beta > 0$, define

$$\Omega_{\beta} := \{ (x, y) \in \mathbb{R}^2 : 0 < x + y < \sqrt{2} \text{ and } 0 < y - x < \beta\sqrt{2} \}.$$
For $\gamma > 0$, let $\sigma_\gamma$ be a homogeneous Poisson point process on $\mathbb{R}^2$ with intensity $\gamma$. Then for each $r \ge 0$, as $\beta$ and $\gamma$ tend to infinity, the random variable $\frac{1}{\beta\gamma}\text{LDS}_r\sqrt{\gamma}(\sigma_\gamma \cap \Omega_\beta)$ converges in $L^1$ to a constant $\phi(r)$.

Then, for $\theta \ge 0$, define $L(\theta) := \phi(\sqrt{2\theta})$. Finally, recall that each $u \in \mathcal{U}(\Omega)$ admits partial derivatives almost everywhere, and define $F_\Omega(u) := \|L(\partial_x u \partial_y u)\|_{1,\Omega}$. The following two lemmas justify the aforementioned idea that $F_\Omega(u)$ can be interpreted as a score associated with $u$:

**Lemma 5.2** (From Lemma 8.2 in [36]) Let $\Omega$ be an arbitrary open subset of $\mathbb{R}^2$, and let $\sigma_n$ be a homogeneous Poisson point process on $\Omega$ with intensity $n$. Then for any $u \in \mathcal{U}(\Omega)$ and any $\epsilon > 0$, there exists $\delta > 0$ such that, with high probability as $n \to \infty$:

$$ \sup_{w \in \mathcal{U}(\Omega), \|w-u\|_{1,\Omega} < \delta} \frac{1}{n} \left| D(w\sqrt{n}) \cap \sigma_n \right| < F_{\Omega}(u) + \epsilon. $$

**Lemma 5.3** (From Lemma 6.3 in [36]) For $a, b, \beta > 0$, define

$$ \Omega_{a,b,\beta} := \{ (x, y) \in \mathbb{R}^2 : |ax + by| < 1 \text{ and } |ax - by| < \beta \} $$

and for $c \ge 0$, define

$$ u_{a,b,c} : (x, y) \in \Omega_{a,b,\beta} \mapsto c(ax + by). $$

Let $\sigma_n$ be a homogeneous Poisson point process on $\Omega_{a,b,\beta}$ with intensity $n$. Then with high probability as $n \to \infty$, for any $d \in \mathbb{R}$, there exists $w^{(n)} \in \mathcal{U}_{d,2c}(\Omega_{a,b,\beta})$ such that:

$$ \frac{1}{n} \left| D \left( w^{(n)} \sqrt{n} \right) \cap \sigma_n \right| \geq F_{\Omega_{a,b,\beta}} (u_{a,b,c}) - \frac{6}{\beta} \mathrm{Leb} (\Omega_{a,b,\beta}), $$

or equivalently:

$$ \frac{1}{n \cdot \mathrm{Leb}(\Omega_{a,b,\beta})} \left| D \left( w^{(n)} \sqrt{n} \right) \cap \sigma_n \right| \geq L(ca \cdot cb) - \frac{6}{\beta}. $$

Contrary to Lemma 5.2, which yields a *global* upper bound, Lemma 5.3 yields a *local* lower bound. In order to get a *global* lower bound, the broad idea is to cover most of the global domain $\Omega$ by a family of adequate local parallelograms, apply Lemma 5.3 on each of them, and carefully “patch” the resulting family of local doubly increasing functions into a global one. Let us introduce some notions from [36] to that aim. Throughout, $\Omega$ denotes an arbitrary open subset of $\mathbb{R}^2$.

If $u \in \mathcal{U}(\Omega)$ and $\iota > 0$, we call $(u, \iota)$-parallelogram any parallelogram $P$ of the form

$$ P = \left\{ (x, y) \in \mathbb{R}^2 : \left| \tilde{u}_x^P(x - x_P) + \tilde{u}_y^P(y - y_P) \right| \le \iota c_P \text{ and } \left| \tilde{u}_x^P(x - x_P) - \tilde{u}_y^P(y - y_P) \right| \le c_P \right\} $$

<figure><img src="image_14.png" /></figure>
where $(x_P, y_P)$ is a differentiability point of $u, c_P > 0$, $\tilde{u}_x^P := \iota^3 \lor \partial_x u(x_P, y_P)$ and $\tilde{u}_y^P := \iota^3 \lor \partial_y u(x_P, y_P)$. We write $u_x^P$ and $u_y^P$ for the partial derivatives of $u$ at $(x_P, y_P)$, and say that $P$ is well-behaved if $u_x^P = \tilde{u}_x^P$ and $u_y^P = \tilde{u}_y^P$.

**Lemma 5.4** (Lemma 7.4 in [36]) Let $P$ be a $(u, \iota)$-parallelogram. Then for each $(x, y) \in P$:

$$|x - x_P| + |y - y_P| \le c_P(1 + \iota)\iota^{-3}.$$

**Lemma 5.5** (From Lemma 7.7 in [36]) Let $u \in \mathcal{U}(\Omega)$ and $\epsilon > 0$. For each $0 < \iota < 1/2$ there exists a measurable subset $S_\iota \subseteq \Omega$ on which $u$ is differentiable, and a finite collection $\mathfrak{P}_\iota$ of disjoint $(u, \iota)$-parallelograms, such that:

(a) $S_\iota \subseteq \bigcup_{P \in \mathfrak{P}_\iota} P$;

(b) $\partial_x u$ and $\partial_y u$ are bounded on $\bigcup_{0 < \iota < 1/2} S_\iota$;

(c) $\text{Leb}(\Omega \setminus S_\iota) < \epsilon + o_\iota(1)$;

and for each $P \in \mathfrak{P}_\iota$:

(a') $P \subseteq \Omega$ and $(x_P, y_P) \in S_\iota$;

(f) for all $(x, y) \in P$:

$$|u(x, y) - (u(x_P, y_P) + (x - x_P)u_x^P + (y - y_P)u_y^P)| \le \iota^5 (|x - x_P| + |y - y_P|);$$

$$(g) \left| \frac{1}{\text{Leb}(P)} F_P(u) - L(u_x^P u_y^P) \right| < \iota.$$

In words, the set $S_\iota$ covers most of the domain $\Omega$, and on each parallelogram, the function $u$ is almost linear and the function $L(\partial_x u \partial_y u)$ is almost constant. This will allow use to use Lemma 5.3 on each parallelogram. Then, patching the resulting local doubly increasing functions into a global one will mainly rely on item (f) above and on the following lemma:

**Lemma 5.6** (From Lemma 9.1 in [36]) Let $S$ be an open subset of $\Omega$, and let $u \in \mathcal{U}(S)$. Then, there exists $w \in \mathcal{U}(\Omega)$ such that $w|_S = u$ and $\overline{u(S)} = \overline{w(\Omega)}$.

Finally, let us state a lemma about parallelograms that we could not find explicitly stated in [36] but that we will need nonetheless:

**Lemma 5.7** Let $u \in \mathcal{U}(\Omega)$, $0 < \iota < 1/2$, and $P$ be a $(u, \iota)$-parallelogram. Let $P'$ denote the open parallelogram obtained by shrinking $P$ by a factor $1-2\iota$ in width and height, that is:

$$P' := \left\{ (x, y) \in \mathbb{R}^2 : \left| \frac{\tilde{u}_x^P}{(1-2\iota)\iota c_P} (x-x_P) + \frac{\tilde{u}_y^P}{(1-2\iota)\iota c_P} (y-y_P) \right| < 1 \right. \\ \left. \text{and} \quad \left| \frac{\tilde{u}_x^P}{(1-2\iota)\iota c_P} (x-x_P) - \frac{\tilde{u}_y^P}{(1-2\iota)\iota c_P} (y-y_P) \right| < \frac{1}{\iota} \right\}.$$
Let $(x_1, y_1) \le (x_2, y_2)$ such that $(x_1, y_1)$ is in $P'$ and $(x_2, y_2)$ is on the boundary of $P$. Then necessarily $(x_2, y_2)$ lies on the northeast boundary of $P$, that is:

$$ \tilde{u}_x^P(x_2 - x_P) + \tilde{u}_y^P(y_2 - y_P) = \iota c_P. $$

**Proof** Obviously, $(x_2, y_2)$ cannot lie on the southwest boundary of $P$. Assume that it lies on the northwest boundary of $P$, that is:

$$ \tilde{u}_x^P(x_2 - x_P) - \tilde{u}_y^P(y_2 - y_P) = -c_P. $$

Since $(x_1, y_1) \in P'$, we have that:

$$ \tilde{u}_x^P(x_1 - x_P) - \tilde{u}_y^P(y_1 - y_P) \ge -(1 - 2\iota)c_P, $$

whence:

$$ \tilde{u}_y^P(y_2 - y_P) = \tilde{u}_x^P(x_2 - x_P) + c_P \ge \tilde{u}_x^P(x_1 - x_P) + c_P \ge \tilde{u}_y^P(y_1 - y_P) + 2\iota c_P. $$

Therefore:

$$ \tilde{u}_x^P(x_2 - x_P) + \tilde{u}_y^P(y_2 - y_P) \ge \tilde{u}_x^P(x_1 - x_P) + \tilde{u}_y^P(y_1 - y_P) + 2\iota c_P \\ \ge -(1 - 2\iota)\iota c_P + 2\iota c_P = \iota c_P + 2\iota^2 c_P, $$

contradicting the definition of $P$. The computation works the same if we assume that $(x_2, y_2)$ lies on the southeast boundary of $P$, and this concludes the proof. □

## 5.2 The uniform case

Now, let us illustrate the results recalled in the previous section with the case study of i.i.d. uniform points inside an arbitrary domain. Note that this is a much simpler framework than the one considered in [36] (since here we have $\rho = 1$), and that Theorem 5.8 below is wholly contained in [36, Theorem 10.2]. Nonetheless, stating it and recalling its proof will be useful for our proof of Theorem 2.7.

**Theorem 5.8** (From Theorem 10.2 in [36]) Let $\Omega$ be an arbitrary open subset of $\mathbb{R}^2$, and let $\sigma_n$ be a homogeneous Poisson point process on $\Omega$ with intensity $n$. Then for each $r \ge 0$, the following convergence holds in probability as $n \to \infty$:

$$ \frac{1}{n}\text{LDS}_{r\sqrt{n}}(\sigma_n) \longrightarrow \sup_{u \in \mathcal{U}_{0,r}(\Omega)} F_{\Omega}(u). $$

**Proof** Fix $r \ge 0$. Thanks to Equation (13), our goal is to bound $|D(w\sqrt{n}) \cap \sigma_n|$ above and below, uniformly over $w \in \mathcal{U}_{0,r}(\Omega)$. Fix $\epsilon > 0$. As stated in the previous section, the upper bound uses Lemma 5.2 whereas the lower bound uses Lemma 5.3 and requires more work.

<figure><img src="image_15.png" /></figure>
**Upper bound:** For each $u \in \mathcal{U}_{0,r}(\Omega)$, use Lemma 5.2 to find $\delta_u > 0$ such that:

$$ \sup_{w \in \mathcal{U}_{0,r}(\Omega), \|w-u\|_{1,\Omega} < \delta_u} \frac{1}{n} |D(w\sqrt{n}) \cap \sigma_n| < F_{\Omega}(u) + \epsilon \quad (14) $$

holds w.h.p. as $n \to \infty$. Write $\mathcal{B}_u := \{w \in \mathcal{U}_{0,r}(\Omega) : \|w-u\|_{1,\Omega} < \delta_u\}$. Then let us use [36, Proposition 9.2], which states that $\mathcal{U}_{0,r}(\Omega)$ is compact for the $L^1$ metric. Since the open subsets $\mathcal{B}_u$ cover $\mathcal{U}_{0,r}(\Omega)$ when $u$ ranges over $\mathcal{U}_{0,r}(\Omega)$, there is a finite subcover

$$ \mathcal{U}_{0,r}(\Omega) \subseteq \mathcal{B}_{u_1} \cup \dots \cup \mathcal{B}_{u_k}. $$

By applying (14) to $u_1, \dots, u_k$, we get that

$$ \sup_{w \in \mathcal{U}_{0,r}(\Omega)} \frac{1}{n} |D(w\sqrt{n}) \cap \sigma_n| < \sup_{1 \le j \le k} F_{\Omega}(u_j) + \epsilon \quad (15) $$

holds w.h.p. as $n \to \infty$.

**Lower bound:** This bound is broadly contained in the proof of [36, Lemma 10.1]. Fix $u \in \mathcal{U}_{0,r}(\Omega)$. We wish to find $w_n \in \mathcal{U}_{0,r}(\Omega)$ such that $\frac{1}{n} |D(w_n\sqrt{n}) \cap \sigma_n| \ge F_{\Omega}(u) - \epsilon$ holds w.h.p. as $n \to \infty$.

For each $0 < \iota < 1/2$, let $S_\iota$ and $\mathfrak{P}_\iota$ be given by Lemma 5.5. Denote by $\tilde{\mathfrak{P}}_\iota$ the set of well-behaved parallelograms in $\mathfrak{P}_\iota$. For each $P \in \mathfrak{P}_\iota$, let $\bar{u}_P \in \mathcal{U}(P)$ be defined by

$$ \text{for all } (x, y) \in P, \quad \bar{u}_P(x, y) := u(x_P, y_P) + (x - x_P)u_x^P + (y - y_P)u_y^P $$

if $P \in \tilde{\mathfrak{P}}_\iota$, and by $\bar{u}_P := u|_P$ if $P \in \mathfrak{P}_\iota \setminus \tilde{\mathfrak{P}}_\iota$. For each $P \in \mathfrak{P}_\iota$, let $P'$ denote the open parallelogram obtained by shrinking $P$ by a factor $1-2\iota$ in width and height, as in Lemma 5.7. Now, For each $P \in \tilde{\mathfrak{P}}_\iota$, let us apply Lemma 5.3 to the linear function $\bar{u}_P$ on the domain $P'$, with corresponding values $a := \frac{u_x^P}{(1-2\iota)\mathfrak{I}_P}$, $b := \frac{u_y^P}{(1-2\iota)\mathfrak{I}_P}$, $c := (1-2\iota)\mathfrak{I}_P$, and $\beta := 1/\iota$. We get that, w.h.p. as $n \to \infty$, there exists $w_P^{(n)} \in \mathcal{U}_{u(x_P, y_P)-(1-2\iota)\mathfrak{I}_P, 2(1-2\iota)\mathfrak{I}_P}(P')$ such that

$$ \frac{1}{n \cdot \text{Leb}(P')} |D(w_P^{(n)} \sqrt{n}) \cap \sigma_n \cap P'| \ge L(u_x^P u_y^P) - o_\iota(1) \quad (16) $$

where $o_\iota(1) \to 0$ as $\iota \to 0$, uniformly in $P$ and $n$. By [36, Lemma 4.9] and item (b) of Lemma 5.5, the function $L$ is increasing and uniformly continuous on the bounded set

$$ \left\{ \partial_x u(x, y) \cdot \partial_y u(x, y) : (x, y) \in \bigcup_{0 < \iota < 1/2} S_\iota \right\} $$
and satisfies $L(0) = 0$. By definition, for any $P \in \mathbb{P}_t \setminus \tilde{\mathbb{P}}_t$ we have $\min(u_x^P, u_y^P) < t^3$, and thus $L(u_x^P u_y^P) \le L(Mt^3) = o_t(1)$ where $M > 0$ is the absolute bound given by item (b) of Lemma 5.5. Therefore, for each $P \in \mathbb{P}_t \setminus \tilde{\mathbb{P}}_t$ and any $w_P^{(n)} \in \mathcal{U}(P')$, Equation (16) trivially holds (with an adequate $o_t(1)$).

For fixed $t$, under the event that $w_P^{(n)}$ exists for all $P \in \tilde{\mathbb{P}}_t$, define a function $w_n$ on $\bigcup_{P \in \tilde{\mathbb{P}}_t} P' \cup (\Omega \setminus \bigcup_{P \in \tilde{\mathbb{P}}_t} \mathring{P})$ as follows: $w_n$ coincides with $w_P^{(n)}$ on $P'$ for each $P \in \tilde{\mathbb{P}}_t$, whereas is coincides with $u$ on $\Omega \setminus \bigcup_{P \in \tilde{\mathbb{P}}_t} \mathring{P}$ (we use the notation $\mathring{P}$ to denote the interior of $P$). Let us check that $w_n$ is doubly increasing on this domain. First consider $(x_1, y_1) \le (x_2, y_2)$ such that $(x_1, y_1) \in P'$ for some $P \in \tilde{\mathbb{P}}_t$ and $(x_2, y_2)$ is on the boundary of $P$. According to Lemma 5.7, we have:

$$ \bar{u}_P(x_2, y_2) - u(x_P, y_P) = (x_2 - x_P)u_x^P + (y_2 - y_P)u_y^P = \iota_{CP}. \quad (17) $$

Since $w_P^{(n)} \in \mathcal{U}_{u(x_P, y_P)-(1-2t)\iota_{CP}, 2(1-2t)\iota_{CP}}(P')$ and $(x_1, y_1) \in P'$, we have:

$$ |w_P^{(n)}(x_1, y_1) - u(x_P, y_P)| \le (1 - 2t)\iota_{CP}. \quad (18) $$

Also, using item (f) of Lemma 5.5 and Lemma 5.7:

$$ \begin{aligned} |w_P^{(n)}(x_2, y_2) - \bar{u}_P(x_2, y_2)| &= |u(x_2, y_2) - \bar{u}_P(x_2, y_2)| \\ &\le \iota^5 (|x - x_P| + |y - y_P|) \\ &\le c_P (1 + \iota) t^3 \le 2c_P t^2. \end{aligned} \quad (19) $$

Finally, putting Equation (17) to 19 together:

$$ \begin{aligned} w_P^{(n)}(x_2, y_2) - w_P^{(n)}(x_1, y_1) &\ge \bar{u}_P(x_2, y_2) - u(x_P, y_P) \\ &\quad - |w_P^{(n)}(x_1, y_1) - u(x_P, y_P)| \\ &\quad - |w_P^{(n)}(x_2, y_2) - \bar{u}_P(x_2, y_2)| \\ &\ge \iota_{CP} - (1 - 2t)\iota_{CP} - 2c_P t^2 = 0, \end{aligned} $$

that is, $w_n(x_2, y_2) \ge w_n(x_1, y_1)$. If $(x_1, y_1) \le (x_2, y_2)$ are such that $(x_2, y_2) \in P'$ for some $P \in \tilde{\mathbb{P}}_t$ and $(x_1, y_1)$ is on the boundary of $P$, it can be proven in the same way that $w_n(x_2, y_2) \ge w_n(x_1, y_1)$. Since $w_n$ is doubly increasing on each $P'$ for $P \in \tilde{\mathbb{P}}_t$ and also on $\Omega \setminus \bigcup_{P \in \tilde{\mathbb{P}}_t} \mathring{P}$, and since the parallelograms forming the family $\tilde{\mathbb{P}}_t$ are disjoint, this suffices to prove that $w_n$ is doubly increasing on its domain of definition.

Using Lemma 5.6, the function $w_n$ can be extended from $\bigcup_{P \in \tilde{\mathbb{P}}_t} P' \cup (\Omega \setminus \bigcup_{P \in \tilde{\mathbb{P}}_t} P)$ to $\Omega$, and we still write $w_n \in \mathcal{U}(\Omega)$ for this function. Since $u \in \mathcal{U}_{0,r}(\Omega)$, by construction we also have that $w_n \in \mathcal{U}_{0,r}(\Omega)$. Using (16), we can write w.h.p. as $n \to \infty$:
$$ \frac{1}{n} |D(w_n \sqrt{n}) \cap \sigma_n| \geq \sum_{P \in \mathfrak{P}_t} \frac{1}{n} |D(w_n \sqrt{n}) \cap \sigma_n \cap P'| \geq \sum_{P \in \mathfrak{P}_t} \mathrm{Leb}(P') (L(u_x^P u_y^P) - o_t(1)) \quad (20) $$

where $o_t(1)$ is independent of $P$ and $n$. By item (g) of Lemma 5.5:

$$ \sum_{P \in \mathfrak{P}_t} \mathrm{Leb}(P') L(u_x^P u_y^P) = (1-2t)^2 \sum_{P \in \mathfrak{P}_t} \mathrm{Leb}(P) L(u_x^P u_y^P) \geq (1-2t)^2 F_{\cup_{P \in \mathfrak{P}_t} P}(u) - o_t(1). \quad (21) $$

Let us also use [36, Lemma 4.9], which states that $0 \leq L(\partial_x u \partial_y u) \leq 1$. Along with items (a) and (c) of Lemma 5.5, we get:

$$ \mathrm{Leb} \left( \bigcup_{P \in \mathfrak{P}_t} P \right) \geq \mathrm{Leb}(\Omega) - \epsilon - o_t(1). $$

This implies $F_{\cup_{P \in \mathfrak{P}_t} P}(u) \geq F_{\Omega}(u) - \epsilon - o_t(1)$. Along with (20) and (21), for small enough $t$ this yields:

$$ \frac{1}{n} |D(w_n \sqrt{n}) \cap \sigma_n| \geq F_{\Omega}(u) - 2\epsilon $$

w.h.p. as $n \to \infty$. Since this holds for arbitrary $u \in \mathcal{U}_{0,r}(\Omega)$, we get that:

$$ \sup_{w \in \mathcal{U}_{0,r}(\Omega)} \frac{1}{n} |D(w \sqrt{n}) \cap \sigma_n| \geq \sup_{u \in \mathcal{U}_{0,r}(\Omega)} F_{\Omega}(u) - 3\epsilon \quad (22) $$

holds w.h.p. as $n \to \infty$.

Putting Equation (15) and 22 together, we deduce that:

$$ \sup_{w \in \mathcal{U}_{0,r}(\Omega)} \frac{1}{n} |D(w \sqrt{n}) \cap \sigma_n| \longrightarrow \sup_{u \in \mathcal{U}_{0,r}(\Omega)} F_{\Omega}(u) $$

in probability as $n \to \infty$. Thanks to (13), this concludes the proof. $\square$

Theorem 2.6 can in particular be applied to the domain $\Omega = (0, 1)^2$. Using Theorem 5.8, this yields the formula:

$$ F_{\mathrm{LSKV}}(r) = \sup_{u \in \mathcal{U}_{0,r}((0,1)^2)} F_{(0,1)^2}(u). \quad (23) $$
<figure><img src="image_16.png" /><figcaption>Fig. 5 The bands defined in the proof of Theorem 2.7. On each $A_i$ and each $B_i$, $\mathcal{P}$ is almost distributed like a homogeneous Poisson point process</figcaption></figure>

## 5.3 Application to our setting

We are now ready to prove Theorem 2.7. Thanks to Lemma 3.3, the proof is very close to that of Theorem 5.8; the main difference is that we need to work individually on a family of rectangular domains which do not intersect the diagonal of $(0, 1)^2$, and we combine them together with the same techniques as in the proof of Theorem 5.8.

**Proof of Theorem 2.7** Fix $r \ge 0$. Let $\mathcal{P}$ be a geometric construction of $\tau_n$. As in the proof of Theorem 5.8, we wish to bound $|D(w\sqrt{n}) \cap \mathcal{P}|$ above and below, uniformly over $w \in \mathcal{U}_{0,r}((0, 1)^2)$. Consider two essentially disjoint intervals $I, J$ of $[0, 1]$ and write $\triangle$ for the symmetric difference of sets. Thanks to Corollary 3.2 and Lemma 3.3, one can construct a homogeneous Poisson point process with intensity $n$ on $I \times J$, say $\sigma_n$, such that $|\sigma_n \triangle \mathcal{P}|/n \to 0$ as $n \to \infty$ almost surely.

Fix a large integer $K$, set $\epsilon := 1/K^2$, and define bands

$$A_i := \left( \frac{i-1}{K+1}, \frac{i}{K+1} \right) \times \left( \frac{i}{K+1}, 1 \right) \quad \text{and} \quad B_i := \left( \frac{i}{K+1}, \frac{i+1}{K+1} \right) \times \left( 0, \frac{i}{K+1} \right)$$

for $i \in [K]$, see Figure 5. These bands each fit in the setting of Lemma 3.3, and they satisfy $\text{Leb}(C) = \frac{1}{K+1}$ where $C := (0, 1)^2 \setminus (\cup_i \tilde{A}_i \cup \tilde{B}_i)$. Moreover, using Corollary 3.2 and Lemma 3.3 as above, one can construct a point process $\sigma_n$ on $(0, 1)^2$ such that:

1. for each $i \in [K]$, $\sigma_n \cap A_i$ and $\sigma_n \cap B_i$ are both distributed like homogeneous Poisson point processes with intensity $n$;

<figure><img src="image_17.png" /></figure>
2. $\sigma_n$ coincides with $\mathcal{P}$ on $C$;

3. $|\sigma_n \Delta \mathcal{P}|/n \to 0$ as $n \to \infty$, almost surely.

From here, the arguments for the lower and upper bounds differ.

**Upper bound:** For each $i \in [K]$, we can apply Lemma 5.2 to $\sigma_n$ on $A_i$. Hence for each $u \in \mathcal{U}(A_i)$, there exists $\delta_{u,A_i} > 0$ such that:

$$ \sup_{w \in \mathcal{U}(A_i), \|w-u\|_{1,A_i} < \delta_{u,A_i}} \frac{1}{n} |D(w\sqrt{n}) \cap \sigma_n \cap A_i| < F_{A_i}(u) + \epsilon $$

holds w.h.p. as $n \to \infty$. The same holds with $B_i$ instead of $A_i$. Moreover, a.s. for any $n$:

$$ \sup_{w \in \mathcal{U}(C)} \frac{1}{n} |D(w\sqrt{n}) \cap \sigma_n \cap C| < \frac{1}{n} |\sigma_n \cap C| = \frac{1}{n} |\mathcal{P} \cap C|. $$

Moreover:

$$ F_{(0,1)^2}(u) = F_C(u) + \sum_{i=1}^{K} (F_{A_i}(u) + F_{B_i}(u)) \geq \sum_{i=1}^{K} (F_{A_i}(u) + F_{B_i}(u)). $$

By summing the previous inequalities we deduce that for each $u \in \mathcal{U}((0, 1)^2)$, with $\delta_u := \min_{1 \leq i \leq K} \delta_{u,A_i} \wedge \delta_{u,B_i}$:

$$ \sup_{w \in \mathcal{U}((0,1)^2), \|w-u\|_{1,(0,1)^2} < \delta_u} \frac{1}{n} |D(w\sqrt{n}) \cap \sigma_n| < F_{(0,1)^2}(u) + 2K\epsilon + \frac{1}{n} |\mathcal{P} \cap C| $$

w.h.p. as $n \to \infty$. Therefore:

$$ \sup_{w \in \mathcal{U}((0,1)^2), \|w-u\|_{1,(0,1)^2} < \delta_u} \frac{1}{n} |D(w\sqrt{n}) \cap \mathcal{P}| < F_{(0,1)^2}(u) + 2K\epsilon + \frac{1}{n} |\mathcal{P} \cap C| + \frac{1}{n} |\sigma_n \Delta \mathcal{P}| $$

w.h.p. as $n \to \infty$. Recall that $\epsilon = 1/K^2$ and that $\frac{1}{n} |\sigma_n \Delta \mathcal{P}| \to 0$ a.s. as $n \to \infty$. Moreover, Corollary 3.2 implies that $\frac{1}{n} |\mathcal{P} \cap C| \to \text{Leb}(C) = 1/(K+1)$ a.s. as $n \to \infty$. Hence for each $u \in \mathcal{U}((0, 1)^2)$:

$$ \sup_{w \in \mathcal{U}((0,1)^2), \|w-u\|_{1,(0,1)^2} < \delta_u} \frac{1}{n} |D(w\sqrt{n}) \cap \mathcal{P}| < F_{(0,1)^2}(u) + 4/K $$

w.h.p. as $n \to \infty$. Using the fact that $\mathcal{U}_{0,r}((0, 1)^2)$ is compact for the $L^1$ metric, as in the proof of Theorem 5.8, we get:

$$ \sup_{w \in \mathcal{U}_{0,r}((0,1)^2)} \frac{1}{n} |D(w\sqrt{n}) \cap \mathcal{P}| < \sup_{u \in \mathcal{U}_{0,r}((0,1)^2)} F_{(0,1)^2}(u) + 4/K \quad (24) $$
w.h.p. as $n \to \infty$.

**Lower bound:** This bound is almost the same as the upper bound of Theorem 5.8, *mutatis mutandis*. Fix an arbitrary $u \in \mathcal{U}_{0,r}((0, 1)^2)$; we wish to exhibit a well-crafted $w_n \in \mathcal{U}_{0,r}((0, 1)^2)$ such that $\frac{1}{n} |D(w_n\sqrt{n}) \cap \mathcal{P}| \geq F_{(0,1)^2}(u) - \epsilon$ holds w.h.p. as $n \to \infty$.

First apply Lemma 5.5 to each domain $A_i \cup B_i$ for $i \in [K]$. For each $0 < \ell < 1/2$, let $S_\ell^i$ and $\mathfrak{P}_\ell^i$ be the resulting sets. Then define $S_\ell := \bigcup_{i \in [K]} S_\ell^i$ and $\mathfrak{P}_\ell := \bigcup_{i \in [K]} \mathfrak{P}_\ell^i$. Denote by $\tilde{\mathfrak{P}}_\ell$ the set of well-behaved parallelograms in $\mathfrak{P}_\ell$. For each $P \in \mathfrak{P}_\ell$, let $P'$ denote the open parallelogram obtained by shrinking $P$ by a factor $1-2\ell$ in width and height, as in Lemma 5.7.

Note that any parallelogram contained in $A_i \cup B_i$ is either wholly contained in $A_i$, or wholly contained in $B_i$. Since $\sigma_n$ is distributed like a homogeneous Poisson point process with intensity $n$ on each $A_i$ and each $B_i$, we can use Lemma 5.3: for each $P \in \tilde{\mathfrak{P}}_\ell$, w.h.p. as $n \to \infty$, there exists $w_P^{(n)} \in \mathcal{U}_{u(x_P, y_P)-(1-2\ell)tc_P, 2(1-2\ell)tc_P}(P')$ such that

$$ \frac{1}{n \cdot \text{Leb}(P')} \left| D \left( w_P^{(n)} \sqrt{n} \right) \cap \sigma_n \cap P' \right| \geq L(u_x^P u_y^P) - o_t(1) \quad (25) $$

where $o_t(1) \to 0$ as $\ell \to 0$, uniformly in $P$ and $n$. This also holds for any $P \in \mathfrak{P}_\ell \setminus \tilde{\mathfrak{P}}_\ell$ and any $w_P^{(n)} \in \mathcal{U}(P')$, for the same reason as in the proof of Theorem 5.8.

Under the event that $w_P^{(n)}$ exists for all $P \in \tilde{\mathfrak{P}}_\ell$, define a function $w_n$ on $\bigcup_{P \in \tilde{\mathfrak{P}}_\ell} P' \cup ((0, 1)^2 \setminus \bigcup_{P \in \tilde{\mathfrak{P}}_\ell} \mathring{P})$ as follows: $w_n$ coincides with $w_P^{(n)}$ on $P'$ for each $P \in \tilde{\mathfrak{P}}_\ell$, whereas is coincides with $u$ on $(0, 1)^2 \setminus \bigcup_{P \in \tilde{\mathfrak{P}}_\ell} \mathring{P}$. As in the proof of Theorem 5.8, one can check that $w_n$ is doubly increasing. Then by Lemma 5.6, this function can be extended to $w_n \in \mathcal{U}_{0,r}((0, 1)^2)$. Therefore, using (25), we can write w.h.p. as $n \to \infty$:

$$ \frac{1}{n} |D(w_n \sqrt{n}) \cap \sigma_n| \geq \sum_{P \in \mathfrak{P}_\ell} \frac{1}{n} |D(w_n \sqrt{n}) \cap \sigma_n \cap P'| \geq \sum_{P \in \mathfrak{P}_\ell} \text{Leb}(P') (L(u_x^P u_y^P) - o_t(1)) \quad (26) $$

where $o_t(1)$ is independent of $P$ and $n$. By item (g) of Lemma 5.5:

$$ \sum_{P \in \mathfrak{P}_\ell} \text{Leb}(P') L(u_x^P u_y^P) = (1-2\ell)^2 \sum_{P \in \mathfrak{P}_\ell} \text{Leb}(P) L(u_x^P u_y^P) \geq (1-2\ell)^2 F_{\bigcup_{P \in \mathfrak{P}_\ell} P}(u) - o_t(1). \quad (27) $$

Let us also use [36, Lemma 4.9], which states that $0 \leq L(\partial_x u \partial_y u) \leq 1$. Along with items (a) and (c) of Lemma 5.5, we get:

$$ \text{Leb} \left( \bigcup_{\mathfrak{P}_\ell} P \right) \geq \text{Leb} \left( \bigcup_{i \in [K]} A_i \cup B_i \right) - K\epsilon - o_t(1) = 1 - 2/K - o_t(1). $$

<figure><img src="image_18.png" /></figure>
This implies $F_{\cup_{\mathfrak{P}_t} P}(u) \geq F_{(0,1)^2}(u) - 2/K - o_t(1)$. Along with (26) and (27), this yields:

$$ \frac{1}{n} |D(w_n\sqrt{n}) \cap \sigma_n| \geq F_{(0,1)^2}(u) - 2/K - o_t(1) $$

w.h.p. as $n \to \infty$, where $o_t(1)$ is uniform in $n$. Take $t$ such that this $o_t(1)$ is less than $1/K$. Using the facts that this holds for any $u \in \mathcal{U}_{0,r}((0,1)^2)$ and that $|\sigma_n \Delta \mathcal{P}|/n \to 0$, we deduce that:

$$ \sup_{w \in \mathcal{U}_{0,r}((0,1)^2)} \frac{1}{n} |D(w\sqrt{n}) \cap \mathcal{P}| \geq \sup_{u \in \mathcal{U}_{0,r}((0,1)^2)} F_{(0,1)^2}(u) - 5/K \quad (28) $$

w.h.p. as $n \to \infty$.

Putting Equation (24) and 28 together, along with (23), we get that:

$$ \sup_{w \in \mathcal{U}_{0,r}((0,1)^2)} \frac{1}{n} |D(w\sqrt{n}) \cap \mathcal{P}| \to \sup_{u \in \mathcal{U}_{0,r}((0,1)^2)} F_{(0,1)^2}(u) = F_{\text{LSKV}}(r) $$

in probability as $n \to \infty$. Thanks to (13), this concludes the proof. □

**Remark 6** With the same arguments as in the proof of [36, Lemma 10.1], we could refine our proof of Theorem 2.7 to show that the longest decreasing subsequences of $\mathcal{P}$ are located on the same limit curves as in the uniform case (see [36, Theorem 10.2 (a)] for a precise statement).

**Proof of Corollary 2.8** Let $\mathcal{P}$ be a geometric construction of $\tau_n$. Since each decreasing subsequence of $\tau_n$ contains at most one fixed point, we can write:

$$ \text{LDS}_k(\check{\tau}_n) \leq \text{LDS}_k(\tau_n) \leq \text{LDS}_k(\check{\tau}_n) + k $$

for any $k \geq 0$. Hence:

$$ \mathbf{P}\left(\left|\frac{1}{\check{n}}\text{LDS}_{r\sqrt{\check{n}}}(\tau_n) - F_{\text{LSKV}}(r)\right| > \epsilon\right) \leq \mathbf{P}\left(\left|\frac{1}{\check{n}}\text{LDS}_{r\sqrt{\check{n}}}(\check{\tau}_n) - F_{\text{LSKV}}(r)\right| > \epsilon_n\right) $$

where $\epsilon_n := \epsilon - \frac{r\sqrt{\check{n}}}{\check{n}} \underset{n \to \infty}{\longrightarrow} \epsilon$ in probability. Then by Theorem 2.7 and dominated convergence theorem:

$$ \mathbf{P}\left(\left|\frac{1}{\check{n}}\text{LDS}_{r\sqrt{\check{n}}}(\check{\tau}_n) - F_{\text{LSKV}}(r)\right| > \epsilon_n\right) = \mathbb{E}\left[\mathbf{P}\left(\left|\frac{1}{\check{n}}\text{LDS}_{r\sqrt{\check{n}}}(\check{\tau}_n) - F_{\text{LSKV}}(r)\right| > \epsilon_n \mid t^{(n)}\right)\right] \underset{n \to \infty}{\longrightarrow} 0, $$

which concludes the proof. □
# 6 Proofs of the results on records

## 6.1 High records

**Lemma 6.1** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ such that $t_1^{(n)} = 0$, and $\mathcal{P}$ be a geometric construction. Set $C := [0, 1/2] \times [1/2, 1]$. Define $Z_{\text{left}} = (U_{\text{left}}, V_{\text{left}})$ as the leftmost point in $\mathcal{P}$, $Z_{\text{left}}^C = (U_{\text{left}}^C, V_{\text{left}}^C)$ as the leftmost point of $\mathcal{P} \cap C$, and let $Z_{\text{up}}$, $Z_{\text{up}}^C$ be the upmost analogues. Those points are well-defined w.h.p. as $n \to \infty$ and:

$$ (nU_{\text{left}}, n(1-V_{\text{up}})) \underset{n \to \infty}{\longrightarrow} (E, E') ; \quad nU_{\text{left}}^C \underset{n \to \infty}{\longrightarrow} 2E ; \quad n(1-V_{\text{up}}^C) \underset{n \to \infty}{\longrightarrow} 2E $$

in distribution, where $E, E'$ are independent Exp (1) variables. Furthermore, w.h.p. as $n \to \infty$ the inequalities $U_{\text{left}} \le U_{\text{left}}^C \le V_{\text{left}}$ hold.

**Proof** Recall from the geometric construction that the lists of x- and y-coordinates of points in $\mathcal{P}$ are both equal to the same family $\{U_i\}_{i \in V_t}$ of i.i.d. Unif ([0, 1]) variables. Thus $U_{\text{left}} =: U_{(1)}$ is their minimum and $V_{\text{up}} =: U_{(n)}$ is their maximum. For any $s, t \ge 0$ we have:

$$ \mathbf{P} (nU_{(1)} \ge s, n(1-U_{(n)}) \ge t) = \mathbf{P} (\forall i, U_i \in [s/n, 1-t/n]) \\ = (1-(s+t)/n)^n \underset{n \to \infty}{\longrightarrow} e^{-s}e^{-t}. $$

This proves the first convergence in distribution. For the second one, use Lemma 3.3 and write, conditionally given $|\mathcal{P} \cap C|$:

$$ \mathbf{P} (nU_{\text{left}}^{C} \ge s) = \left(1 - \frac{s/(2n)}{1/4}\right)^{|\mathcal{P} \cap C|} = (1 - 2s/n)^{|\mathcal{P} \cap C|}. $$

According to Corollary 3.2, $|\mathcal{P} \cap C|$ is concentrated around $n/4$. This readily implies $\mathbf{P}(nU_{\text{left}}^{C} \ge s) \to e^{-s/2}$ as $n \to \infty$, and proves the second convergence in distribution. The third one follows similarly.

For the last claim, it suffices to note that $U_{\text{left}}$ and $U_{\text{left}}^C$ are both $o_P(1)$ whereas $V_{\text{left}}$ has distribution Unif ([0, 1]), and $U_{\text{left}} \le U_{\text{left}}^C$ by definition. $\square$

**Proof of Theorem 2.10** Let $\mathcal{P}$ be a geometric construction of $\tau_n$. Decompose it into its points outside the diagonal $\tilde{\mathcal{P}}$ and its points on the diagonal $\mathcal{P}_{\Delta}$. We shall use the notation of Lemma 6.1, applied to the set $\tilde{\mathcal{P}}$ of size $\tilde{n} := n - t_1^{(n)}$. According to this lemma, w.h.p. the point $Z_{\text{left}}$ is above the diagonal $\Delta$ and the rectangle $[U_{\text{left}}, U_{\text{left}}^C] \times [V_{\text{left}}, V_{\text{left}}^C]$ does not intersect $\Delta$. Likewise, w.h.p. the point $Z_{\text{up}}$ is above the diagonal and the rectangle $[U_{\text{up}}^C, U_{\text{up}}] \times [V_{\text{up}}^C, V_{\text{up}}]$ does not intersect $\Delta$. Under those events, the records of $\mathcal{P}$ are all contained in

<figure><img src="image_19.png" /></figure>
<figure><img src="image_20.png" /><figcaption>Fig. 6 The zones in which we can find records (high ones on the left and low ones on the right)</figcaption></figure>

$$ (\Delta \cap [0, U_{\text{left}}]^2) \cup [U_{\text{left}}, U_{\text{left}}^C] \times [V_{\text{left}}, V_{\text{left}}^C] \cup \\ C \cup [U_{\text{up}}, U_{\text{up}}] \times [V_{\text{up}}, V_{\text{up}}] \cup (\Delta \cap [V_{\text{up}}, 1]^2). $$

This zone is shown on the left-hand side of Figure 6. Note that the rectangles $[U_{\text{left}}, U_{\text{left}}^C] \times [V_{\text{left}}, V_{\text{left}}^C]$ and $[U_{\text{up}}, U_{\text{up}}] \times [V_{\text{up}}, V_{\text{up}}]$ may be flat, i.e. the identities $U_{\text{left}} = U_{\text{left}}^C$ and $V_{\text{up}} = V_{\text{up}}$ may occur with non-negligible probability.

Invertly, all points of $\mathcal{P}_{\Delta}$ in $[0, U_{\text{left}}]^2 \cup [V_{\text{up}}, 1]^2$, as well as the ones which are high records in $\mathcal{P} \cap C$, are high records in $\mathcal{P}$. From the previous two observations we deduce the following inequality w.h.p. as $n \to \infty$:

$$ |\text{rec}^{\uparrow}(\mathcal{P}) - (\text{rec}^{\uparrow}(\check{\mathcal{P}} \cap C) + S_n)| \leq |\check{\mathcal{P}} \cap ([U_{\text{left}}, U_{\text{left}}^C] \times [V_{\text{left}}, V_{\text{left}}^C])| \\ + |\check{\mathcal{P}} \cap ([U_{\text{up}}, U_{\text{up}}] \times [V_{\text{up}}, V_{\text{up}}])| $$

where $S_n := |\mathcal{P}_{\Delta} \cap [0, U_{\text{left}}]^2| + |\mathcal{P}_{\Delta} \cap [V_{\text{up}}, 1]^2|$. For any $M > 0$, we may apply Corollary 3.2 to the rectangle $[0, M/\tilde{n}] \times [0, 1]$ to obtain $|\check{\mathcal{P}} \cap ([0, M/\tilde{n}] \times [0, 1])| \le 2M$ w.h.p. as $n \to \infty$. Since $\tilde{n}U_{\text{left}}^C$ is tight by Lemma 6.1, it holds that $U_{\text{left}}^C \le M/\tilde{n}$ with probability tending to 1 as $M \to \infty$, uniformly in $n$. This implies that the random variable $|\check{\mathcal{P}} \cap ([U_{\text{left}}, U_{\text{left}}^C] \times [V_{\text{left}}, V_{\text{left}}^C])|$ is a $\mathcal{O}_{\mathbf{P}}(1)$. With the same reasoning applied to $1 - V_{\text{up}}^C$ and the corresponding rectangle, we deduce:

$$ |\text{rec}^{\uparrow}(\mathcal{P}) - (\text{rec}^{\uparrow}(\check{\mathcal{P}} \cap C) + S_n)| = \mathcal{O}_{\mathbf{P}}(1). \qquad (29) $$

Now it remains to analyze both terms in the sum. According to Lemma 3.3 and Corollary 3.2, $\check{\mathcal{P}} \cap C$ is a family of i.i.d. uniform points in $C$, with size $\tilde{n}/4 + o_{\mathbf{P}}(\tilde{n})$. We can thus apply Theorem 2.9 to deduce
$$ \frac{\mathrm{rec}^{\uparrow}(\check{\mathcal{P}} \cap C) - \log \check{n}}{\sqrt{\log \check{n}}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, 1) \quad (30) $$

in distribution. Let us turn to the fixed points. $\check{\mathcal{P}}$ and $\mathcal{P}_\Delta$ are independent, so $(U_{\mathrm{left}}, V_{\mathrm{up}})$ and $\mathcal{P}_\Delta$ are as well. Therefore, conditionally given $(U_{\mathrm{left}}, V_{\mathrm{up}})$, $S_n$ follows a Binom $(t_1^{(n)}, U_{\mathrm{left}}+1-V_{\mathrm{up}})$ law. Recall from Lemma 6.1 that

$$ \check{n} (U_{\mathrm{left}} + 1 - V_{\mathrm{up}}) \underset{n \to \infty}{\longrightarrow} \mathrm{Gamma}(2, 1) := \mathrm{Exp}(1) * \mathrm{Exp}(1) $$

in distribution, where $\mathrm{Exp}(1) * \mathrm{Exp}(1)$ denotes the law of the sum of two independent $\mathrm{Exp}(1)$ random variables. If $t_1^{(n)}/\check{n} = \mathcal{O}(1)$ as $n \to \infty$ then $S_n = \mathcal{O}_P(1)$ (use e.g. the Bienaymé—Chebyshev inequality), whereas if $t_1^{(n)}/\check{n} \to \infty$ as $n \to \infty$ then

$$ \frac{\check{n}}{t_1^{(n)}} S_n \underset{n \to \infty}{\longrightarrow} \mathrm{Gamma}(2, 1) \quad (31) $$

in distribution. Now we can use Equation (29) to 31 to identify three regimes in the asymptotics of $\mathrm{rec}^{\uparrow}(\mathcal{P})$.

**“Mostly uniform” regime:** Assume $\frac{\check{n}}{n/\sqrt{\log n}} \to \infty$. Then $\log n \sim \log \check{n}$ as $n \to \infty$, and since $t_1^{(n)} \le n$, we have $\frac{t_1^{(n)}}{\check{n}\sqrt{\log \check{n}}} \to 0$. Consequently the fluctuations of $\mathrm{rec}^{\uparrow}(\check{\mathcal{P}} \cap C)$ dominate, and

$$ \frac{\mathrm{rec}^{\uparrow}(\mathcal{P}) - \log \check{n}}{\sqrt{\log \check{n}}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, 1). $$

**“Mostly fixed points” regime:** Assume $\frac{\check{n}}{n/\sqrt{\log n}} \to 0$ as $n \to \infty$. Since $\log \check{n} \le \log n$ and $t_1^{(n)} = n - \check{n}$, we have $\frac{t_1^{(n)}}{\check{n}\sqrt{\log \check{n}}} \to \infty$. Consequently the fluctuations of $S_n$ dominate, and

$$ \frac{\check{n}}{t_1^{(n)}} (\mathrm{rec}^{\uparrow}(\mathcal{P}) - \log \check{n}) \underset{n \to \infty}{\longrightarrow} \mathrm{Gamma}(2, 1). $$

**“Intermediate” regime:** Assume $\frac{\check{n}}{n/\sqrt{\log n}} \to \alpha \in (0, \infty)$. Then $\log \check{n} \sim \log n$ as $n \to \infty$, and since $t_1^{(n)} = n - \check{n}$, we deduce $\frac{t_1^{(n)}}{\check{n}\sqrt{\log \check{n}}} \to 1/\alpha$. Thus we need to understand the interplay between the limit laws of Equation (30) and 31. To do this, notice that conditionally given $(U_{\mathrm{left}}, V_{\mathrm{up}})$, the variables $S_n$ and $\check{\mathcal{P}} \cap C$ are independent. Recall that under this conditioning, $S_n$ follows a Binom $(t_1^{(n)}, U_{\mathrm{left}}+1-V_{\mathrm{up}})$ law. According to Lemma 3.4, the conditional law of $\mathrm{Perm}(\check{\mathcal{P}} \cap C)$ given $(U_{\mathrm{left}}, V_{\mathrm{up}}) = (U_{(1)}, U_{(n)})$

<figure><img src="image_21.png" /></figure>
and $|\check{\mathcal{P}} \cap C|$ is uniform. From this property we deduce independence of the limit laws in Equation (31) and 30, whence:

$$ \frac{\mathrm{rec}^{\uparrow}(\mathcal{P}) - \log \check{n}}{\frac{t_1^{(n)}}{\check{n}} + \sqrt{\log \check{n}}} = \frac{\mathrm{rec}^{\uparrow}(\check{\mathcal{P}} \cap C) - \log \check{n}}{(1 + 1/\alpha + o(1))\sqrt{\log \check{n}}} + \frac{S_n}{(1 + \alpha + o(1))\frac{t_1^{(n)}}{\check{n}}} + o_{\mathbf{P}}(1) \\ \underset{n \to \infty}{\longrightarrow} \frac{\alpha}{\alpha + 1} \mathcal{N}(0, 1) * \frac{1}{1 + \alpha} \mathrm{Gamma}(2, 1) $$

in distribution, as announced.

□

## 6.2 Low records

**Lemma 6.2** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ such that $t_1^{(n)} = 0$, and $\mathcal{P}$ be a geometric construction. Fix $\epsilon > 0$ and define $B_n := [0, \epsilon/\sqrt{n}] \times [\epsilon/\sqrt{n}, 1]$ and $B_n^* := [\epsilon/\sqrt{n}, 1] \times [0, \epsilon/\sqrt{n}]$. Then

$$ \frac{|\mathcal{P} \cap B_n|}{\epsilon \sqrt{n}} \underset{n \to \infty}{\longrightarrow} 1 ; \quad \frac{|\mathcal{P} \cap B_n^*|}{\epsilon \sqrt{n}} \underset{n \to \infty}{\longrightarrow} 1 $$

in probability. In particular w.h.p. we can define $Z_{down}^B = (U_{down}^B, V_{down}^B)$ as the downmost point in $\mathcal{P} \cap B_n$ and $Z_{left}^B = (U_{left}^B, V_{left}^B)$ as the leftmost point in $\mathcal{P} \cap B_n^*$, and they satisfy:

$$ \epsilon \sqrt{n} V_{down}^B - \epsilon^2 \underset{n \to \infty}{\longrightarrow} \mathrm{Exp}(1) ; \quad \epsilon \sqrt{n} U_{left}^B - \epsilon^2 \underset{n \to \infty}{\longrightarrow} \mathrm{Exp}(1) $$

in distribution.

**Proof** By Corollary 3.2, $|\mathcal{P} \cap B_n|$ is distributed like a sum of three Binom($|n/3| \pm 1$, $(1 - \epsilon/\sqrt{n})\epsilon/\sqrt{n}$), and likewise for $B_n^*$. The first claim readily follows from standard concentration inequalities. Then w.h.p. as $n \to \infty$, the sets $\mathcal{P} \cap B_n$ and $\mathcal{P} \cap B_n^*$ are non-empty and $Z_{down}^B$, $Z_{left}^B$ are well-defined. According to Lemma 3.3, conditionally given $|\mathcal{P} \cap B_n|$, the set $\mathcal{P} \cap B_n$ consists of i.i.d. uniform points in $B_n$. We can thus write, for any $s > 0$ and large enough $n$, conditionally given $|\mathcal{P} \cap B_n|$:

$$ \mathbf{P} \left( \epsilon \sqrt{n} V_{\mathrm{down}}^B > s + \epsilon^2 \right) = \mathbf{P} \left( V_{\mathrm{down}}^B > \frac{s}{\epsilon \sqrt{n}} + \epsilon/\sqrt{n} \right) = \left( 1 - \frac{1}{1 - \epsilon/\sqrt{n}} \frac{s}{\epsilon \sqrt{n}} \right)^{|\mathcal{P} \cap B_n|} $$

Hence $\mathbf{P}(\epsilon\sqrt{n}V_{\mathrm{down}}^B > s + \epsilon^2) \to e^{-s}$ as $n \to \infty$. The same holds for $U_{\mathrm{left}}^B$, and this concludes the proof. □

**Proof of Theorem 2.11** For each $n$, let $t^{(n)}$ be a cycle type of size $n$ and $\mathcal{P}$ be a geometric construction of $t^{(n)}$. Fix $\epsilon > 0$.

**Case 1:** Suppose $t_1^{(n)} = O(\sqrt{n})$.
Define $C_n := [0, \epsilon/\sqrt{\tilde{n}}]^2$. Then $|\tilde{P} \cap C_n|$ is distributed like a sum of three Binom $(\lfloor \tilde{n}/3 \rfloor \pm 1, \epsilon^2/\tilde{n})$ variables by Corollary 3.2, and $|P_\Delta \cap C_n|$ follows a Binom $(t_1^{(n)}, \epsilon/\sqrt{\tilde{n}})$ law. Therefore, there exists $\delta(\epsilon) = o(1)$, independent of $n$, such that:

$$ \limsup_{n \to \infty} \mathbf{P} (P \cap C_n \neq \emptyset) \leq \delta(\epsilon). \quad (32) $$

Define $B_n := [0, \epsilon/\sqrt{\tilde{n}}] \times [\epsilon/\sqrt{\tilde{n}}, 1]$ and $B_n^* := [\epsilon/\sqrt{\tilde{n}}, 1] \times [0, \epsilon/\sqrt{\tilde{n}}]$. According to Lemma 6.2 we can define w.h.p. $Z_{\text{down}}^B = (U_{\text{down}}^B, V_{\text{down}}^B)$ as the downmost point in $\tilde{P} \cap B_n$ and $Z_{\text{left}}^{B*} = (U_{\text{left}}^{B*}, V_{\text{left}}^{B*})$ as the leftmost point in $\tilde{P} \cap B_n^*$. See the right-hand side of Figure 6 for a representation.

Define the event $E_n := \{P \cap C_n = \emptyset\} \cap \{\tilde{P} \cap B_n \neq \emptyset\} \cap \{\tilde{P} \cap B_n^* \neq \emptyset\}$. Under this event, all points which are low records in $\tilde{P} \cap B_n$ or in $\tilde{P} \cap B_n^*$ are also low records in $P$. Reciprocally, all low records of $P$ lie in $B_n$, in $B_n^*$, or in $[\epsilon/\sqrt{\tilde{n}}, U_{\text{left}}^{B*}] \times [\epsilon/\sqrt{\tilde{n}}, V_{\text{down}}^B]$. Hence under $E_n$:

$$ |\text{rec}^{\downarrow}(P) - \text{rec}^{\downarrow}(\tilde{P} \cap B_n) - \text{rec}^{\downarrow}(\tilde{P} \cap B_n^*)| \le |P \cap ([\epsilon/\sqrt{\tilde{n}}, U_{\text{left}}^{B*}] \times [\epsilon/\sqrt{\tilde{n}}, V_{\text{down}}^B])|. \quad (33) $$

Using Lemma 6.2 and the fact that $t_1^{(n)} = O(\sqrt{n})$ we obtain:

$$ |P \cap ([\epsilon/\sqrt{\tilde{n}}, U_{\text{left}}^{B*}] \times [\epsilon/\sqrt{\tilde{n}}, V_{\text{down}}^B])| = O_P(1) $$

as $n \to \infty$, for fixed $\epsilon > 0$. Thus it suffices to study the records in $B_n$ and $B_n^*$. We can apply Lemma 3.3, Lemma 6.2 and Theorem 2.9 to obtain

$$ \frac{\text{rec}^{\downarrow}(\tilde{P} \cap B_n)}{\frac{1}{2} \log(n)} \xrightarrow{n \to \infty} 1 $$

in probability, and likewise for $B_n^*$. Using Equation (33) and 32 we deduce that for any $\eta > 0$:

$$ \limsup_{n \to \infty} \mathbf{P} \left( \left| \frac{\text{rec}^{\downarrow}(P)}{\frac{1}{2} \log(n)} - 2 \right| > \eta \right) \leq \delta(\epsilon). $$

Since this holds for any $\epsilon > 0$, the desired convergence in probability follows.

**Case 2:** Suppose $\sqrt{n} = o(t_1^{(n)})$.

<figure><img src="image_22.png" /></figure>
Let $Z_Δ = (U_Δ, U_Δ)$ be the leftmost point of $\mathcal{P}_Δ$. Then it is standard that

$$t_1^{(n)} U_Δ \underset{n \to \infty}{\longrightarrow} \text{Exp}(1) \qquad (34)$$

in distribution. By Corollary 3.2 and since $\tilde{n}/(t_1^{(n)})^2 \to 0$, w.h.p. it holds that $\tilde{\mathcal{P}} \cap [0, U_Δ]^2 = \emptyset$. Define two bands $B_Δ := [0, U_Δ] \times [U_Δ, 1]$ and $B_Δ^* := [U_Δ, 1] \times [0, U_Δ]$. Then under the event $\{\tilde{\mathcal{P}} \cap [0, U_Δ]^2 = \emptyset\}$ we may write:

$$\text{rec}^\downarrow(\mathcal{P}) = 1 + \text{rec}^\downarrow(\tilde{\mathcal{P}} \cap B_Δ) + \text{rec}^\downarrow(\tilde{\mathcal{P}} \cap B_Δ^*). \qquad (35)$$

Using Corollary 3.2 and Lemma 3.3 conditionally given $U_Δ$, $\tilde{\mathcal{P}} \cap B_Δ$ is a family of i.i.d. uniform points in $B_Δ$ whose size is distributed like a sum of three Binom($\lfloor \tilde{n}/3 \rfloor \pm 1$, $U_Δ(1 - U_Δ)$) variables. The same holds for $B_Δ^*$.

* If $n = O(t_1^{(n)})$ then, by Equation (34), $|\mathcal{P} \cap B_Δ|$ and $|\mathcal{P} \cap B_Δ^*|$ are both $O_P(1)$ as $n \to \infty$. Thus by Equation (35), $\text{rec}^\downarrow(\mathcal{P})$ is also a $O_P(1)$.

* If $t_1^{(n)} = o(n)$ then, by Equation (34), $\frac{t_1^{(n)}}{n} |\mathcal{P} \cap B_Δ| \underset{n \to \infty}{\longrightarrow} \text{Exp}(1)$ in distribution. Therefore:

$$\frac{\log |\mathcal{P} \cap B_Δ|}{\log (n/t_1^{(n)})} \underset{n \to \infty}{\longrightarrow} 1$$

in probability. In particular $|\mathcal{P} \cap B_Δ| \to \infty$ in probability and we can apply Theorem 2.9 to deduce:

$$\frac{\text{rec}^\downarrow(\mathcal{P} \cap B_Δ)}{\log |\mathcal{P} \cap B_Δ|} \underset{n \to \infty}{\longrightarrow} 1$$

in probability. The same holds for $B_Δ^*$, and the previous two equations along with Equation (35) yield:

$$\frac{\text{rec}^\downarrow(\mathcal{P})}{\log (n/t_1^{(n)})} \underset{n \to \infty}{\longrightarrow} 2$$

as desired.

This concludes the proof of Theorem 2.11. □

**Proof of Proposition 2.12** We use the same notation as in the proof of Theorem 2.11. Recall that under $E_n$:

$$|\text{rec}^\downarrow(\mathcal{P}) - \text{rec}^\downarrow(\tilde{\mathcal{P}} \cap B_n) - \text{rec}^\downarrow(\tilde{\mathcal{P}} \cap B_n^*)| \le O_P(1) \qquad (36)$$
where by Lemma 3.3, Lemma 6.2 and Theorem 2.9:

$$ \frac{\mathrm{rec}^{\downarrow}(\check{\mathcal{P}} \cap B_n) - \frac{1}{2} \log n}{\sqrt{\frac{1}{2} \log n}} \xrightarrow{n \to \infty} \mathcal{N}(0, 1) \qquad (37) $$

in distribution, and likewise for $B_n^*$. It remains to understand how $\mathrm{rec}^{\downarrow}(\mathcal{P} \cap B_n)$ and $\mathrm{rec}^{\downarrow}(\mathcal{P} \cap B_n^*)$ are correlated.

**Products of 2-cycles:** Suppose that $t_1^{(n)} + 2t_2^{(n)} = n$, i.e. that $\tau_n$ is a random involution with $t_1^{(n)}$ fixed points. Then the sets $\check{\mathcal{P}} \cap B_n$ and $\check{\mathcal{P}} \cap B_n^*$ are a.s. symmetric with respect to the diagonal. Therefore, $\mathrm{Perm}(\check{\mathcal{P}} \cap B_n)$ and $\mathrm{Perm}(\check{\mathcal{P}} \cap B_n^*)$ are a.s. inverse of each other, and $\mathrm{rec}^{\downarrow}(\mathrm{Perm}(\check{\mathcal{P}} \cap B_n)) = \mathrm{rec}^{\downarrow}(\mathrm{Perm}(\check{\mathcal{P}} \cap B_n^*))$ almost surely. Using Equation (32), 36 and 37 this yields:

$$ \frac{\mathrm{rec}^{\downarrow}(\mathcal{P}) - \log n}{\sqrt{\frac{1}{2} \log n}} \xrightarrow{n \to \infty} \mathcal{N}(0, 4) $$

as announced.

**Products of 3-cycles:** Suppose that $t_1^{(n)} + 3t_3^{(n)} = n$, i.e. that $\tau_n$ is a random product of 3-cycles. We claim the following: conditionally on the event $E_n$ and given the family $\mathcal{P} \cap B_n$, the permutation $\mathrm{Perm}(\mathcal{P} \cap B_n^*)$ has size $|\mathcal{P} \cap B_n|$ and is uniformly random. Let us explain why.

Set $\epsilon_n := \epsilon/\sqrt{n}$ and $D_n := [0, 1]^2 \setminus (C_n \cup B_n \cup B_n^*)$. Consider three independent variables $U, V, W$ distributed under $\mathrm{Unif}([0, 1])$. We may a.s. distinguish four outcomes:

* $U, V, W$ are all less than $\epsilon_n$, i.e. $(U, V), (V, W), (W, U)$ all lie within $C_n$;

* $U, V, W$ are all greater than $\epsilon_n$, i.e. $(U, V), (V, W), (W, U)$ all lie within $D_n$;

* at least one point, say $(U, V)$, is in $B_n$. Then either $W < \epsilon_n$, in which case $(V, W) \in B_n^*$ and $(W, U) \in C_n$, or $W > \epsilon_n$, in which case $(V, W) \in D_n$ and $(W, U) \in B_n^*$.

This holds for each triple $U_{3,k}^1, U_{3,k}^2, U_{3,k}^3$ in the construction of $\mathcal{P}$. Under the event $E_n$, only two possibilities remain: either $Z_{3,k}^1, Z_{3,k}^2, Z_{3,k}^3 \in D_n$, or exactly one point is in $B_n$ and another one is in $B_n^*$, and they share a coordinate. The conditional law of $\mathcal{P} \cap B_n^*$ under $E_n$ and $\mathcal{P} \cap B_n$ can thus be described as follows: write $\mathcal{P} \cap B_n = \{(U_i, V_i)\}$; let $(W_i)$ be i.i.d. $\mathrm{Unif}([\epsilon_n, 1])$ variables; and set $\mathcal{P} \cap B_n^* = \{(W_i, U_i)\}$. One can easily see that for any distinct $u_1, \dots, u_r$, if $W_1, \dots, W_r$ are i.i.d. $\mathrm{Unif}([\epsilon_n, 1])$ variables then $\mathrm{Perm}((W_1, u_1), \dots, (W_r, u_r))$ is uniformly random (e.g. switching $W_i$ with $W_j$ shows that this is the Haar measure on the symmetric group). This proves that conditionally on the event $E_n$ and given the family $\mathcal{P} \cap B_n$, the permutation $\mathrm{Perm}(\mathcal{P} \cap B_n^*)$ has size $|\mathcal{P} \cap B_n|$ and is uniformly random.

This claim implies that conditionally on the event $E_n$ and given the number $|\mathcal{P} \cap B_n|$, the permutations $\mathrm{Perm}(\mathcal{P} \cap B_n)$ and $\mathrm{Perm}(\mathcal{P} \cap B_n^*)$ have size $|\mathcal{P} \cap B_n|$ and are independent uniform. Using Equation (32), 36 and 37 we deduce:

<figure><img src="image_23.png" /></figure>
$$ \frac{\mathrm{rec}^{\downarrow}(\mathcal{P}) - \log n}{\sqrt{\frac{1}{2} \log n}} \underset{n \to \infty}{\longrightarrow} \mathcal{N}(0, 2), $$

and this concludes the proof of the proposition. □

# 7 Proofs of the results on pattern counts

## 7.1 Dependency graphs and asymptotic normality

We recall the notion of dependency graph, as introduced in [32]. Let $(Z_i)_{i \in V}$ be a family of random variables indexed by some set $V$. We say that a graph $(V, E)$ is a dependency graph for $(Z_i)_{i \in V}$ if it has the following property: for any disjoint subsets $V_1, V_2$ of $V$ which are not linked by any edge in $E$, the two families $(Z_i)_{i \in V_1}$ and $(Z_i)_{i \in V_2}$ are independent.

Let $t$ be a cycle type of size $n$, and $\mathcal{L}_t$ be the graph defined in Section 1.3. The following lemma is a direct consequence of the definitions.

**Lemma 7.1** In the geometric construction of Lemma 1.3, the graph $\mathcal{L}_t = (\mathcal{V}_t, \mathcal{E}_t)$ is a dependency graph for the variables $(Z_i)_{i \in \mathcal{V}_t}$.

Now we can use $\mathcal{L}_t$ to construct another dependency graph. Let $(\mathcal{V}_r^i)$ denote the set of subsets of size $r$ in $\mathcal{V}_t$. Define a graph $(\mathcal{L}_r^i)$ with vertices $(\mathcal{V}_r^i)$ as follows: $I, J \in (\mathcal{V}_r^i)$ share an edge if and only if there exist $i \in I$ and $j \in J$ such that $i = j$ or $i \sim j$ in $\mathcal{L}_t$. Using Lemma 7.1, it is straightforward to check that $(\mathcal{L}_r^i)$ is a dependency graph for the family of random variables $((Z_i)_{i \in I})_{I \in (\mathcal{V}_r^i)}$.

The idea that the variables $(Z_i)_{i \in \mathcal{V}_t}$ are “partly dependent” is motivated by the fact that these graphs have low degrees: the degrees of $\mathcal{L}_t$ are bounded by 2, and a rough upper bound for the degrees of $(\mathcal{L}_r^i)$ is $3r(\frac{n}{r-1}) = \mathcal{O}(n^{r-1})$. We could then apply [22, Theorem 2] to deduce asymptotic normality for the pattern count $X_\pi(\tau_n)$, but we rather use Stein’s method to obtain a stronger result.

**Proof of Theorem 2.14** We aim to apply [20, Theorem 3.5], which is based on the results of [8] and [34], to the decomposition (1) of $X_\pi(\tau_n)$. According to Lemma 7.1 and the discussion following it, $(\mathcal{L}_r^i)$ is a dependency graph for the family of random variables $(\mathbf{1}_{\mathrm{Perm}(Z_i, i \in I)}=\pi)_{I \in (\mathcal{V}_r^i)}$. Thus we can use [20, Theorem 3.5] with $B = 1$, $D \le 3r(\frac{n}{r-1})$, and $N = (\frac{n}{r})$. This yields the announced bound on the Kolmogorov distance.

Now suppose $\mathrm{Var}[X_\pi(\tau_n)] = \sigma^2 n^{2r-1} + o(n^{2r-1})$ as $n \to \infty$, for some $\sigma \ge 0$. If $\sigma = 0$ then

$$ \frac{X_{\pi}(\tau_n) - \mathbb{E}[X_{\pi}(\tau_n)]}{n^{r-1/2}} \underset{n \to \infty}{\longrightarrow} 0 $$

in probability, by Bienaymé-Chebychev’s inequality. If $\sigma > 0$ then the previous bound on the Kolmogorov distance is a $\mathcal{O}(n^{-1/2})$. In particular it goes to 0 as $n \to \infty$,
which implies convergence in distribution of the random variables. This concludes the proof. □

## 7.2 Computation of the variance

**Proof of Theorem 2.15** We only prove marginal convergence, for convenience. Joint convergence is proved by the same method, using the Cramér–Wold theorem.

Fix a pattern $\pi \in \mathcal{S}_r$. Throughout the proof we may omit the indices $\pi, p_1, p_2, n$. Thanks to Theorem 2.14, it suffices to compute the mean and variance of $X := X_\pi(\tau)$. Let $\mathcal{P} = (Z_i)_{i \in \mathcal{V}_i}$ be a geometric construction of $\tau_n$. The first idea is to approximate $X$ with a new variable

$$Y := \sum_{I \in \binom{\mathcal{V}_r}{r} \text{ indep.}} \mathbf{1}_{\text{Perm}(Z_i, i \in I) = \pi},$$

where the sum ranges over all subsets $I \in \binom{\mathcal{V}_r}{r}$ which induce an independent (i.e. empty) subgraph of $\mathcal{L}_t$. Since the number of non-independent $r$-sized subgraphs of $\mathcal{L}_t$ is bounded by $2(r-1)\binom{n}{r-1}$, almost surely it holds that $|X - Y| \le 2(r-1)\binom{n}{r-1}$. In particular $\mathbb{E}[X] = \mathbb{E}[Y] + \mathcal{O}(n^{r-1})$ and $\sqrt{\text{Var}[X]} = \sqrt{\text{Var}[Y]} + \mathcal{O}(n^{r-1})$, so it suffices to prove the desired result for $Y$. To do this, we shall rewrite $Y$ while keeping track of how many fixed points are picked in the sum.

Decompose $\mathcal{V}_t$ as $\mathcal{V}_1 \sqcup \mathcal{V}_2 \sqcup \mathcal{V}_3$ where $\mathcal{V}_m := \{(p, k, l) \in \mathcal{V}_t : p = m\}$ for $m \in \{1, 2\}$ correspond to fixed points and points in 2-cycles, and $\mathcal{V}_3 := \{(p, k, l) \in \mathcal{V}_t : p \ge 3\}$ corresponds to all other points. Let $U_1, \dots, U_r, V_1, \dots, V_r$ be i.i.d. Unif([0, 1]) random variables. For any $q \in \{0, 1, \dots, r\}$, define:

$$\mu_q := \mathbf{P} \left( \text{Perm} \left( (U_1, U_1), \dots, (U_q, U_q), (U_{q+1}, V_{q+1}), \dots, (U_r, V_r) \right) = \pi \right),$$

so that

$$\mu := \mu_{\pi}^{p_1} = \sum_{q=0}^{r} \binom{r}{q} p_1^q (1 - p_1)^{r-q} \mu_q.$$

Define $\mathcal{I}_q := \{I \in \binom{\mathcal{V}_r}{r} \text{ indep., } |I \cap \mathcal{V}_1| = q\}$ and $c_q := |\mathcal{I}_q|$. For any $I \in \mathcal{I}_q$, the variables $Z_i, i \in I$ are independent by Lemma 7.1, and $\mathbf{P}(\text{Perm}(Z_i, i \in I) = \pi) = \mu_q$. Therefore, we can write $\mathbb{E}Y = \sum_{q=0}^{r} c_q \mu_q$. Since the number of non-independent $I \in \binom{\mathcal{V}_r}{r}$ is $\mathcal{O}(n^{r-1})$ and the total number of $I \in \binom{\mathcal{V}_r}{r}$ with $|I \cap \mathcal{V}_1| = q$ is

$$\binom{|\mathcal{V}_1|}{q} \binom{|\mathcal{V}_t \setminus \mathcal{V}_1|}{r-q} = \frac{(np_1)^q + o(n^{q-1/2})}{q!} \frac{(n(1-p_1))^{r-q} + o(n^{r-q-1/2})}{(r-q)!} \\ = \binom{n}{r} \binom{r}{q} p_1^q (1-p_1)^{r-q} + o(n^{r-1/2}),$$
we deduce $\mathbb{E}Y = \binom{n}{r}\mu + o(n^{r-1/2})$. It remains to study the variance of $Y$, and for this we rely on the method of U-statistics developed in [19]. The idea is to decompose $Y$ using its univariate projections. First define:

$$ \bar{Y} := Y - \mathbb{E}Y = \sum_{q=0}^{r} \sum_{I \in \mathcal{I}_q} \bar{\phi}_q(Z_i, i \in I) \quad \text{where} \quad \bar{\phi}_q(z_1, \dots, z_r) := \mathbf{1}_{\text{Perm}(z_1, \dots, z_r)=\pi} - \mu_q. $$

Then set for any $q \in \{0, 1, \dots, r-1\}$ and $z \in [0, 1]^2$:

$$ \varphi_q(z) := \mathbf{P}(\text{Perm}((U_1, U_1), \dots, (U_q, U_q), (U_{q+1}, V_{q+1}), \dots, (U_{r-1}, V_{r-1}), z) = \pi), $$ 
so that for any $z \in [0, 1]^2$:

$$ \psi(z) := \psi_{\pi}^{p_1}(z) = \sum_{q=0}^{r-1} \binom{r-1}{q} p_1^q (1-p_1)^{r-q-1} \varphi_q(z). \quad (38) $$

It follows from definition that for any $I \in \mathcal{I}_q$ we have:

$$ \mathbb{E}[\bar{\phi}_q(Z_i, i \in I) | Z_j] = \begin{cases} \varphi_q(Z_j) - \mu_q & \text{if } j \in I \setminus V_1; \\ \varphi_{q-1}(Z_j) - \mu_q & \text{if } j \in I \cap V_1. \end{cases} \quad (39) $$

Now for any $I \in \mathcal{I}_q$ and $(z_i)_{i \in I} \in ([0, 1]^2)^I$, define the “residual function”:

$$ \phi_I^*(z_i, i \in I) := \bar{\phi}_q(z_i, i \in I) - \sum_{i \in I \cap V_1} (\varphi_{q-1}(z_i) - \mu_q) - \sum_{i \in I \setminus V_1} (\varphi_q(z_i) - \mu_q). $$

Notice that if the sum over $i \in I \cap V_1$ is non-empty then $q \ge 1$ i.e. $q-1 \ge 0$. A key property of $\phi_I^*$ is that its univariate projections vanish: for any $j \in I$, a.s. $\mathbb{E}[\phi_I^*(Z_i, i \in I) | Z_j] = 0$. This is checked directly by distinguishing between $j \in V_1$ and $j \notin V_1$ to use (39), observing that most terms have zero mean and that two of them cancel out. With this notation, we can decompose $\bar{Y}$ as:

$$ \begin{aligned} \bar{Y} &= \sum_{I \in \binom{V_1}{r} \text{ indep.}} \phi_I^*(Z_i, i \in I) + \sum_{q=0}^{r} \sum_{I \in \mathcal{I}_q} \left( \sum_{i \in I \cap V_1} \varphi_{q-1}(Z_i) + \sum_{i \in I \setminus V_1} \varphi_q(Z_i) - r\mu_q \right) \\ &= Y_* + \hat{Y}. \end{aligned} $$

When expanding $Y_*^2$, one can distinguish the pairs $(I, J)$ of r-sized independent sub-graphs of $\mathcal{L}_t$ into three categories: the ones sharing no common vertex and connected by no edge; the ones sharing exactly one vertex or connected by exactly one edge; and the others. If $(I, J)$ is in the first category then $\mathbb{E}[\phi_I^*(Z_i, i \in I)\phi_J^*(Z_j, j \in J)] = 0$ by independence (see Lemma 7.1). If $(I, J)$ is in the second category, write $(\alpha, \beta) \in I \times J$
for the unique pair of connected or equal vertices. Then $I \setminus \{\alpha\}$ is independent of $J \setminus \{\beta\}$ and we can write a.s.:

$$ 
\begin{aligned}
& \mathbb{E}[\phi_I^*(Z_i, i \in I)\phi_J^*(Z_j, j \in J) | Z_\alpha, Z_\beta] \\
& = \mathbb{E}[\phi_I^*(Z_i, i \in I) | Z_\alpha] \mathbb{E}[\phi_J^*(Z_j, j \in J) | Z_\beta] = 0.
\end{aligned}
$$

In particular $\mathbb{E}[\phi_I^*(Z_i, i \in I)\phi_J^*(Z_j, j \in J)] = 0$. Since the number of pairs in the third category is bounded by $9r^2 \binom{n}{r-2} \binom{n}{r}$, we deduce $\mathbb{E}[Y_*^2] = \mathcal{O}(n^{2r-2})$ as $n \to \infty$. Thus $\sqrt{\mathrm{Var}\tilde{Y}} = \sqrt{\mathrm{Var}\hat{Y}} + \mathcal{O}(n^{r-1})$, and it suffices to study $\hat{Y}$. Since $\sum_{q=0}^r c_q \mu_q = \binom{n}{r}\mu + o(n^{r-1/2})$, we can rewrite it as:

$$ \hat{Y} = \sum_{i \in \mathcal{V}_1} \sum_{q=1}^{r} c_{i,q} \varphi_{q-1}(Z_i) + \sum_{i \in \mathcal{V}_1 \setminus \mathcal{V}_1} \sum_{q=0}^{r-1} c_{i,q} \varphi_q(Z_i) - r \binom{n}{r} \mu + o(n^{r-1/2}), $$

where the $o$ is deterministic, and for any $q \in \{0, 1, \dots, r\}$ and $i \in \mathcal{V}_t$, $c_{i,q}$ is the number of $I \in \mathcal{I}_q$ containing $i$. These numbers satisfy, as $n \to \infty$:

$$ 
\left\{ 
\begin{array}{l}
c_{i,q} = \binom{|\mathcal{V}_1|-1}{q-1} \binom{|\mathcal{V}_t \setminus \mathcal{V}_1|}{r-q} + \mathcal{O}(n^{r-2}) = \binom{n}{r-1} \binom{r-1}{q-1} p_1^{q-1} (1-p_1)^{r-q} + o(n^{r-3/2}) \\
\text{uniformly in } i \in \mathcal{V}_1; \\
c_{i,q} = \binom{|\mathcal{V}_1|}{q} \binom{|\mathcal{V}_t \setminus \mathcal{V}_1|-1}{r-q-1} + \mathcal{O}(n^{r-2}) = \binom{n}{r-1} \binom{r-1}{q} p_1^{q} (1-p_1)^{r-q-1} + o(n^{r-3/2}) \\
\text{uniformly in } i \in \mathcal{V}_t \setminus \mathcal{V}_1.
\end{array}
\right.
$$

Then define

$$ \tilde{Y} := \binom{n}{r-1} \sum_{i \in \mathcal{V}_t} (\psi(Z_i) - \mu). $$

The previous calculation and (38) imply that $|\hat{Y} - \tilde{Y}| = o(n^{r-1/2})$ a.s. for some deterministic $o$, hence as before we just need to compute the variance of $\tilde{Y}$. Using Lemma 7.1 we can write:

$$ 
\begin{aligned}
\mathrm{Var}\left[\binom{n}{r-1}^{-1} \tilde{Y}\right] &= \sum_{i,j \in \mathcal{V}_t} \mathrm{Cov}[\psi(Z_i), \psi(Z_j)] \\
&= \sum_{i \in \mathcal{V}_t} \mathrm{Var}[\psi(Z_i)] + \sum_{i \in \mathcal{V}_2} \mathrm{Cov}[\psi(Z_i), \psi(Z_{\mathfrak{s}(i)})] \\
&\quad + \sum_{i \in \mathcal{V}_3} (\mathrm{Cov}[\psi(Z_i), \psi(Z_{\mathfrak{s}(i)})] + \mathrm{Cov}[\psi(Z_i), \psi(Z_{\mathfrak{s}^{-1}(i)})]) \\
&= n p_1 \mathrm{Var}[\psi(U, U)] \\
&\quad + n(1-p_1)\mathrm{Var}[\psi(U, V)] + n p_2 \mathrm{Cov}[\psi(U, V), \psi(V, U)] \\
&\quad + 2n(1-p_1-p_2)\mathrm{Cov}[\psi(U, V), \psi(V, W)] + o(n)
\end{aligned}
$$
where $U, V, W$ are i.i.d. Unif([0, 1]) variables. Thus $\mathrm{Var}[X] = \sigma^2 n^{2r-1} + o(n^{2r-1})$ with $\sigma^2 := \Sigma_{\pi, \pi}^{p_1, p_2}$ as defined in the statement of Theorem 2.15. Thanks to Theorem 2.14, this concludes the proof. $\square$

**Proof of Corollary 2.16** Recall that conditionally given $t^{(n)}$, $\tau_n$ is a uniform $t^{(n)}$-cyclic permutation. Using Theorem 2.15, we can thus write for any $x \in \mathbb{R}$:

$$ \mathbf{P} \left( X_{\pi}(\tau_n) - \binom{n}{r} \mu_{\pi}^{p_1} < n^{r-1/2} x \right) = \mathbb{E} \left[ \mathbf{P} \left( X_{\pi}(\tau_n) - \binom{n}{r} \mu_{\pi}^{p_1} < n^{r-1/2} x \mid (t^{(n)})_n \right) \right] \underset{n \to \infty}{\longrightarrow} g_{\pi}^{p_1, p_2}(x) $$

by dominated convergence theorem, where $g_{\pi}^{p_1, p_2}$ is the distribution function of $N(0, \Sigma_{\pi, \pi}^{p_1, p_2})$. Joint convergence is proved by the same method and the Cramér–Wold theorem. $\square$

## 7.3 Non-degeneracy for involutive patterns

**Lemma 7.2** For any $p_1 \in [0, 1]$ and $\pi \in \mathfrak{S}_r$, the function $\psi_{\pi}^{p_1}$ is $(r-1)$-Lipschitz with respect to the $L^1$-norm on $[0, 1]^2$. Moreover, its restriction to $\{0\} \times [0, 1]$ is a polynomial which is non-constant if $p_1 < 1$ and $r \ge 2$.

**Proof** Write $\psi := \psi_{\pi}^{p_1}$. Recall the variables $\hat{Z}_1, \dots, \hat{Z}_r$ used to define $\psi$. For any $z = (u, v), z' = (u', v') \in [0, 1]^2$:

$$ |\psi(z) - \psi(z')| \le \mathbf{P} \left( \mathrm{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, z) \ne \mathrm{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, z') \right). $$

Define $\mathcal{B}_{z,z'}$ as the set of points in $[0, 1]^2$ having x-coordinate between $u$ and $u'$ or y-coordinate between $v$ and $v'$. For the permutations $\mathrm{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, z)$ and $\mathrm{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, z')$ to differ, there needs to be a $\hat{Z}_i$ whose position with respect to $z$ (NW, NE, SW, or SE) is not the same as with respect to $z'$. Therefore:

$$ |\psi(z) - \psi(z')| \le \sum_{i=1}^{r-1} \mathbf{P} \left( \hat{Z}_i \in \mathcal{B}_{z,z'} \right) \le (r-1) (|u-u'| + |v-v'|) $$

and $\psi$ is indeed $(r-1)$-Lipschitz. Now fix $v \in [0, 1]$ and let $Q$ be the number of $\hat{Z}_i's$, $i \le r-1$ on the diagonal $\Delta$. The random variable $Q$ follows a Binom $(r-1, p_1)$ law. Now let $q, j_{SW}, j_{SE}, j_{NE}, j_{NW}, k_{SW}, k_{NE}$ be nonnegative integers satisfying

$$ \left\{ \begin{array}{l} q \in \{0, 1, \dots, r-1\}; \\ j_{SW} + j_{SE} + j_{NE} + j_{NW} + k_{SW} + k_{NE} = r-1; \\ k_{SW} + k_{NE} = q; \\ j_{SW} + j_{SE} + k_{SW} = \pi(1) - 1; \\ j_{NE} + j_{NW} + k_{NE} = r - \pi(1); \end{array} \right. \qquad (40) $$
(the last line is redundant, but we keep it for clarity). Under this condition we write $A_{q,j,k}(v)$ for the event that $Q = q$; $j_{SW}$, $j_{SE}$, $j_{NE}$, $j_{NW}$ are the numbers of non-diagonal $\hat{Z}_i$'s in each quadrant defined by $(v, v)$; and $k_{SW}$, $k_{NE}$ are the numbers of diagonal $\hat{Z}_i$'s lying southwest, resp. northeast of $(v, v)$. If $\text{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, (0, v)) = \pi$ then $A_{q,j,k}(v)$ is verified for some $q, j, k$ satisfying (40). Moreover, conditionally on $A_{q,j,k}(v)$, the probability of this event does not depend on $v$. Indeed one can construct a straightforward coupling between $(\hat{Z}_i)_{1\le i\le r-1}$ conditioned on $A_{q,j,k}(v)$ and $(\hat{Z}'_i)_{1\le i\le r-1}$ conditioned on $A_{q,j,k}(v')$ such that a.s. $\text{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, (0, v)) = \text{Perm}(\hat{Z}'_1, \dots, \hat{Z}'_{r-1}, (0, v'))$. Therefore:

$$
\begin{align*}
\psi(0, v) &= \sum_{q,j,k \text{ s.t. (40)}} \mathbf{P} \left( \text{Perm} \left( \hat{Z}_1, \dots, \hat{Z}_{r-1}, (0, v) \right) \right) = \pi \left| A_{q,j,k}(v) \right| \mathbf{P} \left( A_{q,j,k}(v) \right) \\
&= \sum_{q,j,k \text{ s.t. (40)}} c_{\pi,q,j,k} \binom{r-1}{q} p_1^q (1-p_1)^{r-q-1} \binom{r-q-1}{j_{SW}, j_{SE}, j_{NE}, j_{NW}} \\
&\qquad \nu^{k_{SW}+2j_{SW}+j_{SE}+j_{NW}} (1-v)^{k_{NE}+2j_{NE}+j_{SE}+j_{NW}} \\
&= \nu^{\pi(1)-1} (1-v)^{r-\pi(1)} \sum_{q,j,k \text{ s.t. (40)}} c_{\pi,q,j,k} \binom{r-1}{q} p_1^q (1-p_1)^{r-q-1} \binom{r-q-1}{j_{SW}, j_{SE}, j_{NE}, j_{NW}} \\
&\qquad \nu^{j_{SW}+j_{NW}} (1-v)^{j_{NE}+j_{SE}} \\
&= \nu^{\pi(1)-1} (1-v)^{r-\pi(1)} \sum_{q=0}^{r-1} \sum_{m=0}^{r-q-1} c'_{\pi,q,m} \nu^m (1-v)^{r-q-1-m}
\end{align*}
$$

for some non-negative constants $c_{\pi,q,j,k}$ and $c'_{\pi,q,m}$. Thus $\psi(0, v)$ is a polynomial in $v$. It remains to see that it is non-constant if $p_1 < 1$ and $r \ge 2$.

First suppose that $\pi(1) \ne 1$. The polynomial $\psi(0, v)$ contains a monomial $\nu^{\pi(1)-1} \sum_{q=0}^{r-1} c'_{\pi,q,0}$ where $c'_{\pi,q,0} \ge 0$, along with terms of higher degrees. Since $p_1 < 1$, the event $A_{0,j,0}(v)$ has positive probability for any $(0, j, 0)$ satisfying (40), and also $c_{\pi,0,j,0} > 0$. In particular for $j_{SW} + j_{NW} = 0$, we deduce $c'_{\pi,0,0} > 0$. Thus $\psi(0, v)$ is indeed non-constant.

On the other hand if $\pi(1) = 1$ then $\pi(1) \ne r$ and we can do the same reasoning with the polynomial $\psi(0, 1 - v)$ to conclude. $\square$

**Proof of Proposition 2.17** By the law of total covariance, if $U, V, W$ are i.i.d. Unif $([0, 1])$ variables:

$$
\text{Cov}[\psi(U, V), \psi(V, W)] = \mathbb{E}[\text{Cov}[\psi(U, V), \psi(V, W) | V]] \\
+ \text{Cov}[\mathbb{E}[\psi(U, V) | V], \mathbb{E}[\psi(V, W) | V]].
$$

Conditionally given $V$, the variables $\psi(U, V)$ and $\psi(V, W)$ are independent, and thus the first term is null. Now let us study the second term. Since $\pi$ is an involution, for any $u_1, v_1, \dots, u_r, v_r$ we have $\text{Perm}((u_1, v_1), \dots, (u_r, v_r)) = \pi$ if and only if $\text{Perm}((v_1, u_1), \dots, (v_r, u_r)) = \pi$. Since the distribution $p_1\text{Leb}_\Delta + (1-p_1)\text{Leb}_{[0,1]^2}$

<figure><img src="image_24.png" /></figure>
is symmetric with respect to $\Delta$, we deduce that $\psi(u, v) = \psi(v, u)$ for any $(u, v) \in [0, 1]^2$. Hence:

$$ \begin{aligned} \mathrm{Cov}[\psi(U, V), \psi(V, W)] &= \mathrm{Cov}[\mathbb{E}[\psi(U, V) | V], \mathbb{E}[\psi(W, V) | V]] \\ &= \mathrm{Var}[\mathbb{E}[\psi(U, V) | V]] \ge 0, \end{aligned} $$

and in particular $(r-1)!^2 \sum_{\pi, \pi'}^{p_1, p_2} \ge (1-p_1+p_2)\mathrm{Var}[\psi(U, V)]$. By Lemma 7.2, $\psi$ is continuous and non-constant on $[0, 1]^2$, and thus $\mathrm{Var}[\psi(U, V)] > 0$. As $p_1 < 1$, this concludes the proof. $\square$

## 7.4 Cycle types with few fixed points

In this section we suppose $p_1 = 0$, and drop the index $p_1$. In particular $\mu_\pi = 1/r!$ for any $\pi \in \mathfrak{S}_r$,

$$ \psi_{\pi}(z) = \mathbf{P}(\mathrm{Perm}(\hat{Z}_1, \dots, \hat{Z}_{r-1}, z) = \pi) $$

where $\hat{Z}_1, \dots, \hat{Z}_{r-1}$ are i.i.d. Unif $([0, 1]^2)$ variables, and the matrix of Theorem 2.15 rewrites as:

$$ (r-1)!^2 \sum_{\pi, \rho} p_2^2 = \mathrm{Cov}[\psi_{\pi}(U, V), \psi_{\rho}(U, V)] + p_2 \mathrm{Cov}[\psi_{\pi}(U, V), \psi_{\rho}(V, U)] \\ + 2(1-p_2) \mathrm{Cov}[\psi_{\pi}(U, V), \psi_{\rho}(V, W)] $$

where $U, V, W$ are i.i.d. Unif $([0, 1])$ variables. To establish Theorem 2.18, we need to study the function $\psi$ a bit more.

**Lemma 7.3** If $p_1 = 0$ then for any $\pi, \rho \in \mathfrak{S}_r$:

$$ \mathrm{Cov}[\psi_{\pi}(U, V), \psi_{\rho}(V, W)] = 0. $$

*Proof* For any distinct $u_1, v_1, \dots, u_r, v_r \in [0, 1]$, we can write $\mathrm{Perm}((u_1, v_1), \dots, (u_r, v_r)) = \sigma_2^{-1} \circ \sigma_1$ where $\sigma_1, \sigma_2 \in \mathfrak{S}_r$ are characterized by $u_{\sigma_1(1)} < \dots < u_{\sigma_1(r)}$ and $v_{\sigma_2(1)} < \dots < v_{\sigma_2(r)}$. If $(U_1, V_1), \dots, (U_r, V_r)$ are i.i.d. Unif $([0, 1]^2)$ variables then $\sigma_1, \sigma_2$ are i.i.d. uniform permutations of size $r$. Conditionally given $(V_1, \dots, V_r)$, $\sigma_2$ is determined and $\sigma_1$ is still uniformly random in $\mathfrak{S}_r$. Subsequently

$$ \mathbf{P}(\mathrm{Perm}((U_1, V_1), \dots, (U_r, V_r)) = \pi | V_1, \dots, V_r) = \mathbf{P}(\sigma_1 = \sigma_2 \circ \pi | \sigma_2) = 1/r! $$

almost surely, and similarly

$$ \mathbf{P}(\mathrm{Perm}((U_1, V_1), \dots, (U_r, V_r)) = \rho | U_1, \dots, U_r) = \mathbf{P}(\sigma_2 = \sigma_1 \circ \rho^{-1} | \sigma_1) = 1/r! $$

almost surely. We can thus write
$$ \mathbb{E}[\psi_{\pi}(U, V)\psi_{\rho}(V, W) | V] = \mathbb{E}[\psi_{\pi}(U, V) | V]\mathbb{E}[\psi_{\rho}(V, W) | V] = (1/r!)^2 \quad \square $$
a.s., and the lemma readily follows.

This yields the announced formula for $\sum_{\pi, \rho}^{p_2}$. It remains to compute the rank and show non-degeneracy. For this we shall give an explicit polynomial formula for $\psi_{\pi}$; it can already be found in [24] (see Equation (5) therein for its rescaled expression) but we provide a proof below for completeness.

**Lemma 7.4** Let $\pi \in \mathfrak{S}_r$. We can write, for any $(u, v) \in [0, 1]^2$:

$$ \psi_{\pi}(u, v) = \frac{1}{(r-1)!} \sum_{i=1}^{r} g_i(u) g_{\pi(i)}(v) $$

where for any $j \in [r]$ and $w \in \mathbb{R}$, $g_j(w) := \binom{r-1}{j-1} w^{j-1} (1-w)^{r-j}$. Moreover, if $r \ge 2$ then the symmetrized function $(u, v) \mapsto \psi_{\pi}^{\text{sym}}(u, v) := \psi_{\pi}(u, v) + \psi_{\pi}(v, u)$ is not constant.

**Proof** We omit the index $\pi$ in this proof. Write $\psi = \psi_1 + \dots + \psi_r$ where for any $i \in [r]$ and $(u, v) \in [0, 1]^2$, if $\hat{Z}_1, \dots, \hat{Z}_{r-1}$ denote i.i.d. Unif $([0, 1]^2)$ random variables:

$$ \psi_i(u, v) := \mathbf{P} \left( \text{Perm} \left( \hat{Z}_1, \dots, \hat{Z}_{r-1}, (u, v) \right) = \pi, (u, v) \text{ is } i\text{-th from the left} \right). $$

For this event, say $A_i(u, v)$, to be realized, there needs to be exactly $i-1$ points left of $(u, v)$ and $\pi(i)-1$ below $(u, v)$. More precisely there needs to be exactly $j_{\text{SW}}$, $j_{\text{SE}}$, $j_{\text{NE}}$, $j_{\text{NW}}$ points in each quadrant defined by $(u, v)$, where these quantities depend only on $\pi$ and $i$. Let $B_i(u, v)$ be this last event; its probability can be written as $\binom{r-1}{j_{\text{SW}}, j_{\text{SE}}, j_{\text{NE}}, j_{\text{NW}}} u^{i-1} (1-u)^{r-i} v^{\pi(i)-1} (1-v)^{r-\pi(i)}$. Then conditionally on $B_i(u, v)$, the probability of $A_i(u, v)$ does not depend on $(u, v)$ anymore. Indeed by a coupling argument, one can e.g. see that $\mathbf{P}(A_i(u, v)|B_i(u, v))$ is the probability that $j_{\text{SW}}$ uniform points in $[0, 1/2]^2$, $j_{\text{SE}}$ uniform points in $[1/2, 1] \times [0, 1/2]$, $j_{\text{NE}}$ uniform points in $[1/2, 1]^2$, and $j_{\text{NW}}$ uniform points in $[0, 1/2] \times [1/2, 1]$, all independent, form the permutation induced by $\pi$ on $[r] \setminus \{i\}$. Hence $\mathbf{P}(A_i(u, v)|B_i(u, v))$ equals a positive constant, independent of $(u, v)$, and we deduce that

$$ \psi_i(u, v) = \mathbf{P}(A_i(u, v)|B_i(u, v)) \mathbf{P}(B_i(u, v)) = c_i u^{i-1} (1-u)^{r-i} v^{\pi(i)-1} (1-v)^{r-\pi(i)}. $$

To find the value of $c_i$, first notice that $\mathbb{E}[\psi_i(U, V)] = \frac{1}{r} \frac{1}{r!}$. Then in the previous formula:

$$ \frac{1}{r} \frac{1}{r!} = c_i B(i, r-i+1) B(\pi(i), r-\pi(i)+1) $$

where $B$ denotes the Beta function, and thus

$$ c_i = \frac{(r-1)!}{(i-1)!(r-i)!(\pi(i)-1)!(r-\pi(i))!} = \frac{1}{(r-1)!} \binom{r-1}{i-1} \binom{r-1}{\pi(i)-1}. $$

<figure><img src="image_25.png" /></figure>
This yields the announced formula for $\psi = \sum_{i} \psi_{i}$. Now let us turn to the last claim of the lemma. By reindexing we can write $\psi^{\text{sym}}(u, v) = \sum_{i=1}^{r} u^{i-1}(1-u)^{r-i} Q_{i}(v)$ where

$$Q_i(v) := c_i v^{\pi(i)-1} (1-v)^{r-\pi(i)} + c_{\pi^{-1}(i)} v^{\pi^{-1}(i)-1} (1-v)^{r-\pi^{-1}(i)}.$$

Suppose that $\psi^{\text{sym}}$ is constant on $[0, 1]^2$. Then by setting $u = 0$ we see that the polynomial $Q_1(v)$ is constant in $v$. If $\pi(1) > 1$ then $\pi^{-1}(1) > 1$ and the lowest degree term of $Q_1$ has positive degree and coefficient, which contradicts the fact that $Q_1$ is constant. Hence $\pi(1) = 1$. Likewise by setting $u = 1$ we see that $Q_r$ is constant, which implies $\pi(r) = 1$ or $\pi^{-1}(r) = 1$. Hence $r = 1$ and this concludes the proof. $\square$

**Proof of Theorem 2.18** First, let us show non-degeneracy. Fix $p_2 \in [0, 1]$, $r \ge 2$, $\pi \in \mathfrak{S}_r$. Since $\psi_\pi$ is continuous and not constant on $[0, 1]^2$ according to Lemma 7.4, it holds that $\text{Var}[\psi_\pi(U, V)] > 0$.

By Cauchy–Schwarz inequality, $|\text{Cov}[\psi_\pi(U, V), \psi_\pi(V, U)]| \le \text{Var}[\psi_\pi(U, V)]$. Suppose by contradiction that $\sum_{\pi, \pi}^{p_2} = 0$. Then necessarily $p_2 = 1$ and $\text{Cov}[\psi_\pi(U, V), \psi_\pi(V, U)] = -\text{Var}[\psi_\pi(U, V)]$. This equality case can only happen if $\psi_\pi(U, V)$ and $\psi_\pi(V, U)$ are linearly dependent, and here we would have $\psi_\pi(U, V) = -\psi_\pi(V, U)$ almost surely. However it follows from Lemma 7.4 that $\psi_\pi(U, V) + \psi_\pi(V, U)$ is not a.s. constant, and this proves by contradiction that $\sum_{\pi, \pi}^{p_2} > 0$.

Now, Let us study the rank of $\sum^{p_2}$. Fix $\alpha, \beta \ge 0$ such that $\alpha^2 + \beta^2 = 1$ and $2\alpha\beta = p_2$ (this is possible since $p_2 \le 1$), and define for any $\pi \in \mathfrak{S}_r$ and $(u, v) \in [0, 1]^2$:

$$\chi_{\pi}(u, v) := (r - 1)! (\alpha \bar{\psi}_{\pi}(u, v) + \beta \bar{\psi}_{\pi}(v, u))$$

where $\bar{\psi}_{\pi} := \psi_{\pi} - \frac{1}{r!}$. Then:

$$\begin{align*}
\frac{1}{(r-1)!^2} \text{Cov} \left[ \chi_{\pi}(U, V), \chi_{\rho}(U, V) \right] &= \text{Cov} \left[ \alpha, \psi \right]_{\pi}(U, V) \\
&\quad + \beta \psi_{\pi}(V, U) \alpha \psi_{\rho}(U, V) + \beta \psi_{\rho}(V, U) \\
&= (\alpha^2 + \beta^2) \text{Cov} \left[ \psi_{\pi}(U, V), \psi_{\rho}(U, V) \right] \\
&\quad + 2\alpha\beta \text{Cov} \left[ \psi_{\pi}(U, V), \psi_{\rho}(V, U) \right] \\
&= (r-1)!^2 \sum_{\pi, \rho}^{p_2}.
\end{align*}$$

Hence, up to a multiplicative constant, $\sum^{p_2}$ is the Gram matrix associated to the family $(\chi_\pi)_{\pi \in \mathfrak{S}_r}$ in $L^2([0, 1]^2)$. Therefore, the rank of $\sum^{p_2}$ equals the rank of this family. Recall the notation of Lemma 7.4. For any $(u, v)$ we have:

$$1 = \sum_{\pi \in \mathfrak{S}_r} \psi_{\pi}(u, v) = \sum_{\pi \in \mathfrak{S}_r} \frac{1}{(r-1)!} \sum_{i=1}^{r} g_i(u) g_{\pi(i)}(v) = \sum_{1 \le i, j \le r} g_i(u) g_j(v).$$
Thus as in [24] we can write:

$$ \bar{\psi}_{\pi}(u, v) = \frac{-1}{r!} + \frac{1}{(r-1)!} \sum_{i=1}^{r} g_i(u) g_{\pi(i)}(v) = \frac{1}{(r-1)!} \sum_{1 \le i, j \le r} \left( \delta_{j, \pi(i)} - \frac{1}{r} \right) g_i(u) g_j(v) $$

where $\delta$ is the Kronecker symbol. Define $A^\pi$ as the matrix $(\delta_{j,\pi(i)} - \frac{1}{r})_{1 \le i, j \le r}$. Then

$$ \chi_{\pi}(u, v) = \sum_{1 \le i, j \le r} \left( \alpha A_{i,j}^{\pi} + \beta A_{i,j}^{(\pi^{-1})} \right) g_i(u) g_j(v). $$

Since the family $((u, v) \mapsto g_i(u)g_j(v))_{1 \le i, j \le r}$ is linearly independent in $L^2([0, 1]^2)$, the rank of $(\chi_\pi)_{\pi \in \mathfrak{S}_r}$ is equal to the rank of the family $(\alpha A^\pi + \beta A^{(\pi^{-1})})_{\pi \in \mathfrak{S}_r}$ in $M_r(\mathbb{R})$. As explained in [24] (see the proof of Theorem 2.5 therein), the family $(A^\pi)_{\pi \in \mathfrak{S}_r}$ spans the space of matrices with rows summing to 0 and columns summing to 0, and thus has rank $(r-1)^2$.

First suppose $p_2 < 1$, which corresponds to $\alpha \neq \beta$. This implies that each matrix in $(A^\pi)_{\pi \in \mathfrak{S}_r}$ is a linear combination of matrices in $(\alpha A^\pi + \beta A^{(\pi^{-1})})_{\pi \in \mathfrak{S}_r}$ and vice versa, hence the latter family also has rank $(r-1)^2$.

Now suppose $p_2 = 1$ i.e. $\alpha = \beta$. It is easily checked that the family $(A^\pi + A^{(\pi^{-1})})_{\pi \in \mathfrak{S}_r}$ spans the space of symmetric matrices with rows summing to 0 and columns summing to 0. Such a matrix $A$ is exactly characterized by its coefficients $A_{i,j}$ with $i \le j < r$, hence this space has dimension $r(r-1)/2$. This concludes the proof. □

**Acknowledgements** The author is very grateful to Valentin Féray for insightful discussions and valuable suggestions, and to Mohamed Slim Kammoun for helpful comments.

**Author Contributions** There is only one author for this manuscript.

**Funding** Open access funding provided by Uppsala University.

**Data Availability** No datasets were generated or analysed during the current study.

## Declarations

**Competing interests** The authors declare no competing interests.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

<figure><img src="image_26.png" /></figure>
References

1. Aldous, D., Diaconis, P.: Hammersley's interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields **103**, 199–213 (1995). https://doi.org/10.1007/BF01204214

2. Arratia, R., Barbour, A.D., Tavaré, S.: Logarithmic Combinatorial Structures: A Probabilistic Approach. European Mathematical Society, (2003)

3. Auger, N., Bouvel, M., Nicaud, C., Pivoteau, C.: 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). URL: https://hal.science/hal-01838692/

4. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. **12**(4), 1119–1178 (1999). https://doi.org/10.1090/S0894-0347-99-00307-0

5. Baik, J., Rains, E.M.: Symmetrized random permutations. In Random Matrix Models and Their Applications, pages 1–19. Cambridge University Press, (2001)

6. Betz, V., Ueltschi, D., Velenik, Y.: Random permutations with cycle weights. Ann. Appl. Probab. **21**(1), 312–331 (2011). https://doi.org/10.1214/10-AAP697

7. Bóna, M.: On three different notions of monotone subsequences. Permutation patterns **376**, 89–114 (2010)

8. Chen, L.H., Röllin, A.: Stein couplings for normal approximation. Preprint at arXiv:1003.6039, (2010). https://doi.org/10.48550/arXiv:1003.6039

9. Deuschel, J.-D., Zeitouni, O.: Limiting curves for I.I.D. records. The Annals of Probability **23**(2), 852–878 (1995). (http://www.jstor.org/stable/2245010)

10. Deuschel, J.-D., Zeitouni, O.: On increasing subsequences of I.I.D. samples. Combinatorics, Probability and Computing **8**(3), 247–263 (1999). https://doi.org/10.1017/S0963548399003776

11. Ercolani, N.M., Ueltschi, D.: Cycle structure of random permutations with cycle weights. Random Structures and Algorithms **44**(1), 109–133 (2014). https://doi.org/10.1002/rsa.20430

12. Ewens, W.J.: The sampling theory of selectively neutral alleles. Theor. Popul. Biol. **3**(1), 87–112 (1972). https://doi.org/10.1016/0040-5809(72)90035-4

13. Féray, V.: Asymptotic behavior of some statistics in Ewens random permutations. Electron. J. Probab. **18**(76), 1–32 (2013). https://doi.org/10.1214/EJP.v18.2496

14. Féray, V., Kammoun, M.S.: Asymptotic normality of pattern counts in conjugacy classes. Preprint at arXiv:2312.08756, (2023). https://doi.org/10.48550/arXiv:2312.08756

15. Fulman, J., Kim, G.B., Lee, S.: Central limit theorem for peaks of a random permutation in a fixed conjugacy class of $S_n$. Ann. Comb. **26**(1), 97–123 (2022). https://doi.org/10.1007/s00026-021-00561-4

16. Greene, C.: An extension of Schensted's theorem. Advances in Math. **14**, 254–265 (1974)

17. Guionnet, A., Kammoun, M.S.: About universality of large deviation principles for conjugacy invariant permutations. Preprint at arXiv:2312.00402, (2023). https://doi.org/10.48550/arXiv:2312.00402

18. Hamaker, Z., Rhoades, B.: Characters of local and regular permutation statistics. Preprint at arXiv:2206.06567, (2022). https://doi.org/10.48550/arXiv:2206.06567

19. Hoeffding, W.: A class of statistics with asymptotically normal distribution. Ann. Math. Stat. **19**(3), 293–325 (1948). https://doi.org/10.1214/aoms/1177730196

20. Hofer, L.: A central limit theorem for vincular permutation patterns. Discrete Mathematics & Theoretical Computer Science (2018). https://doi.org/10.23638/DMTCS-19-2-9 https://doi.org/10.23638/DMTCS-19-2-9

21. Ivanov, V., Olshanski, G.: Kerov's central limit theorem for the Plancherel measure on Young diagrams. In Symmetric functions 2001: surveys of developments and perspectives, pages 93–151. Springer, (2002). https://doi.org/10.1007/978-94-010-0524-1_3

22. Janson, S.: Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs. Ann. Probab. **16**(1), 305–312 (1988). https://doi.org/10.1214/aop/1176991903

23. Janson, S.: Large deviations for sums of partly dependent random variables. Random Structures and Algorithms **24**(3), 234–248 (2004). https://doi.org/10.1002/rsa.20008

24. Janson, S., Nakamura, B., Zeilberger, D.: On the asymptotic statistics of the number of occurrences of multiple permutation patterns. Journal of Combinatorics **6**(1), 117–143 (2015). https://doi.org/10.4310/JOC.2015.v6.n1.a8
25. Kammoun, M.S.: Monotonous subsequences and the descent process of invariant random permutations. Electron. J. Probab. 23(118), 1–31 (2018). https://doi.org/10.1214/18-EJP244

26. Kammoun, M.S.: Universality for random permutations and some other groups. Stochastic Processes and their Applications 147, 76–106 (2022). https://doi.org/10.1016/j.spa.2022.01.012

27. Kammoun, M.S.: A note on monotone subsequences and the RS image of invariant random permutations with macroscopic number of fixed points. Preprint at arXiv:2305.04787, (2023). https://doi.org/10.48550/arXiv.2305.04787

28. Kingman, J.F.C.: Random partitions in population genetics. Proc. R. Soc. Lond. Ser. A 361(1704), 1–20 (1978). https://doi.org/10.1098/rspa.1978.0089

29. Kiwi, M.: A concentration bound for the longest increasing subsequence of a randomly chosen involution. Discret. Appl. Math. 154(13), 1816–1823 (2006). https://doi.org/10.1016/j.dam.2006.03.025

30. Logan, B.F., Shepp, L.A.: A variational problem for random Young tableaux. Adv. Math. 26(2), 206–222 (1977). https://doi.org/10.1016/0001-8708(77)90030-5

31. Meliot, P.-L.: Kerov's central limit theorem for Schur-Weyl and Gelfand measures. DMTCS Proceedings, pages 669–681, (2011). https://doi.org/10.46298/dmtcs.2943

32. Petrovskaya, M.B., Leontovich, A.M.: The central limit theorem for a sequence of random variables with a slowly growing number of dependences. Theory of Probability and its Applications 27(4), 815–825 (1982). https://doi.org/10.1137/1127089

33. Romik, D.: The surprising mathematics of longest increasing subsequences. Institute of Mathematical Statistics Textbooks (4). Cambridge University Press, (2015)

34. Ross, N.: Fundamentals of Stein's method. Probab. Surv. 8, 210–293 (2011). https://doi.org/10.1214/11-PS182

35. Seppäläinen, T.: Large deviations for increasing sequences on the plane. Probab. Theory Relat. Fields 112(2), 221–244 (1998). https://doi.org/10.1007/s004400050188

36. Sjöstrand, J.: Monotone subsequences in locally uniform random permutations. Ann. Probab. 51(4), 1502–1547 (2023). https://doi.org/10.1214/23-AOP1624

37. Tsilevich, N.V.: Stationary random partitions of positive integers. Theory of Probability and Its Applications 44(1), 60–74 (2000). https://doi.org/10.1137/S0040585X97977331

38. Vershik, A.M., Kerov, S.V.: Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux. Dokl. Akad. Nauk SSSR 233(6), 1024–1027 (1977)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.