hn_spectrum
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.
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.
unfold hn_spectrum_cell split_ifs with h1 h2 h3 <;> simp_all
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.
unfold hn_spectrum_cell split_ifs with h1 h2 h3 <;> simp_all <;> omega
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.
unfold hn_spectrum_cell split_ifs with h1 h2 h3 <;> simp_all <;> omega
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.
unfold hn_spectrum_cell split_ifs with h1 h2 h3 <;> simp_all <;> omega
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.
uses
hn_spectrum_cell_eq_zero_iff,hn_spectrum_cell_eq_one_iff,hn_spectrum_cell_eq_two_iffhave 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⟩
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.
fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]All diagonal entries of hn_spectrum_M are zero. automation
Exhaustive evaluation on all four elements of Fin 4.
fin_cases a <;> simp [hn_spectrum_M]Every entry of hn_spectrum_M is either 0 or 1. automation
Exhaustive case analysis across all 16 index pairs in Fin 4.
fin_cases a <;> fin_cases b <;> simp [hn_spectrum_M]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.
uses
hn_spectrum_rel_iff,hn_spectrum_M_eq_one_iff,hn_spectrum_M_diag,zero_ne_onehave 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⟩))
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.
uses
Matrix.mul_apply,Finset.sum_eq_singlerw [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
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.
uses
Matrix.mul_apply,hn_spectrum_U_M_apply,Finset.sum_eq_singlerw [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
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).
uses
hn_spectrum_U_M_U_transpose_apply,hn_spectrum_adj_iff_M,hn_spectrum_M_eq_zero_or_oneext 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
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.
uses
Fintype.card_congrhave 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
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.
uses
Fintype.card_congrhave 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
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.
uses
Fintype.card_congrhave 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
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.
uses
hn_spectrum_cell_eq_zero_iff,Fintype.card_congr,hn_spectrum_fin_card_val_ltrw [← 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)
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.
uses
hn_spectrum_cell_eq_one_iff,Fintype.card_congr,hn_spectrum_fin_card_val_betweenrw [← 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
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.
uses
hn_spectrum_cell_eq_two_iff,Fintype.card_congr,hn_spectrum_fin_card_val_betweenrw [← 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
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.
uses
hn_spectrum_cell_eq_three_iff,Fintype.card_congr,hn_spectrum_fin_card_val_eqrw [← 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)
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.
uses
hn_spectrum_card_cell_zero,hn_spectrum_card_cell_one,hn_spectrum_card_cell_two,hn_spectrum_card_cell_threefin_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
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.
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]
(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.
uses
Matrix.mul_apply,hn_spectrum_sum_ite_ite,hn_spectrum_card_cellext 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]
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.
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)
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.
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_charpolyhave 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]
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.
uses
hn_poly_three_roots,hn_spectrum_adj_charpolyobtain ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