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 : ℝ)