AFTD Auto-Formalizing Theoretical Domains

observable_upper_bound_base_polytope

theoremverifiedformalization

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 than LinearOrder — 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 LinearOrder is a TotalPreorder.

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

/-- 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 _
See it in the graphDiscuss this resultChallenge it