is_k_submodular
def
A function f : (Fin n → Option (Fin k)) → ℝ is k-submodular if for all x and y, f (x ⊓ y) + f (x ⊔ y) ≤ f x + f y.
Statement
def is_k_submodular {n k : ℕ} (f : (Fin n → Option (Fin k)) → ℝ) : Prop
- Defined in
- arXiv:2610.26677, Eq. (1)
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 2
- k_submod_meetMeet of two assignments x and y in Fin n → Option (Fin k): at each coordinate e, it is x e if x e = y e, and none otherwise.
- k_submod_joinJoin of two assignments x and y in Fin n → Option (Fin k): at each coordinate e, if one is none it takes the other, if both agree it takes…
- Used by 3
- k_submodular_of_monotone_of_orthant_diminishing_returnsA monotone function on assignments Fin n → Option (Fin k) that satisfies orthant diminishing returns is k-submodular.
- k_submod_c1_hidden_fn_propertiesFor all natural numbers n > 0 and k ≥ 2, every hidden label assignment σ : Fin n → Fin k, and every function H : ℝ → ℝ → ℝ satisfying…
- not_k_submod_hidden_fn_propertiesThe statement
k_submod_hidden_fn_propertiesis false: The definitionis_k_submod_kernellacks a differentiability/continuity…
Read back from the Lean
Given natural numbers n and k, a function f : (Fin n → Option (Fin k)) → ℝ satisfies is_k_submodular if and only if for all x, y : Fin n → Option (Fin k),
f (k_submod_meet x y) + f (k_submod_join x y) ≤ f x + f y
where for each coordinate e : Fin n:
- k_submod_meet x y e is some i if x e = some i and y e = some i, and none otherwise;
- k_submod_join x y e is y e if x e = none, x e if y e = none, some i if x e = some i and y e = some i, and none if x e = some i and y e = some j with i ≠ j.
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
/-- Predicate asserting that a function on assignments is k-submodular. -/ def is_k_submodular {n k : ℕ} (f : (Fin n → Option (Fin k)) → ℝ) : Prop := ∀ x y, f (k_submod_meet x y) + f (k_submod_join x y) ≤ f x + f y