AFTD Auto-Formalizing Theoretical Domains

greedy_vector_chain_saturation

theoremverified

For any set function C on Finset (Fin n) with C(∅) = 0, any permutation π, and any k ≤ n, the sum of the greedy marginal differences z_i = C(S_{rank(i)}) - C(S_{rank(i)+1}) over the upper set S_k equals C(S_k).

Statement

theorem greedy_vector_chain_saturation {n : ℕ} (C : Finset (Fin n) → ℝ)
    (hC_empty : C ∅ = 0) (π : Equiv.Perm (Fin n)) (k : ℕ) (hk : k ≤ n) :
    ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding,
      (C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) ≤ (j : ℕ))).map π.toEmbedding) -
       C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) + 1 ≤ (j : ℕ))).map π.toEmbedding)) =
      C ((Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding)
Source
arXiv:2610.35433 Corollary 1
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • greedy_vector_sum_univFor any set function C on Finset (Fin n) with C ∅ = 0 and any permutation π of Fin n, the sum over all i of the greedy marginal…

Read back from the Lean

For any natural number $n$, any set function $C : \mathrm{Finset}(\mathrm{Fin}\ n) \to \mathbb{R}$ satisfying $C(\emptyset) = 0$, any permutation $\pi$ of $\mathrm{Fin}\ n$, and any natural number $k$ such that $k \le n$: The sum over all $i$ in the $\pi$-image of $\{j : \mathrm{Fin}\ n \mid k \le j\}$ of $$C(\pi(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(i) \le j\})) - C(\pi(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(i) + 1 \le j\}))$$ is equal to $$C(\pi(\{j : \mathrm{Fin}\ n \mid k \le j\})).$$

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 re-indexes the sum of marginal differences over the upper set S_k = π({j ∈ Fin n | k ≤ j}) via the permutation π, setting F(m) = C(S_m). Embedding the indices into ℕ identifies the index set with the integer interval [k, n), turning the sum into a telescoping sum ∑_{x=k}^{n-1} (F(x) - F(x+1)) = F(k) - F(n). Finally, because all elements of Fin n are strictly less than n, the upper boundary set S_n is empty, giving F(n) = C(∅) = 0 and leaving F(k) = C(S_k).

  1. The sum over S_k can be re-indexed as ∑_{j ∈ Fin n, k ≤ j} (F(j) - F(j+1)).

    Let S_m = π({j ∈ Fin n | m ≤ j}) and define F(m) = C(S_m). The original sum is over i ∈ S_k. Changing the index via i = π(j) using Finset.sum_map substitutes π(j) for i. Since π is a bijection, Equiv.symm_apply_apply simplifies π⁻¹(π(j)) to j, transforming the marginal differences into F(j) - F(j+1) summed over j ∈ Fin n with k ≤ j.

    lines 8–16

    uses Finset.sum_map, Equiv.toEmbedding_apply, Equiv.symm_apply_apply

      let F : ℕ → ℝ := fun m => C ((Finset.univ.filter (fun j : Fin n => m ≤ (j : ℕ))).map π.toEmbedding)
      have h1 : ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding,
          (C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) ≤ (j : ℕ))).map π.toEmbedding) -
           C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) + 1 ≤ (j : ℕ))).map π.toEmbedding)) =
          ∑ j ∈ Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ)), (F j - F (j + 1)) := by
        rw [Finset.sum_map]
        simp only [Equiv.toEmbedding_apply, Equiv.symm_apply_apply]
        rfl
      rw [h1]
  2. The image of {j ∈ Fin n | k ≤ j} under the value embedding into ℕ is the half-open interval [k, n).

    By set extensionality, an integer x belongs to [k, n) if and only if k ≤ x and x < n (Finset.mem_Ico). Any such x defines an element ⟨x, x < n⟩ ∈ Fin n that satisfies k ≤ x. Conversely, every a ∈ Fin n with k ≤ a satisfies k ≤ a and a < n by the definition of Fin n. Unfolding membership via Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and, and Fin.valEmbedding_apply establishes that [k, n) is the image of {j ∈ Fin n | k ≤ j} under Fin.valEmbedding.

    lines 17–25

    uses Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and, Fin.valEmbedding_apply, Finset.mem_Ico

      have hmap : Finset.Ico k n = (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map Fin.valEmbedding := by
        ext x
        simp only [Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and,
          Fin.valEmbedding_apply, Finset.mem_Ico]
        constructor
        · rintro ⟨hkx, hx⟩
          exact ⟨⟨x, hx⟩, hkx, rfl⟩
        · rintro ⟨a, hka, rfl⟩
          exact ⟨hka, a.isLt⟩
  3. The sum over {j ∈ Fin n | k ≤ j} equals the sum over the integer interval [k, n).

    Using the bijection hmap between {j ∈ Fin n | k ≤ j} and the interval of natural numbers [k, n), Finset.sum_map translates the sum over Fin n into the integer sum ∑_{x ∈ [k, n)} (F(x) - F(x+1)).

    lines 26–30

    uses Finset.sum_map

      have h2 : ∑ j ∈ Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ)), (F j - F (j + 1)) =
          ∑ x ∈ Finset.Ico k n, (F x - F (x + 1)) := by
        rw [hmap, Finset.sum_map]
        rfl
      rw [h2]
  4. The sum over [k, n) telescopes to F(k) - F(n).

    Since k ≤ n, Finset.sum_Ico_eq_sub splits the sum over [k, n) into the difference between the sum over [0, n) and the sum over [0, k). Each of these ranges telescopes via Finset.sum_range_sub', evaluating to F(0) - F(n) and F(0) - F(k) respectively. Simplifying (F(0) - F(n)) - (F(0) - F(k)) using abelian group arithmetic (abel) yields F(k) - F(n).

    lines 31–34

    uses Finset.sum_Ico_eq_sub, Finset.sum_range_sub'

      have htelescope : ∑ x ∈ Finset.Ico k n, (F x - F (x + 1)) = F k - F n := by
        rw [Finset.sum_Ico_eq_sub _ hk, Finset.sum_range_sub', Finset.sum_range_sub']
        abel
      rw [htelescope]
  5. The upper boundary term vanishes: F(n) = 0.

    Because every element j ∈ Fin n satisfies j < n, no element satisfies n ≤ j by not_le_of_gt. Therefore, by Finset.filter_eq_empty_iff, the set {j ∈ Fin n | n ≤ j} is empty. Then F(n) = C(π(∅)) = C(∅) by Finset.map_empty, which equals 0 by the assumption hC_empty that C is normalized.

    lines 35–41

    uses Finset.filter_eq_empty_iff, not_le_of_gt, Finset.map_empty

      have hFn : F n = 0 := by
        have hempty : Finset.univ.filter (fun j : Fin n => n ≤ (j : ℕ)) = ∅ := by
          rw [Finset.filter_eq_empty_iff]
          intro x _
          exact not_le_of_gt x.isLt
        change C ((Finset.univ.filter (fun j : Fin n => n ≤ (j : ℕ))).map π.toEmbedding) = 0
        rw [hempty, Finset.map_empty, hC_empty]
  6. The telescoping sum evaluates to C(S_k).

    Substituting F(n) = 0 into F(k) - F(n) simplifies it to F(k) via sub_zero. By definition, F(k) is C(S_k), which matches the right-hand side.

    line 42

    uses sub_zero

      rw [hFn, sub_zero]
