AFTD Auto-Formalizing Theoretical Domains

third_principal_specialization_eval_one

theoremverified

Evaluating the third principal specialization of a graph G at (1, 1) via MvPolynomial.eval (fun _ => 1) equals the number of proper 3-colorings Fintype.card (G.Coloring (Fin 3)).

Statement

theorem third_principal_specialization_eval_one {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    MvPolynomial.eval (fun _ : Fin 2 => (1 : ℤ)) (third_principal_specialization G) =
      Fintype.card (G.Coloring (Fin 3))
Source
step towards caterpillar_third_t_chromatic_specialization_fiber_le_two
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • third_principal_specializationThe third principal specialization of the t-chromatic symmetric function of a graph G is the bivariate polynomial in Z[q, t] given by the…
Used by 1

The proof, explained

Evaluating the third principal specialization of G at (1, 1) counts the proper 3-colorings of G. By definition, the specialization is a sum over all proper 3-colorings of monomials in two variables. Because polynomial evaluation is a homomorphism, it distributes over the sum; substituting 1 for each variable reduces each monomial to 1, leaving the sum of 1 over all proper 3-colorings, which is their cardinality.

  1. The polynomial evaluation at (1, 1) distributes across the sum defining the third principal specialization, giving the sum over all proper 3-colorings c of the evaluation of each monomial X₀^(∑ v, c(v)) · X₁^(|im c|) at (1, 1).

    Unfolding the definition of the third principal specialization expresses the polynomial as a sum over proper 3-colorings c : G.Coloring (Fin 3) of the monomial X₀^(∑ v, c(v)) · X₁^(|im c|). Because polynomial evaluation is a ring homomorphism (and thus an additive monoid homomorphism), map_sum moves the evaluation inside the summation.

    lines 6–7

    uses map_sum

      unfold third_principal_specialization
      rw [map_sum]
  2. Evaluating each monomial at (1, 1) produces 1, and the resulting sum of 1 over all proper 3-colorings equals the total number of proper 3-colorings of G.

    At X₀ = 1 and X₁ = 1, each monomial 1^(∑ v, c(v)) · 1^(|im c|) simplifies to 1. Summing 1 over all c : G.Coloring (Fin 3) yields the cardinality of the type of proper 3-colorings, Fintype.card (G.Coloring (Fin 3)).

    line 8

      simp
map_sum
An additive monoid homomorphism preserves finite sums, so evaluating a sum yields the sum of the evaluated terms: g (∑ x ∈ s, f x) = ∑ x ∈ s, g (f 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

/-- Evaluating third_principal_specialization at (1, 1) yields the number of proper 3-colorings. -/theorem third_principal_specialization_eval_one {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    MvPolynomial.eval (fun _ : Fin 2 => (1 : ℤ)) (third_principal_specialization G) =      Fintype.card (G.Coloring (Fin 3)) := by  unfold third_principal_specialization  rw [map_sum]  simp
See it in the graphDiscuss this resultChallenge it