AFTD Auto-Formalizing Theoretical Domains

third_principal_specialization_congr

theoremverified

If two finite graphs are isomorphic, their third principal specializations are equal as bivariate polynomials.

Statement

theorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H
Source
arXiv:2610.31785 Proposition 3.3
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

Let $V$ and $W$ be finite types with decidable equality, and let $G$ and $H$ be simple graphs on $V$ and $W$, respectively, each with decidable adjacency relations. If $e : G \simeq_g H$ is a graph isomorphism, then third_principal_specialization G = third_principal_specialization H.

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 third principal specialization of a graph is a bivariate polynomial defined as a sum over all 3-colorings c of the term X₀^(∑ v, c(v)) * X₁^(|im(c)|). Given a graph isomorphism e : G ≃g H, pulling back colorings along e defines an equivalence between the 3-colorings of H and G. Reindexing the sum for G by this equivalence reduces the equality to showing that each summand is invariant under precomposition with e. The invariance of the X₀-exponent follows by reindexing the sum of color values via the vertex bijection e, while the invariance of the X₁-exponent follows because the bijection e maps the universal vertex set of G onto that of H, preserving the image of the coloring.

  1. An isomorphism of simple graphs e : G ≃g H induces an equivalence between their coloring types H.Coloring α ≃ G.Coloring α.

    Pulling back along the graph homomorphism e : G → H sends any valid coloring of H to a valid coloring of G. The inverse mapping pulls back along e⁻¹ : H → G. These operations are mutually inverse because precomposing with e and then e⁻¹ (or vice versa) yields the identity coloring by extensionality and simplification.

    lines 1–7

    def third_principal_specialization_congr_coloring_equiv {V W α : Type*}
        (G : SimpleGraph V) (H : SimpleGraph W) (e : G ≃g H) :
        H.Coloring α ≃ G.Coloring α where
      toFun c := c.comp e.toHom
      invFun c := c.comp e.symm.toHom
      left_inv c := by ext; simp
      right_inv c := by ext; simp
  2. To show that the third principal specializations of G and H are equal, it suffices to prove that for every 3-coloring c of H, the polynomial term for c ∘ e on G equals the polynomial term for c on H.

    Unfolding the definition of third_principal_specialization expresses each side as a sum over colorings. By Equiv.sum_comp, reindexing the sum over colorings of G via the equivalence third_principal_specialization_congr_coloring_equiv G H e converts it into a sum over colorings of H. Then Fintype.sum_congr reduces the equality of the two sums to checking that their summands agree for each coloring c of H.

    lines 10–14

    uses third_principal_specialization_congr_coloring_equiv, Equiv.sum_comp, Fintype.sum_congr

    theorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H := by
      unfold third_principal_specialization
      rw [← Equiv.sum_comp (third_principal_specialization_congr_coloring_equiv G H e)]
      apply Fintype.sum_congr
      intro c
  3. The sum of the vertex color values on G for c ∘ e equals the sum of the vertex color values on H for c.

    The vertex color value function v ↦ (c(e(v))).val on G is the composition of the vertex bijection e : V ≃ W with the color value function w ↦ (c(w)).val on H. By Equiv.sum_comp, reindexing the sum over V by the equivalence e preserves the sum of the color values.

    lines 15–18

    uses Equiv.sum_comp

      have h1 : ∑ v : V, ((c.comp e.toHom) v).val = ∑ w : W, (c w).val := by
        have h : (fun v => ((c.comp e.toHom) v).val) = (fun w => (c w).val) ∘ e.toEquiv := rfl
        rw [h]
        exact Equiv.sum_comp e.toEquiv (fun w => (c w).val)
  4. The number of colors used by c ∘ e on G equals the number of colors used by c on H.

    The coloring c ∘ e is the composite of the vertex equivalence e : V ≃ W and c : W → Fin 3. By Finset.image_image, the image of the universal finset of V under c ∘ e is the image under c of the image of V under e. Since e is an equivalence, the image of V under e is the universal finset of W by Finset.image_univ_equiv. Therefore, the sets of colors used by both colorings are identical, so their cardinalities match.

    lines 19–21

    uses Finset.image_image, Finset.image_univ_equiv

      have h2 : (Finset.univ.image (c.comp e.toHom)).card = (Finset.univ.image c).card := by
        have h : (c.comp e.toHom : V → Fin 3) = c ∘ e.toEquiv := rfl
        rw [h, ← Finset.image_image, Finset.image_univ_equiv]
  5. The polynomial summands for c ∘ e and c are equal, completing the proof.

    The summand for c ∘ e is X₀^(∑ v, (c(e(v))).val) * X₁^(|im(c ∘ e)|) and the summand for c is X₀^(∑ w, (c(w)).val) * X₁^(|im(c)|). Substituting the previously established equalities h1 (for the exponent of X₀) and h2 (for the exponent of X₁) shows that the two summands are identical.

    lines 22–26

      show (MvPolynomial.X 0 ^ ∑ v, ((c.comp e.toHom) v).val) *
           MvPolynomial.X 1 ^ (Finset.image (c.comp e.toHom) Finset.univ).card =
           (MvPolynomial.X 0 ^ ∑ w, (c w).val) *
           MvPolynomial.X 1 ^ (Finset.image c Finset.univ).card
      rw [h1, h2]
third_principal_specialization_congr_coloring_equiv
A graph isomorphism between two graphs induces an equivalence between their coloring types (by precomposing with the isomorphism).
Equiv.sum_comp
Summing a function over a finite type is invariant under reindexing the domain by an equivalence: ∑ i, g (e i) = ∑ i, g i.
Fintype.sum_congr
Two sums over a finite type are equal if their summands agree at every element.
Finset.image_image
The image under g of the image of a finite set under f equals the image under the composition g ∘ f.
Finset.image_univ_equiv
The image of the universal finset under an equivalence between finite types is the universal finset of the codomain.

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

def third_principal_specialization_congr_coloring_equiv {V W α : Type*}    (G : SimpleGraph V) (H : SimpleGraph W) (e : G ≃g H) :    H.Coloring α ≃ G.Coloring α where  toFun c := c.comp e.toHom  invFun c := c.comp e.symm.toHom  left_inv c := by ext; simp  right_inv c := by ext; simp/-- Isomorphic graphs have equal third principal specializations. -/theorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H := by  unfold third_principal_specialization  rw [← Equiv.sum_comp (third_principal_specialization_congr_coloring_equiv G H e)]  apply Fintype.sum_congr  intro c  have h1 : ∑ v : V, ((c.comp e.toHom) v).val = ∑ w : W, (c w).val := by    have h : (fun v => ((c.comp e.toHom) v).val) = (fun w => (c w).val) ∘ e.toEquiv := rfl    rw [h]    exact Equiv.sum_comp e.toEquiv (fun w => (c w).val)  have h2 : (Finset.univ.image (c.comp e.toHom)).card = (Finset.univ.image c).card := by    have h : (c.comp e.toHom : V → Fin 3) = c ∘ e.toEquiv := rfl    rw [h, ← Finset.image_image, Finset.image_univ_equiv]  show (MvPolynomial.X 0 ^ ∑ v, ((c.comp e.toHom) v).val) *       MvPolynomial.X 1 ^ (Finset.image (c.comp e.toHom) Finset.univ).card =       (MvPolynomial.X 0 ^ ∑ w, (c w).val) *       MvPolynomial.X 1 ^ (Finset.image c Finset.univ).card  rw [h1, h2]
See it in the graphDiscuss this resultChallenge it