op_932_constant_fn_submodular
For any n, k, and value v, the constant function f(x) = v on {0, 1}^n is submodular.
Statement
theorem op_932_constant_fn_submodular (n k : ℕ) (v : Fin (k + 1)) : is_submodular_bounded n k (fun _ => v)
- Source
- arXiv:2611.02374 Def. 2.1
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- vector_seq_max_entry_constantFor positive integers n and k, the maximum entry of a constant sequence of vectors equal to c is c.
Read back from the Lean
For all natural numbers $n$ and $k$, and for every $v : \mathrm{Fin}(k + 1)$, the constant function $(\lambda \_ \mapsto v) : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to \mathrm{Fin}(k + 1)$ satisfies is_submodular_bounded n k.
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
To show that a constant function $f(x) = v$ on the Boolean hypercube is submodular, we unfold the definition of submodularity. The condition requires that $f(x \sqcup y) + f(x \sqcap y) \le f(x) + f(y)$ for all $x$ and $y$, which simplifies to $v + v \le v + v$. This inequality holds trivially by the reflexivity of $\le$ on real numbers.
The constant function $f(x) = v$ satisfies the submodularity condition $f(x \sqcup y) + f(x \sqcap y) \le f(x) + f(y)$ for all $x, y \in \{0, 1\}^n$. automation
Unfolding the definition of `is_submodular_bounded` reduces the goal to showing that $(v : \mathbb{R}) + v \le v + v$ for any inputs $x$ and $y$. This inequality is an identity ($2v \le 2v$), which holds trivially by reflexivity of $\le$ and is solved directly by simplification (`simpa`).
uses
is_submodular_bounded,vector_seq_max_entry_constantis_submodular_bounded n k (fun _ => v) := by first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant | (simp only [is_submodular_bounded] at *; first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant)
is_submodular_bounded- A function $f : (\{0, 1\}^n) \to \{0, \dots, k\}$ is submodular if for all $x, y$, $f(x \sqcup y) + f(x \sqcap y) \le f(x) + f(y)$ holds in $\mathbb{R}$.
vector_seq_max_entry_constant- For positive dimensions $n$ and $k$, the maximum entry of an $n \times k$ matrix with all entries equal to $c$ is $c$.
- The proof was generated by an automated search pattern using `first | ...`. In the branch that succeeds, `vector_seq_max_entry_constant` is passed to `simpa`, but it is entirely unused: Lean's simplifier closes the goal on its own because the inequality $v + v \le v + v$ simplifies to `True` by the reflexivity of $\le$.
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.
/-- Constant functions on the hypercube with bounded range are submodular. -/theorem op_932_constant_fn_submodular (n k : ℕ) (v : Fin (k + 1)) : is_submodular_bounded n k (fun _ => v) := by first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant | (simp only [is_submodular_bounded] at *; first | exact vector_seq_max_entry_constant | (apply vector_seq_max_entry_constant <;> assumption) | (apply vector_seq_max_entry_constant <;> simp_all) | simpa using vector_seq_max_entry_constant)