AFTD Auto-Formalizing Theoretical Domains

young_diagram_row_lens_sublist_embedding

theoremverified

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.

  1. 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.

    lines 5–6

    uses List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp

      rcases List.sublist_iff_exists_orderEmbedding_getElem?_eq.mp h with ⟨f, hf⟩
      refine ⟨f, f.injective, fun k hk => ?_⟩
  2. 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.

    lines 7–9

    uses ν.length_rowLens

      have hk_len : k < ν.rowLens.length := by
        rw [ν.length_rowLens]
        exact hk
  3. 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.

    lines 10–11

    uses List.getElem?_eq_getElem, YoungDiagram.get_rowLens

      have h1 : ν.rowLens[k]? = some (ν.rowLen k) := by
        rw [List.getElem?_eq_getElem hk_len, YoungDiagram.get_rowLens]
  4. 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).

    lines 12–13

      have h2 : μ.rowLens[f k]? = some (ν.rowLen k) := by
        rw [← hf k, h1]
  5. 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.

    lines 14–16

    uses List.getElem?_eq_some_iff.mp, YoungDiagram.get_rowLens

      rcases 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

/-- 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
See it in the graphDiscuss this resultChallenge it