AFTD Auto-Formalizing Theoretical Domains

fin_pair_ne_sum_pow_swap

theoremverified

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
Used by 1

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.

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

    line 6

    uses Finset.sum_bij'

      refine Finset.sum_bij' (fun p _ => p.swap) (fun p _ => p.swap) ?_ ?_ ?_ ?_ ?_
  2. 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.

    line 7

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

    line 8

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

    lines 9–10

      · intro p _; rfl
      · intro p _; rfl
  5. 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.

    line 11

    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

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