AFTD Auto-Formalizing Theoretical Domains

greedy_vector_sum_univ

lemmaverified

For 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 differences C(S_{rank(i)}) - C(S_{rank(i)+1}) equals C Finset.univ, where S_k is the upper set (Finset.univ.filter (fun j : Fin n => k ≤ (j : ℕ))).map π.toEmbedding.

Statement

lemma greedy_vector_sum_univ {n : ℕ} (C : Finset (Fin n) → ℝ)
    (hC_empty : C ∅ = 0) (π : Equiv.Perm (Fin n)) :
    ∑ i, (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
Source
folklore
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • greedy_vector_chain_saturationFor 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 =…

Read back from the Lean

For any natural number $n$, any set function $C : \text{Finset } (\text{Fin } n) \to \mathbb{R}$ satisfying $C(\emptyset) = 0$, and any permutation $\pi$ of $\text{Fin } n$, the sum over all $i : \text{Fin } n$ of $$C\left(\pi\left(\{ j : \text{Fin } n \mid (\pi^{-1}(i) : \mathbb{N}) \le (j : \mathbb{N}) \}\right)\right) - C\left(\pi\left(\{ j : \text{Fin } n \mid (\pi^{-1}(i) : \mathbb{N}) + 1 \le (j : \mathbb{N}) \}\right)\right)$$ equals $C(\text{Finset.univ})$ (the value of $C$ on the full set $\text{Fin } n$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The total sum of greedy marginal differences along a permutation equals the capacity of the universal set. -/
lemma greedy_vector_sum_univ {n : ℕ} (C : Finset (Fin n) → ℝ)
    (hC_empty : C ∅ = 0) (π : Equiv.Perm (Fin n)) :
    ∑ i, (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 := by
  have h0 : (Finset.univ.filter (fun j : Fin n => 0 ≤ (j : ℕ))).map π.toEmbedding = Finset.univ := by
    have hfilt : (Finset.univ.filter (fun j : Fin n => 0 ≤ (j : ℕ))) = Finset.univ := by
      ext j
      simp
    rw [hfilt]
    ext x
    simp
  have hsat := greedy_vector_chain_saturation C hC_empty π 0 (Nat.zero_le n)
  rw [h0] at hsat
  exact hsat
See it in the graphDiscuss this resultChallenge it