b4_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one
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.
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.
uses
b4_cliqueNumhave hc : (b4_graph n).cliqueNum = 2 := by rw [b4_cliqueNum, h0, h1, h2, h3] rfl
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.
uses
b4_quotient_trace_sqhave ht : (b4_quotient_matrix n ^ 2).trace = 6 := by rw [b4_quotient_trace_sq, h0, h1, h2, h3] norm_num
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.
uses
Fin.sum_univ_fourhave hs : ∑ i : Fin 4, (n i : ℝ) = 4 := by rw [Fin.sum_univ_four, h0, h1, h2, h3] norm_num
(∑ 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.
uses
Real.lt_sqrtrw [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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