AFTD Auto-Formalizing Theoretical Domains

symmetrize_image_matroid_polytope_eq_fixed

theoremverified

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

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.

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

    lines 7–9

    uses Set.mem_image, Set.mem_inter_iff

      ext x
      simp only [Set.mem_image, Set.mem_inter_iff]
      constructor
  2. 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`).

    lines 10–11

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

    lines 12–13

      · 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

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