AFTD Auto-Formalizing Theoretical Domains

perm_group_symmetrize_idempotent

theoremverified

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

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

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

    lines 5–21

    uses Finset.sum_nbij', Finset.mem_filter, Finset.mem_univ, true_and, G.mul_mem, G.inv_mem, mul_inv_rev, Equiv.Perm.mul_apply

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

    lines 22–24

      funext u
      show (∑ σ ∈ Finset.univ.filter (· ∈ G), perm_group_symmetrize G x (σ⁻¹ u)) /
          ((Finset.univ.filter (· ∈ G)).card : ℝ) = perm_group_symmetrize G x u
  3. 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).

    lines 25–29

    uses Finset.mem_filter, Finset.mem_univ, true_and

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

    lines 30–31

    uses Finset.sum_congr, Finset.sum_const, nsmul_eq_mul

      rw [Finset.sum_congr rfl h_eq]
      rw [Finset.sum_const, nsmul_eq_mul]
  5. 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).

    lines 32–35

    uses Nat.cast_ne_zero, Finset.card_ne_zero.mpr, Finset.mem_filter.mpr, Finset.mem_univ, G.one_mem

      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⟩⟩
  6. 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₀.

    line 36

    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

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