AFTD Auto-Formalizing Theoretical Domains

multilinear_extension_add

theoremverified

The multilinear extension of a sum of set functions is the sum of their multilinear extensions.

Statement

theorem multilinear_extension_add {m : ℕ} (f g : Finset (Fin m) → ℝ) (x : Fin m → ℝ) : multilinear_extension (f + g) x = multilinear_extension f x + multilinear_extension g x
Source
step towards matroid_symmetry_gap_integral_lt_eight_seventeenths
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • multilinear_extensionThe multilinear extension F(x) = Σ_S f(S) ∏_{u∈S} x_u ∏_{u∉S} (1 − x_u) of a set function f on {0, …, m−1}.

The proof, explained

The multilinear extension of a set function is defined as a sum over all subsets of the domain, where each term is the function's value on that subset multiplied by a multilinear weight. Unfolding this definition and combining the two sums on the right-hand side reduces the theorem to checking equality term by term. For any fixed subset $S$, the identity follows because $(f + g)(S) = f(S) + g(S)$ and multiplication distributes over addition.

  1. The multilinear extensions are unfolded, and the two sums on the right-hand side are merged into a single sum.

    Unfolding the definition of `multilinear_extension` expresses both sides as sums over all subsets $S \subseteq \{0, \dots, m-1\}$. Rewriting with `Finset.sum_add_distrib` in reverse merges the two sums on the right-hand side into a single sum whose summand is the sum of the individual terms for $f$ and $g$.

    lines 3–4

    uses Finset.sum_add_distrib

      unfold multilinear_extension
      rw [← Finset.sum_add_distrib]
  2. It suffices to show that the summands for $f + g$ and $f, g$ agree on each subset $S$.

    Applying `Finset.sum_congr` with reflexivity for the index set reduces equality of the sums to equality of their summands at each index. We then introduce an arbitrary subset $S$.

    lines 5–6

    uses Finset.sum_congr

      apply Finset.sum_congr rfl
      intro S _
  3. The summand for $f + g$ at $S$ equals the sum of the summands for $f$ and $g$ at $S$.

    Evaluating the pointwise sum $(f + g)(S)$ gives $f(S) + g(S)$ by `Pi.add_apply`. The remaining goal is an instance of the distributive law $(f(S) + g(S)) \cdot P = f(S) \cdot P + g(S) \cdot P$, where $P = \left(\prod_{u \in S} x_u\right) \prod_{u \in S^c} (1 - x_u)$, which the `ring` tactic verifies by ring arithmetic.

    lines 7–8

    uses Pi.add_apply

      simp only [Pi.add_apply]
      ring
Finset.sum_add_distrib
The sum of a termwise sum of two functions over a finite set equals the sum of the first plus the sum of the second: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.sum_congr
Two sums over finite sets are equal if the index sets are equal and their summands agree on every element of the index set.
Pi.add_apply
The value of a pointwise sum of functions at an input is the sum of the function values at that input: $(f + g)(i) = f(i) + g(i)$.

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 multilinear extension of a sum of set functions is the sum of their multilinear extensions. -/theorem multilinear_extension_add {m : ℕ} (f g : Finset (Fin m) → ℝ) (x : Fin m → ℝ) : multilinear_extension (f + g) x = multilinear_extension f x + multilinear_extension g x := by  unfold multilinear_extension  rw [← Finset.sum_add_distrib]  apply Finset.sum_congr rfl  intro S _  simp only [Pi.add_apply]  ring
See it in the graphDiscuss this resultChallenge it