AFTD Auto-Formalizing Theoretical Domains

op_932_submodular_not_far

theoremverified

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.

  1. 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.

    lines 5–6

      intro h
      have hf_near := h f hf
  2. 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.

    lines 7–8

    uses hypercube_rel_dist

      simp [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

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