AFTD Auto-Formalizing Theoretical Domains

is_eps_far_submodular

def

A 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 + 1), the relative Hamming distance between f and g is at least ε.

Statement

def is_eps_far_submodular (n k : ℕ) (ε : ℝ) (f : (Fin n → Bool) → Fin (k + 1)) : Prop
Defined in
arXiv:2611.02374 Def. 2.4
Verified
05 Nov 2026
Axioms
none listed
Built on 2
  • is_submodular_boundedA 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.
  • hypercube_rel_distThe relative Hamming distance between two functions f and g from the hypercube Fin n → Bool into Fin (k + 1) is the number of inputs where…
Used by 1
  • 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

Given natural numbers n and k, a real number ε, and a function f : (Fin n → Bool) → Fin (k + 1), is_eps_far_submodular n k ε f asserts that for every function g : (Fin n → Bool) → Fin (k + 1), if g satisfies is_submodular_bounded n k g, then the relative distance hypercube_rel_dist f g is greater than or equal to ε.

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

/-- A function from Fin n → Bool to Fin (k + 1) is ε-far from submodular if its relative distance to every submodular function is at least ε. -/
def is_eps_far_submodular (n k : ℕ) (ε : ℝ) (f : (Fin n → Bool) → Fin (k + 1)) : Prop :=
  ∀ g : (Fin n → Bool) → Fin (k + 1), is_submodular_bounded n k g → ε ≤ hypercube_rel_dist f g
See it in the graphDiscuss this resultChallenge it