AFTD Auto-Formalizing Theoretical Domains

perm_group_symmetrize_mem_matroid_polytope

theoremverified

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

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.

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

    lines 7–9

      classical
      set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S}
        with hV
  2. 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)}.

    lines 10–14

    uses Finset.mem_map_equiv, Equiv.Perm.inv_def

      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]
  3. 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)}.

    lines 15–32

    uses Finset.sum_nbij', mul_inv_rev, Equiv.Perm.mul_apply

      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]
  4. 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.

    lines 33–36

      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
  5. 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).

    lines 37–44

    uses LinearMap.image_convexHull, convexHull_mono

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

    lines 45–48

    uses Finset.card_pos.2

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

    lines 49–54

    uses Finset.sum_apply, Pi.smul_apply, smul_eq_mul, Finset.mul_sum, div_eq_inv_mul, one_div

      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]
  8. 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.

    lines 55–58

    uses convex_convexHull, Finset.sum_const, nsmul_eq_mul

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

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