greedy_vector_sum_univ
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