perm_group_symmetrize
def
The symmetrization x̄ = E_{σ∈G}[σ(x)] of a vector x over a group G of permutations of the coordinates, where σ(x)_{σ(u)} = x_u.
Statement
noncomputable def perm_group_symmetrize {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m))) (x : Fin m → ℝ) : Fin m → ℝ
- Defined in
- arXiv:2610.07387 (Stronger hardness for submodular maximization subject to a matroid constraint), Definition 2.2 (x̄)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 8
- sum_perm_group_symmetrizeSymmetrization preserves the total mass: the coordinates of x̄ = E_{σ∈G}[σ(x)] sum to the same value as the coordinates of x.
- is_strongly_symmetric_instance_botEvery matroid together with any set function is a strongly symmetric instance for the trivial permutation group: a witness that the…
- perm_group_symmetrize_idempotentSymmetrization is idempotent: symmetrizing twice is the same as symmetrizing once, i.e. x̄ is fixed by every element of G.
- perm_group_symmetrize_mem_matroid_polytopeFor a strongly symmetric instance, symmetrizing a point of the matroid polytope stays inside the matroid polytope.
- matroid_symmetry_gap_le_oneFor every strongly symmetric instance max{f(S) : S independent in M} with respect to a permutation group G, the best symmetrized…
- 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 σ ∈…
- symmetry_gap_numerator_eq_sSup_fixedFor a strongly symmetric instance the numerator of the symmetry gap, sup_{x∈P(M)} F(x̄), equals the supremum of F over the points of the…
- symmetrize_image_matroid_polytope_eq_fixedFor a strongly symmetric instance, the image of the matroid polytope under symmetrization is exactly the set of points of the polytope…
Lean source view module on GitHub
/-- The symmetrization `x̄ = E_{σ ∈ G}[σ(x)]` of `x ∈ ℝ^m` over a group `G` of permutations of `Fin m`, where `σ(x)` is `x` with coordinates moved by `σ`: `σ(x)_{σ u} = x_u`. -/ noncomputable def perm_group_symmetrize {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m))) (x : Fin m → ℝ) : Fin m → ℝ := by classical exact fun u => (∑ σ ∈ Finset.univ.filter (· ∈ G), x (σ⁻¹ u)) / (Finset.univ.filter (· ∈ G)).card