sum_perm_group_symmetrize
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).
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.
uses
perm_group_symmetrizeclassical simp only [perm_group_symmetrize]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.
uses
Finset.sum_div,Finset.sum_commrw [← Finset.sum_div] rw [Finset.sum_comm]
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`.
uses
Equiv.sum_comp,Finset.sum_const,nsmul_eq_mulsimp only [Equiv.sum_comp] rw [Finset.sum_const, nsmul_eq_mul]
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`).
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 |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).
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
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.
/-- 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