AFTD Auto-Formalizing Theoretical Domains

latin_partition_is_wide

theoremverifiedformalization

Every Latin Young diagram is wide: if a Young diagram $\mu$ admits a Latin tableau of shape $\mu$ and type $\mu'$ (is_latin_partition μ), then $\mu$ is wide (is_wide_partition μ).

Statement

theorem latin_partition_is_wide (μ : YoungDiagram) (h : is_latin_partition μ) : is_wide_partition μ
Formalizes
arXiv:2610.29291 Section 1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • is_wide_partitionA Young diagram $d$ is wide if for every Young diagram $\mu$ whose list of row lengths $\mu.\text{rowLens}$ is a sublist of…
  • is_latin_partitionA partition $\lambda$ is Latin if there exists a Latin tableau of shape $\lambda$ and type $\lambda'$.
  • young_diagram_row_lens_sublist_embeddingIf 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…
  • is_latin_tableauA filling $T$ of a Young diagram $\lambda$ is a Latin tableau of shape $\lambda$ and type $\lambda'$ if each row $i$ contains entries from…
  • young_diagram_dominates_conjugateA partition $\mu$ dominates its conjugate partition $\mu'$, meaning prefix sums of row lengths are at least prefix sums of column lengths.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For every Young diagram μ, if μ is a Latin partition (meaning there exists a tableau T : ℕ → ℕ → ℕ on μ such that each cell (i, j) ∈ μ satisfies 1 ≤ T i j ≤ μ.rowLen i, with all entries in any row pairwise distinct and all entries in any column pairwise distinct), then μ is a wide partition (meaning for every Young diagram μ', if the list of row lengths of μ' is a sublist of the list of row lengths of μ, then μ' dominates its conjugate diagram).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that every Latin Young diagram μ is wide, we prove that any subpartition ν ⊆ μ dominates its conjugate: for all k, the sum of the first k row lengths of ν is at least the sum of the first k column lengths. The argument embeds ν into μ via a strictly monotonic row map φ and considers the set S of cells in ν whose tableau label T(φ(i), j) is at most k. Summing fiberwise by rows gives |S| = ∑_i min(ν.rowLen(i), k) because each row contains a permutation of 1, ..., ν.rowLen(i); summing fiberwise by columns gives |S| ≤ ∑_j min(ν.colLen(j), k) because column entries are distinct. Equating these minimum sums to the respective conjugate prefix sums via counting formulas establishes dominance.

  1. Left-folding addition over [0, ..., k - 1] computes the finite sum ∑_{i < k} f(i).

    By induction on the list, foldl addition with initial accumulator s produces s plus the list sum; applying this with s = 0 and using induction on k establishes the equality with the Finset sum.

    lines 4–15

    uses List.foldl_cons, add_assoc, zero_add, List.range_succ, Finset.sum_range_succ

      have h (l : List ℕ) (s : ℕ) : List.foldl (fun acc r => acc + f r) s l = s + (l.map f).sum := by
        induction l generalizing s with
        | nil => simp
        | cons x xs ih =>
          simp only [List.foldl_cons, List.map_cons, List.sum_cons]
          rw [ih, add_assoc]
      rw [h, zero_add]
      induction k with
      | zero => simp
      | succ k ih =>
        rw [List.range_succ, List.map_append, List.sum_append, ih, Finset.sum_range_succ]
        simp
  2. The number of cells in ν with column index strictly less than k equals the sum of column lengths ∑_{j < k} ν.colLen(j).

    We partition the cells in columns < k fiberwise by their column coordinate j < k. Each fiber is precisely the j-th column of ν, whose cardinality is ν.colLen(j).

    lines 20–38

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_congr, colLen_eq_card

      let s := ν.cells.filter (fun c => c.2 < k)
      have hmaps : Set.MapsTo Prod.snd (s : Set (ℕ × ℕ)) (Finset.range k : Set ℕ) := by
        intro c hc
        simp only [s, Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hc ⊢
        exact hc.2
      have h := Finset.card_eq_sum_card_fiberwise (s := s) (t := Finset.range k) (f := Prod.snd) hmaps
      rw [h]
      apply Finset.sum_congr rfl
      intro j hj
      simp only [Finset.mem_range] at hj
      have hfiber : (s.filter (fun c => c.2 = j)) = ν.col j := by
        ext ⟨a, b⟩
        simp only [s, Finset.mem_filter, mem_cells, mem_col_iff]
        constructor
        · rintro ⟨⟨h1, _⟩, rfl⟩
          exact ⟨h1, rfl⟩
        · rintro ⟨h1, rfl⟩
          exact ⟨⟨h1, hj⟩, rfl⟩
      rw [hfiber, colLen_eq_card]
  3. The number of cells in ν with column index strictly less than k equals the sum over all rows of min(ν.rowLen(i), k).

    We partition the same set of cells fiberwise by their row coordinate i < ν.colLen(0). Each fiber consists of cells (i, b) with b < ν.rowLen(i) and b < k, which forms a set of size min(ν.rowLen(i), k).

    lines 43–59

    uses mem_iff_lt_colLen, Finset.card_eq_sum_card_fiberwise, Finset.sum_congr, Finset.card_product, Finset.card_singleton, Finset.card_range, one_mul

      let s := ν.cells.filter (fun c => c.2 < k)
      have hmaps : Set.MapsTo Prod.fst (s : Set (ℕ × ℕ)) (Finset.range (ν.colLen 0) : Set ℕ) := by
        intro c hc
        simp only [s, Finset.mem_coe, Finset.mem_filter, Finset.mem_range, mem_cells] at hc ⊢
        rw [mem_iff_lt_colLen] at hc
        exact hc.1.trans_le (ν.colLen_anti 0 c.2 (Nat.zero_le c.2))
      have h := Finset.card_eq_sum_card_fiberwise (s := s) (t := Finset.range (ν.colLen 0)) (f := Prod.fst) hmaps
      rw [h]
      apply Finset.sum_congr rfl
      intro i hi
      simp only [Finset.mem_range] at hi
      have hfiber : (s.filter (fun c => c.1 = i)) = {i} ×ˢ Finset.range (min (ν.rowLen i) k) := by
        ext ⟨a, b⟩
        simp only [s, Finset.mem_filter, mem_cells, Finset.mem_product, Finset.mem_singleton,
          Finset.mem_range, mem_iff_lt_rowLen, lt_min_iff]
        aesop
      rw [hfiber, Finset.card_product, Finset.card_singleton, Finset.card_range, one_mul]
  4. The column prefix sum ∑_{j < k} ν.colLen(j) equals the sum of row minimums ∑_{i} min(ν.rowLen(i), k).

    Both sides express the cardinality of the set of cells of ν with column index strictly less than k, equating the results of the two counting methods.

    line 64

    uses latin_partition_is_wide_col_card, latin_partition_is_wide_row_min_sum

      rw [← latin_partition_is_wide_col_card, latin_partition_is_wide_row_min_sum]
  5. The row prefix sum ∑_{i < k} ν.rowLen(i) equals the sum of column minimums ∑_{j} min(ν.colLen(j), k).

    Applying the previous column-sum identity to the transpose νᵀ and using that transposition interchanges row and column lengths gives the dual formula for row sums.

    lines 69–71

    uses latin_partition_is_wide_sum_col_eq_sum_min_row, colLen_transpose, rowLen_transpose

      have h := latin_partition_is_wide_sum_col_eq_sum_min_row ν.transpose k
      simp only [colLen_transpose, rowLen_transpose] at h
      exact h
  6. If l₁ is a sublist of l₂, there is a strictly monotonic function φ embedding l₁ into l₂ such that l₂[φ(i)] = l₁[i].

    By structural induction on the sublist relation: the empty case uses the identity, prepending to the target list shifts φ by succ, and prepending to both lists maps 0 to 0 and n + 1 to φ(n) + 1.

    lines 77–99

    uses strictMono_id, strictMono_nat_of_lt_succ, Nat.succ_lt_succ, Nat.lt_succ_self

        refine ⟨id, strictMono_id, fun i hi => (Nat.not_lt_zero i hi).elim⟩
      | l₁, a :: l₂, List.Sublist.cons _ h => by
        obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed h
        refine ⟨Nat.succ ∘ φ, strictMono_nat_of_lt_succ fun n => ?_, fun i hi => ?_⟩
        · simp only [Function.comp_apply]
          exact Nat.succ_lt_succ (hφ_mono (Nat.lt_succ_self n))
        · simp only [Function.comp_apply, List.getElem?_cons_succ]
          exact hφ_eq i hi
      | _, _, List.Sublist.cons_cons a h => by
        obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed h
        let φ' : ℕ → ℕ := fun n => match n with
          | 0 => 0
          | n + 1 => φ n + 1
        refine ⟨φ', strictMono_nat_of_lt_succ fun n => ?_, fun i hi => ?_⟩
        · cases n
          · simp only [φ', Nat.zero_lt_succ]
          · simp only [φ', add_lt_add_iff_right]
            exact hφ_mono (Nat.lt_succ_self _)
        · cases i
          · simp [φ']
          · simp only [List.length_cons, Nat.succ_lt_succ_iff] at hi
            simp only [φ', List.getElem?_cons_succ]
            exact hφ_eq _ hi
  7. If g maps {0, ..., m - 1} injectively into {1, ..., m}, the number of elements with g(j) ≤ k is min(m, k).

    Since the domain and codomain have equal cardinality m, injectivity implies g is a bijection onto {1, ..., m}. The subset where g(j) ≤ k maps bijectively onto {1, ..., min(m, k)}, which has cardinality min(m, k).

    lines 106–151

    uses Nat.card_Ioc, Finset.card_image_of_injOn, Finset.eq_of_subset_of_card_le, Nat.sub_zero

      let s := Finset.range m
      let t := Finset.Ioc 0 m
      have ht_card : t.card = m := Nat.card_Ioc 0 m
      have h_img_sub : s.image g ⊆ t := by
        intro y hy
        rw [Finset.mem_image] at hy
        obtain ⟨x, hx, rfl⟩ := hy
        rw [Finset.mem_range] at hx
        simp only [t, Finset.mem_Ioc]
        have := hg_maps x hx
        omega
      have h_img_card : (s.image g).card = m := by
        rw [Finset.card_image_of_injOn]
        · simp [s]
        · intro x hx y hy hxy
          rw [Finset.mem_coe, Finset.mem_range] at hx hy
          exact hg_inj x hx y hy hxy
      have h_img_eq : s.image g = t := by
        apply Finset.eq_of_subset_of_card_le h_img_sub
        rw [h_img_card, ht_card]
      have h_filter_img : ((s.filter (fun j => g j ≤ k)).image g) = t.filter (fun v => v ≤ k) := by
        ext v
        simp only [Finset.mem_image, Finset.mem_filter, s, Finset.mem_range]
        constructor
        · rintro ⟨j, ⟨hj, hgj⟩, rfl⟩
          have := hg_maps j hj
          simp only [t, Finset.mem_Ioc]
          omega
        · rintro ⟨hv_t, hvk⟩
          have hv_img : v ∈ s.image g := by rw [h_img_eq]; exact hv_t
          rw [Finset.mem_image] at hv_img
          obtain ⟨j, hj, rfl⟩ := hv_img
          rw [Finset.mem_range] at hj
          exact ⟨j, ⟨hj, hvk⟩, rfl⟩
      have h_inj_filter : Set.InjOn g ((s.filter (fun j => g j ≤ k)) : Set ℕ) := by
        intro x hx y hy hxy
        rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hx hy
        exact hg_inj x hx.1 y hy.1 hxy
      have h_card_eq : ((s.filter (fun j => g j ≤ k)).image g).card = (s.filter (fun j => g j ≤ k)).card :=
        Finset.card_image_of_injOn h_inj_filter
      rw [← h_card_eq, h_filter_img]
      have h_ioc : (t.filter (fun v => v ≤ k)) = Finset.Ioc 0 (min m k) := by
        ext v
        simp only [t, Finset.mem_filter, Finset.mem_Ioc, le_min_iff]
        omega
      rw [h_ioc, Nat.card_Ioc, Nat.sub_zero]
  8. If h maps {0, ..., m - 1} injectively into positive integers, the number of elements with h(i) ≤ k is at most min(m, k).

    The filtered subset has cardinality at most m (as a subset of {0, ..., m - 1}) and at most k (since h maps it injectively into {1, ..., k}). Hence its size is at most min(m, k).

    lines 158–175

    uses Finset.filter_subset, Finset.card_le_card, Finset.card_range, Finset.card_le_card_of_injOn, Nat.card_Ioc, Nat.sub_zero, le_min

      let s := (Finset.range m).filter (fun i => h i ≤ k)
      have h1 : s.card ≤ m := by
        have : s ⊆ Finset.range m := Finset.filter_subset _ _
        exact (Finset.card_le_card this).trans_eq (Finset.card_range m)
      have h2 : s.card ≤ k := by
        have h_maps : Set.MapsTo h (s : Set ℕ) (Finset.Ioc 0 k : Set ℕ) := by
          intro i hi
          rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hi
          simp only [Finset.mem_coe, Finset.mem_Ioc]
          have := hh_maps i hi.1
          omega
        have h_inj : Set.InjOn h (s : Set ℕ) := by
          intro x hx y hy hxy
          rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hx hy
          exact hh_inj x hx.1 y hy.1 hxy
        have := Finset.card_le_card_of_injOn h h_maps h_inj
        rwa [Nat.card_Ioc, Nat.sub_zero] at this
      exact le_min h1 h2
  9. For any subdiagram ν whose row lengths form a sublist of μ's, there is a strictly monotonic row embedding φ preserving row lengths: ν.rowLen(i) = μ.rowLen(φ(i)).

    Unpacking the Latin tableau T on μ and applying the sublist embedding lemma to the row lengths of ν and μ gives a strictly monotonic map φ. Comparing the elements of the lists confirms that each row length matches.

    lines 179–198

    uses latin_partition_is_wide_sublist_embed, YoungDiagram.length_rowLens, List.getElem?_eq_getElem, List.getElem?_eq_none, Option.some_injective, YoungDiagram.get_rowLens

      obtain ⟨T, hT⟩ := h
      intro ν hsub
      obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed hsub
      have hφ_row : ∀ i < ν.colLen 0, φ i < μ.colLen 0 ∧ ν.rowLen i = μ.rowLen (φ i) := by
        intro i hi
        rw [← YoungDiagram.length_rowLens] at hi
        have h_opt := hφ_eq i hi
        have h_some : ν.rowLens[i]? = some ν.rowLens[i] := List.getElem?_eq_getElem hi
        rw [h_some] at h_opt
        have h_len : φ i < μ.rowLens.length := by
          by_contra h_ge
          rw [List.getElem?_eq_none (not_lt.mp h_ge)] at h_opt
          contradiction
        have h_val : μ.rowLens[φ i] = ν.rowLens[i] := by
          have := List.getElem?_eq_getElem h_len
          rw [h_opt] at this
          exact Option.some_injective _ this.symm
        rw [YoungDiagram.length_rowLens] at h_len
        rw [YoungDiagram.get_rowLens, YoungDiagram.get_rowLens] at h_val
        exact ⟨h_len, h_val.symm⟩
  10. Every cell (i, j) of ν maps to a valid cell (φ(i), j) of μ under the row embedding.

    A cell (i, j) belongs to ν if and only if j < ν.rowLen(i). Since row lengths are preserved by φ, j < μ.rowLen(φ(i)), so (φ(i), j) is a cell of μ.

    lines 199–206

    uses YoungDiagram.mem_iff_lt_colLen, Nat.zero_le, YoungDiagram.mem_iff_lt_rowLen

      have hcell_mem : ∀ {i j : ℕ}, (i, j) ∈ ν → (φ i, j) ∈ μ := by
        intro i j hcell
        have hi : i < ν.colLen 0 := by
          rw [YoungDiagram.mem_iff_lt_colLen] at hcell
          exact hcell.trans_le (ν.colLen_anti 0 j (Nat.zero_le j))
        have hlen := (hφ_row i hi).2
        rw [YoungDiagram.mem_iff_lt_rowLen] at hcell ⊢
        rwa [← hlen]
  11. Dominance translates to Finset sums, and the cell subset S = {c ∈ ν | T(φ(c.1), c.2) ≤ k} projects onto valid row and column index sets.

    We rewrite the foldl prefix sums to Finset sums using latin_partition_is_wide_foldl_sum and define S as the set of cells of ν whose restricted tableau value is at most k. Monotonicity of column and row lengths ensures the row and column coordinates are bounded by ν.colLen(0) and ν.rowLen(0).

    lines 207–220

    uses latin_partition_is_wide_foldl_sum, YoungDiagram.mem_cells, YoungDiagram.mem_iff_lt_colLen, YoungDiagram.mem_iff_lt_rowLen, Nat.zero_le

      intro k
      simp only [ge_iff_le]
      rw [latin_partition_is_wide_foldl_sum, latin_partition_is_wide_foldl_sum]
      let S := ν.cells.filter (fun c => T (φ c.1) c.2 ≤ k)
      have hmaps_row : Set.MapsTo Prod.fst (S : Set (ℕ × ℕ)) (Finset.range (ν.colLen 0) : Set ℕ) := by
        intro c hc
        rw [Finset.mem_coe, Finset.mem_filter, YoungDiagram.mem_cells, YoungDiagram.mem_iff_lt_colLen] at hc
        rw [Finset.mem_coe, Finset.mem_range]
        exact hc.1.trans_le (ν.colLen_anti 0 c.2 (Nat.zero_le c.2))
      have hmaps_col : Set.MapsTo Prod.snd (S : Set (ℕ × ℕ)) (Finset.range (ν.rowLen 0) : Set ℕ) := by
        intro c hc
        rw [Finset.mem_coe, Finset.mem_filter, YoungDiagram.mem_cells, YoungDiagram.mem_iff_lt_rowLen] at hc
        rw [Finset.mem_coe, Finset.mem_range]
        exact hc.1.trans_le (ν.rowLen_anti 0 c.1 (Nat.zero_le c.1))
  12. Counting S by rows shows that |S| equals the sum of row minimums ∑_{i < ν.colLen(0)} min(ν.rowLen(i), k).

    We partition S by row index i. For each row, the tableau entries j ↦ T(φ(i), j) form a permutation of {1, ..., ν.rowLen(i)}. By latin_partition_is_wide_perm_filter, exactly min(ν.rowLen(i), k) cells in that row have entry at most k, and summing over rows gives the total cardinality.

    lines 221–242

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_congr, Finset.card_product, Finset.card_singleton, one_mul, latin_partition_is_wide_perm_filter, YoungDiagram.mem_iff_lt_rowLen

      have hS_row : S.card = ∑ i ∈ Finset.range (ν.colLen 0), min (ν.rowLen i) k := by
        rw [Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.range (ν.colLen 0)) (f := Prod.fst) hmaps_row]
        apply Finset.sum_congr rfl
        intro i hi
        simp only [Finset.mem_range] at hi
        have hfib : (S.filter (fun c => c.1 = i)) = {i} ×ˢ ((Finset.range (ν.rowLen i)).filter (fun j => T (φ i) j ≤ k)) := by
          ext ⟨a, b⟩
          simp only [S, Finset.mem_filter, YoungDiagram.mem_cells, Finset.mem_product, Finset.mem_singleton,
            Finset.mem_range, YoungDiagram.mem_iff_lt_rowLen]
          aesop
        rw [hfib, Finset.card_product, Finset.card_singleton, one_mul]
        apply latin_partition_is_wide_perm_filter
        · intro j hj
          have hc : (i, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]
          have hc_μ := hcell_mem hc
          have h1 := hT.1 hc_μ
          have hlen := (hφ_row i hi).2
          rwa [← hlen] at h1
        · intro j₁ hj₁ j₂ hj₂ heq
          have hc₁ : (i, j₁) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]
          have hc₂ : (i, j₂) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]
          exact hT.2.1 (hcell_mem hc₁) (hcell_mem hc₂) heq
  13. Bounding S by columns shows that |S| is at most the sum of column minimums ∑_{j < ν.rowLen(0)} min(ν.colLen(j), k).

    We partition S by column index j. Along each column, the entries i ↦ T(φ(i), j) are distinct positive integers because T has distinct column entries and φ is strictly monotonic. By latin_partition_is_wide_col_filter_le, at most min(ν.colLen(j), k) cells in column j have entry at most k, yielding the upper bound.

    lines 243–262

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_le_sum, Finset.card_product, Finset.card_singleton, latin_partition_is_wide_col_filter_le, YoungDiagram.mem_iff_lt_colLen

      have hS_col : S.card ≤ ∑ j ∈ Finset.range (ν.rowLen 0), min (ν.colLen j) k := by
        rw [Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.range (ν.rowLen 0)) (f := Prod.snd) hmaps_col]
        apply Finset.sum_le_sum
        intro j hj
        simp only [Finset.mem_range] at hj
        have hfib : (S.filter (fun c => c.2 = j)) = ((Finset.range (ν.colLen j)).filter (fun i => T (φ i) j ≤ k)) ×ˢ {j} := by
          ext ⟨a, b⟩
          simp only [S, Finset.mem_filter, YoungDiagram.mem_cells, Finset.mem_product, Finset.mem_singleton,
            Finset.mem_range, YoungDiagram.mem_iff_lt_colLen]
          aesop
        rw [hfib, Finset.card_product, Finset.card_singleton, mul_one]
        apply latin_partition_is_wide_col_filter_le
        · intro i hi
          have hc : (i, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]
          exact (hT.1 (hcell_mem hc)).1
        · intro i₁ hi₁ i₂ hi₂ heq
          have hc₁ : (i₁, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]
          have hc₂ : (i₂, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]
          have h_phi_eq := hT.2.2 (hcell_mem hc₁) (hcell_mem hc₂) heq
          exact hφ_mono.injective h_phi_eq
  14. The prefix sum of row lengths dominates the prefix sum of column lengths, showing that ν dominates its conjugate and μ is wide.

    From the row count and column bound, ∑_i min(ν.rowLen(i), k) = |S| ≤ ∑_j min(ν.colLen(j), k). Applying the conversion lemmas rewrites these minimum sums into the prefix sums ∑_{j < k} ν.colLen(j) and ∑_{i < k} ν.rowLen(i), proving that the row prefix sum is at least the column prefix sum.

    lines 263–264

    uses latin_partition_is_wide_sum_col_eq_sum_min_row, latin_partition_is_wide_sum_row_eq_sum_min_col

      rw [latin_partition_is_wide_sum_col_eq_sum_min_row, latin_partition_is_wide_sum_row_eq_sum_min_col]
      linarith
List.foldl_cons
folding a function over a cons cell a :: l with accumulator b equals folding over l with updated accumulator f(b, a)
add_assoc
addition is associative: (a + b) + c = a + (b + c)
zero_add
zero is a left identity for addition: 0 + a = a
List.range_succ
the list range up to n + 1 equals the range up to n followed by [n]
Finset.sum_range_succ
a sum over range (n + 1) equals the sum over range n plus the term at n
Finset.card_eq_sum_card_fiberwise
the cardinality of a finite set s mapped to t equals the sum over b ∈ t of the cardinalities of the fibers of b
Finset.sum_congr
two sums over the same finite set are equal if their terms agree on every element
colLen_eq_card
the length of column j in a Young diagram equals the cardinality of the cell set of column j
mem_iff_lt_colLen
a cell (i, j) belongs to a Young diagram if and only if i is strictly less than the length of column j
YoungDiagram.mem_iff_lt_colLen
a cell (i, j) belongs to a Young diagram μ if and only if i is strictly less than the length of column j of μ
Finset.card_product
the cardinality of a Cartesian product of two finite sets equals the product of their cardinalities
Finset.card_singleton
the cardinality of a singleton set is 1
Finset.card_range
the cardinality of Finset.range n is n
one_mul
one is a left identity for multiplication: 1 * a = a
latin_partition_is_wide_col_card
the number of cells in ν with column index strictly less than k equals the sum of column lengths up to k
latin_partition_is_wide_row_min_sum
the number of cells in ν with column index strictly less than k equals the sum over all rows of min(rowLen(i), k)
latin_partition_is_wide_sum_col_eq_sum_min_row
the sum of column lengths up to k equals the sum over all rows of min(rowLen(i), k)
colLen_transpose
the column lengths of the transpose of a Young diagram are the row lengths of the original diagram
rowLen_transpose
the row lengths of the transpose of a Young diagram are the column lengths of the original diagram
strictMono_id
the identity function is strictly monotonic
strictMono_nat_of_lt_succ
a function on ℕ is strictly monotonic if each value is strictly less than the next
Nat.succ_lt_succ
if n < m, then n + 1 < m + 1
Nat.lt_succ_self
every natural number n is strictly less than n + 1
Nat.card_Ioc
the cardinality of the half-open interval (a, b] is b - a
Finset.card_image_of_injOn
the image of a finite set under a map injective on that set has the same cardinality as the original set
Finset.eq_of_subset_of_card_le
if s ⊆ t and |t| ≤ |s| for finite sets, then s = t
Nat.sub_zero
subtracting zero from a natural number leaves it unchanged: n - 0 = n
Finset.filter_subset
filtering a finite set produces a subset of the original set
Finset.card_le_card
if s ⊆ t for finite sets, then |s| ≤ |t|
Finset.card_le_card_of_injOn
if a map between finite sets is injective on s, then |s| ≤ |t|
le_min
if c ≤ a and c ≤ b, then c ≤ min(a, b)
latin_partition_is_wide_sublist_embed
if list l₁ is a sublist of l₂, there is a strictly monotonic index map φ such that l₂[φ i] = l₁[i]
YoungDiagram.length_rowLens
the number of row lengths in a Young diagram equals the length of its zeroth column
List.getElem?_eq_getElem
looking up an in-bounds index in a list with getElem? returns some of the element
List.getElem?_eq_none
looking up an out-of-bounds index in a list with getElem? returns none
Option.some_injective
the Option.some constructor is injective
YoungDiagram.get_rowLens
the i-th element of the rowLens list of a Young diagram equals its i-th row length
Nat.zero_le
zero is less than or equal to any natural number
YoungDiagram.mem_iff_lt_rowLen
a cell (i, j) belongs to a Young diagram μ if and only if j is strictly less than the length of row i of μ
latin_partition_is_wide_foldl_sum
left-folding addition of f over range k equals the sum of f over Finset.range k
YoungDiagram.mem_cells
a coordinate pair belongs to the finset of cells of a Young diagram iff it is in the diagram
latin_partition_is_wide_perm_filter
an injective map from {0, ..., m - 1} to {1, ..., m} has exactly min(m, k) elements with value ≤ k
Finset.sum_le_sum
if f(i) ≤ g(i) for all elements i of a finite set, then the sum of f is at most the sum of g
latin_partition_is_wide_col_filter_le
an injective map from {0, ..., m - 1} into positive integers has at most min(m, k) elements with value ≤ k
latin_partition_is_wide_sum_row_eq_sum_min_col
the sum of row lengths up to k equals the sum over all columns of min(colLen(j), k)

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

open YoungDiagram inlemma latin_partition_is_wide_foldl_sum (f : ℕ → ℕ) (k : ℕ) :    List.foldl (fun s r => s + f r) 0 (List.range k) = ∑ i ∈ Finset.range k, f i := by  have h (l : List ℕ) (s : ℕ) : List.foldl (fun acc r => acc + f r) s l = s + (l.map f).sum := by    induction l generalizing s with    | nil => simp    | cons x xs ih =>      simp only [List.foldl_cons, List.map_cons, List.sum_cons]      rw [ih, add_assoc]  rw [h, zero_add]  induction k with  | zero => simp  | succ k ih =>    rw [List.range_succ, List.map_append, List.sum_append, ih, Finset.sum_range_succ]    simpopen YoungDiagram inlemma latin_partition_is_wide_col_card (ν : YoungDiagram) (k : ℕ) :    (ν.cells.filter (fun c => c.2 < k)).card = ∑ j ∈ Finset.range k, ν.colLen j := by  let s := ν.cells.filter (fun c => c.2 < k)  have hmaps : Set.MapsTo Prod.snd (s : Set (ℕ × ℕ)) (Finset.range k : Set ℕ) := by    intro c hc    simp only [s, Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hc ⊢    exact hc.2  have h := Finset.card_eq_sum_card_fiberwise (s := s) (t := Finset.range k) (f := Prod.snd) hmaps  rw [h]  apply Finset.sum_congr rfl  intro j hj  simp only [Finset.mem_range] at hj  have hfiber : (s.filter (fun c => c.2 = j)) = ν.col j := by    ext ⟨a, b⟩    simp only [s, Finset.mem_filter, mem_cells, mem_col_iff]    constructor    · rintro ⟨⟨h1, _⟩, rfl⟩      exact ⟨h1, rfl⟩    · rintro ⟨h1, rfl⟩      exact ⟨⟨h1, hj⟩, rfl⟩  rw [hfiber, colLen_eq_card]open YoungDiagram inlemma latin_partition_is_wide_row_min_sum (ν : YoungDiagram) (k : ℕ) :    (ν.cells.filter (fun c => c.2 < k)).card = ∑ i ∈ Finset.range (ν.colLen 0), min (ν.rowLen i) k := by  let s := ν.cells.filter (fun c => c.2 < k)  have hmaps : Set.MapsTo Prod.fst (s : Set (ℕ × ℕ)) (Finset.range (ν.colLen 0) : Set ℕ) := by    intro c hc    simp only [s, Finset.mem_coe, Finset.mem_filter, Finset.mem_range, mem_cells] at hc ⊢    rw [mem_iff_lt_colLen] at hc    exact hc.1.trans_le (ν.colLen_anti 0 c.2 (Nat.zero_le c.2))  have h := Finset.card_eq_sum_card_fiberwise (s := s) (t := Finset.range (ν.colLen 0)) (f := Prod.fst) hmaps  rw [h]  apply Finset.sum_congr rfl  intro i hi  simp only [Finset.mem_range] at hi  have hfiber : (s.filter (fun c => c.1 = i)) = {i} ×ˢ Finset.range (min (ν.rowLen i) k) := by    ext ⟨a, b⟩    simp only [s, Finset.mem_filter, mem_cells, Finset.mem_product, Finset.mem_singleton,      Finset.mem_range, mem_iff_lt_rowLen, lt_min_iff]    aesop  rw [hfiber, Finset.card_product, Finset.card_singleton, Finset.card_range, one_mul]open YoungDiagram inlemma latin_partition_is_wide_sum_col_eq_sum_min_row (ν : YoungDiagram) (k : ℕ) :    ∑ j ∈ Finset.range k, ν.colLen j = ∑ i ∈ Finset.range (ν.colLen 0), min (ν.rowLen i) k := by  rw [← latin_partition_is_wide_col_card, latin_partition_is_wide_row_min_sum]open YoungDiagram inlemma latin_partition_is_wide_sum_row_eq_sum_min_col (ν : YoungDiagram) (k : ℕ) :    ∑ i ∈ Finset.range k, ν.rowLen i = ∑ j ∈ Finset.range (ν.rowLen 0), min (ν.colLen j) k := by  have h := latin_partition_is_wide_sum_col_eq_sum_min_row ν.transpose k  simp only [colLen_transpose, rowLen_transpose] at h  exact hopen YoungDiagram inlemma latin_partition_is_wide_sublist_embed {α : Type*} : ∀ {l₁ l₂ : List α}, l₁.Sublist l₂ →    ∃ φ : ℕ → ℕ, StrictMono φ ∧ (∀ i < l₁.length, l₂[φ i]? = l₁[i]?)  | [], [], List.Sublist.slnil => by    refine ⟨id, strictMono_id, fun i hi => (Nat.not_lt_zero i hi).elim⟩  | l₁, a :: l₂, List.Sublist.cons _ h => by    obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed h    refine ⟨Nat.succ ∘ φ, strictMono_nat_of_lt_succ fun n => ?_, fun i hi => ?_⟩    · simp only [Function.comp_apply]      exact Nat.succ_lt_succ (hφ_mono (Nat.lt_succ_self n))    · simp only [Function.comp_apply, List.getElem?_cons_succ]      exact hφ_eq i hi  | _, _, List.Sublist.cons_cons a h => by    obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed h    let φ' : ℕ → ℕ := fun n => match n with      | 0 => 0      | n + 1 => φ n + 1    refine ⟨φ', strictMono_nat_of_lt_succ fun n => ?_, fun i hi => ?_⟩    · cases n      · simp only [φ', Nat.zero_lt_succ]      · simp only [φ', add_lt_add_iff_right]        exact hφ_mono (Nat.lt_succ_self _)    · cases i      · simp [φ']      · simp only [List.length_cons, Nat.succ_lt_succ_iff] at hi        simp only [φ', List.getElem?_cons_succ]        exact hφ_eq _ hiopen YoungDiagram inlemma latin_partition_is_wide_perm_filter (m k : ℕ) (g : ℕ → ℕ)    (hg_maps : ∀ j < m, 1 ≤ g j ∧ g j ≤ m)    (hg_inj : ∀ j₁ < m, ∀ j₂ < m, g j₁ = g j₂ → j₁ = j₂) :    ((Finset.range m).filter (fun j => g j ≤ k)).card = min m k := by  let s := Finset.range m  let t := Finset.Ioc 0 m  have ht_card : t.card = m := Nat.card_Ioc 0 m  have h_img_sub : s.image g ⊆ t := by    intro y hy    rw [Finset.mem_image] at hy    obtain ⟨x, hx, rfl⟩ := hy    rw [Finset.mem_range] at hx    simp only [t, Finset.mem_Ioc]    have := hg_maps x hx    omega  have h_img_card : (s.image g).card = m := by    rw [Finset.card_image_of_injOn]    · simp [s]    · intro x hx y hy hxy      rw [Finset.mem_coe, Finset.mem_range] at hx hy      exact hg_inj x hx y hy hxy  have h_img_eq : s.image g = t := by    apply Finset.eq_of_subset_of_card_le h_img_sub    rw [h_img_card, ht_card]  have h_filter_img : ((s.filter (fun j => g j ≤ k)).image g) = t.filter (fun v => v ≤ k) := by    ext v    simp only [Finset.mem_image, Finset.mem_filter, s, Finset.mem_range]    constructor    · rintro ⟨j, ⟨hj, hgj⟩, rfl⟩      have := hg_maps j hj      simp only [t, Finset.mem_Ioc]      omega    · rintro ⟨hv_t, hvk⟩      have hv_img : v ∈ s.image g := by rw [h_img_eq]; exact hv_t      rw [Finset.mem_image] at hv_img      obtain ⟨j, hj, rfl⟩ := hv_img      rw [Finset.mem_range] at hj      exact ⟨j, ⟨hj, hvk⟩, rfl⟩  have h_inj_filter : Set.InjOn g ((s.filter (fun j => g j ≤ k)) : Set ℕ) := by    intro x hx y hy hxy    rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hx hy    exact hg_inj x hx.1 y hy.1 hxy  have h_card_eq : ((s.filter (fun j => g j ≤ k)).image g).card = (s.filter (fun j => g j ≤ k)).card :=    Finset.card_image_of_injOn h_inj_filter  rw [← h_card_eq, h_filter_img]  have h_ioc : (t.filter (fun v => v ≤ k)) = Finset.Ioc 0 (min m k) := by    ext v    simp only [t, Finset.mem_filter, Finset.mem_Ioc, le_min_iff]    omega  rw [h_ioc, Nat.card_Ioc, Nat.sub_zero]open YoungDiagram inlemma latin_partition_is_wide_col_filter_le (m k : ℕ) (h : ℕ → ℕ)    (hh_maps : ∀ i < m, 1 ≤ h i)    (hh_inj : ∀ i₁ < m, ∀ i₂ < m, h i₁ = h i₂ → i₁ = i₂) :    ((Finset.range m).filter (fun i => h i ≤ k)).card ≤ min m k := by  let s := (Finset.range m).filter (fun i => h i ≤ k)  have h1 : s.card ≤ m := by    have : s ⊆ Finset.range m := Finset.filter_subset _ _    exact (Finset.card_le_card this).trans_eq (Finset.card_range m)  have h2 : s.card ≤ k := by    have h_maps : Set.MapsTo h (s : Set ℕ) (Finset.Ioc 0 k : Set ℕ) := by      intro i hi      rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hi      simp only [Finset.mem_coe, Finset.mem_Ioc]      have := hh_maps i hi.1      omega    have h_inj : Set.InjOn h (s : Set ℕ) := by      intro x hx y hy hxy      rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_range] at hx hy      exact hh_inj x hx.1 y hy.1 hxy    have := Finset.card_le_card_of_injOn h h_maps h_inj    rwa [Nat.card_Ioc, Nat.sub_zero] at this  exact le_min h1 h2/-- Every Latin partition is wide. -/theorem latin_partition_is_wide (μ : YoungDiagram) (h : is_latin_partition μ) : is_wide_partition μ := by  obtain ⟨T, hT⟩ := h  intro ν hsub  obtain ⟨φ, hφ_mono, hφ_eq⟩ := latin_partition_is_wide_sublist_embed hsub  have hφ_row : ∀ i < ν.colLen 0, φ i < μ.colLen 0 ∧ ν.rowLen i = μ.rowLen (φ i) := by    intro i hi    rw [← YoungDiagram.length_rowLens] at hi    have h_opt := hφ_eq i hi    have h_some : ν.rowLens[i]? = some ν.rowLens[i] := List.getElem?_eq_getElem hi    rw [h_some] at h_opt    have h_len : φ i < μ.rowLens.length := by      by_contra h_ge      rw [List.getElem?_eq_none (not_lt.mp h_ge)] at h_opt      contradiction    have h_val : μ.rowLens[φ i] = ν.rowLens[i] := by      have := List.getElem?_eq_getElem h_len      rw [h_opt] at this      exact Option.some_injective _ this.symm    rw [YoungDiagram.length_rowLens] at h_len    rw [YoungDiagram.get_rowLens, YoungDiagram.get_rowLens] at h_val    exact ⟨h_len, h_val.symm⟩  have hcell_mem : ∀ {i j : ℕ}, (i, j) ∈ ν → (φ i, j) ∈ μ := by    intro i j hcell    have hi : i < ν.colLen 0 := by      rw [YoungDiagram.mem_iff_lt_colLen] at hcell      exact hcell.trans_le (ν.colLen_anti 0 j (Nat.zero_le j))    have hlen := (hφ_row i hi).2    rw [YoungDiagram.mem_iff_lt_rowLen] at hcell ⊢    rwa [← hlen]  intro k  simp only [ge_iff_le]  rw [latin_partition_is_wide_foldl_sum, latin_partition_is_wide_foldl_sum]  let S := ν.cells.filter (fun c => T (φ c.1) c.2 ≤ k)  have hmaps_row : Set.MapsTo Prod.fst (S : Set (ℕ × ℕ)) (Finset.range (ν.colLen 0) : Set ℕ) := by    intro c hc    rw [Finset.mem_coe, Finset.mem_filter, YoungDiagram.mem_cells, YoungDiagram.mem_iff_lt_colLen] at hc    rw [Finset.mem_coe, Finset.mem_range]    exact hc.1.trans_le (ν.colLen_anti 0 c.2 (Nat.zero_le c.2))  have hmaps_col : Set.MapsTo Prod.snd (S : Set (ℕ × ℕ)) (Finset.range (ν.rowLen 0) : Set ℕ) := by    intro c hc    rw [Finset.mem_coe, Finset.mem_filter, YoungDiagram.mem_cells, YoungDiagram.mem_iff_lt_rowLen] at hc    rw [Finset.mem_coe, Finset.mem_range]    exact hc.1.trans_le (ν.rowLen_anti 0 c.1 (Nat.zero_le c.1))  have hS_row : S.card = ∑ i ∈ Finset.range (ν.colLen 0), min (ν.rowLen i) k := by    rw [Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.range (ν.colLen 0)) (f := Prod.fst) hmaps_row]    apply Finset.sum_congr rfl    intro i hi    simp only [Finset.mem_range] at hi    have hfib : (S.filter (fun c => c.1 = i)) = {i} ×ˢ ((Finset.range (ν.rowLen i)).filter (fun j => T (φ i) j ≤ k)) := by      ext ⟨a, b⟩      simp only [S, Finset.mem_filter, YoungDiagram.mem_cells, Finset.mem_product, Finset.mem_singleton,        Finset.mem_range, YoungDiagram.mem_iff_lt_rowLen]      aesop    rw [hfib, Finset.card_product, Finset.card_singleton, one_mul]    apply latin_partition_is_wide_perm_filter    · intro j hj      have hc : (i, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]      have hc_μ := hcell_mem hc      have h1 := hT.1 hc_μ      have hlen := (hφ_row i hi).2      rwa [← hlen] at h1    · intro j₁ hj₁ j₂ hj₂ heq      have hc₁ : (i, j₁) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]      have hc₂ : (i, j₂) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_rowLen]      exact hT.2.1 (hcell_mem hc₁) (hcell_mem hc₂) heq  have hS_col : S.card ≤ ∑ j ∈ Finset.range (ν.rowLen 0), min (ν.colLen j) k := by    rw [Finset.card_eq_sum_card_fiberwise (s := S) (t := Finset.range (ν.rowLen 0)) (f := Prod.snd) hmaps_col]    apply Finset.sum_le_sum    intro j hj    simp only [Finset.mem_range] at hj    have hfib : (S.filter (fun c => c.2 = j)) = ((Finset.range (ν.colLen j)).filter (fun i => T (φ i) j ≤ k)) ×ˢ {j} := by      ext ⟨a, b⟩      simp only [S, Finset.mem_filter, YoungDiagram.mem_cells, Finset.mem_product, Finset.mem_singleton,        Finset.mem_range, YoungDiagram.mem_iff_lt_colLen]      aesop    rw [hfib, Finset.card_product, Finset.card_singleton, mul_one]    apply latin_partition_is_wide_col_filter_le    · intro i hi      have hc : (i, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]      exact (hT.1 (hcell_mem hc)).1    · intro i₁ hi₁ i₂ hi₂ heq      have hc₁ : (i₁, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]      have hc₂ : (i₂, j) ∈ ν := by rwa [YoungDiagram.mem_iff_lt_colLen]      have h_phi_eq := hT.2.2 (hcell_mem hc₁) (hcell_mem hc₂) heq      exact hφ_mono.injective h_phi_eq  rw [latin_partition_is_wide_sum_col_eq_sum_min_row, latin_partition_is_wide_sum_row_eq_sum_min_col]  linarith
See it in the graphDiscuss this resultChallenge it