AFTD Auto-Formalizing Theoretical Domains

b5_clique_bound_iff

theoremverifiedoriginal

For 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 quotient matrix M) holds if and only if (n_0, n_1, n_2, n_3) is not (1,1,1,1), (1,1,1,2) or (1,2,1,1) (in the paper's vertex order r_1, r_2, w_1, w_2, r_3); so it fails exactly on three infinite one-parameter families B_5(1,1,1,1,c), B_5(1,1,1,2,c), B_5(1,2,1,1,c).

Statement

theorem b5_clique_bound_iff (n : Fin 5 → ℕ) (hpos : ∀ i, 1 ≤ n i) :
    Real.sqrt ((b5_quotient_matrix n ^ 2).trace)
        ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b5_graph n).cliqueNum : ℝ)) ↔
      ¬ (n 0 = 1 ∧ n 2 = 1 ∧ ((n 1 = 1 ∧ n 3 = 1) ∨ (n 1 = 1 ∧ n 3 = 2) ∨ (n 1 = 2 ∧ n 3 = 1)))
Related work
arXiv:2610.21388 (Stronger spectral bound for clique number): Theorems 3.1 and 3.5 prove the bound for B_3 and B_4 with one exceptional family / one exceptional graph; the example after Theorem 3.5 shows it fails for B_5(1,2,1,1,1) and says that for t = 5 'there may be additional parameter choices for which our bound fails'. This characterizes them
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • b5_graphThe graph B_5(n_1..n_5) of arXiv:2610.21388: each vertex i of G_5 is replaced by a clique of n_i vertices, and cliques of adjacent…
  • 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…
  • b5_quotient_trace_sqtr(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.
  • b5_cliqueNumω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).
  • b5_gap_nonnegFor positive integers a, b, c, d, e with (a,b,c,d) ∉ {(1,1,1,1), (1,1,1,2), (1,2,1,1)}: tr ≤ n^2 (1 - 1/ω)^2 where tr = Σ (x-1)^2 + 2(ab +…
  • b5_clique_bound_fails_of_exceptionalFor (n_0, n_1, n_2, n_3) ∈ {(1,1,1,1), (1,1,1,2), (1,2,1,1)} and every n_4 = e ≥ 1, n^2 (1 - 1/ω)^2 < tr(M^2), i.e. the strong bound fails…

The proof, explained

The proof expresses the strong spectral clique bound √(tr(M^2)) ≤ N(1 - 1/ω) as an explicit inequality in the block sizes n_0, ..., n_4. Because the clique number ω ≥ 1 and the block sizes are positive, the right-hand side is non-negative, allowing the square root to be removed by squaring both sides. The equivalence is then completed by two known results: the bound strictly fails on the three exceptional parameter families by b5_clique_bound_fails_of_exceptional, and holds non-negatively on all other positive tuples by b5_gap_nonneg.

  1. The spectral clique bound is expressed directly in terms of the block sizes n_0, ..., n_4.

    The trace of the squared quotient matrix is rewritten using b5_quotient_trace_sq and the graph clique number ω is rewritten using b5_cliqueNum. The finite sums over Fin 5 on both sides are then expanded into explicit sums of the five block sizes using Fin.sum_univ_five.

    lines 5–6

    uses b5_quotient_trace_sq, b5_cliqueNum, Fin.sum_univ_five

      rw [b5_quotient_trace_sq, b5_cliqueNum]
      simp only [Fin.sum_univ_five]
  2. The bound √(tr(M^2)) ≤ N(1 - 1/ω) is equivalent to the squared inequality tr(M^2) ≤ (N(1 - 1/ω))^2.

    Because n_4 ≥ 1, the clique number ω = n_4 + max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3) is at least 1, so ω > 0. This implies 1/ω ≤ 1, whence 1 - 1/ω ≥ 0. Since each n_i ≥ 1, the total vertex count N = ∑ n_i is non-negative, and therefore the right-hand side Y = N(1 - 1/ω) is non-negative by mul_nonneg. By Real.sqrt_le_left, √(tr(M^2)) ≤ Y is equivalent to tr(M^2) ≤ Y^2.

    lines 7–21

    uses le_trans, Nat.le_add_right, lt_of_lt_of_le, zero_lt_one, div_le_one, mul_nonneg, Real.sqrt_le_left

      have hW1 : (1:ℝ) ≤ ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by
        have h := hpos 4
        have h2 : (1:ℕ) ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) :=
          le_trans h (Nat.le_add_right _ _)
        exact_mod_cast h2
      have hWpos : (0:ℝ) < ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) :=
        lt_of_lt_of_le zero_lt_one hW1
      have hfrac : (0:ℝ) ≤ 1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by
        have h3 : (1:ℝ) / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) ≤ 1 := by
          rw [div_le_one hWpos]; exact hW1
        linarith
      have hNnn : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) := by positivity
      have hY : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) * (1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ)) :=
        mul_nonneg hNnn hfrac
      rw [Real.sqrt_le_left hY]
  3. For all real numbers A and B, (A * B)^2 = A^2 * B^2.

    This algebraic identity distributing the square over multiplication is established by ring arithmetic.

    line 22

      have hsq : ∀ A B : ℝ, (A * B) ^ 2 = A ^ 2 * B ^ 2 := fun A B => by ring
  4. If the spectral clique bound holds, then (n_0, n_1, n_2, n_3) is not any of the three exceptional tuples (1,1,1,1), (1,1,1,2), or (1,2,1,1).

    Assume the bound holds and suppose for contradiction that the tuple is exceptional. By b5_clique_bound_fails_of_exceptional, the strict inequality (N(1 - 1/ω))^2 < tr(M^2) holds for all such tuples. Rewriting the squared product (N(1 - 1/ω))^2 as N^2(1 - 1/ω)^2 produces an immediate contradiction with the assumed bound tr(M^2) ≤ N^2(1 - 1/ω)^2.

    lines 23–27

    uses b5_clique_bound_fails_of_exceptional

      constructor
      · intro hle hexc
        have hgt := b5_clique_bound_fails_of_exceptional (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 4) hexc
        rw [hsq] at hle
        linarith
  5. If (n_0, n_1, n_2, n_3) is not exceptional, then the spectral clique bound holds.

    Assuming the tuple is not exceptional, b5_gap_nonneg provides tr(M^2) ≤ N^2(1 - 1/ω)^2. Rewriting this via the identity (A*B)^2 = A^2*B^2 yields the desired squared bound tr(M^2) ≤ (N(1 - 1/ω))^2.

    lines 28–30

    uses b5_gap_nonneg

      · intro hne
        have hge := b5_gap_nonneg (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 0) (hpos 1) (hpos 2) (hpos 3) (hpos 4) hne
        rwa [hsq]
