perm_group_symmetrize_idempotent
Symmetrization is idempotent: symmetrizing twice is the same as symmetrizing once, i.e. x̄ is fixed by every element of G.
Statement
theorem perm_group_symmetrize_idempotent {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m)))
(x : Fin m → ℝ) :
perm_group_symmetrize G (perm_group_symmetrize G x) = perm_group_symmetrize G x- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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.
- Used by 1
- 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…
The proof, explained
The theorem states that averaging a vector over a permutation subgroup G twice yields the same result as averaging once (idempotence). The proof first shows that the symmetrized vector x̄ is G-invariant—that is, x̄(σ⁻¹ u) = x̄(u) for every σ ∈ G—by reindexing the sum via the bijection τ ↦ σ * τ. Applying symmetrization a second time therefore averages the constant value x̄(u) over all elements of G. Since the subgroup G contains the identity element, its cardinality is non-zero, allowing |G| to cancel from the numerator and denominator to leave x̄(u).
The symmetrized vector is invariant under the action of any permutation σ ∈ G: for every coordinate u, (perm_group_symmetrize G x)(σ⁻¹ u) = (perm_group_symmetrize G x)(u).
Unfolding the definition of symmetrization, both sides are averages over the subgroup G with common denominator |G|, so it suffices to show that their numerators are equal. In the numerator for the shifted vector, each term evaluates x at τ⁻¹ (σ⁻¹ u). Reindexing the sum via Finset.sum_nbij' using the bijection τ ↦ σ * τ (with inverse τ ↦ σ⁻¹ * τ), left-multiplication by σ preserves membership in G (Finset.mem_filter, Finset.mem_univ, true_and, G.mul_mem, G.inv_mem). The summand then transforms into x((σ * τ)⁻¹ u), which matches x(τ⁻¹ (σ⁻¹ u)) by group inverse laws (mul_inv_rev, Equiv.Perm.mul_apply).
uses
Finset.sum_nbij',Finset.mem_filter,Finset.mem_univ,true_and,G.mul_mem,G.inv_mem,mul_inv_rev,Equiv.Perm.mul_applyclassical have hinv : ∀ {σ : Equiv.Perm (Fin m)} (hσ : σ ∈ G) (u : Fin m), perm_group_symmetrize G x (σ⁻¹ u) = perm_group_symmetrize G x u := by intro σ hσ u unfold perm_group_symmetrize congr 1 refine Finset.sum_nbij' (fun τ => σ * τ) (fun τ => σ⁻¹ * τ) ?_ ?_ ?_ ?_ ?_ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hσ hτ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem (G.inv_mem hσ) hτ · intro τ _; simp · intro τ _; simp · intro τ _ simp [mul_inv_rev, Equiv.Perm.mul_apply]
To show idempotence, it suffices to show that for every coordinate u, the group average of the symmetrized vector evaluated at σ⁻¹ u equals the symmetrized vector evaluated at u.
By function extensionality, two functions on Fin m are equal if they agree at every coordinate u. Unfolding the definition of the outer symmetrization evaluated at u, the goal is to show that the average of (perm_group_symmetrize G x)(σ⁻¹ u) over all σ ∈ G equals (perm_group_symmetrize G x)(u).
funext u show (∑ σ ∈ Finset.univ.filter (· ∈ G), perm_group_symmetrize G x (σ⁻¹ u)) / ((Finset.univ.filter (· ∈ G)).card : ℝ) = perm_group_symmetrize G x u
Every term in the outer summation satisfies (perm_group_symmetrize G x)(σ⁻¹ u) = (perm_group_symmetrize G x)(u) for each σ ∈ G.
For any σ belonging to the subgroup G (unpacked using Finset.mem_filter, Finset.mem_univ, and true_and), the G-invariance property established in Step 1 shows that (perm_group_symmetrize G x)(σ⁻¹ u) is identical to the constant value (perm_group_symmetrize G x)(u).
uses
Finset.mem_filter,Finset.mem_univ,true_andhave h_eq : ∀ σ ∈ Finset.univ.filter (· ∈ G), perm_group_symmetrize G x (σ⁻¹ u) = perm_group_symmetrize G x u := by intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ exact hinv hσ u
The sum of the symmetrized vector over all σ ∈ G simplifies to |G| * (perm_group_symmetrize G x)(u).
Rewriting each summand with the equality from Step 3 using Finset.sum_congr, the summation becomes a sum of constant terms. By Finset.sum_const and nsmul_eq_mul, summing a constant over a finite set equals the cardinality of the set multiplied by that constant.
uses
Finset.sum_congr,Finset.sum_const,nsmul_eq_mulrw [Finset.sum_congr rfl h_eq] rw [Finset.sum_const, nsmul_eq_mul]
The cardinality of the subgroup G, viewed as a real number, is non-zero.
By Nat.cast_ne_zero, the cast of |G| into ℝ is non-zero if and only if |G| ≠ 0 as a natural number. By Finset.card_ne_zero.mpr, this holds because the set of elements in G is nonempty, containing the identity permutation 1 (G.one_mem, Finset.mem_filter.mpr, Finset.mem_univ).
uses
Nat.cast_ne_zero,Finset.card_ne_zero.mpr,Finset.mem_filter.mpr,Finset.mem_univ,G.one_memhave hcard : ((Finset.univ.filter (· ∈ G)).card : ℝ) ≠ 0 := by rw [Nat.cast_ne_zero] exact Finset.card_ne_zero.mpr ⟨1, Finset.mem_filter.mpr ⟨Finset.mem_univ 1, G.one_mem⟩⟩
Canceling the factor of |G| completes the proof.
Since |G| ≠ 0 as established in Step 5, the expression (|G| * (perm_group_symmetrize G x)(u)) / |G| simplifies directly to (perm_group_symmetrize G x)(u) by mul_div_cancel_left₀.
uses
mul_div_cancel_left₀exact mul_div_cancel_left₀ _ hcard
Finset.sum_nbij'- Two finite sums are equal if there is a bijection between their index sets such that the summands correspond under the bijection.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The proposition `True ∧ p` simplifies to `p`.
G.mul_mem- If two elements belong to the subgroup G, their product belongs to G.
G.inv_mem- If an element belongs to the subgroup G, its inverse belongs to G.
mul_inv_rev- The inverse of a product in a group is the product of the inverses in reverse order: (a * b)⁻¹ = b⁻¹ * a⁻¹.
Equiv.Perm.mul_apply- The composition of two permutations applied to an element is given by (f * g) x = f (g x).
Finset.sum_congr- Two sums over identical finite sets are equal if their summands agree at every element.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set scalar-multiplied by that constant.
nsmul_eq_mul- Natural number scalar multiplication n • a in a semiring equals the cast ↑n multiplied by a.
Nat.cast_ne_zero- The cast of a natural number into a characteristic-zero semiring (such as ℝ) is non-zero if and only if the natural number is non-zero.
Finset.card_ne_zero.mpr- If a finite set is nonempty, its cardinality is non-zero.
Finset.mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base set and satisfies the predicate.
G.one_mem- The identity element 1 belongs to the subgroup G.
mul_div_cancel_left₀- In a commutative monoid with division, (a * b) / a = b provided that a ≠ 0.
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.
/-- The group average of a group average is the group average: symmetrization is idempotent. -/theorem perm_group_symmetrize_idempotent {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m))) (x : Fin m → ℝ) : perm_group_symmetrize G (perm_group_symmetrize G x) = perm_group_symmetrize G x := by classical have hinv : ∀ {σ : Equiv.Perm (Fin m)} (hσ : σ ∈ G) (u : Fin m), perm_group_symmetrize G x (σ⁻¹ u) = perm_group_symmetrize G x u := by intro σ hσ u unfold perm_group_symmetrize congr 1 refine Finset.sum_nbij' (fun τ => σ * τ) (fun τ => σ⁻¹ * τ) ?_ ?_ ?_ ?_ ?_ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem hσ hτ · intro τ hτ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hτ ⊢ exact G.mul_mem (G.inv_mem hσ) hτ · intro τ _; simp · intro τ _; simp · intro τ _ simp [mul_inv_rev, Equiv.Perm.mul_apply] funext u show (∑ σ ∈ Finset.univ.filter (· ∈ G), perm_group_symmetrize G x (σ⁻¹ u)) / ((Finset.univ.filter (· ∈ G)).card : ℝ) = perm_group_symmetrize G x u have h_eq : ∀ σ ∈ Finset.univ.filter (· ∈ G), perm_group_symmetrize G x (σ⁻¹ u) = perm_group_symmetrize G x u := by intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ exact hinv hσ u rw [Finset.sum_congr rfl h_eq] rw [Finset.sum_const, nsmul_eq_mul] have hcard : ((Finset.univ.filter (· ∈ G)).card : ℝ) ≠ 0 := by rw [Nat.cast_ne_zero] exact Finset.card_ne_zero.mpr ⟨1, Finset.mem_filter.mpr ⟨Finset.mem_univ 1, G.one_mem⟩⟩ exact mul_div_cancel_left₀ _ hcard