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 : ℝ)