AFTD Auto-Formalizing Theoretical Domains

is_far_from_submodular

def

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