all_cube_func_one_is_submodular
On the 1-dimensional Boolean hypercube, every function f : {0, 1}^1 → {0, ..., k} is submodular.
Statement
theorem all_cube_func_one_is_submodular (k : ℕ) (f : CubeFunc 1 k) :
is_submodular_cube f- Source
- arXiv:2611.02374, Sec. 2
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
Read back from the Lean
For every natural number $k$ and every function $f : (\mathrm{Fin}\ 1 \to \mathrm{Bool}) \to \mathrm{Fin}(k + 1)$, $f$ is a submodular cube function (is_submodular_cube 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 case analysis on the relative order of the single coordinates of any two vertices x, y in {0, 1}¹. Because the hypercube has dimension 1, its elements are totally ordered: either x ≤ y or y ≤ x. In either case, the two vertices are comparable, so their join and meet are simply the vertices themselves in some order (that is, {x ⊔ y, x ⊓ y} = {x, y}). The submodularity inequality f(x ⊔ y) + f(x ⊓ y) ≤ f(x) + f(y) then reduces to an equality f(x) + f(y) = f(x) + f(y), which holds trivially.
To prove f is submodular, it suffices to consider arbitrary vertices x, y ∈ {0, 1}¹, which satisfy either x(0) ≤ y(0) or y(0) ≤ x(0).
Unfolding the definition of submodularity introduces two arbitrary hypercube vertices x and y. Because `Bool` is linearly ordered, its values at the coordinate 0 are comparable by totality (`le_total`), giving two cases: x(0) ≤ y(0) or y(0) ≤ x(0).
uses
le_totalintro x y rcases le_total (x 0) (y 0) with h | h
The submodularity inequality holds in the case where x(0) ≤ y(0).
Because the index set Fin 1 has a unique element (any index i equals 0 by `Subsingleton.elim`), x(0) ≤ y(0) implies x ≤ y coordinatewise. For comparable elements with x ≤ y, their join is y (`sup_eq_right.mpr`) and their meet is x (`inf_eq_left.mpr`). Rewriting the submodularity goal with these equalities gives f(y) + f(x) ≤ f(x) + f(y), which holds by commutativity of real addition.
uses
Subsingleton.elim,sup_eq_right.mpr,inf_eq_left.mpr· have hle : x ≤ y := by intro i rw [Subsingleton.elim i 0] exact h rw [sup_eq_right.mpr hle, inf_eq_left.mpr hle] linarith
The submodularity inequality holds in the case where y(0) ≤ x(0).
Symmetrically, since any index i in Fin 1 equals 0 (`Subsingleton.elim`), y(0) ≤ x(0) implies y ≤ x coordinatewise. Hence the join x ⊔ y is x (`sup_eq_left.mpr`) and the meet x ⊓ y is y (`inf_eq_right.mpr`). Rewriting with these identities simplifies the inequality to f(x) + f(y) ≤ f(x) + f(y), which holds identically by reflexivity.
uses
Subsingleton.elim,sup_eq_left.mpr,inf_eq_right.mpr· have hle : y ≤ x := by intro i rw [Subsingleton.elim i 0] exact h rw [sup_eq_left.mpr hle, inf_eq_right.mpr hle]
le_total- Any two elements in a linear order are comparable: a ≤ b or b ≤ a.
Subsingleton.elim- Any two elements of a subsingleton type (a type with at most one element) are equal.
sup_eq_right.mpr- If a ≤ b, then the least upper bound (join) a ⊔ b equals b.
inf_eq_left.mpr- If a ≤ b, then the greatest lower bound (meet) a ⊓ b equals a.
sup_eq_left.mpr- If b ≤ a, then the least upper bound (join) a ⊔ b equals a.
inf_eq_right.mpr- If b ≤ a, then the greatest lower bound (meet) a ⊓ b equals b.
- In Lean, the 1-dimensional Boolean hypercube is represented as functions from `Fin 1` to `Bool`. Comparing two points coordinatewise reduces to checking the single coordinate `0` via `Subsingleton.elim`.
- On line 16, rewriting with `sup_eq_left.mpr` and `inf_eq_right.mpr` leaves the inequality `f x + f y ≤ f x + f y`, which `rw` automatically closes by reflexivity.
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.
/-- Every function on the 1-dimensional Boolean hypercube is submodular. -/theorem all_cube_func_one_is_submodular (k : ℕ) (f : CubeFunc 1 k) : is_submodular_cube f := by intro x y rcases le_total (x 0) (y 0) with h | h · have hle : x ≤ y := by intro i rw [Subsingleton.elim i 0] exact h rw [sup_eq_right.mpr hle, inf_eq_left.mpr hle] linarith · have hle : y ≤ x := by intro i rw [Subsingleton.elim i 0] exact h rw [sup_eq_left.mpr hle, inf_eq_right.mpr hle]