LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6.1-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The RSK union bound localizes Plancherel profiles

Statement

Let $n \geq 1$ , let $σ$ be uniform on $S_{n}$ and let $λ = sh (σ) ⊢ n$ . For every integer $L$ with $1 \leq L \leq n$ , $P (λ_{1} \geq L) \leq \frac{(\binom{n}{L})}{L!} \leq (\frac{e^{2} n}{L^{2}})^{L},$ and the same two inequalities hold for $λ_{1}^{'}$ . Consequently, for every constant $C > e$ there is $n_{0}$ such that for all $n \geq n_{0}$ $P (λ_{1} \leq C \sqrt{n} and λ_{1}^{'} \leq C \sqrt{n}) \geq 1 - 2 (\frac{e^{2}}{C^{2}})^{⌊ C \sqrt{n} ⌋ - 1} ⟶ 1,$ and on the event in question the function $x \mapsto \overset{ˉ}{λ} (x) - ∣ x ∣$ is supported in the fixed compact interval $[- C, C]$ .

Facts & Assumptions

Given: $n \geq 1$ ; $σ$ uniformly distributed on the permutations of ${1, \dots, n}$ ; $λ = sh (σ)$ the Robinson-Schensted shape, a random variable with law $P_{n}$ (The RSK shape of a uniform random permutation has the Plancherel law); an integer $L$ with $1 \leq L \leq n$ .

[F1]

The length of a longest increasing subsequence of $σ$ is $λ_{1}$ and the length of a longest decreasing subsequence is $λ_{1}^{'}$ (The Schensted theorem on longest increasing and decreasing subsequences); the uniform probability on $S_{n}$ gives every permutation weight $1 / n!$ (The uniform probability space on a nonempty finite set, Finite probability spaces, outcome weights, events, and event probabilities).

[F2]

Probability is subadditive: $P (⋃_{j} A_{j}) \leq \sum_{j} P (A_{j})$ for finitely many events (Basic identities for a probability measure).

[F3]

$(\binom{n}{L}) = \frac{n (n - 1) \dots (n - L + 1)}{L!} \leq \frac{n^{L}}{L!}$ for $0 \leq L \leq n$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ); and for real $x \geq 0$ one has $e^{x} = \sum_{j \geq 0} x^{j} / j!$ , so $e^{L} \geq L^{L} / L!$ and hence $L! \geq (L / e)^{L}$ (The power-series, product-limit, IVP, functional-equation, and Picard definitions agree).

[F4]

For a partition $λ ⊢ n$ the support of $σ_{λ}$ is contained in $[- λ_{1}^{'}, λ_{1}]$ , and for the $\sqrt{n}$ -scaled profile $\overset{ˉ}{λ}$ one has $σ_{\overset{ˉ}{λ}} (x) = n^{- 1 / 2} σ_{λ} (\sqrt{n} x)$ (Continual diagrams, Russian profiles, and the $\sqrt{n}$ -scaling of a Young diagram).

Proof

technique · direct

1.1givenF1F2algebra

Union bound: by [F1] the event ${λ_{1} \geq L}$ is contained in the union, over the $(\binom{n}{L})$ subsets $I \subseteq {1, \dots, n}$ of cardinality $L$ , of the event $A_{I}$ that the values $(σ_{i})_{i \in I}$ are increasing in the order of $I$ . For a fixed $I$ , the relative order of the $L$ distinct values $(σ_{i})_{i \in I}$ is uniform over the $L!$ orders, by symmetry of the uniform permutation (each ordering of the values on $I$ is realised by exactly $n! / L!$ permutations); hence $P (A_{I}) = 1 / L!$ , and [F2] gives $P (λ_{1} \geq L) \leq (\binom{n}{L}) / L!$ . Replacing $σ$ by the reversed word, whose uniform law is again uniform on $S_{n}$ and whose longest increasing subsequences are exactly the reversed longest decreasing subsequences of $σ$ , the same computation with [F1] gives $P (λ_{1}^{'} \geq L) \leq (\binom{n}{L}) / L!$ .

1.2givenF4algebra

Support: by [F4] the support of $σ_{λ}$ lies in $[- λ_{1}^{'}, λ_{1}]$ , and $σ_{\overset{ˉ}{λ}} (x) = n^{- 1 / 2} σ_{λ} (\sqrt{n} x)$ ; hence if $λ_{1} \leq C \sqrt{n}$ and $λ_{1}^{'} \leq C \sqrt{n}$ , then $σ_{\overset{ˉ}{λ}}$ is supported in $[- C, C]$ , and so is $x \mapsto \overset{ˉ}{λ} (x) - ∣ x ∣ = 2 σ_{\overset{ˉ}{λ}} (x)$ .

2.1givenF3step 1.1algebra

Arithmetic bound: by [F3], $(\binom{n}{L}) / L! \leq n^{L} / (L!)^{2} \leq n^{L} / (L / e)^{2 L} = (e^{2} n / L^{2})^{L}$ ; combined with step 1.1 this proves both displayed inequalities.

3.1givenF2step 1.1step 2.1algebra

Localization: let $C > e$ and put $L_{n} : = ⌊ C \sqrt{n} ⌋ + 1$ , so $L_{n} > C \sqrt{n} \geq 1$ ; for all sufficiently large $n$ one has $L_{n} \leq n$ . Since ${λ_{1} > C \sqrt{n}} \subseteq {λ_{1} \geq L_{n}}$ , steps 1.1 and 2.1 give $P (λ_{1} > C \sqrt{n}) \leq (e^{2} n / L_{n}^{2})^{L_{n}} \leq (e^{2} / C^{2})^{L_{n}} \leq (e^{2} / C^{2})^{⌊ C \sqrt{n} ⌋ - 1}$ , where $e^{2} n / L_{n}^{2} \leq e^{2} / C^{2}$ uses $L_{n} > C \sqrt{n}$ and the last inequality uses $0 < e^{2} / C^{2} < 1$ and $L_{n} \geq ⌊ C \sqrt{n} ⌋ - 1$ ; the same bound holds with $λ_{1}^{'}$ in place of $λ_{1}$ . By [F2], $P (λ_{1} > C \sqrt{n} or λ_{1}^{'} > C \sqrt{n}) \leq 2 (e^{2} / C^{2})^{⌊ C \sqrt{n} ⌋ - 1}$ , so the probability of the complementary event ${λ_{1} \leq C \sqrt{n}$ and $λ_{1}^{'} \leq C \sqrt{n}}$ is at least $1 - 2 (e^{2} / C^{2})^{⌊ C \sqrt{n} ⌋ - 1}$ ; since $0 < e^{2} / C^{2} < 1$ , this lower bound tends to $1$ .

4.1givenstep 1.2step 3.1algebra∎

Conclusion: on the event ${λ_{1} \leq C \sqrt{n}$ and $λ_{1}^{'} \leq C \sqrt{n}}$ step 1.2 shows that $x \mapsto \overset{ˉ}{λ} (x) - ∣ x ∣$ is supported in the fixed compact interval $[- C, C]$ , and step 3.1 shows that this event has probability at least $1 - 2 (e^{2} / C^{2})^{⌊ C \sqrt{n} ⌋ - 1} \to 1$ .

Depends on

Used by

Dependency tree · two levels

65 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Vladimir Ivanov and Grigori Olshanski, Kerov's central limit theorem for the Plancherel measure on Young diagrams, arXiv:math/0304010; survey-paper version in Symmetric Functions 2001, NATO Science Series II 74 (2002), 93-151 (standard reference, not scraped)
Dan Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press 2015; author-hosted manuscript of 20 August 2014 (363 pp.) (standard reference, not scraped)