symmetry_gap_numerator_eq_sSup_fixed
For 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 matroid polytope that are fixed by the group.
Statement
theorem symmetry_gap_numerator_eq_sSup_fixed {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) (hs : is_strongly_symmetric_instance M f G) : sSup ((fun x => multilinear_extension f (perm_group_symmetrize G x)) '' matroid_polytope M) = sSup (multilinear_extension f '' (matroid_polytope M ∩ {x | perm_group_symmetrize G x = x}))
- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- symmetrize_image_matroid_polytope_eq_fixedFor a strongly symmetric instance, the image of the matroid polytope under symmetrization is exactly the set of points of the polytope…
- 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}.
- 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}.
- perm_group_symmetrizeThe symmetrization x̄ = E_{σ∈G}[σ(x)] of a vector x over a group G of permutations of the coordinates, where σ(x)_{σ(u)} = x_u.
- is_strongly_symmetric_instanceThe problem max{f(S) : S independent in M} is strongly symmetric with respect to a permutation group G: f(σ(S)) = f(S) for all S and σ ∈…
The proof, explained
The proof rewrites the set of values taken by the multilinear extension F on symmetrized points x̄ into the image under F of the symmetrized matroid polytope. By a previously established lemma for strongly symmetric instances, the image of the matroid polytope under symmetrization is exactly its fixed-point face, P(M) ∩ Fix(G). Substituting this set equality immediately yields the desired equality of suprema.
The supremum of the multilinear extension F over the symmetrized matroid polytope equals the supremum of F over the group-fixed points of the matroid polytope.
By `Set.image_image`, the set of values F(x̄) for x in the matroid polytope P(M) is rewritten as the image under F of the symmetrized polytope, F '' (symmetrize '' P(M)). Then, by `symmetrize_image_matroid_polytope_eq_fixed`, strong symmetry implies that the symmetrized matroid polytope is exactly the fixed-point face P(M) ∩ {x | x̄ = x}. Substituting this equality leaves identical expressions on both sides.
uses
Set.image_image,symmetrize_image_matroid_polytope_eq_fixedrw [← Set.image_image, symmetrize_image_matroid_polytope_eq_fixed M f G hs]
Set.image_image- The image of a set under a composite function g ∘ f equals the image under g of the image under f, that is, (g ∘ f) '' s = g '' (f '' s).
symmetrize_image_matroid_polytope_eq_fixed- For a strongly symmetric instance, the image of the matroid polytope under group symmetrization is its intersection with the set of points fixed by the symmetrization.
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 numerator of the symmetry gap is a supremum of F over the fixed polytope P(M) ∩ Fix(G). -/theorem symmetry_gap_numerator_eq_sSup_fixed {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) (hs : is_strongly_symmetric_instance M f G) : sSup ((fun x => multilinear_extension f (perm_group_symmetrize G x)) '' matroid_polytope M) = sSup (multilinear_extension f '' (matroid_polytope M ∩ {x | perm_group_symmetrize G x = x})) := by rw [← Set.image_image, symmetrize_image_matroid_polytope_eq_fixed M f G hs]