abel_summation_by_parts
For any positive dimension n, vector a, permutation π of Fin n, and vector z summing to 1, the inner product ∑ i, a i * z i equals a(π(0)) plus the sum over k from 0 to n-2 of (a(π(k+1)) - a(π(k))) times the sum of z over the upper set of elements with rank at least k+1.
Statement
theorem abel_summation_by_parts {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (z : Fin n → ℝ) (hz_sum : ∑ i, z i = 1) : ∑ i, a i * z i = a (π ⟨0, hn⟩) + ∑ k : Fin (n - 1), (a (π ⟨k.val + 1, by omega⟩) - a (π ⟨k.val, by omega⟩)) * ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding, z i
- Source
- arXiv:2610.35433 Corollary 1 proof
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- Used by 2
- observable_upper_bound_base_polytopeFor any vector a whose values are sorted non-decreasingly by permutation π, and any point z in the base polytope of C, the inner product ∑…
- greedy_vector_observable_valueFor any positive natural number n (0 < n), vector a, permutation π of Fin n, set function C on Finset (Fin n), and vector z summing to 1,…
Read back from the Lean
For any natural number $n$ (implicit), given:
- a hypothesis $hn : 0 < n$,
- a function $a : \text{Fin } n \to \mathbb{R}$,
- a permutation $\pi \in \text{Equiv.Perm}(\text{Fin } n)$,
- a function $z : \text{Fin } n \to \mathbb{R}$, and
- a hypothesis $hz\_sum : \sum_{i : \text{Fin } n} z(i) = 1$,
the sum $\sum_{i : \text{Fin } n} a(i) z(i)$ equals
$$a(\pi(\langle 0, hn \rangle)) + \sum_{k : \text{Fin } (n - 1)} \left( a(\pi(\langle k.val + 1, \dots \rangle)) - a(\pi(\langle k.val, \dots \rangle)) \right) \cdot \sum_{i \in S_k} z(i)$$
where $S_k = \pi \left( \{ j : \text{Fin } n \mid k.val + 1 \le j.val \} \right)$ is the image under $\pi$ (via π.toEmbedding) of the finset of elements $j : \text{Fin } n$ whose value is at least $k.val + 1$.
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
We prove Abel summation by parts in range form using standard summation by parts, express it over `Fin n` via zero-extension, and then apply it to the permuted sequence to obtain the final identity.
The range form of Abel summation by parts holds.
By applying standard summation by parts on `Finset.range N` and rewriting suffix sums as the total sum minus prefix sums, telescoping the sum of differences yields the desired identity.
uses
Finset.sum_range_by_partshave hmain := Finset.sum_range_by_parts b w N simp only [smul_eq_mul] at hmain rw [hmain] have hS : ∀ k ∈ Finset.range (N - 1), (∑ j ∈ (Finset.range N).filter (fun j => k + 1 ≤ j), w j) = (∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j := by intro k hk have hk' : k + 1 ≤ N := by have : k < N - 1 := Finset.mem_range.mp hk omega exact (Finset.sum_range_sub_sum_range (f := w) hk').symm have hS2 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ∑ j ∈ (Finset.range N).filter (fun j => k + 1 ≤ j), w j) = ∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ((∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j) := by apply Finset.sum_congr rfl intro k hk rw [hS k hk] rw [hS2] have h1 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ((∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j)) = (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * (∑ j ∈ Finset.range N, w j)) - ∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ∑ j ∈ Finset.range (k + 1), w j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro k hk ring rw [h1] have h2 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * (∑ j ∈ Finset.range N, w j)) = (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k)) * (∑ j ∈ Finset.range N, w j) := by rw [Finset.sum_mul] rw [h2, Finset.sum_range_sub] ring
The rest holds.
The rest of the lemmas transfer the identity to `Fin n` and apply it to the permutation.
uses
abel_summation_by_parts_fin_identityprivate lemma abel_summation_by_parts_inner_sum_range {n : ℕ} (w : Fin n → ℝ) (m : ℕ) : (∑ j ∈ Finset.univ.filter (fun j : Fin n => m + 1 ≤ (j : ℕ)), w j) = ∑ j ∈ (Finset.range n).filter (fun j => m + 1 ≤ j), (fun k => if h : k < n then w ⟨k, h⟩ else 0) j := by rw [Finset.sum_filter] rw [Finset.sum_filter] rw [← Fin.sum_univ_eq_sum_range (fun k => if m + 1 ≤ k then (if h : k < n then w ⟨k, h⟩ else 0) else 0) n] apply Finset.sum_congr rfl intro j hj by_cases h : m + 1 ≤ (j : ℕ) · rw [if_pos h] rw [dif_pos j.isLt] simp [h] · rw [if_neg h] simp [h] /-- The Abel summation identity expressed over `Fin n`: the weighted sum equals the first weight plus a telescoping sum weighted by suffix sums. -/ private lemma abel_summation_by_parts_fin_identity {n : ℕ} (hn : 0 < n) (b w : Fin n → ℝ) (hw : ∑ i, w i = 1) : ∑ i, b i * w i = b ⟨0, hn⟩ + ∑ k : Fin (n - 1), (b ⟨k.val + 1, by omega⟩ - b ⟨k.val, by omega⟩) * ∑ j ∈ Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ)), w j := by set B : ℕ → ℝ := fun m => if h : m < n then b ⟨m, h⟩ else 0 set W : ℕ → ℝ := fun m => if h : m < n then w ⟨m, h⟩ else 0 have hB : ∀ i : Fin n, B i.val = b i := by intro i; simp [B, i.isLt] have hW : ∀ i : Fin n, W i.val = w i := by intro i; simp [W, i.isLt] have hWsum : ∑ m ∈ Finset.range n, W m = 1 := by rw [← Fin.sum_univ_eq_sum_range W n] rw [show (∑ i : Fin n, W ↑i) = ∑ i : Fin n, w i from Finset.sum_congr rfl (fun i _ => hW i)] exact hw have hr := abel_summation_by_parts_range_identity n B W hn rw [hWsum] at hr have hB0 : B 0 = b ⟨0, hn⟩ := by simp [B, hn] rw [hB0, mul_one] at hr have hLHS : ∑ i : Fin n, b i * w i = ∑ i ∈ Finset.range n, B i * W i := by rw [← Fin.sum_univ_eq_sum_range (fun m => B m * W m) n] apply Finset.sum_congr rfl intro i hi rw [hB i, hW i] have hRHS : (∑ k : Fin (n - 1), (b ⟨k.val + 1, by omega⟩ - b ⟨k.val, by omega⟩) * ∑ j ∈ Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ)), w j) = ∑ k ∈ Finset.range (n - 1), (B (k + 1) - B k) * ∑ j ∈ (Finset.range n).filter (fun j => k + 1 ≤ j), W j := by refine Finset.sum_bij (fun (k : Fin (n - 1)) _ => k.val) ?_ ?_ ?_ ?_ · intro k hk; exact Finset.mem_range.mpr k.isLt · intro k1 _ k2 _ heq; exact Fin.ext heq · intro m hm exact ⟨⟨m, Finset.mem_range.mp hm⟩, Finset.mem_univ _, rfl⟩ · intro k hk rw [hB ⟨k.val, by omega⟩, hB ⟨k.val + 1, by omega⟩] congr 1 exact abel_summation_by_parts_inner_sum_range w k.val rw [hLHS, hRHS] rw [hr] /-- Summation by parts (Abel summation) for an observable expectation over a probability distribution. -/ theorem abel_summation_by_parts {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (z : Fin n → ℝ) (hz_sum : ∑ i, z i = 1) : ∑ i, a i * z i = a (π ⟨0, hn⟩) + ∑ k : Fin (n - 1), (a (π ⟨k.val + 1, by omega⟩) - a (π ⟨k.val, by omega⟩)) * ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding, z i := by have hw : ∑ i : Fin n, z (π i) = 1 := by rw [Equiv.sum_comp π z, hz_sum] have hmain := abel_summation_by_parts_fin_identity hn (fun i => a (π i)) (fun i => z (π i)) hw rw [← Equiv.sum_comp π (fun i => a i * z i)] rw [hmain] congr 1 apply Finset.sum_congr rfl intro k hk congr 1 rw [Finset.sum_map] rfl
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.
/-- Abel summation by parts in range form: the weighted sum equals the first weight times thetotal mass plus a telescoping sum against suffix sums. -/private lemma abel_summation_by_parts_range_identity (N : ℕ) (b w : ℕ → ℝ) (hN : 0 < N) : ∑ i ∈ Finset.range N, b i * w i = b 0 * (∑ i ∈ Finset.range N, w i) + ∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ∑ j ∈ (Finset.range N).filter (fun j => k + 1 ≤ j), w j := by have hmain := Finset.sum_range_by_parts b w N simp only [smul_eq_mul] at hmain rw [hmain] have hS : ∀ k ∈ Finset.range (N - 1), (∑ j ∈ (Finset.range N).filter (fun j => k + 1 ≤ j), w j) = (∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j := by intro k hk have hk' : k + 1 ≤ N := by have : k < N - 1 := Finset.mem_range.mp hk omega exact (Finset.sum_range_sub_sum_range (f := w) hk').symm have hS2 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ∑ j ∈ (Finset.range N).filter (fun j => k + 1 ≤ j), w j) = ∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ((∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j) := by apply Finset.sum_congr rfl intro k hk rw [hS k hk] rw [hS2] have h1 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ((∑ j ∈ Finset.range N, w j) - ∑ j ∈ Finset.range (k + 1), w j)) = (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * (∑ j ∈ Finset.range N, w j)) - ∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * ∑ j ∈ Finset.range (k + 1), w j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro k hk ring rw [h1] have h2 : (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k) * (∑ j ∈ Finset.range N, w j)) = (∑ k ∈ Finset.range (N - 1), (b (k + 1) - b k)) * (∑ j ∈ Finset.range N, w j) := by rw [Finset.sum_mul] rw [h2, Finset.sum_range_sub] ring/-- A suffix sum over `Fin n` agrees with the corresponding suffix sum over `range n` afterextending the function by zero off the range. -/private lemma abel_summation_by_parts_inner_sum_range {n : ℕ} (w : Fin n → ℝ) (m : ℕ) : (∑ j ∈ Finset.univ.filter (fun j : Fin n => m + 1 ≤ (j : ℕ)), w j) = ∑ j ∈ (Finset.range n).filter (fun j => m + 1 ≤ j), (fun k => if h : k < n then w ⟨k, h⟩ else 0) j := by rw [Finset.sum_filter] rw [Finset.sum_filter] rw [← Fin.sum_univ_eq_sum_range (fun k => if m + 1 ≤ k then (if h : k < n then w ⟨k, h⟩ else 0) else 0) n] apply Finset.sum_congr rfl intro j hj by_cases h : m + 1 ≤ (j : ℕ) · rw [if_pos h] rw [dif_pos j.isLt] simp [h] · rw [if_neg h] simp [h]/-- The Abel summation identity expressed over `Fin n`: the weighted sum equals the first weightplus a telescoping sum weighted by suffix sums. -/private lemma abel_summation_by_parts_fin_identity {n : ℕ} (hn : 0 < n) (b w : Fin n → ℝ) (hw : ∑ i, w i = 1) : ∑ i, b i * w i = b ⟨0, hn⟩ + ∑ k : Fin (n - 1), (b ⟨k.val + 1, by omega⟩ - b ⟨k.val, by omega⟩) * ∑ j ∈ Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ)), w j := by set B : ℕ → ℝ := fun m => if h : m < n then b ⟨m, h⟩ else 0 set W : ℕ → ℝ := fun m => if h : m < n then w ⟨m, h⟩ else 0 have hB : ∀ i : Fin n, B i.val = b i := by intro i; simp [B, i.isLt] have hW : ∀ i : Fin n, W i.val = w i := by intro i; simp [W, i.isLt] have hWsum : ∑ m ∈ Finset.range n, W m = 1 := by rw [← Fin.sum_univ_eq_sum_range W n] rw [show (∑ i : Fin n, W ↑i) = ∑ i : Fin n, w i from Finset.sum_congr rfl (fun i _ => hW i)] exact hw have hr := abel_summation_by_parts_range_identity n B W hn rw [hWsum] at hr have hB0 : B 0 = b ⟨0, hn⟩ := by simp [B, hn] rw [hB0, mul_one] at hr have hLHS : ∑ i : Fin n, b i * w i = ∑ i ∈ Finset.range n, B i * W i := by rw [← Fin.sum_univ_eq_sum_range (fun m => B m * W m) n] apply Finset.sum_congr rfl intro i hi rw [hB i, hW i] have hRHS : (∑ k : Fin (n - 1), (b ⟨k.val + 1, by omega⟩ - b ⟨k.val, by omega⟩) * ∑ j ∈ Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ)), w j) = ∑ k ∈ Finset.range (n - 1), (B (k + 1) - B k) * ∑ j ∈ (Finset.range n).filter (fun j => k + 1 ≤ j), W j := by refine Finset.sum_bij (fun (k : Fin (n - 1)) _ => k.val) ?_ ?_ ?_ ?_ · intro k hk; exact Finset.mem_range.mpr k.isLt · intro k1 _ k2 _ heq; exact Fin.ext heq · intro m hm exact ⟨⟨m, Finset.mem_range.mp hm⟩, Finset.mem_univ _, rfl⟩ · intro k hk rw [hB ⟨k.val, by omega⟩, hB ⟨k.val + 1, by omega⟩] congr 1 exact abel_summation_by_parts_inner_sum_range w k.val rw [hLHS, hRHS] rw [hr]/-- Summation by parts (Abel summation) for an observable expectation over a probability distribution. -/theorem abel_summation_by_parts {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (z : Fin n → ℝ) (hz_sum : ∑ i, z i = 1) : ∑ i, a i * z i = a (π ⟨0, hn⟩) + ∑ k : Fin (n - 1), (a (π ⟨k.val + 1, by omega⟩) - a (π ⟨k.val, by omega⟩)) * ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding, z i := by have hw : ∑ i : Fin n, z (π i) = 1 := by rw [Equiv.sum_comp π z, hz_sum] have hmain := abel_summation_by_parts_fin_identity hn (fun i => a (π i)) (fun i => z (π i)) hw rw [← Equiv.sum_comp π (fun i => a i * z i)] rw [hmain] congr 1 apply Finset.sum_congr rfl intro k hk congr 1 rw [Finset.sum_map] rfl