young_lattice_rank_is_ranked_poset
For any m and n, the rank function young_lattice_rank makes L(m, n) into a ranked poset in the sense of is_ranked_poset.
Statement
theorem young_lattice_rank_is_ranked_poset (m n : ℕ) : is_ranked_poset (young_lattice_rank m n)- Source
- arXiv:2610.24148, Section 2.7.4
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_ranked_posetA function rank : α → ℤ from a partially ordered type α to the integers ℤ is a ranked poset structure if it is monotone (for all a b : α,…
- YoungLatticeThe Young lattice L(m, n) is the type of Young diagrams whose cells (i, j) satisfy i < m and j < n, ordered by inclusion.
- young_lattice_rankThe centered rank of a Young diagram μ in L(m, n) is 2 * |cells(μ)| - m * n.
- young_lattice_partial_orderThe Young lattice L(m, n) inherits the partial order on Young diagrams given by cell inclusion.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For all natural numbers $m$ and $n$, the rank function young_lattice_rank m n on the poset YoungLattice m n (Young diagrams fitting within an $m \times n$ grid) makes it a ranked poset in the sense of is_ranked_poset.
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
The proof establishes that the centered rank function young_lattice_rank m n μ = 2 * |μ.cells| - m * n satisfies the three defining axioms of is_ranked_poset on L(m, n). Monotonicity holds because the poset order is inclusion of cell sets, which preserves cardinality. For the covering property a ⋖ b, choosing a minimal cell x in the nonempty difference b \ a allows constructing an intermediate Young diagram γL = a ∪ {x}; the covering condition forces γL = b, which means b contains exactly one more cell than a and its rank increases by 2. Finally, the ranks of any two elements differ by an even integer 2(|b| - |a|), so all elements share the same rank parity modulo 2.
To prove that young_lattice_rank makes L(m, n) a ranked poset, it suffices to prove monotonicity, that covering pairs increase rank by 2, and that all ranks have the same parity modulo 2.
The definition of is_ranked_poset consists of three conjuncts: order preservation, the rank step condition rank(b) = rank(a) + 2 for covering pairs a ⋖ b, and rank(a) ≡ rank(b) [ZMOD 2]. The refine tactic splits the proof into these three independent subgoals.
refine ⟨?_, ?_, ?_⟩The rank function is monotonic: if a ≤ b, then young_lattice_rank m n a ≤ young_lattice_rank m n b.
The partial order on L(m, n) is inclusion of cell sets, so a ≤ b implies a.cells ⊆ b.cells. By Finset.card_le_card, |a.cells| ≤ |b.cells|. Expanding the definition young_lattice_rank m n μ = 2 * |μ.cells| - m * n, the inequality follows by linear arithmetic.
uses
Finset.card_le_card· intro a b hab have hsub : a.1.cells ⊆ b.1.cells := hab have hcard : a.1.cells.card ≤ b.1.cells.card := Finset.card_le_card hsub have hcardZ : (a.1.cells.card : ℤ) ≤ (b.1.cells.card : ℤ) := by exact_mod_cast hcard simp only [young_lattice_rank] linarith
If a ⋖ b, there is a minimal cell x in b.cells \ a.cells with respect to the coordinatewise order.
Since a ⋖ b, we have a ≤ b and a ≠ b, so b.cells is not contained in a.cells. Thus the difference b.cells \ a.cells is nonempty by Finset.sdiff_nonempty.mpr. By Finset.exists_minimal, this finite nonempty set contains a minimal element x, which satisfies x ∈ b.cells and x ∉ a.cells by Finset.mem_sdiff.mp.
uses
Finset.sdiff_nonempty.mpr,Finset.exists_minimal,Finset.mem_sdiff.mp· intro a b hab have hab_le : a ≤ b := hab.1.le have hsub : a.1.cells ⊆ b.1.cells := hab_le have hnot_sub : ¬ b.1.cells ⊆ a.1.cells := hab.1.2 have hne : (b.1.cells \ a.1.cells).Nonempty := Finset.sdiff_nonempty.mpr hnot_sub obtain ⟨x, hmin⟩ := Finset.exists_minimal hne have hx_b : x ∈ b.1.cells := (Finset.mem_sdiff.mp hmin.1).1 have hx_not_a : x ∉ a.1.cells := (Finset.mem_sdiff.mp hmin.1).2
Adjoining x to a.cells yields a lower set γcells in ℕ × ℕ.
Let γcells = insert x a.cells. To verify it is a lower set, suppose u ∈ γcells and v ≤ u. If u ∈ a.cells, then v ∈ a.cells because a is a Young diagram. If u = x, then v ≤ x: either v ∈ a.cells or v ∉ a.cells. In the latter case, because b is a lower set containing x, v ∈ b.cells \ a.cells by Finset.mem_sdiff.mpr. By minimality of x in that difference, x ≤ v; by antisymmetry (le_antisymm), v = x ∈ γcells.
uses
Finset.mem_sdiff.mpr,le_antisymmlet γcells : Finset (ℕ × ℕ) := insert x a.1.cells have hγlower : IsLowerSet (↑γcells : Set (ℕ × ℕ)) := by intro u v huv hu simp only [γcells, Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hu ⊢ rcases hu with hu | hu · rw [hu] at huv by_cases hv : v ∈ a.1.cells · exact Or.inr hv · have hvb : v ∈ b.1.cells := b.1.isLowerSet huv (by simpa using hx_b) have hvd : v ∈ b.1.cells \ a.1.cells := Finset.mem_sdiff.mpr ⟨hvb, hv⟩ have hxle : x ≤ v := hmin.2 hvd huv exact Or.inl (le_antisymm huv hxle) · exact Or.inr (a.1.isLowerSet huv hu)
The lower set γcells forms a Young diagram γ that fits in the m × n bounding box, defining an element γL ∈ L(m, n).
We bundle γcells with the lower-set proof into a Young diagram γ. Every cell c in γ is either x or in a.cells by YoungDiagram.mem_cells and Finset.mem_insert. Since both x ∈ b and all cells of a satisfy the coordinate bounds c.1 < m and c.2 < n, all cells of γ do as well, forming an element γL of L(m, n).
uses
YoungDiagram.mem_cells,Finset.mem_insertlet γ : YoungDiagram := ⟨γcells, hγlower⟩ have hγbox : ∀ c ∈ γ, c.1 < m ∧ c.2 < n := by intro c hc have hc' : c ∈ γcells := (YoungDiagram.mem_cells c).mpr hc rw [show γcells = insert x a.1.cells from rfl, Finset.mem_insert] at hc' rcases hc' with hcx | hc' · rw [hcx] exact b.2 x (by simpa using hx_b) · exact a.2 c (by simpa using hc') let γL : YoungLattice m n := ⟨γ, hγbox⟩
The diagram γL equals b, which implies b.cells = insert x a.cells.
Clearly a.cells ⊆ γL.cells by Finset.mem_insert_of_mem, so a ≤ γL. Since x ∈ γL.cells by Finset.mem_insert_self but x ∉ a.cells, a ≠ γL (via congrArg), giving a < γL by lt_of_le_of_ne. Furthermore, γL ≤ b because both x ∈ b.cells and a.cells ⊆ b.cells (using Finset.mem_insert.mp). If γL ≠ b, then a < γL < b, contradicting the covering assumption a ⋖ b. Hence γL = b, and extracting the cell sets with congrArg yields b.cells = insert x a.cells.
uses
Finset.mem_insert_of_mem,Finset.mem_insert_self,congrArg,lt_of_le_of_ne,Finset.mem_insert.mphave hle_aγ : a ≤ γL := by change a.1.cells ⊆ γL.1.cells intro c hc exact Finset.mem_insert_of_mem hc have hne_aγ : a ≠ γL := by intro h have hxmem : x ∈ γL.1.cells := by change x ∈ insert x a.1.cells exact Finset.mem_insert_self _ _ rw [← congrArg (fun z : YoungLattice m n => z.1.cells) h] at hxmem exact hx_not_a hxmem have hlt_aγ : a < γL := lt_of_le_of_ne hle_aγ hne_aγ have hle_γb : γL ≤ b := by change γL.1.cells ⊆ b.1.cells intro c hc change c ∈ insert x a.1.cells at hc rcases Finset.mem_insert.mp hc with hcx | hc · rw [hcx]; exact hx_b · exact hsub hc have hγb : γL = b := by by_contra h exact hab.2 hlt_aγ (lt_of_le_of_ne hle_γb h) have hcells : b.1.cells = insert x a.1.cells := by have hh := congrArg (fun z : YoungLattice m n => z.1.cells) hγb simpa [γL, γ, γcells] using hh.symm
The rank of b is young_lattice_rank m n a + 2.
Since b.cells = insert x a.cells with x ∉ a.cells, Finset.card_insert_of_notMem gives |b.cells| = |a.cells| + 1. Substituting into young_lattice_rank m n μ = 2 * |μ.cells| - m * n, we find rank(b) = 2(|a| + 1) - mn = (2|a| - mn) + 2 = rank(a) + 2 by linear arithmetic.
uses
Finset.card_insert_of_notMemhave hcard : b.1.cells.card = a.1.cells.card + 1 := by rw [hcells, Finset.card_insert_of_notMem hx_not_a] have hcardZ : (b.1.cells.card : ℤ) = (a.1.cells.card : ℤ) + 1 := by exact_mod_cast hcard simp only [young_lattice_rank] linarith
The ranks of any two diagrams in L(m, n) are congruent modulo 2.
By Int.modEq_iff_dvd, rank(a) ≡ rank(b) [ZMOD 2] is equivalent to 2 dividing rank(b) - rank(a). Unfolding the definition of rank, the difference simplifies to 2 * (|b.cells| - |a.cells|), so |b.cells| - |a.cells| serves as the explicit witness of divisibility.
uses
Int.modEq_iff_dvd· intro a b rw [Int.modEq_iff_dvd] use ((b.1.cells.card : ℤ) - (a.1.cells.card : ℤ)) simp only [young_lattice_rank] ring
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.sdiff_nonempty.mpr- If a finite set s is not a subset of t, their difference s \ t is nonempty.
Finset.exists_minimal- Every nonempty finite subset of a preordered set contains a minimal element.
Finset.mem_sdiff.mp- If an element x belongs to s \ t, then x ∈ s and x ∉ t.
Finset.mem_sdiff.mpr- If x ∈ s and x ∉ t, then x belongs to s \ t.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
YoungDiagram.mem_cells- A coordinate belongs to a Young diagram if and only if it belongs to its underlying finite set of cells.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_insert_of_mem- If an element belongs to s, it also belongs to insert b s.
Finset.mem_insert_self- An element a is always an element of insert a s.
congrArg- Applying a function to equal inputs yields equal outputs.
lt_of_le_of_ne- In a partial order, if a ≤ b and a ≠ b, then a < b.
Finset.mem_insert.mp- If an element belongs to insert a s, then it equals a or belongs to s.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Int.modEq_iff_dvd- Two integers a and b are congruent modulo n if and only if n divides b - a.
- In this formalization, `is_ranked_poset` requires the rank to increase by 2 (rather than the standard 1) along covering relations, and requires all elements to share the same rank parity modulo 2. This matches the factor of 2 in the centered rank function young_lattice_rank m n μ = 2 * |μ.cells| - m * n.
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.
/-- The centered rank function makes the Young lattice L(m, n) into a ranked poset. -/theorem young_lattice_rank_is_ranked_poset (m n : ℕ) : is_ranked_poset (young_lattice_rank m n) := by refine ⟨?_, ?_, ?_⟩ · intro a b hab have hsub : a.1.cells ⊆ b.1.cells := hab have hcard : a.1.cells.card ≤ b.1.cells.card := Finset.card_le_card hsub have hcardZ : (a.1.cells.card : ℤ) ≤ (b.1.cells.card : ℤ) := by exact_mod_cast hcard simp only [young_lattice_rank] linarith · intro a b hab have hab_le : a ≤ b := hab.1.le have hsub : a.1.cells ⊆ b.1.cells := hab_le have hnot_sub : ¬ b.1.cells ⊆ a.1.cells := hab.1.2 have hne : (b.1.cells \ a.1.cells).Nonempty := Finset.sdiff_nonempty.mpr hnot_sub obtain ⟨x, hmin⟩ := Finset.exists_minimal hne have hx_b : x ∈ b.1.cells := (Finset.mem_sdiff.mp hmin.1).1 have hx_not_a : x ∉ a.1.cells := (Finset.mem_sdiff.mp hmin.1).2 let γcells : Finset (ℕ × ℕ) := insert x a.1.cells have hγlower : IsLowerSet (↑γcells : Set (ℕ × ℕ)) := by intro u v huv hu simp only [γcells, Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hu ⊢ rcases hu with hu | hu · rw [hu] at huv by_cases hv : v ∈ a.1.cells · exact Or.inr hv · have hvb : v ∈ b.1.cells := b.1.isLowerSet huv (by simpa using hx_b) have hvd : v ∈ b.1.cells \ a.1.cells := Finset.mem_sdiff.mpr ⟨hvb, hv⟩ have hxle : x ≤ v := hmin.2 hvd huv exact Or.inl (le_antisymm huv hxle) · exact Or.inr (a.1.isLowerSet huv hu) let γ : YoungDiagram := ⟨γcells, hγlower⟩ have hγbox : ∀ c ∈ γ, c.1 < m ∧ c.2 < n := by intro c hc have hc' : c ∈ γcells := (YoungDiagram.mem_cells c).mpr hc rw [show γcells = insert x a.1.cells from rfl, Finset.mem_insert] at hc' rcases hc' with hcx | hc' · rw [hcx] exact b.2 x (by simpa using hx_b) · exact a.2 c (by simpa using hc') let γL : YoungLattice m n := ⟨γ, hγbox⟩ have hle_aγ : a ≤ γL := by change a.1.cells ⊆ γL.1.cells intro c hc exact Finset.mem_insert_of_mem hc have hne_aγ : a ≠ γL := by intro h have hxmem : x ∈ γL.1.cells := by change x ∈ insert x a.1.cells exact Finset.mem_insert_self _ _ rw [← congrArg (fun z : YoungLattice m n => z.1.cells) h] at hxmem exact hx_not_a hxmem have hlt_aγ : a < γL := lt_of_le_of_ne hle_aγ hne_aγ have hle_γb : γL ≤ b := by change γL.1.cells ⊆ b.1.cells intro c hc change c ∈ insert x a.1.cells at hc rcases Finset.mem_insert.mp hc with hcx | hc · rw [hcx]; exact hx_b · exact hsub hc have hγb : γL = b := by by_contra h exact hab.2 hlt_aγ (lt_of_le_of_ne hle_γb h) have hcells : b.1.cells = insert x a.1.cells := by have hh := congrArg (fun z : YoungLattice m n => z.1.cells) hγb simpa [γL, γ, γcells] using hh.symm have hcard : b.1.cells.card = a.1.cells.card + 1 := by rw [hcells, Finset.card_insert_of_notMem hx_not_a] have hcardZ : (b.1.cells.card : ℤ) = (a.1.cells.card : ℤ) + 1 := by exact_mod_cast hcard simp only [young_lattice_rank] linarith · intro a b rw [Int.modEq_iff_dvd] use ((b.1.cells.card : ℤ) - (a.1.cells.card : ℤ)) simp only [young_lattice_rank] ring