AFTD Auto-Formalizing Theoretical Domains

matroid_symmetry_gap_le_one

theoremverifiedformalization

For every strongly symmetric instance max{f(S) : S independent in M} with respect to a permutation group G, the best symmetrized fractional value is at most the best fractional value: max_{x∈P(M)} F(x̄) ≤ max_{x∈P(M)} F(x), i.e. the symmetry gap is at most 1.

Statement

theorem matroid_symmetry_gap_le_one {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)
Formalizes
arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Definition 2.2 (implicit there: x̄ ∈ P(M) because G preserves independence and P(M) is convex)
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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}.
  • 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}.

The proof, explained

The theorem establishes that for any strongly symmetric instance (M, f, G), the supremum of the multilinear extension F over the G-symmetrized points of the matroid polytope P(M) is at most the supremum of F over P(M). The key move is to show that P(M) is invariant under the action of G: permuting an independent set by σ ∈ G preserves its symmetrized indicator vector, which by strong symmetry implies the permuted set remains independent, so G preserves the vertices and hence the entire polytope P(M). Symmetrization x̄ is a convex combination of the permuted points σ · x, so x̄ ∈ P(M) whenever x ∈ P(M). Consequently, the set of symmetrized values is a subset of all fractional values on P(M), and the inequality between their suprema follows by monotonicity.

  1. The matroid polytope P(M) is a nonempty compact set, and the image of P(M) under the multilinear extension F is bounded above.

    Let V be the set of indicator vectors of independent sets of M. Since V is a subset of the finite range of all indicator vectors on subsets of {0, ..., m-1}, V is finite. The matroid polytope P(M) is the convex hull of V, so it is compact. The multilinear extension F is a polynomial and hence continuous, so its image F(P(M)) is compact and bounded above. Furthermore, the empty set is independent in M, so its indicator vector 0 belongs to V ⊆ P(M), showing P(M) is nonempty.

    lines 6–18

    uses Set.finite_range, subset_convexHull

      classical
      set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S}
        with hV
      have hVfin : V.Finite :=
        (Set.finite_range (fun S : Finset (Fin m) => finset_indicator_vec S)).subset
          (by rintro x ⟨S, -, rfl⟩; exact ⟨S, rfl⟩)
      have hPc : IsCompact (matroid_polytope M) := hVfin.isCompact_convexHull (𝕜 := ℝ)
      have hF : Continuous (multilinear_extension f) := by
        unfold multilinear_extension; fun_prop
      have hbdd : BddAbove (multilinear_extension f '' matroid_polytope M) :=
        (hPc.image hF).bddAbove
      have hne : (matroid_polytope M).Nonempty :=
        ⟨finset_indicator_vec ∅, subset_convexHull ℝ _ ⟨∅, by simpa using M.empty_indep, rfl⟩⟩
  2. Permuting coordinates of an indicator vector by σ yields the indicator vector of the permuted set σ(S).

    For any permutation σ and subset S, the coordinate σ⁻¹(u) belongs to S if and only if u belongs to σ(S). Therefore, the vector u ↦ 1_S(σ⁻¹(u)) is identical to the indicator vector 1_{σ(S)}.

    lines 19–23

    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 any subset S, the G-symmetrization of 1_{σ(S)} equals the G-symmetrization of 1_S.

    The G-symmetrization averages coordinate permutations over all τ ∈ G. For 1_{σ(S)}, the term for τ evaluates to 1_S((τ σ)⁻¹(u)). Since σ ∈ G, the map τ ↦ τ σ is a bijection of G onto itself with inverse τ ↦ τ σ⁻¹. Reindexing the sum over G via this bijection leaves the sum and the average unchanged.

    lines 24–43

    uses Finset.sum_nbij', Finset.coe_filter, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and, 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.coe_filter, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ,
            true_and] at hτ ⊢
          exact G.mul_mem hτ hσ
        · intro τ hτ
          simp only [Finset.coe_filter, Finset.mem_coe, 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. The vertex set V of P(M) is invariant under the coordinate action of any permutation σ ∈ G.

    For any x = 1_S ∈ V, S is independent in M. Under σ ∈ G, the permuted vector is 1_{σ(S)}. By the previous step, 1_{σ(S)} and 1_S have identical G-symmetrizations. By strong symmetry (hs.2), sets with identical symmetrized indicator vectors have equivalent independence in M. Hence σ(S) is independent, which means 1_{σ(S)} ∈ V.

    lines 44–47

      have hσV : ∀ σ ∈ G, ∀ x ∈ V, (fun u => x (σ⁻¹ u)) ∈ V := by
        rintro σ hσ _ ⟨S, hS, rfl⟩
        refine ⟨S.map σ.toEmbedding, ?_, hact_ind σ S⟩
        exact (hs.2 _ _ (hsymσ σ hσ S)).2 hS
  5. The matroid polytope P(M) is invariant under the coordinate action of any permutation σ ∈ G.

    The permutation action on vectors is a linear map (LinearMap.funLeft). Since linear maps commute with convex hulls, the image of P(M) = conv(V) is conv(σ · V). Since σ · V ⊆ V by the previous step, monotonicity of the convex hull implies conv(σ · V) ⊆ conv(V) = P(M). Hence σ · x ∈ P(M) for all x ∈ P(M).

    lines 48–55

    uses LinearMap.funLeft, LinearMap.image_convexHull, convexHull_mono

      have hσP : ∀ σ ∈ G, ∀ x ∈ matroid_polytope M, (fun u => x (σ⁻¹ u)) ∈ matroid_polytope M := by
        intro σ hσ x hx
        have h1 : (fun u => x (σ⁻¹ u)) ∈ (LinearMap.funLeft ℝ ℝ ⇑σ⁻¹) '' matroid_polytope M :=
          ⟨x, hx, rfl⟩
        rw [matroid_polytope, LinearMap.image_convexHull] at h1
        refine convexHull_mono ?_ h1
        rintro _ ⟨y, hy, rfl⟩
        exact hσV σ hσ y hy
  6. For every point x in the matroid polytope P(M), its group symmetrization x̄ also belongs to P(M).

    The symmetrization x̄ is defined as the uniform average (1 / |G|) ∑_{σ ∈ G} σ · x. Since G is a subgroup, it contains the identity element, so |G| > 0. The weights 1 / |G| are non-negative and sum to 1, expressing x̄ as a convex combination of the points σ · x. Since each σ · x belongs to P(M) and P(M) is convex, their convex combination x̄ also belongs to P(M).

    lines 56–71

    uses Finset.card_pos, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, Finset.mul_sum, div_eq_inv_mul, one_div, convex_convexHull, Finset.sum_const, nsmul_eq_mul

      have hsymP : ∀ x ∈ matroid_polytope M, perm_group_symmetrize G x ∈ matroid_polytope M := by
        intro x hx
        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
  7. The supremum of F(x̄) over x ∈ P(M) is at most the supremum of F(x) over x ∈ P(M).

    Since every symmetrized point x̄ for x ∈ P(M) belongs to P(M), the image set {F(x̄) | x ∈ P(M)} is a subset of {F(y) | y ∈ P(M)}. Since the latter is bounded above and the former is nonempty, monotonicity of the supremum implies that sup_{x ∈ P(M)} F(x̄) ≤ sup_{y ∈ P(M)} F(y).

    lines 72–74

    uses csSup_le_csSup

      refine csSup_le_csSup hbdd (hne.image _) ?_
      rintro _ ⟨x, hx, rfl⟩
      exact ⟨_, hsymP x hx, rfl⟩
Set.finite_range
The range of a function defined on a finite type is a finite set.
subset_convexHull
Every set is contained in its convex hull.
Finset.mem_map_equiv
An element b belongs to the image of a finite set s under an equivalence f if and only if f⁻¹(b) ∈ s.
Equiv.Perm.inv_def
The group inverse of a permutation equals its equivalence inverse.
Finset.sum_nbij'
Two finite sums are equal if their index sets are in bijection via maps that preserve summands.
Finset.coe_filter
The coercion of a filtered finite set to a set equals the set of elements in the original finite set satisfying the predicate.
Finset.mem_coe
Membership in the set coercion of a finite set is equivalent to membership in the finite set.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set.
true_and
True ∧ p is equivalent to p.
mul_inv_rev
The inverse of a product is the product of the inverses in reverse order: (ab)⁻¹ = b⁻¹ a⁻¹.
Equiv.Perm.mul_apply
Multiplication of permutations corresponds to function composition: (f * g)(x) = f(g(x)).
LinearMap.funLeft
Precomposition with a function defines a linear map between function spaces.
LinearMap.image_convexHull
The image of a convex hull under a linear map equals the convex hull of the image.
convexHull_mono
The convex hull operation is monotone with respect to set inclusion: s ⊆ t implies conv(s) ⊆ conv(t).
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.sum_apply
Pointwise evaluation distributes over finite sums of functions.
Pi.smul_apply
Scalar multiplication on function spaces is defined pointwise: (c • f)(i) = c • (f(i)).
smul_eq_mul
Scalar multiplication of a ring on itself coincides with ring multiplication.
Finset.mul_sum
Multiplication distributes over finite sums from the left: a * ∑ i, f(i) = ∑ i, a * f(i).
div_eq_inv_mul
Division by b equals multiplication by b⁻¹: a / b = b⁻¹ * a.
one_div
Reciprocal equals inverse: 1 / a = a⁻¹.
convex_convexHull
The convex hull of any set is convex.
Finset.sum_const
The sum of a constant b over a finite set s equals |s| • b.
nsmul_eq_mul
Scalar multiplication by a natural number n in a semiring equals multiplication by n: n • a = n * a.
csSup_le_csSup
In a conditionally complete lattice, if s ⊆ t with s nonempty and t bounded above, then sup s ≤ sup t.

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

theorem matroid_symmetry_gap_le_one {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) := by  classical  set V : Set (Fin m → ℝ) := {x | ∃ S : Finset (Fin m), M.Indep ↑S ∧ x = finset_indicator_vec S}    with hV  have hVfin : V.Finite :=    (Set.finite_range (fun S : Finset (Fin m) => finset_indicator_vec S)).subset      (by rintro x ⟨S, -, rfl⟩; exact ⟨S, rfl⟩)  have hPc : IsCompact (matroid_polytope M) := hVfin.isCompact_convexHull (𝕜 := ℝ)  have hF : Continuous (multilinear_extension f) := by    unfold multilinear_extension; fun_prop  have hbdd : BddAbove (multilinear_extension f '' matroid_polytope M) :=    (hPc.image hF).bddAbove  have hne : (matroid_polytope M).Nonempty :=    ⟨finset_indicator_vec ∅, subset_convexHull ℝ _ ⟨∅, by simpa using M.empty_indep, rfl⟩⟩  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.coe_filter, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ,        true_and] at hτ ⊢      exact G.mul_mem hτ hσ    · intro τ hτ      simp only [Finset.coe_filter, Finset.mem_coe, 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, ∀ x ∈ V, (fun u => x (σ⁻¹ 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, ∀ x ∈ matroid_polytope M, (fun u => x (σ⁻¹ u)) ∈ matroid_polytope M := by    intro σ hσ x hx    have h1 : (fun u => x (σ⁻¹ u)) ∈ (LinearMap.funLeft ℝ ℝ ⇑σ⁻¹) '' matroid_polytope M :=      ⟨x, hx, rfl⟩    rw [matroid_polytope, LinearMap.image_convexHull] at h1    refine convexHull_mono ?_ h1    rintro _ ⟨y, hy, rfl⟩    exact hσV σ hσ y hy  have hsymP : ∀ x ∈ matroid_polytope M, perm_group_symmetrize G x ∈ matroid_polytope M := by    intro x hx    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  refine csSup_le_csSup hbdd (hne.image _) ?_  rintro _ ⟨x, hx, rfl⟩  exact ⟨_, hsymP x hx, rfl⟩
See it in the graphDiscuss this resultChallenge it