AFTD Auto-Formalizing Theoretical Domains

hn_spectrum

theoremverifiedformalization

For every integer n ≥ 2, there exist real numbers l1 > l2 > l3 such that 1/2 < l1 < 2n, 0 < l2 < 1/2, -n < l3 < 0, hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3), and the characteristic polynomial of the real adjacency matrix of the competitor graph hn_graph n equals Polynomial.X ^ (3 * n - 4) * (Polynomial.X + Polynomial.C (n : ℝ)) * hn_poly n.

Statement

open scoped Classical in
theorem hn_spectrum (n : ℕ) (hle : 2 ≤ n) :
    ∃ l1 l2 l3 : ℝ,
      1 / 2 < l1 ∧ l1 < 2 * (n : ℝ) ∧
      0 < l2 ∧ l2 < 1 / 2 ∧
      -(n : ℝ) < l3 ∧ l3 < 0 ∧
      l2 < l1 ∧ l3 < l2 ∧
      hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3) ∧
      (SimpleGraph.adjMatrix ℝ (hn_graph n)).charpoly =
        Polynomial.X ^ (3 * n - 4) * (Polynomial.X + Polynomial.C (n : ℝ)) * hn_poly n
Formalizes
arXiv:2610.18636 Theorem 4
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • hn_graphFor each natural number n, hn_graph n is the simple graph on the vertex set Fin (3 * n) defined via SimpleGraph.fromRel from the relation…
  • hn_polyFor every natural number n, hn_poly n is the cubic polynomial q_n(x) = x^3 - n*x^2 - (2*n^2 - n - 1)*x + (n^2 - n) over the real numbers.
  • hn_quotient_matrixFor every natural number n, hn_quotient_matrix n is the 4 by 4 real matrix whose row 0 is ![0, (n : ℝ), (n : ℝ), 1], row 1 is ![(n : ℝ) -…
  • hn_quotient_matrix_charpolyFor every natural number n, the characteristic polynomial of the quotient matrix hn_quotient_matrix n equals (Polynomial.X + Polynomial.C…
  • hn_poly_three_rootsFor every integer n ≥ 2, the cubic polynomial hn_poly n has three real roots l1 > l2 > l3 satisfying 1/2 < l1 < 2n, 0 < l2 < 1/2, and -n <…

Read back from the Lean

For every natural number $n \ge 2$, there exist real numbers $l_1, l_2, l_3$ such that: 1. $1/2 < l_1 < 2n$, 2. $0 < l_2 < 1/2$, 3. $-n < l_3 < 0$, 4. $l_2 < l_1$, 5. $l_3 < l_2$, 6. $\text{hn\_poly}(n) = (X - l_1)(X - l_2)(X - l_3)$ as polynomials in $\mathbb{R}[X]$, and 7. the characteristic polynomial of the adjacency matrix over $\mathbb{R}$ of the graph $\text{hn\_graph}(n)$ equals $X^{3n - 4} \cdot (X + n) \cdot \text{hn\_poly}(n)$ in $\mathbb{R}[X]$.

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 spectrum of the competitor graph H_n is determined by viewing it as an equitable partition into four cells of sizes n - 1, n, n, and 1. The adjacency matrix factors as A = U * M * U^T, where U is the vertex-cell indicator matrix and M is the cell adjacency pattern. By the cyclic identity for characteristic polynomials of rectangular matrix products, charpoly(A) = X^(3n - 4) * charpoly(M * U^T * U) = X^(3n - 4) * charpoly(M * D), which reduces the problem to the 4x4 quotient matrix whose characteristic polynomial is (X + n) * hn_poly n. Finally, combining this factorization with the root separation theorem hn_poly_three_roots yields the three extremal eigenvalues and their bounding intervals.

  1. A vertex v of Fin (3 * n) belongs to cell 0 if and only if v.val < n - 1. automation

    Unfolding the cell assignment definition hn_spectrum_cell and simplifying the nested if-then-else conditions.

    lines 20–21

      unfold hn_spectrum_cell
      split_ifs with h1 h2 h3 <;> simp_all
  2. A vertex v belongs to cell 1 if and only if n - 1 ≤ v.val and v.val < 2 * n - 1. automation

    Unfolding hn_spectrum_cell, case splitting on the conditions, and resolving arithmetic bounds using linear integer arithmetic.

    lines 25–26

      unfold hn_spectrum_cell
      split_ifs with h1 h2 h3 <;> simp_all <;> omega
  3. A vertex v belongs to cell 2 if and only if 2 * n - 1 ≤ v.val and v.val < 3 * n - 1. automation

    Unfolding hn_spectrum_cell, splitting on the conditional branches, and solving the resulting bounds by linear arithmetic.

    lines 30–31

      unfold hn_spectrum_cell
      split_ifs with h1 h2 h3 <;> simp_all <;> omega
  4. A vertex v belongs to cell 3 if and only if v.val = 3 * n - 1. automation

    Unfolding hn_spectrum_cell, analyzing the final branch where v does not lie in cells 0, 1, or 2, and closing via linear integer arithmetic.

    lines 35–36

      unfold hn_spectrum_cell
      split_ifs with h1 h2 h3 <;> simp_all <;> omega
  5. The defining relation of hn_graph holds between u and v if and only if u is in cell 0 and v is not, or u is in cell 1 and v is in cell 2.

    First, v is not in cell 0 iff v.val ≥ n - 1 by hn_spectrum_cell_eq_zero_iff. Then both directions of the logical equivalence follow by rewriting with the cell characterizations for cells 0, 1, and 2.

    lines 43–54

    uses hn_spectrum_cell_eq_zero_iff, hn_spectrum_cell_eq_one_iff, hn_spectrum_cell_eq_two_iff

      have hv0 : hn_spectrum_cell n v ≠ 0 ↔ v.val ≥ n - 1 := by
        rw [Ne, hn_spectrum_cell_eq_zero_iff]; omega
      constructor
      · rintro (⟨h1, h2⟩ | ⟨h1, h2, h3, h4⟩)
        · exact Or.inl ⟨(hn_spectrum_cell_eq_zero_iff u).mpr h1, hv0.mpr h2⟩
        · exact Or.inr ⟨(hn_spectrum_cell_eq_one_iff u).mpr ⟨h1, h2⟩,
            (hn_spectrum_cell_eq_two_iff v).mpr ⟨h3, h4⟩⟩
      · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)
        · exact Or.inl ⟨(hn_spectrum_cell_eq_zero_iff u).mp h1, hv0.mp h2⟩
        · obtain ⟨a, b⟩ := (hn_spectrum_cell_eq_one_iff u).mp h1
          obtain ⟨c, d⟩ := (hn_spectrum_cell_eq_two_iff v).mp h2
          exact Or.inr ⟨a, b, c, d⟩
  6. The entry hn_spectrum_M a b equals 1 if and only if (a = 0 and b ≠ 0), (a = 1 and b = 2), or their symmetric counterparts. automation

    Exhaustive case analysis on all 16 index pairs in Fin 4, evaluating the explicit 4x4 matrix definition.

    line 59

      fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]
  7. All diagonal entries of hn_spectrum_M are zero. automation

    Exhaustive evaluation on all four elements of Fin 4.

    line 62

      fin_cases a <;> simp [hn_spectrum_M]
  8. Every entry of hn_spectrum_M is either 0 or 1. automation

    Exhaustive case analysis across all 16 index pairs in Fin 4.

    line 66

      fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]
  9. Vertices v and w are adjacent in hn_graph n if and only if hn_spectrum_M (cell v) (cell w) = 1.

    In the forward direction, adjacency implies the relation holds in one direction, which gives M = 1 by matching with hn_spectrum_rel_iff and hn_spectrum_M_eq_one_iff. In the reverse direction, M = 1 implies the cells are distinct because diagonal entries of M are 0 (hn_spectrum_M_diag and zero_ne_one), so v ≠ w, and the symmetric relation holds.

    lines 70–92

    uses hn_spectrum_rel_iff, hn_spectrum_M_eq_one_iff, hn_spectrum_M_diag, zero_ne_one

      have h1 := hn_spectrum_rel_iff n v w
      have h2 := hn_spectrum_rel_iff n w v
      have hM := hn_spectrum_M_eq_one_iff (hn_spectrum_cell n v) (hn_spectrum_cell n w)
      simp only [hn_graph, SimpleGraph.fromRel]
      constructor
      · rintro ⟨-, h | h⟩
        · rcases h1.mp h with ⟨a, b⟩ | ⟨a, b⟩
          · exact hM.mpr (Or.inl ⟨a, b⟩)
          · exact hM.mpr (Or.inr (Or.inl ⟨a, b⟩))
        · rcases h2.mp h with ⟨a, b⟩ | ⟨a, b⟩
          · exact hM.mpr (Or.inr (Or.inr (Or.inl ⟨a, b⟩)))
          · exact hM.mpr (Or.inr (Or.inr (Or.inr ⟨a, b⟩)))
      · intro hm
        have hcne : hn_spectrum_cell n v ≠ hn_spectrum_cell n w := by
          intro hab
          rw [hab, hn_spectrum_M_diag] at hm
          exact zero_ne_one hm
        refine ⟨fun he => hcne (by rw [he]), ?_⟩
        rcases hM.mp hm with ⟨a, b⟩ | ⟨a, b⟩ | ⟨a, b⟩ | ⟨a, b⟩
        · exact Or.inl (h1.mpr (Or.inl ⟨a, b⟩))
        · exact Or.inl (h1.mpr (Or.inr ⟨a, b⟩))
        · exact Or.inr (h2.mpr (Or.inl ⟨a, b⟩))
        · exact Or.inr (h2.mpr (Or.inr ⟨a, b⟩))
  10. For every vertex v and cell k, (hn_spectrum_U n * hn_spectrum_M) v k = hn_spectrum_M (cell v) k.

    Expanding the matrix product via Matrix.mul_apply and collapsing the sum using Finset.sum_eq_single, since row v of U has a single 1 at cell v.

    lines 96–99

    uses Matrix.mul_apply, Finset.sum_eq_single

      rw [Matrix.mul_apply, Finset.sum_eq_single (hn_spectrum_cell n v)]
      · simp [hn_spectrum_U]
      · intro l _ hl; simp [hn_spectrum_U, Ne.symm hl]
      · intro h; exact absurd (Finset.mem_univ _) h
  11. For all vertices v and w, (hn_spectrum_U n * hn_spectrum_M * (hn_spectrum_U n).transpose) v w = hn_spectrum_M (cell v) (cell w).

    Expanding the product by Matrix.mul_apply, applying the previous result hn_spectrum_U_M_apply, and summing over the indicator column for w via Finset.sum_eq_single.

    lines 104–109

    uses Matrix.mul_apply, hn_spectrum_U_M_apply, Finset.sum_eq_single

      rw [Matrix.mul_apply]
      simp only [hn_spectrum_U_M_apply, Matrix.transpose_apply]
      rw [Finset.sum_eq_single (hn_spectrum_cell n w)]
      · simp [hn_spectrum_U]
      · intro l _ hl; simp [hn_spectrum_U, Ne.symm hl]
      · intro h; exact absurd (Finset.mem_univ _) h
  12. The adjacency matrix of hn_graph n equals hn_spectrum_U n * hn_spectrum_M * (hn_spectrum_U n).transpose.

    By entrywise equality, rewriting using hn_spectrum_U_M_U_transpose_apply and checking whether v and w are adjacent via hn_spectrum_adj_iff_M, noting that non-adjacent pairs yield 0 since entries of M are binary (hn_spectrum_M_eq_zero_or_one).

    lines 115–126

    uses hn_spectrum_U_M_U_transpose_apply, hn_spectrum_adj_iff_M, hn_spectrum_M_eq_zero_or_one

      ext v w
      rw [hn_spectrum_U_M_U_transpose_apply]
      simp only [SimpleGraph.adjMatrix, Matrix.of_apply]
      by_cases h : (hn_graph n).Adj v w
      · rw [if_pos h]
        exact ((hn_spectrum_adj_iff_M n v w).mp h).symm
      · rw [if_neg h]
        have hne : hn_spectrum_M (hn_spectrum_cell n v) (hn_spectrum_cell n w) ≠ 1 :=
          fun hc => h ((hn_spectrum_adj_iff_M n v w).mpr hc)
        rcases hn_spectrum_M_eq_zero_or_one (hn_spectrum_cell n v) (hn_spectrum_cell n w) with h0 | h1
        · exact h0.symm
        · exact absurd h1 hne
  13. The number of elements in Fin m with value strictly less than a is a, when a ≤ m.

    Constructing an explicit equivalence between {v : Fin m // v.val < a} and Fin a, and transferring cardinality via Fintype.card_congr.

    lines 130–135

    uses Fintype.card_congr

      have e : {v : Fin m // v.val < a} ≃ Fin a :=
        { toFun := fun x => ⟨x.1.val, x.2⟩
          invFun := fun y => ⟨⟨y.val, lt_of_lt_of_le y.isLt h⟩, y.isLt⟩
          left_inv := by intro x; simp
          right_inv := by intro y; simp }
      rw [Fintype.card_congr e]; simp
  14. The number of elements in Fin m with value in [a, b) is b - a, when a ≤ b ≤ m.

    Constructing an explicit equivalence to Fin (b - a) by shifting values by a, and applying Fintype.card_congr.

    lines 139–149

    uses Fintype.card_congr

      have e : {v : Fin m // a ≤ v.val ∧ v.val < b} ≃ Fin (b - a) :=
        { toFun := fun x => ⟨x.1.val - a, by have := x.2.1; have := x.2.2; omega⟩
          invFun := fun y => ⟨⟨y.val + a, by have := y.isLt; omega⟩, by
            have := y.isLt; show a ≤ y.val + a ∧ y.val + a < b; constructor <;> omega⟩
          left_inv := by
            intro x; apply Subtype.ext; apply Fin.ext; simp only
            exact Nat.sub_add_cancel x.2.1
          right_inv := by
            intro y; apply Fin.ext; simp only
            exact Nat.add_sub_cancel_right y.val a }
      rw [Fintype.card_congr e]; simp
  15. The number of elements in Fin m equal to a is 1, when a < m.

    Constructing an explicit equivalence between {v : Fin m // v.val = a} and Fin 1, and applying Fintype.card_congr.

    lines 153–158

    uses Fintype.card_congr

      have e : {v : Fin m // v.val = a} ≃ Fin 1 :=
        { toFun := fun _ => ⟨0, by omega⟩
          invFun := fun _ => ⟨⟨a, h⟩, rfl⟩
          left_inv := by intro x; apply Subtype.ext; apply Fin.ext; exact x.2.symm
          right_inv := by intro y; apply Fin.ext; simp }
      rw [Fintype.card_congr e]; simp
  16. Cell 0 contains exactly n - 1 vertices.

    Rewriting cell 0 membership as v.val < n - 1 using hn_spectrum_cell_eq_zero_iff, and computing the cardinality via Fintype.card_congr and hn_spectrum_fin_card_val_lt.

    lines 162–169

    uses hn_spectrum_cell_eq_zero_iff, Fintype.card_congr, hn_spectrum_fin_card_val_lt

      rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 0)]
      have e : {v : Fin (3*n) // hn_spectrum_cell n v = 0} ≃ {v : Fin (3*n) // v.val < n - 1} :=
        { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_zero_iff x.1).mp x.2⟩
          invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_zero_iff x.1).mpr x.2⟩
          left_inv := by intro x; simp
          right_inv := by intro x; simp }
      rw [Fintype.card_congr e]
      exact hn_spectrum_fin_card_val_lt (by omega)
  17. Cell 1 contains exactly n vertices.

    Rewriting cell 1 membership as n - 1 ≤ v.val < 2n - 1 via hn_spectrum_cell_eq_one_iff, and computing the interval cardinality via Fintype.card_congr and hn_spectrum_fin_card_val_between.

    lines 173–182

    uses hn_spectrum_cell_eq_one_iff, Fintype.card_congr, hn_spectrum_fin_card_val_between

      rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 1)]
      have e : {v : Fin (3*n) // hn_spectrum_cell n v = 1} ≃
          {v : Fin (3*n) // n - 1 ≤ v.val ∧ v.val < 2 * n - 1} :=
        { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_one_iff x.1).mp x.2⟩
          invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_one_iff x.1).mpr x.2⟩
          left_inv := by intro x; simp
          right_inv := by intro x; simp }
      rw [Fintype.card_congr e]
      rw [hn_spectrum_fin_card_val_between (by omega) (by omega)]
      omega
  18. Cell 2 contains exactly n vertices.

    Rewriting cell 2 membership as 2n - 1 ≤ v.val < 3n - 1 via hn_spectrum_cell_eq_two_iff, and computing the interval cardinality via Fintype.card_congr and hn_spectrum_fin_card_val_between.

    lines 186–195

    uses hn_spectrum_cell_eq_two_iff, Fintype.card_congr, hn_spectrum_fin_card_val_between

      rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 2)]
      have e : {v : Fin (3*n) // hn_spectrum_cell n v = 2} ≃
          {v : Fin (3*n) // 2 * n - 1 ≤ v.val ∧ v.val < 3 * n - 1} :=
        { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_two_iff x.1).mp x.2⟩
          invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_two_iff x.1).mpr x.2⟩
          left_inv := by intro x; simp
          right_inv := by intro x; simp }
      rw [Fintype.card_congr e]
      rw [hn_spectrum_fin_card_val_between (by omega) (by omega)]
      omega
  19. Cell 3 contains exactly 1 vertex when n ≥ 1.

    Rewriting cell 3 membership as v.val = 3n - 1 via hn_spectrum_cell_eq_three_iff, and applying Fintype.card_congr and hn_spectrum_fin_card_val_eq.

    lines 199–206

    uses hn_spectrum_cell_eq_three_iff, Fintype.card_congr, hn_spectrum_fin_card_val_eq

      rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 3)]
      have e : {v : Fin (3*n) // hn_spectrum_cell n v = 3} ≃ {v : Fin (3*n) // v.val = 3 * n - 1} :=
        { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_three_iff x.1).mp x.2⟩
          invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_three_iff x.1).mpr x.2⟩
          left_inv := by intro x; simp
          right_inv := by intro x; simp }
      rw [Fintype.card_congr e]
      exact hn_spectrum_fin_card_val_eq (by omega)
  20. For all k in Fin 4 and n ≥ 1, cell k has size hn_spectrum_cell_size n k.

    Case split on k in Fin 4, invoking the individual cell cardinality lemmas hn_spectrum_card_cell_zero, hn_spectrum_card_cell_one, hn_spectrum_card_cell_two, and hn_spectrum_card_cell_three.

    lines 211–215

    uses hn_spectrum_card_cell_zero, hn_spectrum_card_cell_one, hn_spectrum_card_cell_two, hn_spectrum_card_cell_three

      fin_cases k
      · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_zero n
      · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_one n
      · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_two n
      · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_three n hn
  21. The sum over all vertices of indicator(cell v = k) * indicator(cell v = l) equals the size of cell k if k = l, and 0 otherwise.

    If k = l, the product of indicators simplifies to indicator(cell v = k), which sums to the cardinality of cell k. If k ≠ l, no vertex can belong to both cells simultaneously, so every term is 0.

    lines 222–233

      by_cases hkl : k = l
      · subst hkl
        rw [if_pos rfl, ← Finset.sum_boole (fun v => hn_spectrum_cell n v = k) Finset.univ]
        apply Finset.sum_congr rfl
        intro v _
        by_cases h : hn_spectrum_cell n v = k <;> simp [h]
      · rw [if_neg hkl]
        apply Finset.sum_eq_zero
        intro v _
        by_cases h : hn_spectrum_cell n v = k
        · simp [h, hkl]
        · simp [h]
  22. (hn_spectrum_U n).transpose * hn_spectrum_U n equals the diagonal matrix hn_spectrum_D n of cell sizes.

    By matrix extensionality, expanding the product with Matrix.mul_apply, evaluating the resulting sum using hn_spectrum_sum_ite_ite, and substituting cell sizes via hn_spectrum_card_cell.

    lines 237–244

    uses Matrix.mul_apply, hn_spectrum_sum_ite_ite, hn_spectrum_card_cell

      ext k l
      rw [Matrix.mul_apply]
      simp only [Matrix.transpose_apply, hn_spectrum_U, hn_spectrum_D, Matrix.diagonal, Matrix.of_apply]
      rw [hn_spectrum_sum_ite_ite]
      by_cases hkl : k = l
      · rw [if_pos hkl, if_pos hkl]
        rw [hn_spectrum_card_cell n hn k]
      · rw [if_neg hkl, if_neg hkl]
  23. hn_spectrum_M * hn_spectrum_D n equals the quotient matrix hn_quotient_matrix n.

    By matrix extensionality, evaluating all 16 entries of the 4x4 matrix product and simplifying algebraic expressions over the real numbers.

    lines 248–252

      ext i j
      fin_cases i <;> fin_cases j <;>
        simp [hn_spectrum_M, hn_spectrum_D, hn_spectrum_cell_size, hn_quotient_matrix,
          Matrix.diagonal, Matrix.mul_apply]
      all_goals (rw [Nat.cast_sub hn]; ring)
  24. The characteristic polynomial of the adjacency matrix of hn_graph n is X^(3n - 4) * (X + n) * hn_poly n.

    Factoring the adjacency matrix as A = U * (M * U^T) via hn_spectrum_adjMatrix_eq. By Matrix.charpoly_mul_comm_of_le, charpoly(U * (M * U^T)) = X^(3n - 4) * charpoly((M * U^T) * U). By associativity and hn_spectrum_U_transpose_mul_U, (M * U^T) * U = M * D, which equals hn_quotient_matrix n by hn_spectrum_M_mul_D. Finally, hn_quotient_matrix_charpoly computes the characteristic polynomial of the quotient matrix as (X + n) * hn_poly n.

    lines 258–269

    uses hn_spectrum_adjMatrix_eq, Matrix.charpoly_mul_comm_of_le, hn_spectrum_U_transpose_mul_U, hn_spectrum_M_mul_D, hn_quotient_matrix_charpoly

      have hn1 : 1 ≤ n := by omega
      have hcard : Fintype.card (Fin 4) ≤ Fintype.card (Fin (3*n)) := by simp; omega
      have hA : SimpleGraph.adjMatrix ℝ (hn_graph n)
          = hn_spectrum_U n * (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) := by
        rw [hn_spectrum_adjMatrix_eq n hle, Matrix.mul_assoc]
      have hBU : (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) * hn_spectrum_U n
          = hn_quotient_matrix n := by
        rw [Matrix.mul_assoc, hn_spectrum_U_transpose_mul_U n hn1, hn_spectrum_M_mul_D n hn1]
      rw [hA, Matrix.charpoly_mul_comm_of_le (hn_spectrum_U n)
        (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) hcard, hBU, hn_quotient_matrix_charpoly]
      simp only [Fintype.card_fin]
      rw [mul_assoc]
  25. There exist three separated real roots l1 > l2 > l3 factoring hn_poly n, and the characteristic polynomial of hn_graph n factors as stated.

    Obtaining the three ordered roots of hn_poly n and their interval bounds from hn_poly_three_roots, and pairing them with the characteristic polynomial formula established in hn_spectrum_adj_charpoly.

    lines 282–283

    uses hn_poly_three_roots, hn_spectrum_adj_charpoly

      obtain ⟨l1, l2, l3, h1, h2, h3, h4, h5, h6, h7, h8, h9⟩ := hn_poly_three_roots n hle
      exact ⟨l1, l2, l3, h1, h2, h3, h4, h5, h6, h7, h8, h9, hn_spectrum_adj_charpoly n hle⟩
