sSup_indep_le_sSup_multilinear_extension
The 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 set is a vertex of the matroid polytope.
Statement
theorem sSup_indep_le_sSup_multilinear_extension {m : ℕ} (M : Matroid (Fin m))
(f : Finset (Fin m) → ℝ) :
sSup (f '' {S : Finset (Fin m) | M.Indep ↑S})
≤ sSup (multilinear_extension f '' matroid_polytope M)- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- multilinear_extension_indicatorThe multilinear extension agrees with f on indicator vectors: F(1_S) = f(S).
- matroid_polytopeThe matroid polytope P(M): the convex hull of the indicator vectors of the independent sets of a matroid M on {0, …, m−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}.
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {0, …, m−1}.
The proof, explained
To show that the supremum of a set function f over the independent sets of a matroid M is at most the supremum of its multilinear extension F over the matroid polytope P(M), the proof bounds each value f(S) individually by the fractional supremum. For any independent set S, its indicator vector 1_S lies in the matroid polytope P(M) and satisfies F(1_S) = f(S). Because P(M) is the convex hull of finitely many indicator vectors, it is compact, and since F is a polynomial and thus continuous, the image F(P(M)) is bounded above. Finally, because the empty set is independent, the collection of independent values is nonempty, so the pointwise bound implies the bound on the supremum.
The matroid polytope P(M) is compact.
Define V as the set of indicator vectors of all independent sets in M. Since the ground set has only finitely many subsets, the range of the indicator map is finite by `Set.finite_range`, so its subset V is finite. By definition, the matroid polytope P(M) is the convex hull of V. The convex hull of any finite subset in ℝᵐ is compact by `isCompact_convexHull`.
uses
Set.finite_range,isCompact_convexHullclassical set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S} with hV have hVfin : V.Finite := (Set.finite_range (fun S : Finset (Fin m) => finset_indicator_vec S)).subset (by rintro x ⟨S, -, rfl⟩; exact ⟨S, rfl⟩) have hPc : IsCompact (matroid_polytope M) := hVfin.isCompact_convexHull (𝕜 := ℝ)
The multilinear extension of f is continuous. automation
Unfolding the definition shows that the multilinear extension F(x) = ∑_S f(S) (∏_{u ∈ S} x_u) (∏_{u ∉ S} (1 - x_u)) is a multilinear polynomial in the coordinates of x. Lean's `fun_prop` tactic proves continuity automatically from this structure.
have hF : Continuous (multilinear_extension f) := by unfold multilinear_extension; fun_prop
The image of the matroid polytope under the multilinear extension is bounded above.
Because the matroid polytope is compact and the multilinear extension is continuous, the image F(P(M)) is compact. Any compact subset of ℝ is bounded above.
have hbdd : BddAbove (multilinear_extension f '' matroid_polytope M) := (hPc.image hF).bddAboveThe set of values of f on independent sets is nonempty.
The empty set ∅ is independent in M by `M.empty_indep`, so f(∅) belongs to the set of independent values, witnessing that it is nonempty.
uses
M.empty_indephave hne : (f '' {S : Finset (Fin m) | M.Indep ↑S}).Nonempty := by refine ⟨f ∅, ∅, ?_, rfl⟩ simp [M.empty_indep]
To bound the supremum over independent sets, it suffices to show that f(S) ≤ sup F(P(M)) for each independent set S.
By `csSup_le`, since the set of values on independent sets is nonempty, its supremum is at most sup F(P(M)) as long as every element f(S) for S independent satisfies f(S) ≤ sup F(P(M)).
uses
csSup_lerefine csSup_le hne ?_For every independent set S, f(S) ≤ sup F(P(M)).
Let S be an independent set. By `multilinear_extension_indicator`, f(S) equals the multilinear extension evaluated at the indicator vector 1_S. Since S is independent, 1_S belongs to the vertex set V, which is contained in the matroid polytope P(M) by `subset_convexHull`. Since F(P(M)) is bounded above, F(1_S) ≤ sup F(P(M)) follows by `le_csSup`.
uses
multilinear_extension_indicator,le_csSup,subset_convexHullrintro _ ⟨S, hS, rfl⟩ rw [← multilinear_extension_indicator f S] refine le_csSup hbdd ?_ refine ⟨finset_indicator_vec S, ?_, rfl⟩ exact subset_convexHull ℝ _ ⟨S, hS, rfl⟩
Set.finite_range- The range of a function defined on a finite domain is a finite set.
isCompact_convexHull- The convex hull of a finite subset of a topological real vector space is compact.
M.empty_indep- The empty set is an independent set in the matroid M.
csSup_le- If a nonempty set s in a conditionally complete lattice has an upper bound a (every element of s is at most a), then the supremum of s is at most a.
multilinear_extension_indicator- Evaluating the multilinear extension of f at the indicator vector of a finite set S yields f(S).
le_csSup- In a conditionally complete lattice, any element of a set bounded above is at most the supremum of that set.
subset_convexHull- Every set is contained in its convex hull.
- The continuity of the multilinear extension (lines 13–14) is proved automatically by the `fun_prop` tactic from its polynomial definition (a finite sum of finite products of coordinates).
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 integral optimum is at most the fractional optimum over the matroid polytope. -/theorem sSup_indep_le_sSup_multilinear_extension {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) : sSup (f '' {S : Finset (Fin m) | M.Indep ↑S}) ≤ sSup (multilinear_extension f '' matroid_polytope M) := by classical set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S} with hV have hVfin : V.Finite := (Set.finite_range (fun S : Finset (Fin m) => finset_indicator_vec S)).subset (by rintro x ⟨S, -, rfl⟩; exact ⟨S, rfl⟩) have hPc : IsCompact (matroid_polytope M) := hVfin.isCompact_convexHull (𝕜 := ℝ) have hF : Continuous (multilinear_extension f) := by unfold multilinear_extension; fun_prop have hbdd : BddAbove (multilinear_extension f '' matroid_polytope M) := (hPc.image hF).bddAbove have hne : (f '' {S : Finset (Fin m) | M.Indep ↑S}).Nonempty := by refine ⟨f ∅, ∅, ?_, rfl⟩ simp [M.empty_indep] refine csSup_le hne ?_ rintro _ ⟨S, hS, rfl⟩ rw [← multilinear_extension_indicator f S] refine le_csSup hbdd ?_ refine ⟨finset_indicator_vec S, ?_, rfl⟩ exact subset_convexHull ℝ _ ⟨S, hS, rfl⟩