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