weak_sl2_hall_condition
Let α be a finite partially ordered type with decidable equality and an integer rank function rank : α → ℤ. If rank makes α a ranked poset and E, F, H : Module.End ℂ (α → ℂ) define a weak sl_2-action, and for an integer n the raising operator E is injective on functions supported on rank n, then for every subset A of the level set of rank n, the cardinality of A is at most the cardinality of the set of elements in the level set of rank n + 2 that cover some element of A.
Statement
open scoped Classical in theorem weak_sl2_hall_condition {α : Type*} [Fintype α] [DecidableEq α] [PartialOrder α] (rank : α → ℤ) (hrk : is_ranked_poset rank) (E F H : Module.End ℂ (α → ℂ)) (hact : weak_sl2_action rank E F H) (n : ℤ) (hinj : ∀ (v : α → ℂ), (∀ x, v x ≠ 0 → rank x = n) → E v = 0 → v = 0) (A : Finset {x : α // rank x = n}) : A.card ≤ (Finset.univ.filter (fun y : {y : α // rank y = n + 2} => ∃ a ∈ A, (a : α) ⋖ (y : α))).card
- Source
- arXiv:2610.24148 Theorem 4.1 "Strong sl_2 Actions and Symmetric Chain Decompositions"
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 : α,…
- weak_sl2_actionGiven a finite partially ordered type α with decidable equality, an integer-valued function rank : α → ℤ, and linear endomorphisms E, F, H…
Read back from the Lean
Let $\alpha$ be a finite type with decidable equality and a partial order. Let $\operatorname{rank} : \alpha \to \mathbb{Z}$ be a function such that $(\alpha, \le, \operatorname{rank})$ is a ranked poset (in the sense that $\operatorname{rank}$ is order-preserving, whenever $b$ covers $a$ we have $\operatorname{rank}(b) = \operatorname{rank}(a) + 2$, and all elements of $\alpha$ have ranks of the same parity modulo $2$). Let $E, F, H \in \operatorname{End}_{\mathbb{C}}(\alpha \to \mathbb{C})$ form a weak $\mathfrak{sl}_2$-action with respect to $\operatorname{rank}$. Let $n \in \mathbb{Z}$, and suppose that $E$ is injective on the subspace of functions supported on elements of rank $n$ (that is, for any $v : \alpha \to \mathbb{C}$, if $v(x) \ne 0 \implies \operatorname{rank}(x) = n$, then $E(v) = 0 \implies v = 0$). Then for any finite set $A$ of elements of $\alpha$ of rank $n$, the cardinality of $A$ is at most the cardinality of the set of elements $y \in \alpha$ of rank $n + 2$ that cover at least one element of $A$.
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 establish Hall's marriage condition |A| ≤ |N| between rank levels n and n + 2, the proof constructs a linear map φ : ℂ^A → ℂ^N by embedding ℂ^A into ℂ^α, applying the raising operator E, and restricting to N. Because E is supported on covers, E(L(c)) is supported entirely on N; therefore, whenever φ(c) = 0, E(L(c)) vanishes identically on α. Since L(c) is supported on rank n and E is assumed injective on that level, L(c) = 0 and hence c = 0, proving that φ is an injective linear map and concluding that |A| ≤ |N| by comparing vector space dimensions.
Define N as the set of elements of rank n + 2 that cover at least one element of A.
We enable classical reasoning and set N to be the sub-finset of elements in α of rank n + 2 that cover some element of A. The ultimate goal is to prove |A| ≤ |N|.
classical set N : Finset {y : α // rank y = n + 2} := Finset.univ.filter (fun y => ∃ a ∈ A, (a : α) ⋖ (y : α)) with hN
For every a ∈ A, the function E(δ_a) is supported on N.
Let a ∈ A and suppose E(δ_a)(y) ≠ 0. The covering condition of the weak sl_2-action implies that a ⋖ y. In a ranked poset, covering increases rank by 2, so rank y = rank a + 2 = n + 2. Because a ∈ A and a ⋖ y, y satisfies the membership condition of N.
uses
Finset.mem_filter.mpr,Finset.mem_univhave hsupp : ∀ (a : A) (y : α), E (Pi.single (a:α) (1:ℂ)) y ≠ 0 → ∃ b : N, (((b : N) : {y : α // rank y = n + 2}) : α) = y := by intro a y hy have hra : rank (a:α) = n := (a : {x : α // rank x = n}).2 have hcover : (a:α) ⋖ y := hact.2.2.2.2 (a:α) y hy have hrank : rank y = n + 2 := by have h := hrk.2.1 hcover rw [hra] at h exact h refine ⟨⟨⟨y, hrank⟩, ?_⟩, rfl⟩ rw [hN] exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (a : {x : α // rank x = n}), a.2, hcover⟩
Construct the linear map L extending functions on A to functions on α supported on A.
We define L(c) = ∑_{a ∈ A} c(a) δ_a. Linearity over ℂ follows by distributing scalar multiplication and rearranging sums.
uses
Finset.sum_add_distrib,add_smul,Finset.smul_sum,smul_smullet L : (A → ℂ) →ₗ[ℂ] (α → ℂ) := { toFun := fun c => ∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ) map_add' := by intro c d simp [Finset.sum_add_distrib, add_smul] map_smul' := by intro r c simp [Finset.smul_sum, smul_smul] }
Construct the linear map φ from functions on A to functions on N via E ∘ L.
We define φ(c)(y) = (E(L(c)))(y) for each c ∈ ℂ^A and y ∈ N. Linearity follows from the linearity of E and L.
let φ : (A → ℂ) →ₗ[ℂ] (N → ℂ) := { toFun := fun c y => E (L c) (((y : N) : {y : α // rank y = n + 2}) : α) map_add' := by intro c d ext y simp map_smul' := by intro r c ext y simp }
For any c ∈ ℂ^A, the function L(c) is supported on elements of rank n.
Suppose φ(c) = 0. By definition, L(c) = ∑_{a ∈ A} c(a) δ_a. For any x with rank x ≠ n, x cannot equal any a ∈ A (since all elements in A have rank n), so δ_a(x) = 0 for every a, meaning (L(c))(x) = 0.
uses
Finset.sum_apply,Finset.sum_eq_zero,Pi.single_eq_of_ne,Ne.symmhave key : ∀ c : A → ℂ, φ c = 0 → c = 0 := by intro c hc have hv_supp : ∀ x, L c x ≠ 0 → rank x = n := by intro x hx by_contra hcon apply hx change (∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ)) x = 0 rw [Finset.sum_apply] apply Finset.sum_eq_zero intro a _ have hane : (a:α) ≠ x := by rintro rfl exact hcon (a : {x : α // rank x = n}).2 simp [Pi.single_eq_of_ne (Ne.symm hane)]
The function E(L(c)) is supported on N.
By linearity of E, E(L(c))(x) = ∑_{a ∈ A} c(a) E(δ_a)(x). For any x ∉ N, each term E(δ_a)(x) vanishes because the support of each E(δ_a) is in N, so the entire sum is zero.
uses
map_sum,Finset.sum_apply,Finset.sum_eq_zero,map_smulhave hEsupp : ∀ x : α, E (L c) x ≠ 0 → ∃ b : N, (((b : N) : {y : α // rank y = n + 2}) : α) = x := by intro x hx by_contra hcon apply hx change E (∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ)) x = 0 rw [map_sum] rw [Finset.sum_apply] apply Finset.sum_eq_zero intro a _ rw [map_smul] have hzero : E (Pi.single (a:α) (1:ℂ)) x = 0 := by by_contra hne exact hcon (hsupp a x hne) simp [hzero]
E(L(c)) = 0, and therefore L(c) = 0.
Since φ(c) = 0, E(L(c)) vanishes on N. Because E(L(c)) is supported on N, it is zero everywhere on α. Since L(c) is supported on rank n, the injectivity assumption hinj on rank n implies L(c) = 0.
uses
congrFunhave hEv0 : E (L c) = 0 := by funext x by_contra hx obtain ⟨b, hb⟩ := hEsupp x hx have hN0 : E (L c) (((b : N) : {y : α // rank y = n + 2}) : α) = 0 := by have := congrFun hc b simpa [φ] using this exact hx (hb ▸ hN0) have hLc0 : L c = 0 := hinj (L c) hv_supp hEv0
c = 0, showing that φ has trivial kernel.
Evaluating L(c) = ∑_{b ∈ A} c(b) δ_b at an element a ∈ A yields c(a) because δ_b(a) = 0 for all b ≠ a. Since L(c) = 0, we have c(a) = 0 for every a ∈ A, hence c = 0.
uses
Finset.sum_apply,Finset.sum_eq_single,Subtype.ext,Pi.single_eq_of_ne,Ne.symm,Finset.mem_univfunext a have hval : L c (a:α) = c a := by change (∑ b : A, c b • (Pi.single (b:α) (1:ℂ) : α → ℂ)) (a:α) = c a rw [Finset.sum_apply] rw [Finset.sum_eq_single a] · simp · intro b _ hb have hne : (b:α) ≠ (a:α) := by rintro h exact hb (Subtype.ext (Subtype.ext h)) simp [Pi.single_eq_of_ne (Ne.symm hne)] · intro h exact absurd (Finset.mem_univ a) h rw [← hval, hLc0] simp
The linear map φ is injective.
If φ(c) = φ(d), then by linearity φ(c - d) = 0. Since φ has trivial kernel, c - d = 0, which implies c = d.
uses
map_sub,sub_self,sub_eq_zero.mphave hinjφ : Function.Injective φ := by intro c d hcd have h1 : φ (c - d) = 0 := by rw [map_sub, hcd, sub_self] have h2 : c - d = 0 := key (c - d) h1 exact sub_eq_zero.mp h2
|A| ≤ |N|, which is the desired Hall marriage condition.
An injective linear map between finite-dimensional vector spaces requires dim(ℂ^A) ≤ dim(ℂ^N). Since the dimension of ℂ^S equals |S| for any finite set S, this yields |A| ≤ |N|.
uses
LinearMap.finrank_le_finrank_of_injective,Module.finrank_fintype_fun_eq_card,Fintype.card_coehave hfin := LinearMap.finrank_le_finrank_of_injective hinjφ rw [Module.finrank_fintype_fun_eq_card, Module.finrank_fintype_fun_eq_card] at hfin rwa [Fintype.card_coe, Fintype.card_coe] at hfin
add_smul- Scalar multiplication distributes over addition of scalars: (r + s) • x = r • x + s • x.
congrFun- If two functions are equal, their values are equal at every input: f = g implies f a = g a.
Fintype.card_coe- The cardinality of a Finset viewed as a subtype equals its cardinality as a Finset: Fintype.card (↑s) = s.card.
Finset.mem_filter.mpr- An element belongs to a filtered finset if it belongs to the ambient finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.smul_sum- Scalar multiplication distributes over a finite sum: r • ∑ x ∈ s, f x = ∑ x ∈ s, r • f x.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_apply- Evaluating a finite sum of functions at a point equals the sum of their individual evaluations at that point.
Finset.sum_eq_single- A finite sum with at most one non-zero term at index a equals the value of that term f(a).
Finset.sum_eq_zero- If every term of a finite sum is zero, then the sum is zero.
LinearMap.finrank_le_finrank_of_injective- An injective linear map between finite-dimensional vector spaces has domain dimension at most codomain dimension.
map_smul- A linear map preserves scalar multiplication: f(c • x) = c • f(x).
map_sub- A linear map preserves subtraction: f(a - b) = f(a) - f(b).
map_sum- A linear map preserves finite sums: g(∑ x, f(x)) = ∑ x, g(f(x)).
Module.finrank_fintype_fun_eq_card- The dimension of the space of functions from a finite type η to the base field R equals the cardinality of η.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
Pi.single_eq_of_ne- The basis vector δ_i evaluated at any index i' ≠ i is zero.
smul_smul- Successive scalar multiplications satisfy a₁ • a₂ • b = (a₁ * a₂) • b.
sub_eq_zero.mp- If the difference of two elements is zero, then they are equal: a - b = 0 implies a = b.
sub_self- Subtracting any element from itself yields zero: a - a = 0.
Subtype.ext- Two elements of a subtype are equal if their underlying values in the ambient type are equal.
- In this formalization of a ranked poset, covering pairs increase rank by 2 rather than 1 (as seen in `is_ranked_poset`, where a ⋖ b implies rank b = rank a + 2), matching the sl_2 representation weight shift where the raising operator increases weight by 2.
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 scoped Classical in/-- The marriage condition holds between adjacent levels when the raising operator is injective and supported on covers. -/theorem weak_sl2_hall_condition {α : Type*} [Fintype α] [DecidableEq α] [PartialOrder α] (rank : α → ℤ) (hrk : is_ranked_poset rank) (E F H : Module.End ℂ (α → ℂ)) (hact : weak_sl2_action rank E F H) (n : ℤ) (hinj : ∀ (v : α → ℂ), (∀ x, v x ≠ 0 → rank x = n) → E v = 0 → v = 0) (A : Finset {x : α // rank x = n}) : A.card ≤ (Finset.univ.filter (fun y : {y : α // rank y = n + 2} => ∃ a ∈ A, (a : α) ⋖ (y : α))).card := by classical set N : Finset {y : α // rank y = n + 2} := Finset.univ.filter (fun y => ∃ a ∈ A, (a : α) ⋖ (y : α)) with hN have hsupp : ∀ (a : A) (y : α), E (Pi.single (a:α) (1:ℂ)) y ≠ 0 → ∃ b : N, (((b : N) : {y : α // rank y = n + 2}) : α) = y := by intro a y hy have hra : rank (a:α) = n := (a : {x : α // rank x = n}).2 have hcover : (a:α) ⋖ y := hact.2.2.2.2 (a:α) y hy have hrank : rank y = n + 2 := by have h := hrk.2.1 hcover rw [hra] at h exact h refine ⟨⟨⟨y, hrank⟩, ?_⟩, rfl⟩ rw [hN] exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (a : {x : α // rank x = n}), a.2, hcover⟩ let L : (A → ℂ) →ₗ[ℂ] (α → ℂ) := { toFun := fun c => ∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ) map_add' := by intro c d simp [Finset.sum_add_distrib, add_smul] map_smul' := by intro r c simp [Finset.smul_sum, smul_smul] } let φ : (A → ℂ) →ₗ[ℂ] (N → ℂ) := { toFun := fun c y => E (L c) (((y : N) : {y : α // rank y = n + 2}) : α) map_add' := by intro c d ext y simp map_smul' := by intro r c ext y simp } have key : ∀ c : A → ℂ, φ c = 0 → c = 0 := by intro c hc have hv_supp : ∀ x, L c x ≠ 0 → rank x = n := by intro x hx by_contra hcon apply hx change (∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ)) x = 0 rw [Finset.sum_apply] apply Finset.sum_eq_zero intro a _ have hane : (a:α) ≠ x := by rintro rfl exact hcon (a : {x : α // rank x = n}).2 simp [Pi.single_eq_of_ne (Ne.symm hane)] have hEsupp : ∀ x : α, E (L c) x ≠ 0 → ∃ b : N, (((b : N) : {y : α // rank y = n + 2}) : α) = x := by intro x hx by_contra hcon apply hx change E (∑ a : A, c a • (Pi.single (a:α) (1:ℂ) : α → ℂ)) x = 0 rw [map_sum] rw [Finset.sum_apply] apply Finset.sum_eq_zero intro a _ rw [map_smul] have hzero : E (Pi.single (a:α) (1:ℂ)) x = 0 := by by_contra hne exact hcon (hsupp a x hne) simp [hzero] have hEv0 : E (L c) = 0 := by funext x by_contra hx obtain ⟨b, hb⟩ := hEsupp x hx have hN0 : E (L c) (((b : N) : {y : α // rank y = n + 2}) : α) = 0 := by have := congrFun hc b simpa [φ] using this exact hx (hb ▸ hN0) have hLc0 : L c = 0 := hinj (L c) hv_supp hEv0 funext a have hval : L c (a:α) = c a := by change (∑ b : A, c b • (Pi.single (b:α) (1:ℂ) : α → ℂ)) (a:α) = c a rw [Finset.sum_apply] rw [Finset.sum_eq_single a] · simp · intro b _ hb have hne : (b:α) ≠ (a:α) := by rintro h exact hb (Subtype.ext (Subtype.ext h)) simp [Pi.single_eq_of_ne (Ne.symm hne)] · intro h exact absurd (Finset.mem_univ a) h rw [← hval, hLc0] simp have hinjφ : Function.Injective φ := by intro c d hcd have h1 : φ (c - d) = 0 := by rw [map_sub, hcd, sub_self] have h2 : c - d = 0 := key (c - d) h1 exact sub_eq_zero.mp h2 have hfin := LinearMap.finrank_le_finrank_of_injective hinjφ rw [Module.finrank_fintype_fun_eq_card, Module.finrank_fintype_fun_eq_card] at hfin rwa [Fintype.card_coe, Fintype.card_coe] at hfin