AFTD Auto-Formalizing Theoretical Domains

multilinear_extension_nonneg

theoremverified

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.

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

    lines 3–5

    uses Finset.sum_nonneg

      unfold multilinear_extension
      apply Finset.sum_nonneg
      intro S hS
  2. 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.

    lines 6–11

    uses mul_nonneg, Finset.prod_nonneg

      apply mul_nonneg
      · apply mul_nonneg
        · exact hf S
        · apply Finset.prod_nonneg
          intro u hu
          exact (hx u).1
  3. 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.

    lines 12–15

    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

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