AFTD Auto-Formalizing Theoretical Domains

is_submodular_smul_nonneg

theoremverified

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.

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

    lines 3–4

      intro S T j hST hj
      have h1 := hf S T j hST hj
  2. 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`.

    line 5

    uses Pi.smul_apply, smul_eq_mul

      simp only [Pi.smul_apply, smul_eq_mul]
  3. 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.

    line 6

      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

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