AFTD Auto-Formalizing Theoretical Domains

is_strongly_symmetric_instance_bot

theoremverified

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.

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

    lines 5–15

    uses Subgroup.mem_bot, Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, div_one

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

    lines 16–21

    uses Finset.mem_map, Equiv.coe_toEmbedding, Equiv.Perm.one_apply

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

    line 22

      refine ⟨?_, ?_⟩
  4. 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.

    lines 23–26

    uses Subgroup.mem_bot

      · intro σ hσ S
        rw [Subgroup.mem_bot] at hσ
        subst hσ
        rw [hmap]
  5. 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'.

    lines 27–28

      · intro S S' h
        rw [hsym, hsym] at h
  6. 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.

    lines 29–39

    uses congrFun

        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
  7. Matroid independence is preserved between S and S'.

    Because S = S', the condition M.Indep ↑S ↔ M.Indep ↑S' holds trivially.

    line 40

        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

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