is_submodular_add
The pointwise sum of two submodular set functions is submodular.
Statement
theorem is_submodular_add {m : ℕ} (f g : Finset (Fin m) → ℝ) (hf : is_submodular f) (hg : is_submodular g) : is_submodular (f + g)- Source
- step towards matroid_symmetry_gap_integral_lt_eight_seventeenths
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
The proof, explained
A set function is submodular when it satisfies the diminishing returns property: adding an element to a larger set yields at most as much marginal gain as adding it to a smaller subset. The proof instantiates this condition for both $f$ and $g$ on the same sets $S \subseteq T$ and candidate element $j \notin T$. Since $(f + g)$ is defined pointwise, its marginal gain is the sum of the marginal gains of $f$ and $g$, so the result follows by summing the two inequalities.
Fix subsets $S \subseteq T \subseteq \{0, \dots, m-1\}$ and an element $j \notin T$.
By the definition of submodularity (`is_submodular`), we need to verify the diminishing returns condition for $f + g$: for any $S \subseteq T$ and $j \notin T$, the marginal gain $(f + g)(T \cup \{j\}) - (f + g)(T)$ is bounded above by $(f + g)(S \cup \{j\}) - (f + g)(S)$.
intro S T j hST hjThe diminishing returns inequality holds individually for $f$ and $g$ on $S, T$, and $j$.
Instantiating the submodularity hypotheses `hf` and `hg` on the inclusion $S \subseteq T$ and the element $j \notin T$ yields $f(T \cup \{j\}) - f(T) \le f(S \cup \{j\}) - f(S)$ and $g(T \cup \{j\}) - g(T) \le g(S \cup \{j\}) - g(S)$.
have h1 := hf S T j hST hj have h2 := hg S T j hST hj
The diminishing returns inequality holds for $f + g$, completing the proof.
Expanding the pointwise function addition via `Pi.add_apply` expresses each $(f + g)(X)$ as $f(X) + g(X)$. The required inequality is then precisely the sum of the two inequalities for $f$ and $g$, which is settled by linear real arithmetic (`linarith`).
uses
Pi.add_applysimp only [Pi.add_apply] linarith
Pi.add_apply- The sum of two functions evaluated at an argument is the sum of their values: $(f + g)(x) = f(x) + g(x)$.
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.
/-- The pointwise sum of two submodular set functions is submodular. -/theorem is_submodular_add {m : ℕ} (f g : Finset (Fin m) → ℝ) (hf : is_submodular f) (hg : is_submodular g) : is_submodular (f + g) := by intro S T j hST hj have h1 := hf S T j hST hj have h2 := hg S T j hST hj simp only [Pi.add_apply] linarith