AFTD Auto-Formalizing Theoretical Domains

op_932_constant_fn_submodular

theoremverified

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.

  1. 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`).

    line 3

    uses is_submodular_bounded, vector_seq_max_entry_constant

        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)
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$.

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

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