AFTD Auto-Formalizing Theoretical Domains

third_principal_specialization_card_eq

theoremverifiedformalization

The third principal specialization of any finite tree on at least one vertex uniquely determines its number of vertices.

Statement

theorem third_principal_specialization_card_eq {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂] (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj] (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (heq : third_principal_specialization T₁ = third_principal_specialization T₂) : Fintype.card V₁ = Fintype.card V₂
Formalizes
arXiv:2610.31785 Proposition 3.3
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For any two finite types $V₁$ and $V₂$ with decidable equality, and any simple graphs $T₁$ on $V₁$ and $T₂$ on $V₂$ with decidable adjacency, if both $T₁$ and $T₂$ are trees, and their third principal specializations are equal (third_principal_specialization T₁ = third_principal_specialization T₂), then the number of vertices of $V₁$ is equal to the number of vertices of $V₂$ (Fintype.card V₁ = Fintype.card V₂).

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

Evaluating the third principal specialization of a graph at (1, 1) counts its proper 3-colorings. For any tree on vertex set V, the number of 3-colorings is 3 * 2 ^ (|V| - 1). Two trees with identical third principal specializations must have identical evaluations at (1, 1), equating 3 * 2 ^ (|V₁| - 1) and 3 * 2 ^ (|V₂| - 1). Canceling 3 and applying injectivity of powers of 2 gives |V₁| - 1 = |V₂| - 1, which implies |V₁| = |V₂| because trees are nonempty.

  1. Evaluating the third principal specialization of each tree at (1, 1) yields 3 * 2 ^ (|V| - 1).

    Evaluating the third principal specialization at all ones counts the proper 3-colorings of a graph (third_principal_specialization_eval_one). Because T₁ and T₂ are trees, each has 3 * 2 ^ (|V| - 1) proper 3-colorings (is_tree_card_coloring_three). Rewriting with this formula expresses the evaluation at ones for both trees in terms of their respective vertex counts.

    lines 3–6

    uses third_principal_specialization_eval_one, is_tree_card_coloring_three

      have h₁ := third_principal_specialization_eval_one T₁
      have h₂ := third_principal_specialization_eval_one T₂
      rw [is_tree_card_coloring_three T₁ hT₁] at h₁
      rw [is_tree_card_coloring_three T₂ hT₂] at h₂
  2. 3 * 2 ^ (|V₁| - 1) = 3 * 2 ^ (|V₂| - 1) as an equality in ℕ.

    Because the third principal specializations of T₁ and T₂ are assumed equal (heq), their evaluations at (1, 1) are equal. Substituting the closed forms from the previous step yields 3 * 2 ^ (|V₁| - 1) = 3 * 2 ^ (|V₂| - 1) in ℤ, which is then cast to an equality of natural numbers using exact_mod_cast.

    lines 7–12

      have hpoly : MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₁)
          = MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₂) := by
        rw [heq]
      rw [h₁, h₂] at hpoly
      have hn : 3 * 2 ^ (Fintype.card V₁ - 1) = 3 * 2 ^ (Fintype.card V₂ - 1) := by
        exact_mod_cast hpoly
  3. |V₁| - 1 = |V₂| - 1

    Canceling the common factor of 3 (via Nat.mul_left_cancel, since 3 > 0) leaves 2 ^ (|V₁| - 1) = 2 ^ (|V₂| - 1). Since the base satisfies 2 ≥ 2, base-2 exponentiation is injective on ℕ (Nat.pow_right_injective), giving |V₁| - 1 = |V₂| - 1.

    lines 13–16

    uses Nat.mul_left_cancel, Nat.pow_right_injective

      have h2 : 2 ^ (Fintype.card V₁ - 1) = 2 ^ (Fintype.card V₂ - 1) :=
        Nat.mul_left_cancel (by norm_num) hn
      have hab : Fintype.card V₁ - 1 = Fintype.card V₂ - 1 :=
        Nat.pow_right_injective (by norm_num : 2 ≤ 2) h2
  4. |V₁| = |V₂|

    Because trees are connected, their vertex sets are nonempty. A finite type is nonempty if and only if its cardinality is strictly positive (Fintype.card_pos_iff.mpr), which establishes |V₁| > 0 and |V₂| > 0. From |V₁| - 1 = |V₂| - 1 together with positivity of both cardinalities, linear integer arithmetic (omega) concludes that |V₁| = |V₂|.

    lines 17–19

    uses Fintype.card_pos_iff.mpr

      have n1 : 0 < Fintype.card V₁ := Fintype.card_pos_iff.mpr hT₁.connected.nonempty
      have n2 : 0 < Fintype.card V₂ := Fintype.card_pos_iff.mpr hT₂.connected.nonempty
      omega
third_principal_specialization_eval_one
Evaluating the third principal specialization of a graph with all variables set to 1 equals the number of proper 3-colorings of the graph.
is_tree_card_coloring_three
A finite tree on vertex set V has 3 * 2 ^ (|V| - 1) proper 3-colorings.
Nat.mul_left_cancel
If n > 0 and n * m = n * k in ℕ, then m = k.
Nat.pow_right_injective
For any base a ≥ 2, the power map x ↦ a ^ x is an injective function on ℕ.
Fintype.card_pos_iff.mpr
If a type is nonempty, its cardinality as a finite type is strictly positive.

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

/-- The third principal specialization of any tree determines its number of vertices. -/theorem third_principal_specialization_card_eq {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂] (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj] (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (heq : third_principal_specialization T₁ = third_principal_specialization T₂) : Fintype.card V₁ = Fintype.card V₂ := by  have h₁ := third_principal_specialization_eval_one T₁  have h₂ := third_principal_specialization_eval_one T₂  rw [is_tree_card_coloring_three T₁ hT₁] at h₁  rw [is_tree_card_coloring_three T₂ hT₂] at h₂  have hpoly : MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₁)      = MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₂) := by    rw [heq]  rw [h₁, h₂] at hpoly  have hn : 3 * 2 ^ (Fintype.card V₁ - 1) = 3 * 2 ^ (Fintype.card V₂ - 1) := by    exact_mod_cast hpoly  have h2 : 2 ^ (Fintype.card V₁ - 1) = 2 ^ (Fintype.card V₂ - 1) :=    Nat.mul_left_cancel (by norm_num) hn  have hab : Fintype.card V₁ - 1 = Fintype.card V₂ - 1 :=    Nat.pow_right_injective (by norm_num : 2 ≤ 2) h2  have n1 : 0 < Fintype.card V₁ := Fintype.card_pos_iff.mpr hT₁.connected.nonempty  have n2 : 0 < Fintype.card V₂ := Fintype.card_pos_iff.mpr hT₂.connected.nonempty  omega
See it in the graphDiscuss this resultChallenge it