symmetrize_image_matroid_polytope_eq_fixed
For a strongly symmetric instance, the image of the matroid polytope under symmetrization is exactly the set of points of the polytope fixed by every element of G.
Statement
theorem symmetrize_image_matroid_polytope_eq_fixed {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) (hs : is_strongly_symmetric_instance M f G) : (fun x => perm_group_symmetrize G x) '' matroid_polytope M = 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
- perm_group_symmetrize_idempotentSymmetrization is idempotent: symmetrizing twice is the same as symmetrizing once, i.e. x̄ is fixed by every element of G.
- perm_group_symmetrize_mem_matroid_polytopeFor a strongly symmetric instance, symmetrizing a point of the matroid polytope stays inside the matroid polytope.
- 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}.
- 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 σ ∈…
- 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.
- Used by 1
- 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…
The proof, explained
The proof establishes the equality of the two sets by extensionality, splitting the equivalence into two inclusions. For the forward inclusion, symmetrization preserves membership in the matroid polytope for a strongly symmetric instance and is an idempotent operation, so the image of any point in the polytope is both in the polytope and fixed by symmetrization. For the reverse inclusion, any point in the polytope that is already fixed by symmetrization serves as its own preimage under the symmetrization map.
Equality of the two sets reduces to showing mutual inclusion of their elements.
By set extensionality, two sets are identical if they contain the same elements. Rewriting the membership conditions using the definitions of the image of a set under a function (`Set.mem_image`) and the intersection of two sets (`Set.mem_inter_iff`), we split the required equivalence into two separate implications.
uses
Set.mem_image,Set.mem_inter_iffext x simp only [Set.mem_image, Set.mem_inter_iff] constructor
Every point in the symmetrized image of the matroid polytope belongs to the polytope and is fixed by symmetrization.
Let y be a point in the matroid polytope, and consider its symmetrization x = perm_group_symmetrize G y. First, x remains in the matroid polytope by `perm_group_symmetrize_mem_matroid_polytope`, using the hypothesis that the instance is strongly symmetric. Second, x is fixed under symmetrization because group symmetrization is idempotent (`perm_group_symmetrize_idempotent`).
uses
perm_group_symmetrize_mem_matroid_polytope,perm_group_symmetrize_idempotent· rintro ⟨y, hy, rfl⟩ exact ⟨perm_group_symmetrize_mem_matroid_polytope M f G hs hy, perm_group_symmetrize_idempotent G y⟩
Every point in the matroid polytope that is fixed by symmetrization belongs to the symmetrized image.
Given a point x in the matroid polytope satisfying perm_group_symmetrize G x = x, x itself provides the required witness in the polytope whose symmetrization equals x.
· rintro ⟨hx, hfix⟩ exact ⟨x, hx, hfix⟩
Set.mem_image- An element y is in the image f(s) if and only if there exists x ∈ s such that f(x) = y.
Set.mem_inter_iff- An element x is in the intersection a ∩ b if and only if x ∈ a and x ∈ b.
perm_group_symmetrize_mem_matroid_polytope- Group symmetrization preserves membership in the matroid polytope of a strongly symmetric instance.
perm_group_symmetrize_idempotent- Group symmetrization is idempotent: symmetrizing an already symmetrized point leaves it unchanged.
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 symmetrized matroid polytope is exactly the part of the polytope fixed by the group. -/theorem symmetrize_image_matroid_polytope_eq_fixed {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) (hs : is_strongly_symmetric_instance M f G) : (fun x => perm_group_symmetrize G x) '' matroid_polytope M = matroid_polytope M ∩ {x | perm_group_symmetrize G x = x} := by ext x simp only [Set.mem_image, Set.mem_inter_iff] constructor · rintro ⟨y, hy, rfl⟩ exact ⟨perm_group_symmetrize_mem_matroid_polytope M f G hs hy, perm_group_symmetrize_idempotent G y⟩ · rintro ⟨hx, hfix⟩ exact ⟨x, hx, hfix⟩