AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_eval_one

theoremverified

For any finite simple graph G on a finite vertex type V and any natural number n, evaluating the n-th principal specialization of the t-chromatic symmetric function ps_n(Z_G(x; t)) at t = 1 via Polynomial.eval 1 yields the n-th principal specialization of the chromatic symmetric function ps_n(X_G(x)).

Statement

theorem simple_graph_t_chromatic_ps_eval_one {V : Type*} [Fintype V]
    (G : SimpleGraph V) (n : ℕ) :
    Polynomial.eval 1 (simple_graph_t_chromatic_principal_specialization G n) =
      simple_graph_chromatic_principal_specialization G n
Source
arXiv:2610.31785, proof of Proposition 3.9
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For any finite type $V$, any simple graph $G$ on $V$, and any natural number $n$, evaluating the $t$-chromatic principal specialization polynomial of $G$ with $n$ colors at $t = 1$ yields the chromatic principal specialization polynomial of $G$ with $n$ colors.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by expanding the definitions of both principal specializations as sums of monomials indexed by proper colorings of $G$. Because polynomial evaluation at $t = 1$ is a ring homomorphism, it distributes across the finite sum. Finally, evaluating each monomial $t^{|\mathrm{im}(c)|} q^{\sum_{v} c(v)}$ at $t = 1$ leaves $q^{\sum_{v} c(v)}$, matching the chromatic principal specialization term by term.

  1. The goal is rewritten in terms of the explicit sums defining both principal specializations.

    Unfolding the definitions of `simple_graph_t_chromatic_principal_specialization` and `simple_graph_chromatic_principal_specialization` expresses both sides as sums over all proper vertex colorings $c : V \to \{0, \dots, n-1\}$. On the left, each coloring contributes $t^{|\mathrm{im}(c)|} q^{\sum_v c(v)}$ inside an evaluation at $t = 1$; on the right, each coloring contributes $q^{\sum_v c(v)}$.

    line 6

    uses simple_graph_t_chromatic_principal_specialization, simple_graph_chromatic_principal_specialization

      simp only [simple_graph_t_chromatic_principal_specialization, simple_graph_chromatic_principal_specialization]
  2. Evaluation at $t = 1$ distributes across the sum over proper colorings.

    Because polynomial evaluation at $1$ definitionally coincides with the ring homomorphism `Polynomial.evalRingHom 1` (recorded as hypothesis $h$), it preserves addition and commutes with finite sums via `map_sum`, moving the evaluation inside the sum onto each individual summand.

    lines 7–9

    uses map_sum

      have h : ∀ p : Polynomial (Polynomial ℕ),
          Polynomial.eval (1 : Polynomial ℕ) p = Polynomial.evalRingHom 1 p := fun p => rfl
      rw [h, map_sum]
  3. Evaluating each monomial at $t = 1$ yields the chromatic principal specialization.

    Each summand on the left is a monomial of the form $a \cdot t^k$, where $a = q^{\sum_v c(v)}$ and $k = |\mathrm{im}(c)|$. Applying `Polynomial.eval_monomial` evaluates $a \cdot t^k$ at $t = 1$ to $a \cdot 1^k = a$, reducing the left-hand sum to the right-hand sum and closing the goal.

    line 10

    uses Polynomial.eval_monomial

      simp [Polynomial.eval_monomial]
simple_graph_t_chromatic_principal_specialization
The $n$-th principal specialization of the $t$-chromatic symmetric function of $G$, defined as $\sum_c t^{|\mathrm{im}(c)|} q^{\sum_{v} c(v)}$ over proper colorings $c : V \to \{0, \dots, n-1\}$.
simple_graph_chromatic_principal_specialization
The $n$-th principal specialization of the chromatic symmetric function of $G$, defined as $\sum_c q^{\sum_{v} c(v)}$ over proper colorings $c : V \to \{0, \dots, n-1\}$.
map_sum
An additive monoid homomorphism respects finite sums: $g(\sum_{x \in s} f(x)) = \sum_{x \in s} g(f(x))$.
Polynomial.eval_monomial
Evaluating a monomial $a \cdot X^n$ at $x$ yields $a \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

/-- Evaluating the n-th principal specialization ps_n(Z_G(x; t)) at t = 1 yields ps_n(X_G(x)). -/theorem simple_graph_t_chromatic_ps_eval_one {V : Type*} [Fintype V]    (G : SimpleGraph V) (n : ℕ) :    Polynomial.eval 1 (simple_graph_t_chromatic_principal_specialization G n) =      simple_graph_chromatic_principal_specialization G n := by  simp only [simple_graph_t_chromatic_principal_specialization, simple_graph_chromatic_principal_specialization]  have h : ∀ p : Polynomial (Polynomial ℕ),      Polynomial.eval (1 : Polynomial ℕ) p = Polynomial.evalRingHom 1 p := fun p => rfl  rw [h, map_sum]  simp [Polynomial.eval_monomial]
See it in the graphDiscuss this resultChallenge it