AFTD Auto-Formalizing Theoretical Domains

sSup_indep_le_sSup_multilinear_extension

theoremverified

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.

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

    lines 6–12

    uses Set.finite_range, isCompact_convexHull

      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 (𝕜 := ℝ)
  2. 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.

    lines 13–14

      have hF : Continuous (multilinear_extension f) := by
        unfold multilinear_extension; fun_prop
  3. 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.

    lines 15–16

      have hbdd : BddAbove (multilinear_extension f '' matroid_polytope M) :=
        (hPc.image hF).bddAbove
  4. The 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.

    lines 17–19

    uses M.empty_indep

      have hne : (f '' {S : Finset (Fin m) | M.Indep ↑S}).Nonempty := by
        refine ⟨f ∅, ∅, ?_, rfl⟩
        simp [M.empty_indep]
  5. 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)).

    line 20

    uses csSup_le

      refine csSup_le hne ?_
  6. 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`.

    lines 21–25

    uses multilinear_extension_indicator, le_csSup, subset_convexHull

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

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