observable_upper_bound_base_polytope
For any vector a whose values are sorted non-decreasingly by permutation π, and any point z in the base polytope of C, the inner product ∑ i, a i * z i is bounded by a(π(0)) + ∑_{k=0}^{n-2} (a(π(k+1)) - a(π(k))) * C(S_{k+1}).
Statement
theorem observable_upper_bound_base_polytope {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (hπ_mono : Monotone (a ∘ π)) (C : Finset (Fin n) → ℝ) (z : Fin n → ℝ) (hz : z ∈ submodular_base_polytope C) : ∑ 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)
- Formalizes
- arXiv:2610.35433 Corollary 1 proof
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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))…
- submodular_base_polytopeThe base polytope B(f) of a set function f on Finset (Fin m) is the set of vectors z in ℝ^m such that the sum of z over every subset S is…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
Read back from the Lean
Let $n$ be a positive natural number ($n > 0$).
Let $a : \text{Fin } n \to \mathbb{R}$.
Let $\pi$ be a permutation of $\text{Fin } n$.
Assume that $a \circ \pi$ is monotone (i.e., for all $i, j \in \text{Fin } n$, if $i \le j$ then $a(\pi(i)) \le a(\pi(j))$).
Let $C : \text{Finset}(\text{Fin } n) \to \mathbb{R}$ be a set function.
Let $z : \text{Fin } n \to \mathbb{R}$ be a point in submodular_base_polytope C.
Then the inner product $\sum_{i \in \text{Fin } n} a(i) z(i)$ is bounded above by:
$$a(\pi(0)) + \sum_{k \in \text{Fin }(n-1)} (a(\pi(k+1)) - a(\pi(k))) \cdot C(\pi(\{j \in \text{Fin } n \mid j \ge k + 1\}))$$
where:
- $\pi(0)$ denotes $\pi$ applied to $0 \in \text{Fin } n$,
- for $k \in \text{Fin }(n-1)$, $k$ and $k+1$ are viewed as elements of $\text{Fin } n$,
- and $\pi(\{j \in \text{Fin } n \mid j \ge k+1\})$ denotes the image under $\pi$ of the subset of elements in $\text{Fin } n$ whose index is at least $k+1$.
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
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.
/-- Upper bound on the expectation of an observable over the base polytope of a submodular capacity. -/theorem observable_upper_bound_base_polytope {n : ℕ} (hn : 0 < n) (a : Fin n → ℝ) (π : Equiv.Perm (Fin n)) (hπ_mono : Monotone (a ∘ π)) (C : Finset (Fin n) → ℝ) (z : Fin n → ℝ) (hz : z ∈ submodular_base_polytope C) : ∑ 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 have hz_sum : ∑ i, z i = 1 := hz.2 have hz_le : ∀ S, ∑ i ∈ S, z i ≤ C S := hz.1 rw [abel_summation_by_parts hn a π z hz_sum] gcongr with k · have hle_fin : (⟨k.val, by omega⟩ : Fin n) ≤ ⟨k.val + 1, by omega⟩ := by simp only [Fin.le_iff_val_le_val] omega have hmono := hπ_mono hle_fin dsimp [Function.comp] at hmono linarith · exact hz_le _