AFTD Auto-Formalizing Theoretical Domains

b4_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one

theoremverifiedformalization

For n : Fin 4 → ℕ with n 0 = 1, n 1 = 1, n 2 = 1, and n 3 = 1, (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ)) < Real.sqrt ((b4_quotient_matrix n ^ 2).trace).

Statement

theorem b4_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one (n : Fin 4 → ℕ)
    (h0 : n 0 = 1) (h1 : n 1 = 1) (h2 : n 2 = 1) (h3 : n 3 = 1) :
    (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ))
      < Real.sqrt ((b4_quotient_matrix n ^ 2).trace)
Formalizes
arXiv:2610.21388, Section 3, lines 835-851
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • b4_graphThe graph B_4(n_0, n_1, n_2, n_3) on the disjoint union of four complete blocks of sizes n_0, n_1, n_2, n_3, with edges between blocks 0…
  • b4_quotient_matrixGiven a function n : Fin 4 → ℕ of natural numbers, b4_quotient_matrix n is the 4x4 real matrix Matrix (Fin 4) (Fin 4) ℝ with entries: row…
  • b4_quotient_trace_sqFor any n : Fin 4 → ℕ, the trace of the square of b4_quotient_matrix n equals ((n 0 : ℝ) + n 1)^2 + ((n 2 : ℝ) + n 3)^2 + 2 * (n 1 : ℝ) *…
  • b4_cliqueNumThe clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).

Read back from the Lean

For any function $n : \mathrm{Fin}\ 4 \to \mathbb{N}$ satisfying $n(0) = 1$, $n(1) = 1$, $n(2) = 1$, and $n(3) = 1$, the product of the sum of the components of $n$ (as real numbers) and $(1 - 1 / \omega(G))$, where $\omega(G)$ is the clique number of the graph $\mathtt{b4\_graph}(n)$, is strictly less than the square root of the trace of the square of the matrix $\mathtt{b4\_quotient\_matrix}(n)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem establishes that for the vector n = (1, 1, 1, 1), the clique bound (∑ n i) * (1 - 1 / ω) is strictly less than the square root of the trace of the squared quotient matrix. The proof calculates each quantity directly: the clique number ω is 2, the trace of the squared quotient matrix is 6, and the sum of vertex weights is 4. Substituting these values reduces the inequality to 4 * (1 - 1/2) = 2 < √6, which is confirmed by checking 2² < 6.

  1. The clique number of b4_graph n is 2.

    Rewriting with `b4_cliqueNum` expresses the clique number as max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3). Substituting the values n 0 = n 1 = n 2 = n 3 = 1 from the hypotheses yields max(max(2, 2), 2) = 2, which holds by reflexivity.

    lines 6–8

    uses b4_cliqueNum

      have hc : (b4_graph n).cliqueNum = 2 := by
        rw [b4_cliqueNum, h0, h1, h2, h3]
        rfl
  2. The trace of (b4_quotient_matrix n ^ 2) is 6.

    Rewriting with `b4_quotient_trace_sq` gives an explicit polynomial expression for the trace of the squared quotient matrix in terms of the components n i. Substituting n 0 = n 1 = n 2 = n 3 = 1 gives (1 + 1)² + (1 + 1)² + 2(1)(1) - 2(1 + 1 + 1 + 1) + 4, which evaluates to 6 by arithmetic.

    lines 9–11

    uses b4_quotient_trace_sq

      have ht : (b4_quotient_matrix n ^ 2).trace = 6 := by
        rw [b4_quotient_trace_sq, h0, h1, h2, h3]
        norm_num
  3. The total sum of the components ∑ i : Fin 4, n i is 4.

    Expanding the sum over Fin 4 with `Fin.sum_univ_four` and substituting the hypothesis that each n i = 1 produces 1 + 1 + 1 + 1 = 4.

    lines 12–14

    uses Fin.sum_univ_four

      have hs : ∑ i : Fin 4, (n i : ℝ) = 4 := by
        rw [Fin.sum_univ_four, h0, h1, h2, h3]
        norm_num
  4. (∑ i, n i) * (1 - 1 / cliqueNum) < √(trace of (quotient matrix)²).

    Substituting the clique number 2, trace 6, and vertex sum 4 into the goal yields 4 * (1 - 1 / 2) < √6, which simplifies to 2 < √6. Since 0 ≤ 2, applying `Real.lt_sqrt` reduces this to 2² < 6, which holds because 4 < 6.

    lines 15–18

    uses Real.lt_sqrt

      rw [hc, ht, hs]
      norm_num
      rw [Real.lt_sqrt (by norm_num)]
      norm_num
b4_cliqueNum
The clique number of the blow-up graph B₄(n) is max(max(n₀ + n₁, n₁ + n₃), n₂ + n₃).
b4_quotient_trace_sq
The trace of the square of the quotient matrix for B₄(n) is (n₀ + n₁)² + (n₂ + n₃)² + 2 n₁ n₃ - 2(n₀ + n₁ + n₂ + n₃) + 4.
Fin.sum_univ_four
A sum over the four elements of Fin 4 equals f(0) + f(1) + f(2) + f(3).
Real.lt_sqrt
For a non-negative real x, x < √y if and only if x² < y.

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

/-- Failure of the strengthened spectral clique bound for B_4(1, 1, 1, 1) = P_4. -/theorem b4_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one (n : Fin 4 → ℕ)    (h0 : n 0 = 1) (h1 : n 1 = 1) (h2 : n 2 = 1) (h3 : n 3 = 1) :    (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ))      < Real.sqrt ((b4_quotient_matrix n ^ 2).trace) := by  have hc : (b4_graph n).cliqueNum = 2 := by    rw [b4_cliqueNum, h0, h1, h2, h3]    rfl  have ht : (b4_quotient_matrix n ^ 2).trace = 6 := by    rw [b4_quotient_trace_sq, h0, h1, h2, h3]    norm_num  have hs : ∑ i : Fin 4, (n i : ℝ) = 4 := by    rw [Fin.sum_univ_four, h0, h1, h2, h3]    norm_num  rw [hc, ht, hs]  norm_num  rw [Real.lt_sqrt (by norm_num)]  norm_num
See it in the graphDiscuss this resultChallenge it