multilinear_extension
def
The 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}.
Statement
def multilinear_extension {m : ℕ} (f : Finset (Fin m) → ℝ) (x : Fin m → ℝ) : ℝ- Defined in
- arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Sec. 2.1 (multilinear extension)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 8
- 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…
- multilinear_extension_addThe multilinear extension of a sum of set functions is the sum of their multilinear extensions.
- matroid_symmetry_gap_le_oneFor every strongly symmetric instance max{f(S) : S independent in M} with respect to a permutation group G, the best symmetrized…
- symmetry_gap_numerator_eq_sSup_fixedFor a strongly symmetric instance the numerator of the symmetry gap, sup_{x∈P(M)} F(x̄), equals the supremum of F over the points of the…
- multilinear_extension_perm_invariantIf a set function f is invariant under a permutation σ of the ground set, then its multilinear extension is invariant under the…
- multilinear_extension_smulThe multilinear extension commutes with scalar multiplication.
- multilinear_extension_nonnegThe multilinear extension of a non-negative set function evaluated on the unit hypercube is non-negative.
- multilinear_extension_indicatorThe multilinear extension agrees with f on indicator vectors: F(1_S) = f(S).
Lean source view module on GitHub
/-- The multilinear extension `F(x) = ∑_S f(S) ∏_{u ∈ S} x_u ∏_{u ∉ S} (1 - x_u)` of a set function `f` on `Fin m`. -/ def multilinear_extension {m : ℕ} (f : Finset (Fin m) → ℝ) (x : Fin m → ℝ) : ℝ := ∑ S : Finset (Fin m), f S * (∏ u ∈ S, x u) * ∏ u ∈ Sᶜ, (1 - x u)