is_strongly_symmetric_instance_bot
Every matroid together with any set function is a strongly symmetric instance for the trivial permutation group: a witness that the definition of strong symmetry is inhabited (non-vacuity).
Statement
theorem is_strongly_symmetric_instance_bot {m : ℕ} (M : Matroid (Fin m))
(f : Finset (Fin m) → ℝ) :
is_strongly_symmetric_instance M f ⊥- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- finset_indicator_vecThe indicator vector 1_S ∈ ℝ^m of a set S ⊆ {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 σ ∈…
The proof, explained
The theorem establishes that any matroid M and set function f form a strongly symmetric instance under the trivial permutation group ⊥ = {1}. Because ⊥ contains only the identity permutation, group symmetrization is simply the identity operator on vectors, and the action on sets is trivial. Therefore, f is trivially invariant, and any two sets with equal symmetrized indicator vectors are identical, trivially preserving matroid independence.
Symmetrization by the trivial permutation group is the identity operator on vectors.
For any vector y and element u, the set of group elements in the trivial subgroup ⊥ is just the singleton {1} by Subgroup.mem_bot. By definition, perm_group_symmetrize computes the average of y(σ⁻¹ u) over σ in the subgroup. Using Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, and div_one, this average simplifies to y(1⁻¹ u), which is just y u.
uses
Subgroup.mem_bot,Finset.sum_singleton,Finset.card_singleton,Nat.cast_one,div_oneclassical have hsym : ∀ (y : Fin m → ℝ), perm_group_symmetrize (⊥ : Subgroup (Equiv.Perm (Fin m))) y = y := by intro y funext u have h1 : (Finset.univ.filter (fun x : Equiv.Perm (Fin m) => x ∈ (⊥ : Subgroup (Equiv.Perm (Fin m))))) = {1} := by ext x; simp [Subgroup.mem_bot] rw [perm_group_symmetrize, h1, Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, div_one] simp
The identity permutation fixes every finset under Finset.map.
By extensionality and the characterization of Finset.map (Finset.mem_map, Equiv.coe_toEmbedding, and Equiv.Perm.one_apply), an element x is in the image of S under the identity permutation if and only if x = a for some a ∈ S, which means x ∈ S.
uses
Finset.mem_map,Equiv.coe_toEmbedding,Equiv.Perm.one_applyhave hmap : ∀ (S : Finset (Fin m)), Finset.map (Equiv.toEmbedding (1 : Equiv.Perm (Fin m))) S = S := by intro S ext x simp only [Finset.mem_map, Equiv.coe_toEmbedding, Equiv.Perm.one_apply] simp
Decompose the goal into invariance of f and independence preservation.
By the definition of is_strongly_symmetric_instance, two conditions must be shown: first, f must be invariant under permutations in ⊥; second, finsets with the same symmetrized indicator vector must have equivalent matroid independence.
refine ⟨?_, ?_⟩The set function f is invariant under permutations in the trivial group.
Given σ ∈ ⊥ and a finset S, Subgroup.mem_bot shows σ = 1. Applying the lemma hmap established earlier gives Finset.map 1 S = S, so f(Finset.map σ S) = f S.
uses
Subgroup.mem_bot· intro σ hσ S rw [Subgroup.mem_bot] at hσ subst hσ rw [hmap]
Having identical symmetrizations implies having identical indicator vectors.
If the symmetrized indicator vectors of S and S' under ⊥ are equal, rewriting with the fact hsym that symmetrization is the identity reduces the equality directly to finset_indicator_vec S = finset_indicator_vec S'.
· intro S S' h rw [hsym, hsym] at h
Equal indicator vectors imply S = S'.
By extensionality, we show u ∈ S ↔ u ∈ S' for all u. Applying congrFun to the indicator equality at u gives equality of the indicator values. If u were in one set but not the other, the indicator values 1 and 0 would be equal, a contradiction.
uses
congrFunhave hSS : S = S' := by ext u have h2 := congrFun h u simp only [finset_indicator_vec] at h2 constructor <;> intro hu · by_contra h1 simp [h1] at h2 simp [hu] at h2 · by_contra h1 simp [h1] at h2 simp [hu] at h2
Matroid independence is preserved between S and S'.
Because S = S', the condition M.Indep ↑S ↔ M.Indep ↑S' holds trivially.
simp [hSS]
Subgroup.mem_bot- an element of the trivial subgroup ⊥ is equal to the identity element 1, and conversely
Finset.sum_singleton- the sum of a function over a singleton set {a} equals the value of the function at a
Finset.card_singleton- the cardinality of any singleton set {a} is 1
Nat.cast_one- the natural number 1 coerced into a ring or group with 1 is equal to 1
div_one- dividing any element by 1 yields the element itself
Finset.mem_map- an element b belongs to Finset.map f s for an embedding f if and only if b = f a for some a ∈ s
Equiv.coe_toEmbedding- the embedding induced by an equivalence agrees with the equivalence as a function
Equiv.Perm.one_apply- the identity permutation leaves every element unchanged (1 x = x)
congrFun- if two functions are equal, they take the same value at any given argument
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.
/-- Non-vacuity witness: with the trivial group, every (M, f) is a strongly symmetric instance. -/theorem is_strongly_symmetric_instance_bot {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ) : is_strongly_symmetric_instance M f ⊥ := by classical have hsym : ∀ (y : Fin m → ℝ), perm_group_symmetrize (⊥ : Subgroup (Equiv.Perm (Fin m))) y = y := by intro y funext u have h1 : (Finset.univ.filter (fun x : Equiv.Perm (Fin m) => x ∈ (⊥ : Subgroup (Equiv.Perm (Fin m))))) = {1} := by ext x; simp [Subgroup.mem_bot] rw [perm_group_symmetrize, h1, Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, div_one] simp have hmap : ∀ (S : Finset (Fin m)), Finset.map (Equiv.toEmbedding (1 : Equiv.Perm (Fin m))) S = S := by intro S ext x simp only [Finset.mem_map, Equiv.coe_toEmbedding, Equiv.Perm.one_apply] simp refine ⟨?_, ?_⟩ · intro σ hσ S rw [Subgroup.mem_bot] at hσ subst hσ rw [hmap] · intro S S' h rw [hsym, hsym] at h have hSS : S = S' := by ext u have h2 := congrFun h u simp only [finset_indicator_vec] at h2 constructor <;> intro hu · by_contra h1 simp [h1] at h2 simp [hu] at h2 · by_contra h1 simp [h1] at h2 simp [hu] at h2 simp [hSS]