AFTD Auto-Formalizing Theoretical Domains

b3_sqrt_trace_quotient_sq_le_clique_bound

theoremverifiedformalization

Let n_0, n_1, n_2 be positive integers with (n_0, n_1) ≠ (1, 1), G = B_3(n_0, n_1, n_2) of order n = n_0 + n_1 + n_2, and λ_1, λ_2, λ_3 the adjacency eigenvalues of G other than -1 (the eigenvalues of the quotient matrix M). Then sqrt(λ_1^2 + λ_2^2 + λ_3^2) ≤ n(1 - 1/ω(G)). In Lean λ_1^2 + λ_2^2 + λ_3^2 is tr(M^2) and ω(G) is the clique number of the graph.

Statement

theorem b3_sqrt_trace_quotient_sq_le_clique_bound (n : Fin 3 → ℕ) (hpos : ∀ i, 1 ≤ n i)
    (h11 : ¬ (n 0 = 1 ∧ n 1 = 1)) :
    Real.sqrt ((b3_quotient_matrix n ^ 2).trace)
      ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ))
Formalizes
arXiv:2610.21388 (Stronger spectral bound for clique number), Theorem 3.1 (first part). The Lean states the sum of squares of the three eigenvalues other than -1 as tr(M^2) for the quotient matrix M (Theorems 2.3 and 2.6); ω is Mathlib's cliqueNum of the graph; proof differs from the paper's (nlinarith instead of derivative analysis)
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • b3_graphThe graph B_3(n_0, n_1, n_2) on the disjoint union of blocks of sizes n_0, n_1, n_2: two distinct vertices are adjacent iff they lie in…
  • b3_quotient_matrixThe 3x3 quotient matrix M = [[n_0 - 1, 0, n_2], [0, n_1 - 1, n_2], [n_0, n_1, n_2 - 1]] of B_3(n_0, n_1, n_2), whose three eigenvalues are…
  • b3_quotient_trace_sqtr(M^2) = n_0^2 + n_1^2 - n_2^2 + 2 n n_2 + 3 - 2n for the quotient matrix M of B_3(n_0,n_1,n_2), n = n_0 + n_1 + n_2; this is the sum of…
  • b3_cliqueNumThe clique number of B_3(n_0, n_1, n_2) is max(n_0 + n_2, n_1 + n_2).
  • b3_sq_leFor positive naturals a, b, c with (a, b) ≠ (1, 1): sqrt(a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)) ≤ (a+b+c)(1 - 1/max(a+c, b+c)).

The proof, explained

The proof reduces the graph spectral bound directly to an explicit algebraic inequality. It first rewrites the trace of the squared quotient matrix, the clique number of $B_3(n)$, and the total order of the graph in terms of the block sizes $n_0, n_1, n_2$. The resulting scalar inequality is then closed by invoking the auxiliary algebraic lemma `b3_sq_le`.

  1. The goal reduces to the algebraic inequality $\sqrt{n_0^2 + n_1^2 - n_2^2 + 2(n_0 + n_1 + n_2)n_2 + 3 - 2(n_0 + n_1 + n_2)} \le (n_0 + n_1 + n_2)\left(1 - \frac{1}{\max(n_0 + n_2, n_1 + n_2)}\right)$.

    We rewrite the trace of the squared quotient matrix using `b3_quotient_trace_sq`, substitute the clique number of $B_3(n)$ with $\max(n_0 + n_2, n_1 + n_2)$ using `b3_cliqueNum`, and expand the sum of the components $\sum_{i} n_i$ into $n_0 + n_1 + n_2$ using `Fin.sum_univ_three`.

    line 5

    uses b3_quotient_trace_sq, b3_cliqueNum, Fin.sum_univ_three

      rw [b3_quotient_trace_sq, b3_cliqueNum, Fin.sum_univ_three]
  2. The inequality holds.

    This is precisely the inequality proven in `b3_sq_le`, applied to $a = n_0$, $b = n_1$, and $c = n_2$, using the positivity of each $n_i$ (from hypothesis `hpos`) and the condition $(n_0, n_1) \neq (1, 1)$ (from hypothesis `h11`).

    line 6

    uses b3_sq_le

      exact b3_sq_le (n 0) (n 1) (n 2) (hpos 0) (hpos 1) (hpos 2) h11
b3_cliqueNum
The clique number of the graph $B_3(n)$ is $\max(n_0 + n_2, n_1 + n_2)$.
b3_quotient_trace_sq
The trace of the square of the quotient matrix $M(n)$ equals $n_0^2 + n_1^2 - n_2^2 + 2(n_0 + n_1 + n_2)n_2 + 3 - 2(n_0 + n_1 + n_2)$.
b3_sq_le
For positive integers $a, b, c$ with $(a, b) \neq (1, 1)$, $\sqrt{a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)} \le (a+b+c)(1 - 1/\max(a+c, b+c))$.
Fin.sum_univ_three
For any function $f : \mathrm{Fin}\,3 \to M$ into an additive monoid, $\sum_{i} f(i) = f(0) + f(1) + f(2)$.

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 b3_sqrt_trace_quotient_sq_le_clique_bound (n : Fin 3 → ℕ) (hpos : ∀ i, 1 ≤ n i)    (h11 : ¬ (n 0 = 1 ∧ n 1 = 1)) :    Real.sqrt ((b3_quotient_matrix n ^ 2).trace)      ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ)) := by  rw [b3_quotient_trace_sq, b3_cliqueNum, Fin.sum_univ_three]  exact b3_sq_le (n 0) (n 1) (n 2) (hpos 0) (hpos 1) (hpos 2) h11
See it in the graphDiscuss this resultChallenge it