AFTD Auto-Formalizing Theoretical Domains

b5_quotient_trace_sq

theoremverified

tr(M^2) = Σ (n_i - 1)^2 + 2 (n_0 n_1 + n_2 n_3 + n_1 n_3 + n_4 (n_0 + n_1 + n_2 + n_3)) for the quotient matrix of B_5.

Statement

theorem b5_quotient_trace_sq (n : Fin 5 → ℕ) :
    (b5_quotient_matrix n ^ 2).trace =
      ∑ i, ((n i : ℝ) - 1) ^ 2 + 2 * ((n 0 : ℝ) * n 1 + n 2 * n 3 + n 1 * n 3 + n 4 * (n 0 + n 1 + n 2 + n 3))
Source
arXiv:2610.21388 (Stronger spectral bound for clique number), Theorem 2.6 with s = 2 (odd case t = 5); serves b5_clique_bound_iff
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • b5_quotient_matrixM_ii = n_i - 1, M_ij = a_ij n_j (a = adjacency of G_5); the eigenvalues of M are those of B_5 other than -1 (Theorem 2.3 of…
  • g5_adjG_5 on vertices r_1, r_2, w_1, w_2, r_3 (indices 0..4): edges r_1 r_2, w_1 w_2, r_2 w_2, and r_3 adjacent to all.
Used by 1
  • b5_clique_bound_iffFor B_5(n_0..n_4) with all n_i ≥ 1, the strong spectral clique bound sqrt(Σ_{λ ≠ -1} λ^2) ≤ n(1 - 1/ω) (with Σ_{λ≠-1} λ^2 = tr(M^2) for…

The proof, explained

The identity expresses the trace of the squared quotient matrix for B₅ in terms of the vertex weights n_i. The proof proceeds by direct finite computation: it unfolds the trace of M² into an explicit double sum over the 5 vertices, expands the finite sums with Fin.sum_univ_five, and checks that the resulting polynomial in n_0, ..., n_4 matches the right-hand side using ring arithmetic.

  1. The trace tr(M²) is rewritten as the double sum ∑ x, ∑ x₁, M x x₁ * M x₁ x with explicit entry definitions.

    By unfolding the definitions of trace (`Matrix.trace`, `Matrix.diag_apply`), matrix square (`pow_two`, `Matrix.mul_apply`), and the matrix entries (`b5_quotient_matrix`, `g5_adj`), the trace of the squared quotient matrix becomes the sum over all index pairs (x, x₁) of the product M(x, x₁) * M(x₁, x).

    line 4

    uses Matrix.trace, Matrix.diag_apply, pow_two, Matrix.mul_apply, b5_quotient_matrix, g5_adj

      simp only [Matrix.trace, Matrix.diag_apply, pow_two, Matrix.mul_apply, b5_quotient_matrix, g5_adj]
  2. The sums over Fin 5 are unrolled and the adjacency conditions evaluated for all pairs of indices.

    Rewriting with `Fin.sum_univ_five` expands both the outer and inner sums over the 5 vertices into explicit sums of 5 terms. The simplifier also decides the equality and adjacency relations for each concrete pair in {0, 1, 2, 3, 4}, reducing the expression to an explicit polynomial in n 0, n 1, n 2, n 3, n 4.

    line 5

    uses Fin.sum_univ_five

      simp [Fin.sum_univ_five]
  3. The expanded polynomial matches the right-hand side.

    Both sides of the equation are now concrete polynomials in the real variables n 0, ..., n 4. The `ring` tactic verifies that expanding all products and collecting like terms yields identical polynomials on both sides.

    line 6

      ring
Matrix.trace
The trace of a square matrix is the sum of its diagonal entries, ∑ i, A i i.
Matrix.diag_apply
The i-th entry of the diagonal vector of a matrix A is the entry A i i.
pow_two
Squaring an element in a monoid equals multiplying it by itself: a ^ 2 = a * a.
Matrix.mul_apply
The (i, k)-th entry of a matrix product M * N is the sum ∑ j, M i j * N j k.
b5_quotient_matrix
The definition of the 5 × 5 quotient matrix for B₅, whose (i, j)-th entry is n i - 1 when i = j, n j when i and j are adjacent in G₅, and 0 otherwise.
g5_adj
The adjacency relation for the 5-vertex graph G₅, in which vertex 4 is adjacent to vertices 0, 1, 2, 3, and the remaining edges form the path 0-1-3-2.
Fin.sum_univ_five
A sum over all five elements of Fin 5 expands to f 0 + f 1 + f 2 + f 3 + f 4.

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 b5_quotient_trace_sq (n : Fin 5 → ℕ) :    (b5_quotient_matrix n ^ 2).trace =      ∑ i, ((n i : ℝ) - 1) ^ 2 + 2 * ((n 0 : ℝ) * n 1 + n 2 * n 3 + n 1 * n 3 + n 4 * (n 0 + n 1 + n 2 + n 3)) := by  simp only [Matrix.trace, Matrix.diag_apply, pow_two, Matrix.mul_apply, b5_quotient_matrix, g5_adj]  simp [Fin.sum_univ_five]  ring
See it in the graphDiscuss this resultChallenge it