greedy_vector_chain_saturation
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).
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.
uses
Finset.sum_map,Equiv.toEmbedding_apply,Equiv.symm_apply_applylet 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]
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.
uses
Finset.mem_map,Finset.mem_filter,Finset.mem_univ,true_and,Fin.valEmbedding_apply,Finset.mem_Icohave 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⟩
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)).
uses
Finset.sum_maphave 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]
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).
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]
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.
uses
Finset.filter_eq_empty_iff,not_le_of_gt,Finset.map_emptyhave 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]
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.
uses
sub_zerorw [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.
- Line 33 uses the `abel` tactic to perform the abelian group simplification $(F(0) - F(n)) - (F(0) - F(k)) = F(k) - F(n)$.
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.
/-- 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]