AFTD Auto-Formalizing Theoretical Domains

op223_example_spectral_upper

theoremverified

The spectral radius of the eight-vertex example tree is at most 209/100.

Statement

theorem op223_example_spectral_upper :
    adjacency_spectral_radius op223_example_graph ≤ ENNReal.ofReal (209 / 100 : ℝ)
Source
arXiv:2610.17078 Open Problem 6.1; experiments 22883 and 22914
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • op223_example_graphThe eight-vertex tree with edges 01, 04, 07, 12, 23, 45 and 46.
  • adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
  • op223_matrix_spectral_upperIf both tI minus A and tI plus A are positive semidefinite, the real spectral radius of A is at most t.
Used by 1

The proof, explained

The theorem bounds the spectral radius of the adjacency matrix A of the 8-vertex tree by 209/100. It establishes this by exhibiting explicit Cholesky-like factorizations t*I - A = Bᴴ * D * B and t*I + A = B_+ᴴ * D * B_+ for t = 209/100, where D is a diagonal matrix with strictly positive entries, proving that both t*I - A and t*I + A are positive semidefinite. Applying op223_matrix_spectral_upper then immediately implies that the spectral radius of A is at most 209/100.

  1. (209/100) * I - A is positive semidefinite

    We show that (209/100) * I - A is positive semidefinite by factoring it as Bᴴ * D * B, where D is a diagonal matrix with positive entries and B is upper unitriangular.

    lines 12–26

      have hd : ∀ i, 0 ≤ example_upper_d i := by
        intro i; fin_cases i <;> norm_num [example_upper_d, Matrix.cons_val_zero, Matrix.cons_val_succ]
      have hp := (Matrix.posSemidef_diagonal_iff.mpr hd).conjTranspose_mul_mul_same example_upper_B
      have he : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) -
          op223_example_graph.adjMatrix ℝ) = example_upper_Bᴴ * Matrix.diagonal example_upper_d * example_upper_B := by
        ext i j
        simp only [Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.sub_apply,
          Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply, SimpleGraph.adjMatrix_apply]
        fin_cases i <;> fin_cases j <;>
          norm_num [example_upper_B, example_upper_d, Matrix.mul_apply, Fin.sum_univ_succ,
            Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.sub_apply,
            Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply,
            SimpleGraph.adjMatrix_apply, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decide
      rw [he]
      exact hp
  2. (209/100) * I + A is positive semidefinite

    Similarly, we show that (209/100) * I + A is positive semidefinite via a B_+ᴴ * D * B_+ factorization.

    lines 33–47

      have hd : ∀ i, 0 ≤ example_upper_d i := by
        intro i; fin_cases i <;> norm_num [example_upper_d, Matrix.cons_val_zero, Matrix.cons_val_succ]
      have hp := (Matrix.posSemidef_diagonal_iff.mpr hd).conjTranspose_mul_mul_same example_upper_plus_B
      have he : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) +
          op223_example_graph.adjMatrix ℝ) = example_upper_plus_Bᴴ * Matrix.diagonal example_upper_d * example_upper_plus_B := by
        ext i j
        simp only [Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.add_apply,
          Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply, SimpleGraph.adjMatrix_apply]
        fin_cases i <;> fin_cases j <;>
          norm_num [example_upper_plus_B, example_upper_d, Matrix.mul_apply, Fin.sum_univ_succ,
            Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.add_apply,
            Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply,
            SimpleGraph.adjMatrix_apply, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decide
      rw [he]
      exact hp
  3. The spectral radius of the adjacency matrix is at most 209/100

    Unfolding the definition of adjacency spectral radius and applying op223_matrix_spectral_upper with the two positive semidefiniteness certificates yields the result.

    lines 51–52

    uses op223_matrix_spectral_upper

      unfold adjacency_spectral_radius
      exact op223_matrix_spectral_upper _ _ example_x_minus_psd example_x_plus_psd
op223_matrix_spectral_upper
The spectral radius of a real symmetric matrix A is at most t if both t*I - A and t*I + A are positive semidefinite.
adjacency_spectral_radius
The spectral radius of the graph's adjacency matrix.

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 Matrixopen scoped ENNRealopen scoped Classicalnoncomputable def example_upper_B : Matrix (Fin 8) (Fin 8) ℝ := ![![1, (-100/209), 0, 0, (-100/209), 0, 0, (-100/209)], ![0, 1, (-20900/33681), 0, (-10000/33681), 0, 0, (-10000/33681)], ![0, 0, 1, (-3368100/4949329), (-1000000/4949329), 0, 0, (-1000000/4949329)], ![0, 0, 0, 1, (-100000000/697599761), 0, 0, (-100000000/697599761)], ![0, 0, 0, 0, 1, (-69759976100/96305060049), (-69759976100/96305060049), (-236810000/460789761)], ![0, 0, 0, 0, 0, 1, (-6975997610000/13151759940241), (-4949329000000/13151759940241)], ![0, 0, 0, 0, 0, 0, 1, (-209000000/260789761)], ![0, 0, 0, 0, 0, 0, 0, 1]]noncomputable def example_upper_d : Fin 8 → ℝ := ![(209/100), (33681/20900), (4949329/3368100), (697599761/494932900), (96305060049/69759976100), (13151759940241/9630506004900), (1290734327020369/1315175994024100), (5011770049/26078976100)]set_option maxHeartbeats 2000000 inlemma example_x_minus_psd : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) -      op223_example_graph.adjMatrix ℝ).PosSemidef := by  have hd : ∀ i, 0 ≤ example_upper_d i := by    intro i; fin_cases i <;> norm_num [example_upper_d, Matrix.cons_val_zero, Matrix.cons_val_succ]  have hp := (Matrix.posSemidef_diagonal_iff.mpr hd).conjTranspose_mul_mul_same example_upper_B  have he : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) -      op223_example_graph.adjMatrix ℝ) = example_upper_Bᴴ * Matrix.diagonal example_upper_d * example_upper_B := by    ext i j    simp only [Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.sub_apply,      Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply, SimpleGraph.adjMatrix_apply]    fin_cases i <;> fin_cases j <;>      norm_num [example_upper_B, example_upper_d, Matrix.mul_apply, Fin.sum_univ_succ,        Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.sub_apply,        Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply,        SimpleGraph.adjMatrix_apply, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decide  rw [he]  exact hpnoncomputable def example_upper_plus_B : Matrix (Fin 8) (Fin 8) ℝ := ![![1, (100/209), 0, 0, (100/209), 0, 0, (100/209)], ![0, 1, (20900/33681), 0, (-10000/33681), 0, 0, (-10000/33681)], ![0, 0, 1, (3368100/4949329), (1000000/4949329), 0, 0, (1000000/4949329)], ![0, 0, 0, 1, (-100000000/697599761), 0, 0, (-100000000/697599761)], ![0, 0, 0, 0, 1, (69759976100/96305060049), (69759976100/96305060049), (-236810000/460789761)], ![0, 0, 0, 0, 0, 1, (-6975997610000/13151759940241), (4949329000000/13151759940241)], ![0, 0, 0, 0, 0, 0, 1, (209000000/260789761)], ![0, 0, 0, 0, 0, 0, 0, 1]]set_option maxHeartbeats 2000000 inlemma example_x_plus_psd : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) +      op223_example_graph.adjMatrix ℝ).PosSemidef := by  have hd : ∀ i, 0 ≤ example_upper_d i := by    intro i; fin_cases i <;> norm_num [example_upper_d, Matrix.cons_val_zero, Matrix.cons_val_succ]  have hp := (Matrix.posSemidef_diagonal_iff.mpr hd).conjTranspose_mul_mul_same example_upper_plus_B  have he : ((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209 / 100 : ℝ) +      op223_example_graph.adjMatrix ℝ) = example_upper_plus_Bᴴ * Matrix.diagonal example_upper_d * example_upper_plus_B := by    ext i j    simp only [Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.add_apply,      Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply, SimpleGraph.adjMatrix_apply]    fin_cases i <;> fin_cases j <;>      norm_num [example_upper_plus_B, example_upper_d, Matrix.mul_apply, Fin.sum_univ_succ,        Matrix.conjTranspose_apply, Matrix.diagonal_apply, Matrix.add_apply,        Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply,        SimpleGraph.adjMatrix_apply, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decide  rw [he]  exact hptheorem op223_example_spectral_upper :    adjacency_spectral_radius op223_example_graph ≤ ENNReal.ofReal (209 / 100 : ℝ) := by  unfold adjacency_spectral_radius  exact op223_matrix_spectral_upper _ _ example_x_minus_psd example_x_plus_psd
See it in the graphDiscuss this resultChallenge it