simple_graph_t_chromatic_ps_coeff_t_eq_sum
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
- 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_of_edgeLet G be a connected finite simple graph with a proper 2-coloring b : V → Fin 2 and an edge u0 w0 with b u0 = 0, b w0 = 1. Let s0, s1 be…
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.
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$.
uses
Polynomial.finsetSum_coeff,Finset.sum_filterclassical unfold simple_graph_t_chromatic_principal_specialization rw [Polynomial.finsetSum_coeff, Finset.sum_filter]
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.
uses
Finset.sum_congr,Polynomial.coeff_monomial,Polynomial.X_pow_eq_monomialrefine 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$.
- The principal specialization is formalized as an element of the iterated polynomial ring `Polynomial (Polynomial ℕ)`, which represents polynomials in $t$ whose coefficients are polynomials in $q$: the outer indeterminate represents $t$ (with exponent $|c(V)|$), while the inner indeterminate $X$ represents $q$ (with exponent $\sum_{v} c(v)$).
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 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]