greedy_vector_observable_value
For 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, if z saturates each upper set S_{k+1} = (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding for all k : Fin (n - 1), then the inner product ∑ i, a i * z i equals a(π(0)) + ∑ k : Fin (n - 1), (a(π(k+1)) - a(π(k))) * C(S_{k+1}).
Statement
lemma greedy_vector_observable_value {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (C : Finset (Fin n) → ℝ) (z : Fin n → ℝ) (hz_sum : ∑ i, z i = 1) (hS : ∀ k : Fin (n - 1), ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding, z i = C ((Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding)) : ∑ i, a i * z i = a (π ⟨0, hn⟩) + ∑ k : Fin (n - 1), (a (π ⟨k.val + 1, by omega⟩) - a (π ⟨k.val, by omega⟩)) * C ((Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding)
- Source
- folklore
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- abel_summation_by_partsFor 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))…
Read back from the Lean
Let $n$ be a positive natural number ($0 < n$), $a : \text{Fin } n \to \mathbb{R}$, $\pi$ a permutation of $\text{Fin } n$, $C : \text{Finset } (\text{Fin } n) \to \mathbb{R}$, and $z : \text{Fin } n \to \mathbb{R}$. Assume: 1. $\sum_{i : \text{Fin } n} z(i) = 1$, and 2. For all $k \in \text{Fin } (n - 1)$, the sum of $z(i)$ over all $i$ in the set $S_k = \pi(\{j : \text{Fin } n \mid k + 1 \le j\})$ equals $C(S_k)$. Then: \[ \sum_{i : \text{Fin } n} a(i) z(i) = a(\pi(0)) + \sum_{k : \text{Fin } (n - 1)} (a(\pi(k + 1)) - a(\pi(k))) \cdot C(S_k), \] where $S_k$ is the image under $\pi$ of the set of indices $j : \text{Fin } n$ with $k + 1 \le j$, and $\pi(0)$, $\pi(k)$, $\pi(k + 1)$ denote $\pi$ evaluated at the corresponding elements of $\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
/-- Evaluating an observable on a vector that saturates the upper set chain gives the telescoping capacity sum. -/ lemma greedy_vector_observable_value {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (C : Finset (Fin n) → ℝ) (z : Fin n → ℝ) (hz_sum : ∑ i, z i = 1) (hS : ∀ k : Fin (n - 1), ∑ i ∈ (Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding, z i = C ((Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding)) : ∑ i, a i * z i = a (π ⟨0, hn⟩) + ∑ k : Fin (n - 1), (a (π ⟨k.val + 1, by omega⟩) - a (π ⟨k.val, by omega⟩)) * C ((Finset.univ.filter (fun j : Fin n => k.val + 1 ≤ (j : ℕ))).map π.toEmbedding) := by rw [abel_summation_by_parts hn a π z hz_sum] congr 1 apply Finset.sum_congr rfl intro k hk rw [hS k]