perm_group_symmetrize_mem_matroid_polytope
For a strongly symmetric instance, symmetrizing a point of the matroid polytope stays inside the matroid polytope.
Statement
theorem perm_group_symmetrize_mem_matroid_polytope {m : ℕ} (M : Matroid (Fin m))
(f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m)))
(hs : is_strongly_symmetric_instance M f G) {x : Fin m → ℝ}
(hx : x ∈ matroid_polytope M) :
perm_group_symmetrize G x ∈ matroid_polytope M- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- 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 σ ∈…
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {0, …, m−1}.
- Used by 1
- 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…
The proof, explained
To show that symmetrizing a point x of the matroid polytope remains in the polytope, the symmetrizer is expressed as a convex combination of coordinate-permuted points x ∘ σ⁻¹ over all σ ∈ G, with uniform weights 1/|G|. Strong symmetry ensures that permuting an independent set by σ ∈ G yields another independent set, which implies that the action of G preserves the vertices of the polytope. Because coordinate permutation is linear, it preserves the entire matroid polytope, and the convexity of the polytope guarantees that the convex combination remains inside.
Define V as the set of indicator vectors of independent sets of M.
The matroid polytope is defined as the convex hull of V, the vertices corresponding to independent sets of M. Naming V allows us to reason about the polytope by first analyzing its extreme points.
classical set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S} with hV
For any permutation σ and subset S, the permuted indicator vector equals the indicator vector of σ(S).
Evaluating the indicator vector 1_S at σ⁻¹ u yields 1 if and only if σ⁻¹ u ∈ S, which is equivalent to u ∈ σ(S) because σ is a bijection. Thus, permuting coordinates by σ⁻¹ carries 1_S to 1_{σ(S)}.
uses
Finset.mem_map_equiv,Equiv.Perm.inv_defhave hact_ind : ∀ (σ : Equiv.Perm (Fin m)) (S : Finset (Fin m)), (fun u => finset_indicator_vec S (σ⁻¹ u)) = finset_indicator_vec (S.map σ.toEmbedding) := by intro σ S; funext u simp [finset_indicator_vec, Finset.mem_map_equiv, Equiv.Perm.inv_def]
For any permutation σ ∈ G and subset S, symmetrizing 1_{σ(S)} produces the same vector as symmetrizing 1_S.
Symmetrizing averages the permuted vector over all elements τ ∈ G. Since right multiplication by σ is a bijection of the subgroup G onto itself, reindexing the sum replaces τ with τ σ. The argument of the indicator vector becomes ((τ σ)⁻¹ u) = (σ⁻¹ τ⁻¹ u), which matches the symmetrization of 1_{σ(S)}.
uses
Finset.sum_nbij',mul_inv_rev,Equiv.Perm.mul_applyhave hsymσ : ∀ σ ∈ G, ∀ S : Finset (Fin m), perm_group_symmetrize G (finset_indicator_vec (S.map σ.toEmbedding)) = perm_group_symmetrize G (finset_indicator_vec S) := by intro σ hσ S funext u unfold perm_group_symmetrize congr 1 rw [← hact_ind] refine Finset.sum_nbij' (fun τ => τ * σ) (fun τ => τ * σ⁻¹) ?_ ?_ ?_ ?_ ?_ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hτ hσ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hτ (G.inv_mem hσ) · intro τ _; simp · intro τ _; simp · intro τ _; simp [mul_inv_rev, Equiv.Perm.mul_apply]
Permutation by any σ ∈ G preserves the vertex set V.
A vertex y ∈ V has the form 1_S for an independent set S. Its permuted vector is 1_{σ(S)}. Since 1_{σ(S)} and 1_S have identical symmetrizations, the strong symmetry hypothesis guarantees that σ(S) is independent if and only if S is independent. Therefore 1_{σ(S)} is also in V.
have hσV : ∀ σ ∈ G, ∀ y ∈ V, (fun u => y (σ⁻¹ u)) ∈ V := by rintro σ hσ _ ⟨S, hS, rfl⟩ refine ⟨S.map σ.toEmbedding, ?_, hact_ind σ S⟩ exact (hs.2 _ _ (hsymσ σ hσ S)).2 hS
Permutation by any σ ∈ G maps the matroid polytope into itself.
Permuting coordinates by σ⁻¹ is a linear map on the function space. A linear map commutes with forming convex hulls, so the image of the matroid polytope conv(V) is conv((· ∘ σ⁻¹)'' V). Since every permuted vertex remains in V, monotonicity of convex hulls implies that the image is contained in conv(V).
uses
LinearMap.image_convexHull,convexHull_monohave hσP : ∀ σ ∈ G, ∀ y ∈ matroid_polytope M, (fun u => y (σ⁻¹ u)) ∈ matroid_polytope M := by intro σ hσ y hy have h1 : (fun u => y (σ⁻¹ u)) ∈ (LinearMap.funLeft ℝ ℝ ⇑σ⁻¹) '' matroid_polytope M := ⟨y, hy, rfl⟩ rw [matroid_polytope, LinearMap.image_convexHull] at h1 refine convexHull_mono ?_ h1 rintro _ ⟨z, hz, rfl⟩ exact hσV σ hσ z hz
The finite subgroup G (denoted T) is nonempty and has positive cardinality.
The group identity 1 belongs to G, so T contains at least one element and its cardinality |T| is strictly positive.
uses
Finset.card_pos.2set T := Finset.univ.filter (· ∈ G) with hT have hcard : (0 : ℝ) < T.card := by have : (1 : Equiv.Perm (Fin m)) ∈ T := by simp [hT, G.one_mem] exact_mod_cast Finset.card_pos.2 ⟨_, this⟩
The symmetrizer of x is a convex combination of the permuted vectors x ∘ σ⁻¹ over σ ∈ G with uniform weights 1/|G|.
Unfolding the definition of perm_group_symmetrize and distributing the division by |T| across the sum expresses the symmetrizer coordinate-wise as the sum of (1 / |T|) • (x ∘ σ⁻¹) over all σ ∈ T.
uses
Finset.sum_apply,Pi.smul_apply,smul_eq_mul,Finset.mul_sum,div_eq_inv_mul,one_divhave heq : perm_group_symmetrize G x = ∑ σ ∈ T, (1 / (T.card : ℝ)) • (fun u => x (σ⁻¹ u)) := by funext u simp only [perm_group_symmetrize, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hT] rw [← Finset.mul_sum, div_eq_inv_mul, one_div] rw [heq]
The symmetrized vector perm_group_symmetrize G x belongs to the matroid polytope.
The matroid polytope is convex because it is a convex hull. The weights 1/|T| are positive (hence non-negative) and sum to 1 since |T| • (1/|T|) = 1. Because each permuted vector x ∘ σ⁻¹ lies in the matroid polytope, their convex combination must also lie in the matroid polytope.
uses
convex_convexHull,Finset.sum_const,nsmul_eq_mulrefine (convex_convexHull ℝ _).sum_mem (fun _ _ => by positivity) ?_ ?_ · rw [Finset.sum_const, nsmul_eq_mul]; field_simp · intro σ hσ exact hσP σ (by simpa [hT] using hσ) x hx
Finset.mem_map_equiv- an element belongs to the image of a set under an equivalence if and only if its inverse image belongs to the original set
Equiv.Perm.inv_def- the group inverse of a permutation is equal to its inverse equivalence
Finset.sum_nbij'- a sum over a finite set is unchanged by reindexing along a bijection
mul_inv_rev- the inverse of a product in a group is the product of the inverses in reverse order: (a * b)⁻¹ = b⁻¹ * a⁻¹
Equiv.Perm.mul_apply- composition of permutations evaluates from right to left: (f * g) x = f (g x)
LinearMap.image_convexHull- the image of a convex hull under a linear map is the convex hull of the image
convexHull_mono- the convex hull operation preserves set inclusion: if s ⊆ t, then conv(s) ⊆ conv(t)
Finset.card_pos.2- a finite set has positive cardinality if it is nonempty
Finset.sum_apply- evaluating a sum of functions at a point equals the sum of their values at that point
Pi.smul_apply- scalar multiplication on a function space is defined pointwise: (a • f) i = a • (f i)
smul_eq_mul- scalar multiplication in a ring by a scalar on itself is ring multiplication: a • b = a * b
Finset.mul_sum- multiplication distributes over finite sums: a * ∑ i, f i = ∑ i, a * f i
div_eq_inv_mul- division is multiplication by the reciprocal: a / b = b⁻¹ * a
one_div- the reciprocal 1 / a equals the inverse a⁻¹
convex_convexHull- the convex hull of any set is convex
Finset.sum_const- the sum of a constant value b over a finite set s is equal to |s| • b
nsmul_eq_mul- natural number scalar multiplication is multiplication by the coerced natural: n • a = n * a
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.
/-- Under strong symmetry the matroid polytope is invariant under symmetrization. -/theorem perm_group_symmetrize_mem_matroid_polytope {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) (G : Subgroup (Equiv.Perm (Fin m))) (hs : is_strongly_symmetric_instance M f G) {x : Fin m → ℝ} (hx : x ∈ matroid_polytope M) : perm_group_symmetrize G x ∈ 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 hact_ind : ∀ (σ : Equiv.Perm (Fin m)) (S : Finset (Fin m)), (fun u => finset_indicator_vec S (σ⁻¹ u)) = finset_indicator_vec (S.map σ.toEmbedding) := by intro σ S; funext u simp [finset_indicator_vec, Finset.mem_map_equiv, Equiv.Perm.inv_def] have hsymσ : ∀ σ ∈ G, ∀ S : Finset (Fin m), perm_group_symmetrize G (finset_indicator_vec (S.map σ.toEmbedding)) = perm_group_symmetrize G (finset_indicator_vec S) := by intro σ hσ S funext u unfold perm_group_symmetrize congr 1 rw [← hact_ind] refine Finset.sum_nbij' (fun τ => τ * σ) (fun τ => τ * σ⁻¹) ?_ ?_ ?_ ?_ ?_ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hτ hσ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hτ (G.inv_mem hσ) · intro τ _; simp · intro τ _; simp · intro τ _; simp [mul_inv_rev, Equiv.Perm.mul_apply] have hσV : ∀ σ ∈ G, ∀ y ∈ V, (fun u => y (σ⁻¹ u)) ∈ V := by rintro σ hσ _ ⟨S, hS, rfl⟩ refine ⟨S.map σ.toEmbedding, ?_, hact_ind σ S⟩ exact (hs.2 _ _ (hsymσ σ hσ S)).2 hS have hσP : ∀ σ ∈ G, ∀ y ∈ matroid_polytope M, (fun u => y (σ⁻¹ u)) ∈ matroid_polytope M := by intro σ hσ y hy have h1 : (fun u => y (σ⁻¹ u)) ∈ (LinearMap.funLeft ℝ ℝ ⇑σ⁻¹) '' matroid_polytope M := ⟨y, hy, rfl⟩ rw [matroid_polytope, LinearMap.image_convexHull] at h1 refine convexHull_mono ?_ h1 rintro _ ⟨z, hz, rfl⟩ exact hσV σ hσ z hz set T := Finset.univ.filter (· ∈ G) with hT have hcard : (0 : ℝ) < T.card := by have : (1 : Equiv.Perm (Fin m)) ∈ T := by simp [hT, G.one_mem] exact_mod_cast Finset.card_pos.2 ⟨_, this⟩ have heq : perm_group_symmetrize G x = ∑ σ ∈ T, (1 / (T.card : ℝ)) • (fun u => x (σ⁻¹ u)) := by funext u simp only [perm_group_symmetrize, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hT] rw [← Finset.mul_sum, div_eq_inv_mul, one_div] rw [heq] refine (convex_convexHull ℝ _).sum_mem (fun _ _ => by positivity) ?_ ?_ · rw [Finset.sum_const, nsmul_eq_mul]; field_simp · intro σ hσ exact hσP σ (by simpa [hT] using hσ) x hx