Finset.sum_map
The sum of a function over the image of a finset under an embedding equals the sum over the original finset with the embedding applied to the arguments.
Equiv.toEmbedding_apply
Evaluating the embedding induced by an equivalence at an element is equal to applying the equivalence directly.
Equiv.symm_apply_apply
Applying an equivalence to an element and then applying its inverse returns the original element: e⁻¹(e(x)) = x.
Finset.mem_map
An element b belongs to the image f(s) of a finset under an embedding f if and only if b = f(a) for some a ∈ s.
Finset.mem_filter
An element belongs to the filtered sub-finset {x ∈ s | p(x)} if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The logical conjunction True ∧ p simplifies to p.
Fin.valEmbedding_apply
The canonical embedding of Fin n into ℕ maps each element to its underlying natural number value.
Finset.mem_Ico
An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.sum_Ico_eq_sub
For m ≤ n, the sum of a function over the half-open interval [m, n) equals the sum over [0, n) minus the sum over [0, m).
Finset.sum_range_sub'
The sum of consecutive differences ∑_{i=0}^{n-1} (f(i) - f(i+1)) telescopes to f(0) - f(n).
Finset.filter_eq_empty_iff
The filtered finset {x ∈ s | p(x)} is empty if and only if no element of s satisfies p.
not_le_of_gt
If a < b in a preorder, then b ≤ a is false.
Finset.map_empty
The image of the empty finset under an embedding is empty.
sub_zero
Subtracting zero leaves an element unchanged: a - 0 = a.

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

/-- The greedy marginal difference vector along a chain saturates the chain's sets for any normalized set function. -/theorem greedy_vector_chain_saturation {n : ℕ} (C : Finset (Fin n) → ℝ)    (hC_empty : C ∅ = 0) (π : Equiv.Perm (Fin n)) (k : ℕ) (hk : k ≤ n) :    ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding,      (C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) ≤ (j : ℕ))).map π.toEmbedding) -       C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) + 1 ≤ (j : ℕ))).map π.toEmbedding)) =      C ((Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding) := by  let F : ℕ → ℝ := fun m => C ((Finset.univ.filter (fun j : Fin n => m ≤ (j : ℕ))).map π.toEmbedding)  have h1 : ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding,      (C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) ≤ (j : ℕ))).map π.toEmbedding) -       C ((Finset.univ.filter (fun j : Fin n => (π.symm i : ℕ) + 1 ≤ (j : ℕ))).map π.toEmbedding)) =      ∑ j ∈ Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ)), (F j - F (j + 1)) := by    rw [Finset.sum_map]    simp only [Equiv.toEmbedding_apply, Equiv.symm_apply_apply]    rfl  rw [h1]  have hmap : Finset.Ico k n = (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map Fin.valEmbedding := by    ext x    simp only [Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and,      Fin.valEmbedding_apply, Finset.mem_Ico]    constructor    · rintro ⟨hkx, hx⟩      exact ⟨⟨x, hx⟩, hkx, rfl⟩    · rintro ⟨a, hka, rfl⟩      exact ⟨hka, a.isLt⟩  have h2 : ∑ j ∈ Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ)), (F j - F (j + 1)) =      ∑ x ∈ Finset.Ico k n, (F x - F (x + 1)) := by    rw [hmap, Finset.sum_map]    rfl  rw [h2]  have htelescope : ∑ x ∈ Finset.Ico k n, (F x - F (x + 1)) = F k - F n := by    rw [Finset.sum_Ico_eq_sub _ hk, Finset.sum_range_sub', Finset.sum_range_sub']    abel  rw [htelescope]  have hFn : F n = 0 := by    have hempty : Finset.univ.filter (fun j : Fin n => n ≤ (j : ℕ)) = ∅ := by      rw [Finset.filter_eq_empty_iff]      intro x _      exact not_le_of_gt x.isLt    change C ((Finset.univ.filter (fun j : Fin n => n ≤ (j : ℕ))).map π.toEmbedding) = 0    rw [hempty, Finset.map_empty, hC_empty]  rw [hFn, sub_zero]
See it in the graphDiscuss this resultChallenge it