AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_coeff_coeff

theoremverified

For a finite simple graph G and natural numbers n, k, j, the coefficient of t^k q^j in the n-th principal specialization ps_n(Z_G(x; t)) (simple_graph_t_chromatic_principal_specialization G n, outer variable t, inner variable q) equals the number of proper colorings c : V → Fin n that use exactly k distinct colors and have weight ∑_v c(v) = j.

Statement

theorem simple_graph_t_chromatic_ps_coeff_coeff {V : Type*} [Fintype V] (G : SimpleGraph V) (n k j : ℕ) :
    ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j =
      Fintype.card {c : G.Coloring (Fin n) //
        (Finset.univ.image c).card = k ∧ ∑ v : V, (c v : ℕ) = j}
Source
arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16 (equation (3.1): the coefficients count proper colorings by number of colors and weight)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The proof shows that extracting the coefficient of t^k q^j from the principal specialization counts proper colorings with exactly k colors and total weight j. It expands the specialization into a sum of monomials t^(|c(V)|) q^(∑_v c(v)) over colorings c and moves the coefficient extractions inside the sum. Simultaneously, it rewrites the cardinality on the right-hand side as a sum of 1s over matching colorings, reducing the goal by sum congruence to verifying term-by-term equality for each coloring via a straightforward case split.

  1. The coefficient [t^k q^j] of the principal specialization equals the sum over all proper colorings c of the coefficient [q^j] of (if |c(V)| = k then q^(∑_v c(v)) else 0).

    Unfolding the definition of the principal specialization shows it is a sum over all proper n-colorings c of the bivariate monomial t^(|c(V)|) q^(∑_v c(v)). Applying `Polynomial.finsetSum_coeff` twice moves the coefficient extractions for t (degree k) and q (degree j) inside the sum over colorings. Then `Polynomial.coeff_monomial` evaluates the outer coefficient with respect to t, leaving an indicator (if |c(V)| = k then q^(∑_v c(v)) else 0).

    lines 5–8

    uses Polynomial.finsetSum_coeff, Polynomial.coeff_monomial

      classical
      unfold simple_graph_t_chromatic_principal_specialization
      rw [Polynomial.finsetSum_coeff, Polynomial.finsetSum_coeff]
      simp only [Polynomial.coeff_monomial]
  2. The right-hand side, counting colorings using k colors with total weight j, can be written as the sum over all colorings of an indicator function for those two conditions.

    By `Fintype.card_subtype`, the cardinality of the subtype is the cardinality of the corresponding filtered set of colorings. Writing this cardinality as a sum of ones via `Finset.card_eq_sum_ones` and transforming the filter into an if-then-else condition via `Finset.sum_filter`, the right-hand side becomes the sum over all colorings c of (if |c(V)| = k ∧ ∑_v c(v) = j then 1 else 0).

    lines 9–10

    uses Fintype.card_subtype, Finset.card_eq_sum_ones, Finset.sum_filter

      rw [Fintype.card_subtype]
      rw [Finset.card_eq_sum_ones, Finset.sum_filter]
  3. It suffices to show that the summands on both sides are equal for each individual coloring c.

    Using `Finset.sum_congr`, since both sides are sums over the universal set of colorings, equality of the entire sums follows if the summands agree for every coloring c.

    line 11

    uses Finset.sum_congr

      refine Finset.sum_congr rfl (fun c _ => ?_)
  4. For every coloring c, the contribution from the polynomial equals the indicator function testing whether |c(V)| = k and ∑_v c(v) = j.

    We split into four cases depending on whether |c(V)| = k holds and whether ∑_v c(v) = j holds. In all four cases, simplifying with the case hypotheses and `Polynomial.coeff_monomial` shows both sides evaluate to 1 when both conditions are satisfied, and to 0 otherwise.

    lines 12–13

    uses Polynomial.coeff_monomial

      by_cases h1 : (Finset.univ.image c).card = k <;> by_cases h2 : ∑ v : V, (c v : ℕ) = j <;>
        simp [h1, h2, Polynomial.coeff_monomial]
Polynomial.finsetSum_coeff
The coefficient of degree n of a finite sum of polynomials is the sum of their degree-n coefficients: [Xⁿ] (∑ᵢ f(i)) = ∑ᵢ ([Xⁿ] f(i)).
Polynomial.coeff_monomial
The coefficient of degree m of the monomial a Xⁿ is a if n = m and 0 otherwise.
Fintype.card_subtype
The cardinality of a subtype {x // p x} is equal to the cardinality of the filtered finset of elements satisfying p.
Finset.card_eq_sum_ones
The cardinality of a finite set s equals the sum of 1 over all elements of s.
Finset.sum_filter
Summing a function f over elements satisfying a predicate p equals summing (if p(a) then f(a) else 0) over the entire finite set.
Finset.sum_congr
If two finite sets are equal and two summands agree on every element, their sums are equal.

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_coeff {V : Type*} [Fintype V] (G : SimpleGraph V) (n k j : ℕ) :    ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j =      Fintype.card {c : G.Coloring (Fin n) //        (Finset.univ.image c).card = k ∧ ∑ v : V, (c v : ℕ) = j} := by  classical  unfold simple_graph_t_chromatic_principal_specialization  rw [Polynomial.finsetSum_coeff, Polynomial.finsetSum_coeff]  simp only [Polynomial.coeff_monomial]  rw [Fintype.card_subtype]  rw [Finset.card_eq_sum_ones, Finset.sum_filter]  refine Finset.sum_congr rfl (fun c _ => ?_)  by_cases h1 : (Finset.univ.image c).card = k <;> by_cases h2 : ∑ v : V, (c v : ℕ) = j <;>    simp [h1, h2, Polynomial.coeff_monomial]
See it in the graphDiscuss this resultChallenge it