multilinear_extension_indicator
The multilinear extension agrees with f on indicator vectors: F(1_S) = f(S).
Statement
theorem multilinear_extension_indicator {m : ℕ} (f : Finset (Fin m) → ℝ) (S : Finset (Fin m)) :
multilinear_extension f (finset_indicator_vec S) = f S- Source
- sanity check of multilinear_extension
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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}.
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {0, …, m−1}.
- Used by 1
- sSup_indep_le_sSup_multilinear_extensionThe best integral value max{f(S) : S independent in M} is at most the best fractional value max_{x∈P(M)} F(x), because every independent…
The proof, explained
The multilinear extension of a function f is defined as a sum over all subsets T of {0, ..., m-1}. By isolating the term T = S using `Finset.sum_eq_single_of_mem`, the proof reduces to showing that the summand at S evaluates to f(S) and all other summands vanish. For T = S, both products evaluate to 1 because 1_S(u) = 1 on S and 1_S(u) = 0 on Sᶜ. For any T ≠ S, either some element lies in T ∖ S (making the first product zero) or some element lies in S ∖ T (making the second product zero), so every other term is zero.
The multilinear extension sum reduces to evaluating the summand for T = S and showing that every summand for T ≠ S vanishes.
Unfolding the definition of `multilinear_extension` expresses the value as a sum over all subsets. Applying `Finset.sum_eq_single_of_mem` with S ∈ Finset.univ isolates the single term T = S, leaving two obligations: proving the term for T = S equals f(S), and proving every term for T ≠ S is zero.
uses
Finset.sum_eq_single_of_mem,Finset.mem_univdsimp [multilinear_extension] rw [Finset.sum_eq_single_of_mem S (Finset.mem_univ S)]
The product ∏ u ∈ S, 1_S(u) equals 1.
For each u ∈ S, the indicator function 1_S(u) evaluates to 1 by `if_pos`. By `Finset.prod_eq_one`, since every factor in the product over S is 1, the entire product equals 1.
uses
Finset.prod_eq_one,if_pos· have h1 : (∏ u ∈ S, finset_indicator_vec S u) = 1 := by apply Finset.prod_eq_one intro u hu dsimp [finset_indicator_vec] rw [if_pos hu]
The product ∏ u ∈ Sᶜ, (1 - 1_S(u)) equals 1.
For each u ∈ Sᶜ, we have u ∉ S by `Finset.mem_compl`, so the indicator 1_S(u) evaluates to 0 by `if_neg`. Each factor is therefore 1 - 0 = 1, and by `Finset.prod_eq_one`, the product over Sᶜ equals 1.
uses
Finset.prod_eq_one,Finset.mem_compl,if_neghave h2 : (∏ u ∈ Sᶜ, (1 - finset_indicator_vec S u)) = 1 := by apply Finset.prod_eq_one intro u hu have hu' : u ∉ S := by rw [Finset.mem_compl] at hu exact hu dsimp [finset_indicator_vec] rw [if_neg hu'] ring
The summand for T = S simplifies to f(S).
Substituting the values of the two products (both equal to 1) into (f(S) * 1) * 1 and simplifying with `mul_one` shows that the summand at S is f(S).
uses
mul_onerw [h1, h2, mul_one, mul_one]If T ≠ S, then either there is some element in T ∖ S or some element in S ∖ T.
Proceeding by contradiction, if neither condition held, then every element of T would be in S and every element of S in T (that is, T ⊆ S and S ⊆ T). By `Finset.Subset.antisymm`, this would mean T = S, contradicting T ≠ S.
uses
Finset.Subset.antisymm· intro T _ hne have hdisj : (∃ u ∈ T, u ∉ S) ∨ (∃ u ∈ S, u ∉ T) := by by_contra! h rcases h with ⟨h1, h2⟩ exact hne (Finset.Subset.antisymm h1 h2)
If there is an element u ∈ T ∖ S, the summand for T is 0.
Since u ∉ S, the indicator 1_S(u) is 0 by `if_neg`. Because u ∈ T, `Finset.prod_eq_zero` implies that the product ∏ x ∈ T, 1_S(x) has a zero factor and vanishes. Multiplying by zero (`mul_zero`, `zero_mul`) makes the entire summand 0.
uses
Finset.prod_eq_zero,if_neg,mul_zero,zero_mulcases hdisj with | inl h1 => rcases h1 with ⟨u, huT, huS⟩ have hzero : ∏ u ∈ T, finset_indicator_vec S u = 0 := by apply Finset.prod_eq_zero huT dsimp [finset_indicator_vec] rw [if_neg huS] rw [hzero, mul_zero, zero_mul]
If there is an element u ∈ S ∖ T, the summand for T is 0.
Since u ∉ T, u ∈ Tᶜ by `Finset.mem_compl`. Since u ∈ S, 1_S(u) is 1 by `if_pos`, so the factor 1 - 1_S(u) is 0. Because u ∈ Tᶜ, `Finset.prod_eq_zero` shows that the product ∏ x ∈ Tᶜ, (1 - 1_S(x)) vanishes. Multiplying by zero (`mul_zero`) makes the entire summand 0.
uses
Finset.mem_compl,Finset.prod_eq_zero,if_pos,mul_zero| inr h2 => rcases h2 with ⟨u, huS, huT⟩ have hucompl : u ∈ Tᶜ := by rw [Finset.mem_compl] exact huT have hzero : ∏ u ∈ Tᶜ, (1 - finset_indicator_vec S u) = 0 := by apply Finset.prod_eq_zero hucompl dsimp [finset_indicator_vec] rw [if_pos huS] ring rw [hzero, mul_zero]
Finset.sum_eq_single_of_mem- If every element of a finite set except possibly a designated element has value 0, the sum over the set equals the value at that element.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.prod_eq_one- If every factor in a finite product equals 1, the product equals 1.
Finset.mem_compl- An element belongs to the complement of a finset if and only if it does not belong to the finset.
Finset.Subset.antisymm- Two finite sets that are subsets of each other are equal.
Finset.prod_eq_zero- If at least one factor in a finite product is 0, the product equals 0.
if_pos- If the condition of an if-then-else expression holds, the expression evaluates to the 'then' branch.
if_neg- If the condition of an if-then-else expression is false, the expression evaluates to the 'else' branch.
mul_one- Multiplying any element by 1 on the right yields the element itself (a * 1 = a).
mul_zero- Multiplying any element by 0 on the right yields 0 (a * 0 = 0).
zero_mul- Multiplying any element by 0 on the left yields 0 (0 * a = 0).
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.
theorem multilinear_extension_indicator {m : ℕ} (f : Finset (Fin m) → ℝ) (S : Finset (Fin m)) : multilinear_extension f (finset_indicator_vec S) = f S := by dsimp [multilinear_extension] rw [Finset.sum_eq_single_of_mem S (Finset.mem_univ S)] · have h1 : (∏ u ∈ S, finset_indicator_vec S u) = 1 := by apply Finset.prod_eq_one intro u hu dsimp [finset_indicator_vec] rw [if_pos hu] have h2 : (∏ u ∈ Sᶜ, (1 - finset_indicator_vec S u)) = 1 := by apply Finset.prod_eq_one intro u hu have hu' : u ∉ S := by rw [Finset.mem_compl] at hu exact hu dsimp [finset_indicator_vec] rw [if_neg hu'] ring rw [h1, h2, mul_one, mul_one] · intro T _ hne have hdisj : (∃ u ∈ T, u ∉ S) ∨ (∃ u ∈ S, u ∉ T) := by by_contra! h rcases h with ⟨h1, h2⟩ exact hne (Finset.Subset.antisymm h1 h2) cases hdisj with | inl h1 => rcases h1 with ⟨u, huT, huS⟩ have hzero : ∏ u ∈ T, finset_indicator_vec S u = 0 := by apply Finset.prod_eq_zero huT dsimp [finset_indicator_vec] rw [if_neg huS] rw [hzero, mul_zero, zero_mul] | inr h2 => rcases h2 with ⟨u, huS, huT⟩ have hucompl : u ∈ Tᶜ := by rw [Finset.mem_compl] exact huT have hzero : ∏ u ∈ Tᶜ, (1 - finset_indicator_vec S u) = 0 := by apply Finset.prod_eq_zero hucompl dsimp [finset_indicator_vec] rw [if_pos huS] ring rw [hzero, mul_zero]