young_diagram_row_lens_sublist_embedding
If the row-length list of ν is a sublist of that of μ, then the rows of ν sit inside distinct rows of μ of the same length: there is an injective map φ on row indices with μ.rowLen (φ k) = ν.rowLen k for every row k of ν.
Statement
theorem young_diagram_row_lens_sublist_embedding (μ ν : YoungDiagram)
(h : ν.rowLens.Sublist μ.rowLens) :
∃ φ : ℕ → ℕ, Function.Injective φ ∧ ∀ k, k < ν.colLen 0 → μ.rowLen (φ k) = ν.rowLen k- Source
- step towards latin_partition_is_wide
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- latin_partition_is_wideEvery Latin Young diagram is wide: if a Young diagram $\mu$ admits a Latin tableau of shape $\mu$ and type $\mu'$ (…
The proof, explained
The sublist relation between the row-length lists ν.rowLens and μ.rowLens is witnessed by an order embedding f : ℕ ↪o ℕ preserving row lengths. Choosing φ to be f ensures injectivity, and for any valid row index k of ν, the lengths of the corresponding rows match: μ.rowLen (f k) = ν.rowLen k.
The sublist hypothesis provides an order embedding f, which yields the injective row map φ and reduces the goal to matching row lengths.
By List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp, the fact that ν.rowLens is a sublist of μ.rowLens yields an order embedding f : ℕ ↪o ℕ such that ν.rowLens[i]? = μ.rowLens[f i]? for all indices i. Since order embeddings are injective, f provides the required injective function φ. We then fix an index k with k < ν.colLen 0 and need to show μ.rowLen (f k) = ν.rowLen k.
uses
List.sublist_iff_exists_orderEmbedding_getElem?_eq.mprcases List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp h with ⟨f, hf⟩ refine ⟨f, f.injective, fun k hk => ?_⟩
The index k is within bounds for ν.rowLens, that is, k < ν.rowLens.length.
By ν.length_rowLens, the length of ν.rowLens is precisely the 0-th column height ν.colLen 0. The hypothesis k < ν.colLen 0 therefore implies k < ν.rowLens.length.
uses
ν.length_rowLenshave hk_len : k < ν.rowLens.length := by rw [ν.length_rowLens] exact hk
The optional k-th entry ν.rowLens[k]? equals some (ν.rowLen k).
Because k < ν.rowLens.length, safe lookup ν.rowLens[k]? evaluates to some (ν.rowLens[k]) by List.getElem?_eq_getElem. Then YoungDiagram.get_rowLens identifies ν.rowLens[k] with the row length ν.rowLen k.
uses
List.getElem?_eq_getElem,YoungDiagram.get_rowLenshave h1 : ν.rowLens[k]? = some (ν.rowLen k) := by rw [List.getElem?_eq_getElem hk_len, YoungDiagram.get_rowLens]
The optional entry μ.rowLens[f k]? equals some (ν.rowLen k).
The sublist property guarantees ν.rowLens[k]? = μ.rowLens[f k]?. Substituting the value of ν.rowLens[k]? from the previous step gives μ.rowLens[f k]? = some (ν.rowLen k).
have h2 : μ.rowLens[f k]? = some (ν.rowLen k) := by rw [← hf k, h1]
The row length μ.rowLen (f k) equals ν.rowLen k.
By List.getElem?_eq_some_iff.mp, the identity μ.rowLens[f k]? = some (ν.rowLen k) implies that f k < μ.rowLens.length and μ.rowLens[f k] = ν.rowLen k. Rewriting the left-hand side with YoungDiagram.get_rowLens converts μ.rowLens[f k] to μ.rowLen (f k), establishing the required equality.
uses
List.getElem?_eq_some_iff.mp,YoungDiagram.get_rowLensrcases List.getElem?_eq_some_iff.mp h2 with ⟨hfk_len, h_elem⟩ rw [YoungDiagram.get_rowLens] at h_elem exact h_elem
List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp- A list l₁ is a sublist of l₂ if and only if there exists an order embedding f : ℕ ↪o ℕ such that l₁[i]? = l₂[f(i)]? for every index i.
ν.length_rowLens- The length of the row-lengths list ν.rowLens is equal to the length of the 0-th column ν.colLen 0.
List.getElem?_eq_getElem- For an index i strictly less than the length of list l, the optional element l[i]? equals some (l[i]).
YoungDiagram.get_rowLens- For any Young diagram μ and valid row index i, the i-th entry of μ.rowLens is equal to μ.rowLen i.
List.getElem?_eq_some_iff.mp- If l[i]? = some x, then i is within bounds (i < l.length) and l[i] = x.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A sublist of row lengths is realised by an injective choice of rows of the ambient diagram. -/theorem young_diagram_row_lens_sublist_embedding (μ ν : YoungDiagram) (h : ν.rowLens.Sublist μ.rowLens) : ∃ φ : ℕ → ℕ, Function.Injective φ ∧ ∀ k, k < ν.colLen 0 → μ.rowLen (φ k) = ν.rowLen k := by rcases List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp h with ⟨f, hf⟩ refine ⟨f, f.injective, fun k hk => ?_⟩ have hk_len : k < ν.rowLens.length := by rw [ν.length_rowLens] exact hk have h1 : ν.rowLens[k]? = some (ν.rowLen k) := by rw [List.getElem?_eq_getElem hk_len, YoungDiagram.get_rowLens] have h2 : μ.rowLens[f k]? = some (ν.rowLen k) := by rw [← hf k, h1] rcases List.getElem?_eq_some_iff.mp h2 with ⟨hfk_len, h_elem⟩ rw [YoungDiagram.get_rowLens] at h_elem exact h_elem