is_far_from_submodular
A function f is ε-far from submodular if its normalized Hamming distance to every submodular function g with the same domain and codomain is at least ε.
Statement
def is_far_from_submodular {n k : ℕ} (ε : ℝ) (f : CubeFunc n k) : Prop
- Defined in
- arXiv:2611.02374, Def. 2.4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 3
- CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
- is_submodular_cubeA function f from the Boolean hypercube to {0, ..., k} is submodular if f(x ∨ y) + f(x ∧ y) ≤ f(x) + f(y) for all x, y in {0, 1}^n when…
- cube_distThe normalized Hamming distance between two functions f, g : {0, 1}^n → {0, ..., k} is the fraction of points in {0, 1}^n where f and g…
Read back from the Lean
Given natural numbers $n$ and $k$, a real number $\varepsilon$, and a function $f : (\text{Fin } n \to \text{Bool}) \to \text{Fin}(k + 1)$, is_far_from_submodular ε f asserts that for every function $g : (\text{Fin } n \to \text{Bool}) \to \text{Fin}(k + 1)$, if $g$ is submodular on the Boolean hypercube (meaning that for all $x, y : \text{Fin } n \to \text{Bool}$, $(g(x \sqcup y) : \mathbb{R}) + (g(x \sqcap y) : \mathbb{R}) \le (g(x) : \mathbb{R}) + (g(y) : \mathbb{R})$), then $\varepsilon$ is less than or equal to the normalized Hamming distance between $f$ and $g$, which is the number of inputs $x : \text{Fin } n \to \text{Bool}$ such that $f(x) \neq g(x)$ divided by $2^n$.
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 is ε-far from submodular if every submodular function disagrees on at least an ε fraction of inputs. -/ def is_far_from_submodular {n k : ℕ} (ε : ℝ) (f : CubeFunc n k) : Prop := ∀ g : CubeFunc n k, is_submodular_cube g → ε ≤ cube_dist f g