AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it