AFTD Auto-Formalizing Theoretical Domains

weak_sl2_hall_condition

theoremverified

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.

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

    lines 13–15

      classical
      set N : Finset {y : α // rank y = n + 2} :=
        Finset.univ.filter (fun y => ∃ a ∈ A, (a : α) ⋖ (y : α)) with hN
  2. 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.

    lines 16–27

    uses Finset.mem_filter.mpr, Finset.mem_univ

      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⟩
  3. 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.

    lines 28–35

    uses Finset.sum_add_distrib, add_smul, Finset.smul_sum, smul_smul

      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] }
  4. 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.

    lines 36–45

      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 }
  5. 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.

    lines 46–59

    uses Finset.sum_apply, Finset.sum_eq_zero, Pi.single_eq_of_ne, Ne.symm

      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)]
  6. 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.

    lines 60–74

    uses map_sum, Finset.sum_apply, Finset.sum_eq_zero, map_smul

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

    lines 75–83

    uses congrFun

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

    lines 84–98

    uses Finset.sum_apply, Finset.sum_eq_single, Subtype.ext, Pi.single_eq_of_ne, Ne.symm, Finset.mem_univ

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

    lines 99–104

    uses map_sub, sub_self, sub_eq_zero.mp

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

    lines 105–107

    uses LinearMap.finrank_le_finrank_of_injective, Module.finrank_fintype_fun_eq_card, Fintype.card_coe

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

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