hn_spectrum_adjMatrix_eq
The adjacency matrix of hn_graph n factors as U * M * U^T, where U is the vertex-to-cell indicator matrix and M is the cell adjacency pattern.
hn_spectrum_adj_charpoly
The characteristic polynomial of the adjacency matrix of hn_graph n equals X^(3n - 4) * (X + n) * hn_poly n.
hn_spectrum_adj_iff_M
Two vertices v and w are adjacent in hn_graph n if and only if M has a 1 between their respective cells.
hn_spectrum_card_cell_zero
Cell 0 contains exactly n - 1 vertices.
hn_spectrum_card_cell_one
Cell 1 contains exactly n vertices.
hn_spectrum_card_cell_two
Cell 2 contains exactly n vertices.
hn_spectrum_card_cell_three
Cell 3 contains exactly 1 vertex when n ≥ 1.
hn_spectrum_card_cell
For every cell index k in Fin 4 and n ≥ 1, cell k contains exactly hn_spectrum_cell_size n k vertices.
hn_spectrum_cell_eq_zero_iff
A vertex v belongs to cell 0 if and only if its index is strictly less than n - 1.
hn_spectrum_cell_eq_one_iff
A vertex v belongs to cell 1 if and only if its index lies in [n - 1, 2n - 1).
hn_spectrum_cell_eq_two_iff
A vertex v belongs to cell 2 if and only if its index lies in [2n - 1, 3n - 1).
hn_spectrum_cell_eq_three_iff
A vertex v belongs to cell 3 if and only if its index equals 3n - 1.
hn_spectrum_fin_card_val_lt
The number of elements in Fin m strictly less than a is a, provided a ≤ m.
hn_spectrum_fin_card_val_between
The number of elements in Fin m with value in [a, b) is b - a, provided a ≤ b ≤ m.
hn_spectrum_fin_card_val_eq
The number of elements in Fin m with value equal to a is 1, provided a < m.
hn_spectrum_M_eq_one_iff
The entry M a b equals 1 if and only if one index is 0 and the other is nonzero, or one index is 1 and the other is 2.
hn_spectrum_M_diag
All diagonal entries of M are 0.
hn_spectrum_M_eq_zero_or_one
Every entry of M is either 0 or 1.
hn_spectrum_M_mul_D
The product M * D of the pattern matrix M and diagonal cell-size matrix D equals the quotient matrix hn_quotient_matrix n.
hn_poly_three_roots
For n ≥ 2, hn_poly n has three distinct real roots l1 > l2 > l3 lying in (1/2, 2n), (0, 1/2), and (-n, 0) respectively.
hn_quotient_matrix_charpoly
The characteristic polynomial of the quotient matrix hn_quotient_matrix n equals (X + n) * hn_poly n.
hn_spectrum_rel_iff
The graph relation holds between u and v if and only if u is in cell 0 and v is not, or u is in cell 1 and v is in cell 2.
hn_spectrum_sum_ite_ite
The sum over v of indicator(cell(v) = k) * indicator(cell(v) = l) equals the cell size if k = l, and 0 otherwise.
hn_spectrum_U_M_apply
The product (U * M) v k equals M(cell(v), k).
hn_spectrum_U_M_U_transpose_apply
The product (U * M * U^T) v w equals M(cell(v), cell(w)).
hn_spectrum_U_transpose_mul_U
U^T * U equals the diagonal matrix D of cell sizes.
Fintype.card_congr
Two finite types in bijection have the same cardinality.
Matrix.charpoly_mul_comm_of_le
For rectangular matrices A (m x n) and B (n x m) with n ≤ m, the characteristic polynomial of AB is X^(m - n) times the characteristic polynomial of BA.
Matrix.mul_apply
Entrywise formula for matrix multiplication: (M * N) i k = ∑ j, M i j * N j k.
Finset.sum_eq_single
A sum over a finite set with at most one nonzero term equals that single term.
zero_ne_one
In any type with distinct zero and one, 0 ≠ 1.

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

