AFTD Auto-Formalizing Theoretical Domains

base_polytope_extreme_bases

def

The set of greedy bases of a set function f on Finset (Fin n) consists of the vectors generated by Edmonds' greedy algorithm over all permutations π of Fin n.

Statement

def base_polytope_extreme_bases {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ)
Defined in
Edmonds 1970; Fujishige 1980
Verified
11 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given an implicit natural number $n$ and a set function $f : \mathrm{Finset}(\mathrm{Fin}\ n) \to \mathbb{R}$, base_polytope_extreme_bases f is the set of all vectors $p : \mathrm{Fin}\ n \to \mathbb{R}$ for which there exists a permutation $\pi$ of $\mathrm{Fin}\ n$ such that for all $i : \mathrm{Fin}\ n$, $$p(i) = f(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(j) \le \pi^{-1}(i)\}) - f(\{j : \mathrm{Fin}\ n \mid \pi^{-1}(j) < \pi^{-1}(i)\}).$$

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 set of greedy bases (extreme points) of the base polytope of f. -/
def base_polytope_extreme_bases {n : ℕ} (f : Finset (Fin n) → ℝ) : Set (Fin n → ℝ) := { p | ∃ π : Equiv.Perm (Fin n), p = fun i => f (Finset.univ.filter (fun j => π.symm j ≤ π.symm i)) - f (Finset.univ.filter (fun j => π.symm j < π.symm i)) }
See it in the graphDiscuss this resultChallenge it