AFTD Auto-Formalizing Theoretical Domains

is_submodular_cube

def

A 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 embedded into ℝ.

Statement

def is_submodular_cube {n k : ℕ} (f : CubeFunc n k) : Prop
Defined in
arXiv:2611.02374, Def. 2.1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
Used by 3
  • is_far_from_submodularA function f is ε-far from submodular if its normalized Hamming distance to every submodular function g with the same domain and codomain…
  • all_cube_func_one_is_submodularOn the 1-dimensional Boolean hypercube, every function f : {0, 1}^1 → {0, ..., k} is submodular.
  • not_submodular_cube_three_twoFor dimension n = 3 and range bound k = 2, the conjunction function x ↦ if x 0 ∧ x 1 then 1 else 0 is not submodular.

Read back from the Lean

For fixed natural numbers n and k, a function f : (Fin n → Bool) → Fin (k + 1) satisfies is_submodular_cube if and only if for all x, y : Fin n → Bool, the sum of f(x ⊔ y) and f(x ⊓ y) (coerced from Fin (k + 1) to ℝ) is less than or equal to the sum of f(x) and f(y) (coerced to ℝ), where ⊔ and ⊓ are the pointwise lattice operations (boolean OR and AND) on Fin n → Bool.

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

/-- Submodularity of a function on the Boolean hypercube into {0, ..., k} embedded in ℝ. -/
def is_submodular_cube {n k : ℕ} (f : CubeFunc n k) : Prop := ∀ x y : Fin n → Bool, (f (x ⊔ y) : ℝ) + (f (x ⊓ y) : ℝ) ≤ (f x : ℝ) + (f y : ℝ)
See it in the graphDiscuss this resultChallenge it