open scoped Classical indef hn_spectrum_cell (n : ℕ) (v : Fin (3 * n)) : Fin 4 :=  if v.val < n - 1 then 0  else if v.val < 2 * n - 1 then 1  else if v.val < 3 * n - 1 then 2  else 3def hn_spectrum_cell_size (n : ℕ) (k : Fin 4) : ℕ := ![n - 1, n, n, 1] knoncomputable def hn_spectrum_U (n : ℕ) : Matrix (Fin (3*n)) (Fin 4) ℝ :=  fun v k => if hn_spectrum_cell n v = k then 1 else 0noncomputable def hn_spectrum_D (n : ℕ) : Matrix (Fin 4) (Fin 4) ℝ :=  Matrix.diagonal (fun k => (hn_spectrum_cell_size n k : ℝ))def hn_spectrum_M : Matrix (Fin 4) (Fin 4) ℝ := !![0,1,1,1; 1,0,1,0; 1,1,0,0; 1,0,0,0]lemma hn_spectrum_cell_eq_zero_iff {n : ℕ} (v : Fin (3 * n)) :    hn_spectrum_cell n v = 0 ↔ v.val < n - 1 := by  unfold hn_spectrum_cell  split_ifs with h1 h2 h3 <;> simp_alllemma hn_spectrum_cell_eq_one_iff {n : ℕ} (v : Fin (3 * n)) :    hn_spectrum_cell n v = 1 ↔ n - 1 ≤ v.val ∧ v.val < 2 * n - 1 := by  unfold hn_spectrum_cell  split_ifs with h1 h2 h3 <;> simp_all <;> omegalemma hn_spectrum_cell_eq_two_iff {n : ℕ} (v : Fin (3 * n)) :    hn_spectrum_cell n v = 2 ↔ 2 * n - 1 ≤ v.val ∧ v.val < 3 * n - 1 := by  unfold hn_spectrum_cell  split_ifs with h1 h2 h3 <;> simp_all <;> omegalemma hn_spectrum_cell_eq_three_iff {n : ℕ} (v : Fin (3 * n)) :    hn_spectrum_cell n v = 3 ↔ v.val = 3 * n - 1 := by  unfold hn_spectrum_cell  split_ifs with h1 h2 h3 <;> simp_all <;> omegalemma hn_spectrum_rel_iff (n : ℕ) (u v : Fin (3 * n)) :    ((u.val < n - 1 ∧ v.val ≥ n - 1) ∨      (n - 1 ≤ u.val ∧ u.val < 2 * n - 1 ∧ 2 * n - 1 ≤ v.val ∧ v.val < 3 * n - 1))    ↔ (hn_spectrum_cell n u = 0 ∧ hn_spectrum_cell n v ≠ 0) ∨      (hn_spectrum_cell n u = 1 ∧ hn_spectrum_cell n v = 2) := by  have hv0 : hn_spectrum_cell n v ≠ 0 ↔ v.val ≥ n - 1 := by    rw [Ne, hn_spectrum_cell_eq_zero_iff]; omega  constructor  · rintro (⟨h1, h2⟩ | ⟨h1, h2, h3, h4⟩)    · exact Or.inl ⟨(hn_spectrum_cell_eq_zero_iff u).mpr h1, hv0.mpr h2⟩    · exact Or.inr ⟨(hn_spectrum_cell_eq_one_iff u).mpr ⟨h1, h2⟩,        (hn_spectrum_cell_eq_two_iff v).mpr ⟨h3, h4⟩⟩  · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)    · exact Or.inl ⟨(hn_spectrum_cell_eq_zero_iff u).mp h1, hv0.mp h2⟩    · obtain ⟨a, b⟩ := (hn_spectrum_cell_eq_one_iff u).mp h1      obtain ⟨c, d⟩ := (hn_spectrum_cell_eq_two_iff v).mp h2      exact Or.inr ⟨a, b, c, d⟩lemma hn_spectrum_M_eq_one_iff (a b : Fin 4) :    hn_spectrum_M a b = 1 ↔      (a = 0 ∧ b ≠ 0) ∨ (a = 1 ∧ b = 2) ∨ (b = 0 ∧ a ≠ 0) ∨ (b = 1 ∧ a = 2) := by  fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]lemma hn_spectrum_M_diag (a : Fin 4) : hn_spectrum_M a a = 0 := by  fin_cases a <;> simp [hn_spectrum_M]lemma hn_spectrum_M_eq_zero_or_one (a b : Fin 4) :    hn_spectrum_M a b = 0 ∨ hn_spectrum_M a b = 1 := by  fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]lemma hn_spectrum_adj_iff_M (n : ℕ) (v w : Fin (3 * n)) :    (hn_graph n).Adj v w ↔ hn_spectrum_M (hn_spectrum_cell n v) (hn_spectrum_cell n w) = 1 := by  have h1 := hn_spectrum_rel_iff n v w  have h2 := hn_spectrum_rel_iff n w v  have hM := hn_spectrum_M_eq_one_iff (hn_spectrum_cell n v) (hn_spectrum_cell n w)  simp only [hn_graph, SimpleGraph.fromRel]  constructor  · rintro ⟨-, h | h⟩    · rcases h1.mp h with ⟨a, b⟩ | ⟨a, b⟩      · exact hM.mpr (Or.inl ⟨a, b⟩)      · exact hM.mpr (Or.inr (Or.inl ⟨a, b⟩))    · rcases h2.mp h with ⟨a, b⟩ | ⟨a, b⟩      · exact hM.mpr (Or.inr (Or.inr (Or.inl ⟨a, b⟩)))      · exact hM.mpr (Or.inr (Or.inr (Or.inr ⟨a, b⟩)))  · intro hm    have hcne : hn_spectrum_cell n v ≠ hn_spectrum_cell n w := by      intro hab      rw [hab, hn_spectrum_M_diag] at hm      exact zero_ne_one hm    refine ⟨fun he => hcne (by rw [he]), ?_⟩    rcases hM.mp hm with ⟨a, b⟩ | ⟨a, b⟩ | ⟨a, b⟩ | ⟨a, b⟩    · exact Or.inl (h1.mpr (Or.inl ⟨a, b⟩))    · exact Or.inl (h1.mpr (Or.inr ⟨a, b⟩))    · exact Or.inr (h2.mpr (Or.inl ⟨a, b⟩))    · exact Or.inr (h2.mpr (Or.inr ⟨a, b⟩))lemma hn_spectrum_U_M_apply (n : ℕ) (v : Fin (3*n)) (k : Fin 4) :    (hn_spectrum_U n * hn_spectrum_M) v k = hn_spectrum_M (hn_spectrum_cell n v) k := by  rw [Matrix.mul_apply, Finset.sum_eq_single (hn_spectrum_cell n v)]  · simp [hn_spectrum_U]  · intro l _ hl; simp [hn_spectrum_U, Ne.symm hl]  · intro h; exact absurd (Finset.mem_univ _) hlemma hn_spectrum_U_M_U_transpose_apply (n : ℕ) (v w : Fin (3*n)) :    (hn_spectrum_U n * hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) v w      = hn_spectrum_M (hn_spectrum_cell n v) (hn_spectrum_cell n w) := by  rw [Matrix.mul_apply]  simp only [hn_spectrum_U_M_apply, Matrix.transpose_apply]  rw [Finset.sum_eq_single (hn_spectrum_cell n w)]  · simp [hn_spectrum_U]  · intro l _ hl; simp [hn_spectrum_U, Ne.symm hl]  · intro h; exact absurd (Finset.mem_univ _) hopen scoped Classical inlemma hn_spectrum_adjMatrix_eq (n : ℕ) (hle : 2 ≤ n) :    SimpleGraph.adjMatrix ℝ (hn_graph n)      = hn_spectrum_U n * hn_spectrum_M * Matrix.transpose (hn_spectrum_U n) := by  ext v w  rw [hn_spectrum_U_M_U_transpose_apply]  simp only [SimpleGraph.adjMatrix, Matrix.of_apply]  by_cases h : (hn_graph n).Adj v w  · rw [if_pos h]    exact ((hn_spectrum_adj_iff_M n v w).mp h).symm  · rw [if_neg h]    have hne : hn_spectrum_M (hn_spectrum_cell n v) (hn_spectrum_cell n w) ≠ 1 :=      fun hc => h ((hn_spectrum_adj_iff_M n v w).mpr hc)    rcases hn_spectrum_M_eq_zero_or_one (hn_spectrum_cell n v) (hn_spectrum_cell n w) with h0 | h1    · exact h0.symm    · exact absurd h1 hnelemma hn_spectrum_fin_card_val_lt {m a : ℕ} (h : a ≤ m) :    Fintype.card {v : Fin m // v.val < a} = a := by  have e : {v : Fin m // v.val < a} ≃ Fin a :=    { toFun := fun x => ⟨x.1.val, x.2⟩      invFun := fun y => ⟨⟨y.val, lt_of_lt_of_le y.isLt h⟩, y.isLt⟩      left_inv := by intro x; simp      right_inv := by intro y; simp }  rw [Fintype.card_congr e]; simplemma hn_spectrum_fin_card_val_between {m a b : ℕ} (h1 : a ≤ b) (h2 : b ≤ m) :    Fintype.card {v : Fin m // a ≤ v.val ∧ v.val < b} = b - a := by  have e : {v : Fin m // a ≤ v.val ∧ v.val < b} ≃ Fin (b - a) :=    { toFun := fun x => ⟨x.1.val - a, by have := x.2.1; have := x.2.2; omega⟩      invFun := fun y => ⟨⟨y.val + a, by have := y.isLt; omega⟩, by        have := y.isLt; show a ≤ y.val + a ∧ y.val + a < b; constructor <;> omega⟩      left_inv := by        intro x; apply Subtype.ext; apply Fin.ext; simp only        exact Nat.sub_add_cancel x.2.1      right_inv := by        intro y; apply Fin.ext; simp only        exact Nat.add_sub_cancel_right y.val a }  rw [Fintype.card_congr e]; simplemma hn_spectrum_fin_card_val_eq {m a : ℕ} (h : a < m) :    Fintype.card {v : Fin m // v.val = a} = 1 := by  have e : {v : Fin m // v.val = a} ≃ Fin 1 :=    { toFun := fun _ => ⟨0, by omega⟩      invFun := fun _ => ⟨⟨a, h⟩, rfl⟩      left_inv := by intro x; apply Subtype.ext; apply Fin.ext; exact x.2.symm      right_inv := by intro y; apply Fin.ext; simp }  rw [Fintype.card_congr e]; simplemma hn_spectrum_card_cell_zero (n : ℕ) :    (Finset.univ.filter (fun v : Fin (3*n) => hn_spectrum_cell n v = 0)).card = n - 1 := by  rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 0)]  have e : {v : Fin (3*n) // hn_spectrum_cell n v = 0} ≃ {v : Fin (3*n) // v.val < n - 1} :=    { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_zero_iff x.1).mp x.2⟩      invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_zero_iff x.1).mpr x.2⟩      left_inv := by intro x; simp      right_inv := by intro x; simp }  rw [Fintype.card_congr e]  exact hn_spectrum_fin_card_val_lt (by omega)lemma hn_spectrum_card_cell_one (n : ℕ) :    (Finset.univ.filter (fun v : Fin (3*n) => hn_spectrum_cell n v = 1)).card = n := by  rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 1)]  have e : {v : Fin (3*n) // hn_spectrum_cell n v = 1} ≃      {v : Fin (3*n) // n - 1 ≤ v.val ∧ v.val < 2 * n - 1} :=    { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_one_iff x.1).mp x.2⟩      invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_one_iff x.1).mpr x.2⟩      left_inv := by intro x; simp      right_inv := by intro x; simp }  rw [Fintype.card_congr e]  rw [hn_spectrum_fin_card_val_between (by omega) (by omega)]  omegalemma hn_spectrum_card_cell_two (n : ℕ) :    (Finset.univ.filter (fun v : Fin (3*n) => hn_spectrum_cell n v = 2)).card = n := by  rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 2)]  have e : {v : Fin (3*n) // hn_spectrum_cell n v = 2} ≃      {v : Fin (3*n) // 2 * n - 1 ≤ v.val ∧ v.val < 3 * n - 1} :=    { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_two_iff x.1).mp x.2⟩      invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_two_iff x.1).mpr x.2⟩      left_inv := by intro x; simp      right_inv := by intro x; simp }  rw [Fintype.card_congr e]  rw [hn_spectrum_fin_card_val_between (by omega) (by omega)]  omegalemma hn_spectrum_card_cell_three (n : ℕ) (hn : 1 ≤ n) :    (Finset.univ.filter (fun v : Fin (3*n) => hn_spectrum_cell n v = 3)).card = 1 := by  rw [← Fintype.card_subtype (fun v : Fin (3*n) => hn_spectrum_cell n v = 3)]  have e : {v : Fin (3*n) // hn_spectrum_cell n v = 3} ≃ {v : Fin (3*n) // v.val = 3 * n - 1} :=    { toFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_three_iff x.1).mp x.2⟩      invFun := fun x => ⟨x.1, (hn_spectrum_cell_eq_three_iff x.1).mpr x.2⟩      left_inv := by intro x; simp      right_inv := by intro x; simp }  rw [Fintype.card_congr e]  exact hn_spectrum_fin_card_val_eq (by omega)lemma hn_spectrum_card_cell (n : ℕ) (hn : 1 ≤ n) (k : Fin 4) :    (Finset.univ.filter (fun v : Fin (3*n) => hn_spectrum_cell n v = k)).card      = hn_spectrum_cell_size n k := by  fin_cases k  · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_zero n  · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_one n  · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_two n  · simpa [hn_spectrum_cell_size] using hn_spectrum_card_cell_three n hnlemma hn_spectrum_sum_ite_ite (n : ℕ) (k l : Fin 4) :    (∑ v : Fin (3*n),        (if hn_spectrum_cell n v = k then (1:ℝ) else 0) *          (if hn_spectrum_cell n v = l then 1 else 0))      = if k = l then ((Finset.univ.filter (fun v => hn_spectrum_cell n v = k)).card : ℝ) else 0 := by  by_cases hkl : k = l  · subst hkl    rw [if_pos rfl, ← Finset.sum_boole (fun v => hn_spectrum_cell n v = k) Finset.univ]    apply Finset.sum_congr rfl    intro v _    by_cases h : hn_spectrum_cell n v = k <;> simp [h]  · rw [if_neg hkl]    apply Finset.sum_eq_zero    intro v _    by_cases h : hn_spectrum_cell n v = k    · simp [h, hkl]    · simp [h]lemma hn_spectrum_U_transpose_mul_U (n : ℕ) (hn : 1 ≤ n) :    Matrix.transpose (hn_spectrum_U n) * hn_spectrum_U n = hn_spectrum_D n := by  ext k l  rw [Matrix.mul_apply]  simp only [Matrix.transpose_apply, hn_spectrum_U, hn_spectrum_D, Matrix.diagonal, Matrix.of_apply]  rw [hn_spectrum_sum_ite_ite]  by_cases hkl : k = l  · rw [if_pos hkl, if_pos hkl]    rw [hn_spectrum_card_cell n hn k]  · rw [if_neg hkl, if_neg hkl]lemma hn_spectrum_M_mul_D (n : ℕ) (hn : 1 ≤ n) :    hn_spectrum_M * hn_spectrum_D n = hn_quotient_matrix n := by  ext i j  fin_cases i <;> fin_cases j <;>    simp [hn_spectrum_M, hn_spectrum_D, hn_spectrum_cell_size, hn_quotient_matrix,      Matrix.diagonal, Matrix.mul_apply]  all_goals (rw [Nat.cast_sub hn]; ring)open scoped Classical inlemma hn_spectrum_adj_charpoly (n : ℕ) (hle : 2 ≤ n) :    (SimpleGraph.adjMatrix ℝ (hn_graph n)).charpoly =      Polynomial.X ^ (3 * n - 4) * (Polynomial.X + Polynomial.C (n : ℝ)) * hn_poly n := by  have hn1 : 1 ≤ n := by omega  have hcard : Fintype.card (Fin 4) ≤ Fintype.card (Fin (3*n)) := by simp; omega  have hA : SimpleGraph.adjMatrix ℝ (hn_graph n)      = hn_spectrum_U n * (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) := by    rw [hn_spectrum_adjMatrix_eq n hle, Matrix.mul_assoc]  have hBU : (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) * hn_spectrum_U n      = hn_quotient_matrix n := by    rw [Matrix.mul_assoc, hn_spectrum_U_transpose_mul_U n hn1, hn_spectrum_M_mul_D n hn1]  rw [hA, Matrix.charpoly_mul_comm_of_le (hn_spectrum_U n)    (hn_spectrum_M * Matrix.transpose (hn_spectrum_U n)) hcard, hBU, hn_quotient_matrix_charpoly]  simp only [Fintype.card_fin]  rw [mul_assoc]open scoped Classical in/-- Spectrum of the complete tripartite competitor graph H_n (arXiv:2610.18636 Theorem 4). -/theorem hn_spectrum (n : ℕ) (hle : 2 ≤ n) :    ∃ l1 l2 l3 : ℝ,      1 / 2 < l1 ∧ l1 < 2 * (n : ℝ) ∧      0 < l2 ∧ l2 < 1 / 2 ∧      -(n : ℝ) < l3 ∧ l3 < 0 ∧      l2 < l1 ∧ l3 < l2 ∧      hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3) ∧      (SimpleGraph.adjMatrix ℝ (hn_graph n)).charpoly =        Polynomial.X ^ (3 * n - 4) * (Polynomial.X + Polynomial.C (n : ℝ)) * hn_poly n := by  obtain ⟨l1, l2, l3, h1, h2, h3, h4, h5, h6, h7, h8, h9⟩ := hn_poly_three_roots n hle  exact ⟨l1, l2, l3, h1, h2, h3, h4, h5, h6, h7, h8, h9, hn_spectrum_adj_charpoly n hle⟩
See it in the graphDiscuss this resultChallenge it