AFTD Auto-Formalizing Theoretical Domains

is_strongly_symmetric_instance

def

The 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 σ ∈ G, and two sets with equal symmetrized indicator vectors E_σ[1_{σ(S)}] are both independent or both dependent.

Statement

def is_strongly_symmetric_instance {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ)
    (G : Subgroup (Equiv.Perm (Fin m))) : Prop
Defined in
arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Definition 2.1 (strong symmetry)
Verified
07 Oct 2026
Axioms
none listed
Built on 2
  • 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}.
Used by 5

Lean source view module on GitHub

/-- The problem `max {f(S) : S independent in M}` is strongly symmetric with respect to the permutation group `G`: `f(σ(S)) = f(S)` for every `σ ∈ G`, and two sets with the same symmetrized indicator vector are both independent or both dependent. -/
def is_strongly_symmetric_instance {m : ℕ} (M : Matroid (Fin m)) (f : Finset (Fin m) → ℝ)
    (G : Subgroup (Equiv.Perm (Fin m))) : Prop :=
  (∀ σ ∈ G, ∀ S : Finset (Fin m), f (S.map σ.toEmbedding) = f S) ∧
    ∀ S S' : Finset (Fin m),
      perm_group_symmetrize G (finset_indicator_vec S) =
        perm_group_symmetrize G (finset_indicator_vec S') →
      (M.Indep ↑S ↔ M.Indep ↑S')
See it in the graphDiscuss this resultChallenge it