AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_q_coeff_symm

theoremverifiedformalization

Let n ≥ 2 and let G be a finite simple graph with at least 2 vertices that has a proper coloring with n colors. Let d and D be the minimum and maximum degrees of q appearing in ps_n(Z_G(x; t)). Then for every j with d ≤ j ≤ D, the coefficient of q^j in ps_n(Z_G(x; t)) (a polynomial in t) equals the coefficient of q^(d+D-j); that is, for every k the coefficients of t^k q^j and t^k q^(d+D-j) agree.

Statement

theorem simple_graph_t_chromatic_ps_q_coeff_symm {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n)
    (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ)
    (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d)
    (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) :
    ∀ j, d ≤ j → j ≤ D → ∀ k,
      ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j =
        ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff (d + D - j)
Formalizes
arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(2)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Read back from the Lean

Let $V$ be a finite type with at least 2 elements, and let $G$ be a simple graph on $V$. Let $n \ge 2$ be a natural number, and assume $G$ is $n$-colorable. Let $d, D \in \mathbb{N}$. Assume that $d$ is the least element of the set of natural numbers $j$ such that there exists $k \in \mathbb{N}$ for which the $k$-th outer coefficient, evaluated at the $j$-th inner coefficient, of simple_graph_t_chromatic_principal_specialization G n is nonzero. Assume that $D$ is the greatest element of that same set. Then, for all natural numbers $j$ satisfying $d \le j \le D$, and for all $k \in \mathbb{N}$, the $j$-th inner coefficient of the $k$-th outer coefficient of simple_graph_t_chromatic_principal_specialization G n equals its $(d + D - j)$-th inner coefficient.

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 coefficient of t^k q^j in the principal specialization ps_n(Z_G(x; t)) counts the number of proper n-colorings of G using k colors whose vertex colors sum to j. Inverting colors via c(v) ↦ (n - 1) - c(v) yields a bijection between colorings with sum j and those with sum (n - 1)|V| - j. Since the minimum and maximum q-degrees satisfy d + D = (n - 1)|V|, this reflection (n - 1)|V| - j equals d + D - j, proving the coefficient symmetry.

  1. Fix an exponent j with j ≤ D and an exponent k.

    We introduce j, the upper bound j ≤ D (the lower bound d ≤ j is unused), and the exponent k of t.

    line 8

      intro j _ hjD k
  2. The sum of the minimum and maximum q-degrees satisfies d + D = (n - 1)|V|.

    By simple_graph_t_chromatic_ps_min_add_max_q_degree, the sum of the least q-degree d and greatest q-degree D appearing with non-zero coefficient in the principal specialization is equal to (n - 1)|V|.

    line 9

    uses simple_graph_t_chromatic_ps_min_add_max_q_degree

      have h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hD
  3. The coefficient of t^k q^j equals the coefficient of t^k q^(d + D - j).

    Rewriting both sides with simple_graph_t_chromatic_ps_coeff_coeff expresses each coefficient as the number of proper n-colorings using k colors whose vertex colors sum to j and d + D - j, respectively. Then simple_graph_t_chromatic_ps_coloring_count_rev equates the count for sum j with the count for sum (n - 1)|V| - j (where the side condition j ≤ (n - 1)|V| is discharged by linear arithmetic via `omega` since j ≤ D ≤ d + D = (n - 1)|V|). Finally, rewriting with h replaces (n - 1)|V| with d + D, completing the proof.

    line 10

    uses simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coloring_count_rev

      rw [simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coloring_count_rev G n k j (by omega), h]
simple_graph_t_chromatic_ps_min_add_max_q_degree
For a graph G and n colors, the sum of the minimum degree d and maximum degree D of q with non-zero coefficient in the principal specialization is (n - 1)|V|.
simple_graph_t_chromatic_ps_coeff_coeff
The coefficient of t^k q^j in the principal specialization is the number of proper n-colorings of G using exactly k colors whose vertex color values sum to j.
simple_graph_t_chromatic_ps_coloring_count_rev
For j ≤ (n - 1)|V|, the number of proper n-colorings of G using k colors with vertex color sum j equals the number of such colorings with vertex color sum (n - 1)|V| - j.

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_q_coeff_symm {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n)    (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ)    (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d)    (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) :    ∀ j, d ≤ j → j ≤ D → ∀ k,      ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j =        ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff (d + D - j) := by  intro j _ hjD k  have h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hD  rw [simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coloring_count_rev G n k j (by omega), h]
See it in the graphDiscuss this resultChallenge it