AFTD Auto-Formalizing Theoretical Domains

base_polytope_submodular

def

The base polytope B(f) of a set function f on Finset (Fin n) is the set of points x in ℝ^n satisfying ∑_{i ∈ S} x i ≤ f(S) for all subsets S and ∑_{i} x i = f(Finset.univ).

Statement

def base_polytope_submodular {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ)
Defined in
Fujishige 1980; Schrijver "Combinatorial Optimization" Sec. 44.1
Verified
11 Nov 2026
Axioms
none listed

Read back from the Lean

Given a natural number $n$ and a set function $f : \mathrm{Finset}(\mathrm{Fin}\ n) \to \mathbb{R}$, base_polytope_submodular f is defined as the set of vectors $x : \mathrm{Fin}\ n \to \mathbb{R}$ satisfying: 1. For every subset $S \subseteq \mathrm{Fin}\ n$, $\sum_{i \in S} x(i) \le f(S)$; and 2. The total sum over all coordinates $\sum_{i : \mathrm{Fin}\ n} x(i)$ equals $f(\mathrm{univ})$.

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

/-- The base polytope B(f) of a set function f on Finset (Fin n). -/
def base_polytope_submodular {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ) := { x | (∀ S : Finset (Fin n), ∑ i ∈ S, x i ≤ f S) ∧ ∑ i : Fin n, x i = f Finset.univ }
See it in the graphDiscuss this resultChallenge it