b5_quotient_trace_sq
The trace of the squared quotient matrix of B_5(n) is ∑_{i=0}^4 (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)).
b5_cliqueNum
The clique number of B_5(n) equals n_4 + max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
Fin.sum_univ_five
The sum of a 5-element sequence over Fin 5 is the sum of its values at indices 0, 1, 2, 3, and 4.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.le_add_right
For any natural numbers n and k, n ≤ n + k.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
zero_lt_one
In an ordered semiring, 0 < 1.
div_le_one
For b > 0, the quotient a / b ≤ 1 if and only if a ≤ b.
mul_nonneg
The product of two non-negative numbers is non-negative.
Real.sqrt_le_left
For y ≥ 0, √x ≤ y if and only if x ≤ y^2.
b5_clique_bound_fails_of_exceptional
For the exceptional parameter choices where (n_0, n_2) = (1, 1) and (n_1, n_3) ∈ {(1, 1), (1, 2), (2, 1)}, the squared spectral clique bound strictly fails: (N(1 - 1/ω))^2 < tr(M^2).
b5_gap_nonneg
For any non-exceptional tuple of positive block sizes, the squared spectral clique bound holds: tr(M^2) ≤ N^2 (1 - 1/ω)^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 b5_clique_bound_iff (n : Fin 5 → ℕ) (hpos : ∀ i, 1 ≤ n i) :    Real.sqrt ((b5_quotient_matrix n ^ 2).trace)        ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b5_graph n).cliqueNum : ℝ)) ↔      ¬ (n 0 = 1 ∧ n 2 = 1 ∧ ((n 1 = 1 ∧ n 3 = 1) ∨ (n 1 = 1 ∧ n 3 = 2) ∨ (n 1 = 2 ∧ n 3 = 1))) := by  rw [b5_quotient_trace_sq, b5_cliqueNum]  simp only [Fin.sum_univ_five]  have hW1 : (1:ℝ) ≤ ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by    have h := hpos 4    have h2 : (1:ℕ) ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) :=      le_trans h (Nat.le_add_right _ _)    exact_mod_cast h2  have hWpos : (0:ℝ) < ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) :=    lt_of_lt_of_le zero_lt_one hW1  have hfrac : (0:ℝ) ≤ 1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by    have h3 : (1:ℝ) / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) ≤ 1 := by      rw [div_le_one hWpos]; exact hW1    linarith  have hNnn : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) := by positivity  have hY : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) * (1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ)) :=    mul_nonneg hNnn hfrac  rw [Real.sqrt_le_left hY]  have hsq : ∀ A B : ℝ, (A * B) ^ 2 = A ^ 2 * B ^ 2 := fun A B => by ring  constructor  · intro hle hexc    have hgt := b5_clique_bound_fails_of_exceptional (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 4) hexc    rw [hsq] at hle    linarith  · intro hne    have hge := b5_gap_nonneg (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 0) (hpos 1) (hpos 2) (hpos 3) (hpos 4) hne    rwa [hsq]
See it in the graphDiscuss this resultChallenge it