multilinear_extension_add
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.
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$.
uses
Finset.sum_add_distribunfold multilinear_extension rw [← Finset.sum_add_distrib]
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$.
uses
Finset.sum_congrapply Finset.sum_congr rfl intro S _
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.
uses
Pi.add_applysimp 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
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 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