AFTD Auto-Formalizing Theoretical Domains

is_submodular_add

theoremverified

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.

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

    line 3

      intro S T j hST hj
  2. The 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)$.

    lines 4–5

      have h1 := hf S T j hST hj
      have h2 := hg S T j hST hj
  3. 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`).

    lines 6–7

    uses Pi.add_apply

      simp 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

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