op_932_submodular_not_far
For any positive ε, a submodular function from Fin n → Bool to Fin (k + 1) is not ε-far from submodularity.
Statement
theorem op_932_submodular_not_far (n k : ℕ) (f : (Fin n → Bool) → Fin (k + 1))
(hf : is_submodular_bounded n k f) (ε : ℝ) (hε : 0 < ε) :
¬ is_eps_far_submodular n k ε f- Source
- arXiv:2611.02374 Def. 2.4
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- is_eps_far_submodularA 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 +…
- 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…
Read back from the Lean
For all natural numbers $n$ and $k$, for any function $f : (\text{Fin } n \to \text{Bool}) \to \text{Fin}(k + 1)$ that is submodular bounded (meaning for all $x, y : \text{Fin } n \to \text{Bool}$, the real values satisfy $f(x \sqcup y) + f(x \sqcap y) \le f(x) + f(y)$), and for any real number $\varepsilon > 0$, $f$ is not $\varepsilon$-far from being submodular (that is, it is not the case that every submodular bounded function $g : (\text{Fin } n \to \text{Bool}) \to \text{Fin}(k + 1)$ has relative hypercube distance at least $\varepsilon$ from $f$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction: suppose f is ε-far from submodularity. By definition of ε-farness, every submodular function must have relative distance at least ε from f. But f is itself submodular, so its relative distance to itself must be at least ε, implying ε ≤ 0 and contradicting the assumption that ε > 0.
If f were ε-far from submodularity, then the relative distance from f to itself would be at least ε.
Assume for contradiction that f is ε-far from submodularity (h). By definition, this means that every submodular function g satisfies ε ≤ dist(f, g). Since f itself is submodular (by assumption hf), we can test this condition on g = f, which yields ε ≤ hypercube_rel_dist f f.
intro h have hf_near := h f hf
Contradiction.
The set of inputs where f(x) ≠ f(x) is empty, so unfolding the definition of hypercube_rel_dist simplifies the self-distance to 0, leaving ε ≤ 0. Linear arithmetic then derives a contradiction with the hypothesis that ε > 0.
uses
hypercube_rel_distsimp [hypercube_rel_dist] at hf_near linarith
hypercube_rel_dist- The relative distance between two functions on the Boolean hypercube, defined as the fraction of inputs where they differ: |{x | f(x) ≠ g(x)}| / 2^n.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A submodular function is never ε-far from submodularity for any positive ε. -/theorem op_932_submodular_not_far (n k : ℕ) (f : (Fin n → Bool) → Fin (k + 1)) (hf : is_submodular_bounded n k f) (ε : ℝ) (hε : 0 < ε) : ¬ is_eps_far_submodular n k ε f := by intro h have hf_near := h f hf simp [hypercube_rel_dist] at hf_near linarith