AFTD Auto-Formalizing Theoretical Domains

is_submodular_bounded

def

A function f on {0, 1}^n with range {0, 1, ..., k} is submodular if f(x ⊔ y) + f(x ⊓ y) ≤ f(x) + f(y) for all x and y.

Statement

def is_submodular_bounded (n k : ℕ) (f : (Fin n → Bool) → Fin (k + 1)) : Prop
Defined in
arXiv:2611.02374 Def. 2.1
Verified
05 Nov 2026
Axioms
none listed
Used by 3
  • op_932_constant_fn_submodularFor any n, k, and value v, the constant function f(x) = v on {0, 1}^n is submodular.
  • is_eps_far_submodularA function f from Fin n → Bool to Fin (k + 1) is ε-far from submodularity if for every submodular function g from Fin n → Bool to Fin (k +…
  • op_932_submodular_not_farFor any positive ε, a submodular function from Fin n → Bool to Fin (k + 1) is not ε-far from submodularity.

Read back from the Lean

For given natural numbers n and k, and a function f : (Fin n → Bool) → Fin (k + 1), is_submodular_bounded n k f asserts that for all x, y : Fin n → Bool, the sum of the real-valued coercions of f (x ⊔ y) and f (x ⊓ y) is less than or equal to the sum of the real-valued coercions of f x and f y, where ⊔ and ⊓ are the pointwise lattice operations (disjunction and conjunction) on Fin n → Bool, and elements of Fin (k + 1) are coerced to ℝ via their natural number value Fin.val.

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

/-- Submodularity for functions from the n-dimensional hypercube to Fin (k + 1). -/
def is_submodular_bounded (n k : ℕ) (f : (Fin n → Bool) → Fin (k + 1)) : Prop :=
  ∀ x y : Fin n → Bool, (f (x ⊔ y) : ℝ) + (f (x ⊓ y) : ℝ) ≤ (f x : ℝ) + (f y : ℝ)
See it in the graphDiscuss this resultChallenge it