is_submodular_smul_nonneg
Non-negative scaling preserves submodularity of a set function.
Statement
theorem is_submodular_smul_nonneg {m : ℕ} (c : ℝ) (hc : 0 ≤ c) (f : Finset (Fin m) → ℝ) (hf : is_submodular f) : is_submodular (c • f)- 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
To show that non-negative scaling preserves submodularity, we unpack the definition of submodularity for c • f by considering arbitrary nested subsets S ⊆ T and an element j ∉ T. The submodularity of f provides the marginal-gain inequality f(T ∪ {j}) - f(T) ≤ f(S ∪ {j}) - f(S). Multiplying this inequality by the non-negative scalar c preserves the inequality and completes the proof.
Fix subsets S ⊆ T and an element j ∉ T, and obtain the marginal-gain inequality f(T ∪ {j}) - f(T) ≤ f(S ∪ {j}) - f(S)
By the definition of submodularity, we must show that the marginal gain of adding j to T is at most the marginal gain of adding j to S for the scaled function c • f. We introduce arbitrary sets S, T with S ⊆ T and an element j ∉ T. Applying the submodularity hypothesis `hf` to these inputs gives the corresponding inequality for f.
intro S T j hST hj have h1 := hf S T j hST hj
The goal is rewritten to c * f(T ∪ {j}) - c * f(T) ≤ c * f(S ∪ {j}) - c * f(S)
We expand scalar multiplication of functions pointwise using `Pi.smul_apply` and express scalar multiplication on real numbers as standard multiplication via `smul_eq_mul`.
uses
Pi.smul_apply,smul_eq_mulsimp only [Pi.smul_apply, smul_eq_mul]The scaled function c • f satisfies the submodular inequality automation
Since c ≥ 0, multiplying both sides of the inequality f(T ∪ {j}) - f(T) ≤ f(S ∪ {j}) - f(S) by c preserves the inequality. The `nlinarith` tactic verifies this non-linear arithmetic step automatically.
nlinarith
Pi.smul_apply- pointwise scalar multiplication of a function evaluates as `(a • f) i = a • f i`
smul_eq_mul- scalar multiplication of numbers is given by standard multiplication: `a • b = a * b`
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.
/-- Non-negative scaling preserves submodularity of a set function. -/theorem is_submodular_smul_nonneg {m : ℕ} (c : ℝ) (hc : 0 ≤ c) (f : Finset (Fin m) → ℝ) (hf : is_submodular f) : is_submodular (c • f) := by intro S T j hST hj have h1 := hf S T j hST hj simp only [Pi.smul_apply, smul_eq_mul] nlinarith