AFTD Auto-Formalizing Theoretical Domains

multilinear_extension_indicator

theoremverified

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

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.

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

    lines 3–4

    uses Finset.sum_eq_single_of_mem, Finset.mem_univ

      dsimp [multilinear_extension]
      rw [Finset.sum_eq_single_of_mem S (Finset.mem_univ S)]
  2. 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.

    lines 5–9

    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]
  3. 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.

    lines 10–18

    uses Finset.prod_eq_one, Finset.mem_compl, if_neg

        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
  4. 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).

    line 19

    uses mul_one

        rw [h1, h2, mul_one, mul_one]
  5. 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.

    lines 20–24

    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)
  6. 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.

    lines 25–32

    uses Finset.prod_eq_zero, if_neg, mul_zero, zero_mul

        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]
  7. 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.

    lines 33–43

    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

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