AFTD Auto-Formalizing Theoretical Domains

sum_perm_group_symmetrize

theoremverified

Symmetrization preserves the total mass: the coordinates of x̄ = E_{σ∈G}[σ(x)] sum to the same value as the coordinates of x.

Statement

theorem sum_perm_group_symmetrize {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m)))
    (x : Fin m → ℝ) :
    ∑ u, perm_group_symmetrize G x u = ∑ u, x u
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.

The proof, explained

The proof expands the definition of group symmetrization as an average over G and swaps the order of summation between the coordinates and the group elements. Because every permutation in G acts bijectively on the coordinate indices, re-indexing shows that the sum over coordinates is invariant under each permutation, making the inner sum constant across all |G| elements of the group. Summing this constant yields |G| * ∑_u x(u), and canceling the non-zero factor |G| (which is non-zero because the identity permutation belongs to G) leaves the original sum ∑_u x(u).

  1. Expanding the definition expresses the sum of the symmetrized vector's coordinates as ∑_u ((∑_{σ ∈ G} x(σ⁻¹ u)) / |G|).

    We enable classical logic and unfold `perm_group_symmetrize`, which defines each coordinate u of the symmetrized vector as the average of x(σ⁻¹ u) over all permutations σ in G.

    lines 5–6

    uses perm_group_symmetrize

      classical
      simp only [perm_group_symmetrize]
  2. The sum over coordinates is rewritten as (∑_{σ ∈ G} ∑_u x(σ⁻¹ u)) / |G|.

    We factor the division by |G| out of the sum over u using `Finset.sum_div`, and then swap the two summations using `Finset.sum_comm` so that the outer sum runs over permutations σ ∈ G and the inner sum runs over coordinates u.

    lines 7–8

    uses Finset.sum_div, Finset.sum_comm

      rw [← Finset.sum_div]
      rw [Finset.sum_comm]
  3. The inner sum simplifies to ∑_u x(u), and the numerator evaluates to |G| * ∑_u x(u).

    Because each permutation σ⁻¹ is a bijection on the index set, precomposing with it does not change the sum over all coordinates; rewriting with `Equiv.sum_comp` simplifies ∑_u x(σ⁻¹ u) to ∑_u x(u). Since this inner sum no longer depends on σ, summing it over all elements of G gives |G| * ∑_u x(u) via `Finset.sum_const` and `nsmul_eq_mul`.

    lines 9–10

    uses Equiv.sum_comp, Finset.sum_const, nsmul_eq_mul

      simp only [Equiv.sum_comp]
      rw [Finset.sum_const, nsmul_eq_mul]
  4. The cardinality of G is non-zero as a real number (|G| ≠ 0).

    By `Nat.cast_ne_zero`, the real cast of |G| is non-zero if and only if |G| is non-zero in ℕ. By `Finset.card_ne_zero.mpr`, this is equivalent to G being nonempty, which is witnessed by the identity permutation 1 belonging to G (`G.one_mem`) and to the universal finset (`Finset.mem_univ`, `Finset.mem_filter.mpr`).

    lines 11–14

    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⟩⟩
  5. Canceling |G| yields the original coordinate sum ∑_u x(u).

    With |G| ≠ 0 established, `mul_div_cancel_left₀` cancels |G| from the numerator and denominator of (|G| * ∑_u x(u)) / |G|, leaving ∑_u x(u).

    line 15

    uses mul_div_cancel_left₀

      exact mul_div_cancel_left₀ _ hcard
perm_group_symmetrize
The symmetrization of a vector x under a subgroup G of permutations, defined at coordinate u by (1 / |G|) ∑_{σ ∈ G} x(σ⁻¹ u).
Finset.sum_div
A common divisor can be factored out of a finite sum: (∑_{i ∈ s} f(i)) / a = ∑_{i ∈ s} (f(i) / a).
Finset.sum_comm
The order of two independent finite summations can be exchanged: ∑_{x ∈ s} ∑_{y ∈ t} f(x, y) = ∑_{y ∈ t} ∑_{x ∈ s} f(x, y).
Equiv.sum_comp
Summing a function composed with a bijection over the entire finite domain equals summing the function directly: ∑_i g(e(i)) = ∑_i g(i).
Finset.sum_const
Summing a constant b over a finite set s equals |s| • b.
nsmul_eq_mul
Natural number scalar multiplication in a ring agrees with multiplication by the natural number cast: n • a = (↑n) * a.
Nat.cast_ne_zero
The cast of a natural number into a characteristic-zero ring is non-zero if and only if the natural number is non-zero: ↑n ≠ 0 ↔ n ≠ 0.
Finset.card_ne_zero.mpr
A finite set has non-zero cardinality if it is nonempty.
Finset.mem_filter.mpr
An element belongs to the filtered finset if it belongs to the ambient finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
G.one_mem
The identity element 1 belongs to any subgroup G.
mul_div_cancel_left₀
For a non-zero element a ≠ 0, (a * b) / a = b.

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

/-- Symmetrization over a permutation group preserves the sum of the coordinates. -/theorem sum_perm_group_symmetrize {m : ℕ} (G : Subgroup (Equiv.Perm (Fin m)))    (x : Fin m → ℝ) :    ∑ u, perm_group_symmetrize G x u = ∑ u, x u := by  classical  simp only [perm_group_symmetrize]  rw [← Finset.sum_div]  rw [Finset.sum_comm]  simp only [Equiv.sum_comp]  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