matroid_symmetry_gap_le_one
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.
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.
uses
Set.finite_range,subset_convexHullclassical 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⟩⟩
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)}.
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 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.
uses
Finset.sum_nbij',Finset.coe_filter,Finset.mem_coe,Finset.mem_filter,Finset.mem_univ,true_and,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.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]
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.
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
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).
uses
LinearMap.funLeft,LinearMap.image_convexHull,convexHull_monohave 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
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).
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_mulhave 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
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).
uses
csSup_le_csSuprefine 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.
- The continuity of the multilinear extension (line 14) is proved automatically by Lean's function properties tactic `fun_prop`.
- In Step 6, the facts that the convex combination weights 1 / |G| are non-negative and sum to 1 are discharged by `positivity` and `field_simp`.
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.
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⟩