LemmaStatement: Literature-sourcedProof: 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.

Monotonicity of the bumping route and standardness of the output

Statement

Let $T$ be a standard tableau with distinct real entries and let $x \notin T$ be a real number, with the notation of Row insertion and the bumping route for $T \leftarrow x$ . Then:

the bumped letters strictly increase, $x = x_{1} < x_{2} < \dots < x_{s}$ , and the route positions weakly decrease, $r_{1} \geq r_{2} \geq \dots \geq r_{s} \geq 1$ ;
the new box $b = (s, r_{s})$ is an addable node of $[shape (T)]$ , and $T \leftarrow x$ is a standard tableau of shape $shape (T) + b$ whose entries are exactly the entries of $T$ together with $x$ .

Facts & Assumptions

Given: A standard tableau $T$ with distinct real entries and a real number $x$ that is not an entry of $T$ .

[L1]

At row $i$ of $T \leftarrow x$ : if row $i$ is nonempty and some entry exceeds $x_{i}$ , then $r_{i}$ is the position of the leftmost such entry $y_{i}$ , the entry is replaced by $x_{i}$ and $x_{i + 1} : = y_{i}$ ; otherwise $x_{i}$ is appended at the right end of row $i$ , at position $λ_{i} + 1$ , and the route stops (Row insertion and the bumping route).

[L2]

For the distinct real alphabets of Row insertion and the bumping route, a standard tableau is an injective filling with strictly increasing rows and columns; its rank relabelling gives a standard tableau in the published alphabet ${1, \dots, n}$ , and $(i, j) \in [λ]$ with $(i + 1, j) \in [λ]$ implies $T (i, j) < T (i + 1, j)$ (Tableaux and standard tableaux, Partitions, English diagrams, and conjugation).

[L3]

A node $(i, λ_{i} + 1)$ is addable for $λ$ if and only if $i = 1$ or $λ_{i - 1} > λ_{i}$ ; and $[λ] \cup {(i, λ_{i} + 1)}$ is then the diagram of a partition (Removable and addable nodes).

Proof

technique · direct

1.1L1given

The bumped letters increase: when the route replaces at row $i$ , the new carried letter is $x_{i + 1} = y_{i} > x_{i}$ by the leftmost-greater choice of $r_{i}$ ; hence $x = x_{1} < x_{2} < \dots < x_{s}$ .

1.2L1L2

The positions weakly decrease: supposing the route continues from row $i$ to row $i + 1$ with $r_{i}$ defined, if row $i + 1$ has length $λ_{i + 1} \geq r_{i}$ , then the entry of $T$ at $(i + 1, r_{i})$ lies below the old entry $y_{i} = x_{i + 1}$ of $(i, r_{i})$ , so it exceeds $x_{i + 1}$ ; the leftmost entry of row $i + 1$ exceeding $x_{i + 1}$ is therefore at a position $r_{i + 1} \leq r_{i}$ . If instead $λ_{i + 1} < r_{i}$ , the next step either bumps at $r_{i + 1} \leq λ_{i + 1}$ or appends at $r_{i + 1} = λ_{i + 1} + 1$ ; both give $r_{i + 1} \leq r_{i}$ .

2.1step 1.2L1

The route terminates at a well-defined row $s$ : the positions are positive integers with $r_{1} \leq λ_{1} + 1$ , they weakly decrease along the visited rows, and after the last nonempty row the next row is empty and the letter is appended, so only finitely many rows are visited and the appended new box is $b = (s, r_{s})$ with $r_{s} = λ_{s} + 1$ .

3.1step 1.2step 2.1L3

The new box is addable: if $s = 1$ then $b = (1, λ_{1} + 1)$ is addable by [L3]; if $s > 1$ , the route reached row $s$ after replacing at row $s - 1$ , so $r_{s - 1} \leq λ_{s - 1}$ and $r_{s} = λ_{s} + 1 \leq r_{s - 1}$ by step 1.2, whence $λ_{s} < λ_{s - 1}$ and $b$ is addable by [L3].

3.2step 2.1L1

The entries of the output are exactly the entries of $T$ together with $x$ : each row visit writes the carried letter $x_{i}$ into a box of row $i$ and removes the entry $y_{i} = x_{i + 1}$ from it, and the final visit appends $x_{s}$ into the new box without removing anything; thus the multiset of entries changes from that of $T$ by adding $x_{1} = x$ and deleting nothing, and the shape grows by the single box $b$ .

4.1step 1.1step 1.2step 3.1L1L2

The output is standard: the replaced entries keep strictly increasing rows because $x_{i}$ is placed at the leftmost position whose old entry exceeded it, so its left neighbour is $< x_{i}$ and its right neighbour is larger than the displaced entry and hence $> x_{i}$ , and an appended letter exceeds every entry of its row; columns remain strictly increasing because at each replaced box $(i, r_{i})$ the entry above is either a previously placed bumped letter $x_{i - 1} < x_{i}$ or an unchanged entry lying left of the old entry $x_{i}$ in row $i - 1$ , hence smaller than $x_{i}$ , and the entry below is either the newly placed $x_{i + 1} > x_{i}$ (when $r_{i + 1} = r_{i}$ ) or the unchanged entry at $(i + 1, r_{i})$ , which exceeds the old entry $y_{i} = x_{i + 1}$ and hence $x_{i}$ (when $r_{i + 1} < r_{i}$ ), while the appended box $(s, λ_{s} + 1)$ lies below either a placed $x_{s - 1} < x_{s}$ or an unchanged entry left of the old entry $x_{s}$ of $(s - 1, r_{s - 1})$ ; all other boxes are unchanged.

5.1step 3.1step 3.2step 4.1∎

The output is a standard tableau of shape $shape (T) + b$ with entries those of $T$ plus $x$ , as asserted.

Depends on

Used by

Column insertion Definition
Basic subsequences of the first row Lemma
Reversing a word transposes its insertion tableau Lemma
Row and column insertion commute Lemma
Row insertion and reverse deletion are inverse Lemma
The recording tableau is standard Lemma
The Robinson-Schensted correspondence Theorem
The RSK correspondence for two-line arrays Theorem
The Schensted theorem on longest increasing and decreasing subsequences Theorem

Dependency tree · two levels

5 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

C. Schensted, Longest Increasing and Decreasing Subsequences, Canadian Journal of Mathematics 13 (1961), 179-191 (13 pp.) (standard reference, not scraped)
Donald E. Knuth, Permutations, Matrices, and Generalized Young Tableaux, Pacific Journal of Mathematics 34 (1970), 709-727 (standard reference, not scraped)
David A. Craven, Groups, Geometries and Representation Theory (Spring Term 2013 lecture notes, 42 pp.) (standard reference, not scraped)