fin_pair_ne_sum_pow_swap
For natural numbers n, a, b, the sum over ordered pairs (j1, j2) of distinct elements of Fin n of X^(a j1 + b j2) in ℕ[X] equals the sum of X^(b j1 + a j2).
Statement
theorem fin_pair_ne_sum_pow_swap (n a b : ℕ) : ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), (Polynomial.X : Polynomial ℕ) ^ (a * (p.1 : ℕ) + b * (p.2 : ℕ)) = ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), (Polynomial.X : Polynomial ℕ) ^ (b * (p.1 : ℕ) + a * (p.2 : ℕ))
- Source
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(3), symmetry used to order the part sizes
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_t_chromatic_principal_specializationFor a finite simple graph G on a finite vertex type V and a natural number n, the n-th principal specialization of the t-chromatic…
- Used by 1
- simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartiteLet n ≥ 2 and let G be a connected finite simple graph with at least 2 vertices that has a proper coloring with n colors, and let b : V →…
The proof, explained
The identity is proved by reindexing the sum via the coordinate swap bijection (j₁, j₂) ↦ (j₂, j₁). Swapping coordinates is an involution that preserves distinctness of indices, providing a bijection from the set of distinct pairs to itself. Under this bijection, the summand X^(a j₁ + b j₂) is mapped to X^(b j₂ + a j₁), which is identical by commutativity of addition in the exponent.
The sum equality reduces to showing that coordinate swapping is a bijection on distinct pairs and transforms the summands correctly.
Applying Finset.sum_bij' with the swap map p ↦ p.swap in both directions sets up five obligations: the map sends distinct pairs to distinct pairs; the inverse map does the same; the map and its inverse compose to the identity in both orders; and each summand equals the corresponding term at the swapped index.
uses
Finset.sum_bij'refine Finset.sum_bij' (fun p _ => p.swap) (fun p _ => p.swap) ?_ ?_ ?_ ?_ ?_
Swapping coordinates maps any pair of distinct elements to another pair of distinct elements.
Given a pair p = (j₁, j₂) with j₁ ≠ j₂, simplifying the universe and filter conditions with Finset.mem_filter, Finset.mem_univ, and true_and reduces the goal to j₂ ≠ j₁. An assumed equality j₂ = j₁ would imply j₁ = j₂ by symmetry, contradicting the distinctness of the original coordinates.
uses
Finset.mem_filter,Finset.mem_univ,true_and· intro p hp; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢; exact fun e => hp e.symm
The inverse map also maps pairs of distinct elements to pairs of distinct elements.
Because the inverse map is also coordinate swapping, the reasoning is identical to the forward direction.
uses
Finset.mem_filter,Finset.mem_univ,true_and· intro p hp; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢; exact fun e => hp e.symm
Coordinate swapping is an involution, so the map and its inverse compose to the identity.
Swapping the coordinates of a pair twice returns the original pair, which holds definitionally (by rfl) for both the left-inverse and right-inverse requirements.
· intro p _; rfl · intro p _; rfl
For each pair p, the summand matches the swapped term.
Simplifying the components of the swapped pair using Prod.fst_swap and Prod.snd_swap rewrites the exponent b * p.swap.1 + a * p.swap.2 into b * p.2 + a * p.1. Ring normalization (ring_nf) confirms that a * p.1 + b * p.2 = b * p.2 + a * p.1 by commutativity of addition and multiplication, making the powers of X identical.
uses
Prod.fst_swap,Prod.snd_swap· intro p _; simp only [Prod.fst_swap, Prod.snd_swap]; ring_nf
Finset.sum_bij'- A sum over a finite set equals a sum over another finite set if there is a bijection between the sets preserving the summands.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- True ∧ P is logically equivalent to P.
Prod.fst_swap- The first projection of a swapped pair (x, y).swap is the second component, y.
Prod.snd_swap- The second projection of a swapped pair (x, y).swap is the first component, x.
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.
theorem fin_pair_ne_sum_pow_swap (n a b : ℕ) : ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), (Polynomial.X : Polynomial ℕ) ^ (a * (p.1 : ℕ) + b * (p.2 : ℕ)) = ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), (Polynomial.X : Polynomial ℕ) ^ (b * (p.1 : ℕ) + a * (p.2 : ℕ)) := by refine Finset.sum_bij' (fun p _ => p.swap) (fun p _ => p.swap) ?_ ?_ ?_ ?_ ?_ · intro p hp; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢; exact fun e => hp e.symm · intro p hp; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢; exact fun e => hp e.symm · intro p _; rfl · intro p _; rfl · intro p _; simp only [Prod.fst_swap, Prod.snd_swap]; ring_nf