latin_partition_is_wide
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
List.foldl_cons,add_assoc,zero_add,List.range_succ,Finset.sum_range_succhave 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
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).
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_congr,colLen_eq_cardlet 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]
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).
uses
mem_iff_lt_colLen,Finset.card_eq_sum_card_fiberwise,Finset.sum_congr,Finset.card_product,Finset.card_singleton,Finset.card_range,one_mullet 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]
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.
uses
latin_partition_is_wide_col_card,latin_partition_is_wide_row_min_sumrw [← latin_partition_is_wide_col_card, latin_partition_is_wide_row_min_sum]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.
uses
latin_partition_is_wide_sum_col_eq_sum_min_row,colLen_transpose,rowLen_transposehave h := latin_partition_is_wide_sum_col_eq_sum_min_row ν.transpose k simp only [colLen_transpose, rowLen_transpose] at h exact h
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.
uses
strictMono_id,strictMono_nat_of_lt_succ,Nat.succ_lt_succ,Nat.lt_succ_selfrefine ⟨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
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).
uses
Nat.card_Ioc,Finset.card_image_of_injOn,Finset.eq_of_subset_of_card_le,Nat.sub_zerolet 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]
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).
uses
Finset.filter_subset,Finset.card_le_card,Finset.card_range,Finset.card_le_card_of_injOn,Nat.card_Ioc,Nat.sub_zero,le_minlet 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
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.
uses
latin_partition_is_wide_sublist_embed,YoungDiagram.length_rowLens,List.getElem?_eq_getElem,List.getElem?_eq_none,Option.some_injective,YoungDiagram.get_rowLensobtain ⟨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⟩
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 μ.
uses
YoungDiagram.mem_iff_lt_colLen,Nat.zero_le,YoungDiagram.mem_iff_lt_rowLenhave 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]
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).
uses
latin_partition_is_wide_foldl_sum,YoungDiagram.mem_cells,YoungDiagram.mem_iff_lt_colLen,YoungDiagram.mem_iff_lt_rowLen,Nat.zero_leintro 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))
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.
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_rowLenhave 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
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.
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_colLenhave 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
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.
uses
latin_partition_is_wide_sum_col_eq_sum_min_row,latin_partition_is_wide_sum_row_eq_sum_min_colrw [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)
- In the formal definition of Young diagrams and subpartitions, a subpartition ν is specified by its row-length list being a sublist of μ's row-length list; the proof explicitly constructs a strictly monotonic embedding φ of row indices to align the diagrams.
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.
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