multilinear_extension_nonneg
The multilinear extension of a non-negative set function evaluated on the unit hypercube is non-negative.
Statement
theorem multilinear_extension_nonneg {m : ℕ} (f : Finset (Fin m) → ℝ) (hf : ∀ S, 0 ≤ f S) (x : Fin m → ℝ) (hx : ∀ u, 0 ≤ x u ∧ x u ≤ 1) : 0 ≤ multilinear_extension f 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
By definition, the multilinear extension of f evaluated at x is a sum over all subsets S of terms of the form f(S) ∏_{u ∈ S} x_u ∏_{u ∉ S} (1 - x_u). Because x lies in the unit hypercube [0, 1]^m, both x_u ≥ 0 and 1 - x_u ≥ 0 hold for every coordinate u. Together with the assumption that f(S) ≥ 0 for all S, each summand is a product of non-negative factors, and therefore the total sum is non-negative.
It suffices to show that each summand in the multilinear extension is non-negative.
Unfolding the definition of the multilinear extension, the expression is a finite sum over all subsets S ⊆ Fin m of terms of the form (f(S) ∏_{u ∈ S} x_u) ∏_{u ∈ Sᶜ} (1 - x_u). By Finset.sum_nonneg, a sum of non-negative real numbers is non-negative, so it suffices to show that the summand for an arbitrary subset S is non-negative.
uses
Finset.sum_nonnegunfold multilinear_extension apply Finset.sum_nonneg intro S hS
The first factor f(S) ∏_{u ∈ S} x_u is non-negative.
By mul_nonneg, the non-negativity of the summand splits into showing 0 ≤ f(S) ∏_{u ∈ S} x_u and 0 ≤ ∏_{u ∈ Sᶜ} (1 - x_u). A second application of mul_nonneg reduces the first goal to 0 ≤ f(S), which holds by hypothesis hf, and 0 ≤ ∏_{u ∈ S} x_u. Using Finset.prod_nonneg, the product over S is non-negative because each coordinate satisfies 0 ≤ x_u by the first part of hypothesis hx.
uses
mul_nonneg,Finset.prod_nonnegapply mul_nonneg · apply mul_nonneg · exact hf S · apply Finset.prod_nonneg intro u hu exact (hx u).1
The second factor ∏_{u ∈ Sᶜ} (1 - x_u) is non-negative, completing the proof.
By Finset.prod_nonneg, the product is non-negative if each factor satisfies 0 ≤ 1 - x_u for u ∈ Sᶜ. From the second part of hypothesis hx we have x_u ≤ 1, from which linear arithmetic (linarith) concludes 0 ≤ 1 - x_u.
uses
Finset.prod_nonneg· apply Finset.prod_nonneg intro u hu have := (hx u).2 linarith
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
mul_nonneg- The product of two non-negative numbers is non-negative.
Finset.prod_nonneg- A finite product of non-negative factors is non-negative.
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 non-negative set function evaluated on the unit hypercube is non-negative. -/theorem multilinear_extension_nonneg {m : ℕ} (f : Finset (Fin m) → ℝ) (hf : ∀ S, 0 ≤ f S) (x : Fin m → ℝ) (hx : ∀ u, 0 ≤ x u ∧ x u ≤ 1) : 0 ≤ multilinear_extension f x := by unfold multilinear_extension apply Finset.sum_nonneg intro S hS apply mul_nonneg · apply mul_nonneg · exact hf S · apply Finset.prod_nonneg intro u hu exact (hx u).1 · apply Finset.prod_nonneg intro u hu have := (hx u).2 linarith