AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_coeff_t_eq_sum

theoremverified

For a finite simple graph G and natural numbers n, k, the coefficient of t^k in ps_n(Z_G(x; t)) is the polynomial in q equal to the sum of q^(∑_v c(v)) over the proper colorings c : V → Fin n using exactly k distinct colors.

Statement

theorem simple_graph_t_chromatic_ps_coeff_t_eq_sum {V : Type*} [Fintype V] (G : SimpleGraph V) (n k : ℕ) :
    (simple_graph_t_chromatic_principal_specialization G n).coeff k =
      ∑ c ∈ Finset.univ.filter (fun c : G.Coloring (Fin n) => (Finset.univ.image c).card = k),
        Polynomial.X ^ (∑ v : V, (c v : ℕ))
Source
arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(3), the coefficient of t^k as a sum over colorings
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The principal specialization is defined as a sum over all proper colorings $c$ of the graph, where each coloring contributes a monomial $q^{\sum_v c(v)} t^{|c(V)|}$ in the polynomial ring $\mathbb{N}[q][t]$. To extract the coefficient of $t^k$, the proof uses linearity to interchange coefficient extraction with the finite sum. The $k$-th coefficient of each coloring's monomial is non-zero (and equal to $q^{\sum_v c(v)}$) precisely when the coloring uses exactly $k$ colors (i.e., $|c(V)| = k$), which term-by-term matches the filtered sum definition.

  1. The equality reduces to equating $\sum_{c} [t^k] \left(q^{\sum_{v} c(v)} t^{|c(V)|}\right)$ with $\sum_{c} \left(\text{if } |c(V)| = k \text{ then } q^{\sum_{v} c(v)} \text{ else } 0\right)$.

    Unfolding the definition of the chromatic principal specialization, the polynomial is expressed as a sum over all proper colorings $c : V \to \mathrm{Fin}\, n$ of the monomial $q^{\sum_{v} c(v)} t^{|c(V)|}$. By linearity of the polynomial coefficient operator (via `Polynomial.finsetSum_coeff`), taking the $k$-th coefficient commutes with the finite sum. On the right-hand side, `Finset.sum_filter` rewrites the sum over colorings using exactly $k$ colors as an unrestricted sum over all colorings with an indicator function that selects only those satisfying $|c(V)| = k$.

    lines 5–7

    uses Polynomial.finsetSum_coeff, Finset.sum_filter

      classical
      unfold simple_graph_t_chromatic_principal_specialization
      rw [Polynomial.finsetSum_coeff, Finset.sum_filter]
  2. The summands of both sums are identical for every coloring $c$.

    By congruence of sums (`Finset.sum_congr`), it suffices to show that the summands match for an arbitrary coloring $c$. By `Polynomial.coeff_monomial`, the $k$-th coefficient of the monomial with degree $|c(V)|$ and coefficient $q^{\sum_{v} c(v)}$ is equal to $q^{\sum_{v} c(v)}$ if $|c(V)| = k$ and $0$ otherwise. Rewriting the power $X^{\sum_{v} c(v)}$ as a monomial via `Polynomial.X_pow_eq_monomial`, this conditional term matches the right-hand summand, completing the proof.

    lines 8–9

    uses Finset.sum_congr, Polynomial.coeff_monomial, Polynomial.X_pow_eq_monomial

      refine Finset.sum_congr rfl (fun c _ => ?_)
      rw [Polynomial.coeff_monomial, Polynomial.X_pow_eq_monomial]
Polynomial.finsetSum_coeff
The $n$-th coefficient of a finite sum of polynomials is the sum of their $n$-th coefficients.
Finset.sum_filter
A sum over a filtered finite set $\{a \in s \mid p(a)\}$ equals the sum over all $a \in s$ of the conditional term that is $f(a)$ when $p(a)$ holds and $0$ otherwise.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on every element of the index set.
Polynomial.coeff_monomial
The $m$-th coefficient of the monomial $a X^n$ is $a$ if $n = m$ and $0$ otherwise.
Polynomial.X_pow_eq_monomial
The power $X^n$ is equal to the monomial $1 \cdot X^n$.

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 simple_graph_t_chromatic_ps_coeff_t_eq_sum {V : Type*} [Fintype V] (G : SimpleGraph V) (n k : ℕ) :    (simple_graph_t_chromatic_principal_specialization G n).coeff k =      ∑ c ∈ Finset.univ.filter (fun c : G.Coloring (Fin n) => (Finset.univ.image c).card = k),        Polynomial.X ^ (∑ v : V, (c v : ℕ)) := by  classical  unfold simple_graph_t_chromatic_principal_specialization  rw [Polynomial.finsetSum_coeff, Finset.sum_filter]  refine Finset.sum_congr rfl (fun c _ => ?_)  rw [Polynomial.coeff_monomial, Polynomial.X_pow_eq_monomial]
See it in the graphDiscuss this resultChallenge it