AFTD Auto-Formalizing Theoretical Domains

b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one

theoremverifiedformalization

If n_0 = n_1 = 1 and n_2 ≥ 1, then for G = B_3(1, 1, n_2) the bound fails strictly: n(1 - 1/ω(G)) < sqrt(λ_1^2 + λ_2^2 + λ_3^2) (with the sum of squares as tr(M^2)).

Statement

theorem b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one (n : Fin 3 → ℕ) (h2 : 1 ≤ n 2)
    (h0 : n 0 = 1) (h1 : n 1 = 1) :
    (∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ))
      < Real.sqrt ((b3_quotient_matrix n ^ 2).trace)
Formalizes
arXiv:2610.21388 (Stronger spectral bound for clique number), Theorem 3.1 ("in particular" part: D(1,1,n_3) < 0). Sum of squares of eigenvalues other than -1 stated as tr(M^2) of the quotient matrix
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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).

The proof, explained

The proof shows that the Motzkin–Straus-type clique bound fails strictly for the graph family $B_3(1, 1, n_2)$ with $n_2 \ge 1$ by explicitly calculating both sides. Under $n_0 = n_1 = 1$, the total vertex count is $n_2 + 2$, the clique number is $n_2 + 1$, and the trace of the squared quotient matrix is $(n_2 + 1)^2$, with square root $n_2 + 1$. The bound then simplifies to $\frac{n_2(n_2 + 2)}{n_2 + 1} < n_2 + 1$, which reduces upon clearing denominators to $n_2^2 + 2n_2 < n_2^2 + 2n_2 + 1$, a strict inequality.

  1. The sum of vertex counts $\sum_{i} n_i$ equals $n_2 + 2$.

    Expanding the three-element sum using `Fin.sum_univ_three` and substituting the hypotheses $n_0 = 1$ and $n_1 = 1$, the sum simplifies to $1 + 1 + n_2 = n_2 + 2$.

    lines 5–6

    uses Fin.sum_univ_three

      have hsum : (∑ i, (n i : ℝ)) = (n 2 : ℝ) + 2 := by
        rw [Fin.sum_univ_three, h0, h1]; push_cast; ring
  2. The clique number $\omega(G)$ of the graph is $n_2 + 1$.

    By `b3_cliqueNum`, the clique number is $\max(n_0 + n_2, n_1 + n_2)$. Since $n_0 = n_1 = 1$, this becomes $\max(1 + n_2, 1 + n_2) = n_2 + 1$.

    lines 7–10

    uses b3_cliqueNum

      have hclique : ((b3_graph n).cliqueNum : ℝ) = (n 2 : ℝ) + 1 := by
        rw [b3_cliqueNum, h0, h1]
        have hmax : max (1 + n 2) (1 + n 2) = n 2 + 1 := by omega
        rw [hmax]; push_cast; ring
  3. The trace of the squared quotient matrix is $(n_2 + 1)^2$.

    Using `b3_quotient_trace_sq` and substituting $n_0 = 1$ and $n_1 = 1$, algebraic simplification yields $1 + 1 - n_2^2 + 2(2 + n_2)n_2 + 3 - 2(2 + n_2) = (n_2 + 1)^2$.

    lines 11–12

    uses b3_quotient_trace_sq

      have htrace : (b3_quotient_matrix n ^ 2).trace = ((n 2 : ℝ) + 1) ^ 2 := by
        rw [b3_quotient_trace_sq, h0, h1]; push_cast; ring
  4. The main inequality simplifies to $(n_2 + 2)(1 - \frac{1}{n_2 + 1}) < n_2 + 1$.

    Substituting the simplified vertex sum, clique number, and trace into the goal, the square root $\sqrt{(n_2 + 1)^2}$ evaluates to $n_2 + 1$ by `Real.sqrt_sq`, since $n_2 + 1 \ge 0$.

    line 13

    uses Real.sqrt_sq

      rw [hsum, hclique, htrace, Real.sqrt_sq (by positivity)]
  5. The left-hand side $(n_2 + 2)(1 - \frac{1}{n_2 + 1})$ equals $\frac{n_2(n_2 + 2)}{n_2 + 1}$.

    Writing $1 - \frac{1}{n_2 + 1}$ over a common denominator gives $\frac{n_2}{n_2 + 1}$, so multiplying by $n_2 + 2$ results in $\frac{n_2(n_2 + 2)}{n_2 + 1}$.

    lines 14–16

      have hfun : ((n 2 : ℝ) + 2) * (1 - 1 / ((n 2 : ℝ) + 1))
          = ((n 2 : ℝ) * ((n 2 : ℝ) + 2)) / ((n 2 : ℝ) + 1) := by
        field_simp; ring
  6. The inequality holds strictly.

    Replacing the left-hand side by $\frac{n_2(n_2 + 2)}{n_2 + 1}$ and clearing the positive denominator $n_2 + 1$ via `div_lt_iff₀`, the inequality reduces to $n_2(n_2 + 2) < (n_2 + 1)^2$. Expanding both sides gives $n_2^2 + 2n_2 < n_2^2 + 2n_2 + 1$, which holds strictly for all $n_2$. Non-linear arithmetic (`nlinarith`) closes the goal.

    lines 17–18

    uses div_lt_iff₀

      rw [hfun, div_lt_iff₀ (by positivity)]
      nlinarith
Fin.sum_univ_three
For any function $f$ on `Fin 3` into an additive commutative monoid, the sum over all three elements equals $f(0) + f(1) + f(2)$.
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 squared quotient matrix of $B_3(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)$.
Real.sqrt_sq
For any real number $x \ge 0$, the square root of $x^2$ is $x$.
div_lt_iff₀
For positive $c > 0$ in a ordered group with zero, $b / c < a \iff b < a \cdot c$.

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_gt_clique_bound_of_one_one (n : Fin 3 → ℕ) (h2 : 1 ≤ n 2)    (h0 : n 0 = 1) (h1 : n 1 = 1) :    (∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ))      < Real.sqrt ((b3_quotient_matrix n ^ 2).trace) := by  have hsum : (∑ i, (n i : ℝ)) = (n 2 : ℝ) + 2 := by    rw [Fin.sum_univ_three, h0, h1]; push_cast; ring  have hclique : ((b3_graph n).cliqueNum : ℝ) = (n 2 : ℝ) + 1 := by    rw [b3_cliqueNum, h0, h1]    have hmax : max (1 + n 2) (1 + n 2) = n 2 + 1 := by omega    rw [hmax]; push_cast; ring  have htrace : (b3_quotient_matrix n ^ 2).trace = ((n 2 : ℝ) + 1) ^ 2 := by    rw [b3_quotient_trace_sq, h0, h1]; push_cast; ring  rw [hsum, hclique, htrace, Real.sqrt_sq (by positivity)]  have hfun : ((n 2 : ℝ) + 2) * (1 - 1 / ((n 2 : ℝ) + 1))      = ((n 2 : ℝ) * ((n 2 : ℝ) + 2)) / ((n 2 : ℝ) + 1) := by    field_simp; ring  rw [hfun, div_lt_iff₀ (by positivity)]  nlinarith
See it in the graphDiscuss this resultChallenge it