b4_sqrt_trace_quotient_sq_le_clique_bound
For any n : Fin 4 → ℕ with 1 ≤ n i for all i : Fin 4 and ¬ (n 0 = 1 ∧ n 1 = 1 ∧ n 2 = 1 ∧ n 3 = 1), Real.sqrt ((b4_quotient_matrix n ^ 2).trace) ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ)).
Statement
theorem b4_sqrt_trace_quotient_sq_le_clique_bound (n : Fin 4 → ℕ) (hpos : ∀ i, 1 ≤ n i)
(hne : ¬ (n 0 = 1 ∧ n 1 = 1 ∧ n 2 = 1 ∧ n 3 = 1)) :
Real.sqrt ((b4_quotient_matrix n ^ 2).trace)
≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ))- Formalizes
- arXiv:2610.21388, Theorem 3.5
- Verified
- 29 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}$ (i.e., a 4-tuple of natural numbers $(n_0, n_1, n_2, n_3)$) satisfying:
1. $1 \le n(i)$ for all $i \in \mathrm{Fin}\ 4$ (each $n(i) \ge 1$), and
2. $\neg (n(0) = 1 \wedge n(1) = 1 \wedge n(2) = 1 \wedge n(3) = 1)$ (the components are not all equal to 1),
the square root of the trace of the square of the quotient matrix b4_quotient_matrix n is less than or equal to
$$\left(\sum_{i \in \mathrm{Fin}\ 4} n(i)\right) \left(1 - \frac{1}{\omega(G)}\right)$$
where $\omega(G) = (\mathtt{b4\_graph}\ n).\mathrm{cliqueNum}$ is the clique number of the graph b4_graph n, cast to $\mathbb{R}$.
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 spectral clique bound for the graph family B₄(n) compares the Frobenius norm of its quotient matrix (via the trace of its square) to its total vertex count and clique number ω. Clearing denominators and squaring both sides reduces the claim to the non-negativity of a polynomial discriminant D(ω) ≥ 0 across three regimes, depending on which pairwise sum achieves the clique number: Regime R (b + d), Regime P (a + b), and Regime Q (c + d, which reduces to Regime P by symmetry). In each regime, rewriting the parameters in terms of non-negative offsets and applying the assumption that the parameters are not all equal to 1 produces an expanded polynomial with only positive coefficients, which establishes the inequality.
The polynomial difference is non-negative in Regime R, where a ≤ d and c ≤ b.
Since 1 ≤ a, b, c, d with a ≤ d and c ≤ b, we reparametrize the variables using non-negative integer offsets: a = u + 1, c = v + 1, b = (v + 1) + y, and d = (u + 1) + x. The non-degeneracy condition ¬(a = 1 ∧ b = 1 ∧ c = 1 ∧ d = 1) guarantees that 1 ≤ u + v + x + y. A case analysis on which offset is strictly positive allows us to shift that positive offset by 1; expanding the resulting expression via ring_nf produces only positive coefficients on non-negative variables, which positivity certifies as non-negative.
uses
Nat.eq_zero_or_posobtain ⟨u, rfl⟩ : ∃ u, a = u+1 := ⟨a-1, by omega⟩ obtain ⟨v, rfl⟩ : ∃ v, c = v+1 := ⟨c-1, by omega⟩ obtain ⟨y, rfl⟩ : ∃ y, b = (v+1)+y := ⟨b-(v+1), by omega⟩ obtain ⟨x, rfl⟩ : ∃ x, d = (u+1)+x := ⟨d-(u+1), by omega⟩ have hz : 1 ≤ u + v + x + y := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos v with hv0 | hv1 · rcases Nat.eq_zero_or_pos x with hx0 | hx1 · obtain ⟨y', rfl⟩ : ∃ y', y = y'+1 := ⟨y-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨x', rfl⟩ : ∃ x', x = x'+1 := ⟨x-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨v', rfl⟩ : ∃ v', v = v'+1 := ⟨v-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivity
The polynomial difference is non-negative in Regime P, where d ≤ a and c + d ≤ a + b.
We split on the comparison between b and c using le_total. If b ≤ c, we set d = u + 1, b = v + 1, c = (v + 1) + t, and a = ((u + 1) + t) + q using the condition c + d ≤ a + b. If c ≤ b, we set d = u + 1, a = (u + 1) + p, c = m + 1, and b = (m + 1) + r. In both branches, the offsets cannot all be zero, so at least one offset is positive. Shifting the positive offset by 1 expands the polynomial via ring_nf into a sum of positive monomials, verified non-negative by positivity.
uses
le_total,Nat.eq_zero_or_posrcases le_total b c with hbcle | hcble · obtain ⟨u, rfl⟩ : ∃ u, d = u+1 := ⟨d-1, by omega⟩ obtain ⟨v, rfl⟩ : ∃ v, b = v+1 := ⟨b-1, by omega⟩ obtain ⟨t, rfl⟩ : ∃ t, c = (v+1)+t := ⟨c-(v+1), by omega⟩ obtain ⟨q, rfl⟩ : ∃ q, a = ((u+1)+t)+q := ⟨a-((u+1)+t), by omega⟩ have hz : 1 ≤ u+v+t+q := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos v with hv0 | hv1 · rcases Nat.eq_zero_or_pos q with hq0 | hq1 · obtain ⟨t', rfl⟩ : ∃ t', t = t'+1 := ⟨t-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨q', rfl⟩ : ∃ q', q = q'+1 := ⟨q-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨v', rfl⟩ : ∃ v', v = v'+1 := ⟨v-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u, rfl⟩ : ∃ u, d = u+1 := ⟨d-1, by omega⟩ obtain ⟨p, rfl⟩ : ∃ p, a = (u+1)+p := ⟨a-(u+1), by omega⟩ obtain ⟨m, rfl⟩ : ∃ m, c = m+1 := ⟨c-1, by omega⟩ obtain ⟨r, rfl⟩ : ∃ r, b = (m+1)+r := ⟨b-(m+1), by omega⟩ have hz : 1 ≤ u+p+m+r := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos p with hp0 | hp1 · rcases Nat.eq_zero_or_pos m with hm0 | hm1 · obtain ⟨r', rfl⟩ : ∃ r', r = r'+1 := ⟨r-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨m', rfl⟩ : ∃ m', m = m'+1 := ⟨m-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨p', rfl⟩ : ∃ p', p = p'+1 := ⟨p-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivity
The polynomial difference is non-negative in Regime Q, where b ≤ c and a + b ≤ c + d.
Swapping the pairs (a, b) and (c, d) transforms the conditions of Regime Q into those of Regime P (specifically, b ≤ c becomes the first hypothesis, and a + b ≤ c + d becomes the second). Because the polynomial expression is symmetric under this swap, applying b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP with the swapped variables and simplifying with ring proves the claim.
uses
b4_sqrt_trace_quotient_sq_le_clique_bound_regimePhave h := b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP c d a b hc hd ha hb (by omega) (by omega) (by rintro ⟨hc1,hd1,ha1,hb1⟩; exact hne ⟨ha1,hb1,hc1,hd1⟩) convert h using 2 <;> ring
The discriminant polynomial difference D(ω) = (a+b+c+d)²(ω-1)² - [(a+b)² + (c+d)² + 2bd - 2(a+b+c+d) + 4]ω² is non-negative for ω = max(max(a+b, b+d), c+d).
We case-split on whether b + d achieves the maximum clique size. If a + b ≤ b + d and c + d ≤ b + d, then ω = b + d, which is Regime R, so b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR applies. Otherwise, b + d ≤ max(a+b, c+d) by De Morgan's law (not_and_or.mp), so ω = max(a+b, c+d). We then compare a + b and c + d: if c + d ≤ a + b, then ω = a + b and Regime P applies via b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP; if a + b ≤ c + d, then ω = c + d and Regime Q applies via b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQ.
uses
max_eq_right,max_eq_left,b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR,not_and_or.mp,le_trans,le_max_left,le_max_right,le_antisymm,max_le,le_total,b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP,b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQhave hD : ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)-1)^2 - (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ))^2 ≥ 0 := by by_cases hRtop : a+b ≤ b+d ∧ c+d ≤ b+d · have hOm : max (max (a+b) (b+d)) (c+d) = b+d := by rw [max_eq_right hRtop.1, max_eq_left hRtop.2] have hωeq : ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) = (b:ℝ)+(d:ℝ) := by rw [hOm]; push_cast; ring rw [hωeq] exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR a b c d ha hb hc hd (by omega) (by omega) hne · have hRle : b+d ≤ max (a+b) (c+d) := by rcases (not_and_or.mp hRtop) with h | h · exact le_trans (by omega) (le_max_left _ _) · exact le_trans (by omega) (le_max_right _ _) have hOm2 : max (max (a+b) (b+d)) (c+d) = max (a+b) (c+d) := by apply le_antisymm · exact max_le (max_le (le_max_left _ _) hRle) (le_max_right _ _) · exact max_le (le_trans (le_max_left _ _) (le_max_left _ _)) (le_max_right _ _) rw [hOm2] rcases le_total (c+d) (a+b) with hPQ | hQP · have hOmP : max (a+b) (c+d) = a+b := max_eq_left hPQ have hωeq : ((max (a+b) (c+d) : ℕ) : ℝ) = (a:ℝ)+(b:ℝ) := by rw [hOmP]; push_cast; ring rw [hωeq] have hdad : d ≤ a := by rw [hOmP] at hRle; omega exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP a b c d ha hb hc hd hdad hPQ hne · have hOmQ : max (a+b) (c+d) = c+d := max_eq_right hQP have hωeq : ((max (a+b) (c+d) : ℕ) : ℝ) = (c:ℝ)+(d:ℝ) := by rw [hOmQ]; push_cast; ring rw [hωeq] have hbc : b ≤ c := by rw [hOmQ] at hRle; omega exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQ a b c d ha hb hc hd hbc hQP hne
The clique number satisfies ω ≥ 2 > 0, and the right-hand side (a+b+c+d)(1 - 1/ω) is non-negative.
Since c ≥ 1 and d ≥ 1, we have ω ≥ c + d ≥ 2 by transitivity (le_trans) and bounding by the maximum (le_max_right). Thus ω > 0, which implies 1/ω ≤ 1 by div_le_one. Because the total vertex count a + b + c + d is non-negative and 1 - 1/ω ≥ 0, their product is non-negative by mul_nonneg.
uses
le_trans,le_max_right,mul_nonneg,div_le_onehave hωpos : (0:ℝ) < ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) := by have hM2 : 2 ≤ max (max (a+b) (b+d)) (c+d) := le_trans (by omega : 2 ≤ c+d) (le_max_right _ _) exact_mod_cast (by omega : (0:ℕ) < max (max (a+b) (b+d)) (c+d)) have hω1 : (1:ℝ) ≤ ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) := by have hM2 : 2 ≤ max (max (a+b) (b+d)) (c+d) := le_trans (by omega : 2 ≤ c+d) (le_max_right _ _) exact_mod_cast (by omega : (1:ℕ) ≤ max (max (a+b) (b+d)) (c+d)) have hNnn : (0:ℝ) ≤ (a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ) := by positivity have hRHSnn : (0:ℝ) ≤ ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) * (1 - 1/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)) := by apply mul_nonneg hNnn have h1 : (1:ℝ)/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) ≤ 1 := by rw [div_le_one hωpos]; exact hω1 linarith
The square-root inequality √((a+b)² + (c+d)² + 2bd - 2(a+b+c+d) + 4) ≤ (a+b+c+d)(1 - 1/ω) holds.
Because the right-hand side is non-negative, Real.sqrt_le_left reduces the square-root inequality to the comparison of squares. Expanding and normalizing with field_simp and clearing the positive denominator ω² with le_div_iff₀ turns the comparison into D(ω) ≥ 0, which was established as hypothesis hD. Nonlinear arithmetic (nlinarith) finishes the proof.
uses
Real.sqrt_le_left,ne_of_gt,le_div_iff₀rw [Real.sqrt_le_left hRHSnn] have hωne : ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) ≠ 0 := ne_of_gt hωpos have hpow : (((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) * (1 - 1/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)))^2 = ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)-1)^2 / (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ))^2 := by field_simp rw [hpow] rw [le_div_iff₀ (by positivity : (0:ℝ) < ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)^2)] nlinarith [hD]
The strengthened spectral clique bound holds for the quotient matrix of B₄(n).
Rewriting the squared quotient matrix trace with b4_quotient_trace_sq, the clique number with b4_cliqueNum, and the sum over Fin 4 with Fin.sum_univ_four transforms the statement into the algebraic bound established by b4_sqrt_trace_quotient_sq_le_clique_bound_key.
uses
b4_quotient_trace_sq,b4_cliqueNum,Fin.sum_univ_four,b4_sqrt_trace_quotient_sq_le_clique_bound_keyrw [b4_quotient_trace_sq, b4_cliqueNum, Fin.sum_univ_four] exact b4_sqrt_trace_quotient_sq_le_clique_bound_key (n 0) (n 1) (n 2) (n 3) (hpos 0) (hpos 1) (hpos 2) (hpos 3) hne
Nat.eq_zero_or_pos- Every natural number is either equal to zero or strictly positive.
le_total- In any linear order, for any two elements a and b, either a ≤ b or b ≤ a.
b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP- In Regime P (where d ≤ a and c + d ≤ a + b), the polynomial difference (a+b+c+d)²(a+b-1)² - [(a+b)² + (c+d)² + 2bd - 2(a+b+c+d) + 4](a+b)² is non-negative for positive integers not all equal to 1.
max_eq_right- If a ≤ b in a linear order, then max a b = b.
max_eq_left- If b ≤ a in a linear order, then max a b = a.
b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR- In Regime R (where a ≤ d and c ≤ b), the polynomial difference (a+b+c+d)²(b+d-1)² - [(a+b)² + (c+d)² + 2bd - 2(a+b+c+d) + 4](b+d)² is non-negative for positive integers not all equal to 1.
not_and_or.mp- De Morgan's law for conjunction: if ¬(P ∧ Q), then ¬P ∨ ¬Q.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
le_max_left- An element is bounded above by its maximum with another element: a ≤ max a b.
le_max_right- An element is bounded above by the maximum of another element and itself: b ≤ max a b.
le_antisymm- Antisymmetry of inequality: if a ≤ b and b ≤ a, then a = b.
max_le- If a ≤ c and b ≤ c, then max a b ≤ c.
b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQ- In Regime Q (where b ≤ c and a + b ≤ c + d), the polynomial difference (a+b+c+d)²(c+d-1)² - [(a+b)² + (c+d)² + 2bd - 2(a+b+c+d) + 4](c+d)² is non-negative for positive integers not all equal to 1.
mul_nonneg- The product of two non-negative numbers is non-negative.
div_le_one- For b > 0, the quotient a / b ≤ 1 if and only if a ≤ b.
Real.sqrt_le_left- For y ≥ 0, √x ≤ y if and only if x ≤ y².
ne_of_gt- If b < a, then a ≠ b.
le_div_iff₀- For c > 0, a ≤ b / c if and only if a * c ≤ b.
b4_quotient_trace_sq- The trace of the squared quotient matrix of B₄(n) is (n₀+n₁)² + (n₂+n₃)² + 2n₁n₃ - 2(n₀+n₁+n₂+n₃) + 4.
b4_cliqueNum- The clique number of B₄(n) is max(max(n₀+n₁, n₁+n₃), n₂+n₃).
Fin.sum_univ_four- The sum of a function over Fin 4 equals f 0 + f 1 + f 2 + f 3.
b4_sqrt_trace_quotient_sq_le_clique_bound_key- The square root of the trace of the squared quotient matrix is bounded by (a+b+c+d)(1 - 1/ω) where ω = max(max(a+b, b+d), c+d).
- In Regimes R and P, the non-negativity of large multi-variable polynomials is established by reparametrizing with non-negative integer offsets and expanding via ring_nf, which leaves only non-negative monomials with positive coefficients that positivity certifies automatically.
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.
lemma b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR (a b c d : ℕ) (ha:1≤a)(hb:1≤b)(hc:1≤c)(hd:1≤d) (hda : a ≤ d) (hbc : c ≤ b) (hne : ¬(a=1∧b=1∧c=1∧d=1)) : ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((b:ℝ)+(d:ℝ))-1)^2 - (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) * ((b:ℝ)+(d:ℝ))^2 ≥ 0 := by obtain ⟨u, rfl⟩ : ∃ u, a = u+1 := ⟨a-1, by omega⟩ obtain ⟨v, rfl⟩ : ∃ v, c = v+1 := ⟨c-1, by omega⟩ obtain ⟨y, rfl⟩ : ∃ y, b = (v+1)+y := ⟨b-(v+1), by omega⟩ obtain ⟨x, rfl⟩ : ∃ x, d = (u+1)+x := ⟨d-(u+1), by omega⟩ have hz : 1 ≤ u + v + x + y := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos v with hv0 | hv1 · rcases Nat.eq_zero_or_pos x with hx0 | hx1 · obtain ⟨y', rfl⟩ : ∃ y', y = y'+1 := ⟨y-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨x', rfl⟩ : ∃ x', x = x'+1 := ⟨x-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨v', rfl⟩ : ∃ v', v = v'+1 := ⟨v-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivitylemma b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP (a b c d : ℕ) (ha:1≤a)(hb:1≤b)(hc:1≤c)(hd:1≤d) (had : d ≤ a) (hPQ : c+d ≤ a+b) (hne : ¬(a=1∧b=1∧c=1∧d=1)) : ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((a:ℝ)+(b:ℝ))-1)^2 - (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) * ((a:ℝ)+(b:ℝ))^2 ≥ 0 := by rcases le_total b c with hbcle | hcble · obtain ⟨u, rfl⟩ : ∃ u, d = u+1 := ⟨d-1, by omega⟩ obtain ⟨v, rfl⟩ : ∃ v, b = v+1 := ⟨b-1, by omega⟩ obtain ⟨t, rfl⟩ : ∃ t, c = (v+1)+t := ⟨c-(v+1), by omega⟩ obtain ⟨q, rfl⟩ : ∃ q, a = ((u+1)+t)+q := ⟨a-((u+1)+t), by omega⟩ have hz : 1 ≤ u+v+t+q := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos v with hv0 | hv1 · rcases Nat.eq_zero_or_pos q with hq0 | hq1 · obtain ⟨t', rfl⟩ : ∃ t', t = t'+1 := ⟨t-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨q', rfl⟩ : ∃ q', q = q'+1 := ⟨q-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨v', rfl⟩ : ∃ v', v = v'+1 := ⟨v-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u, rfl⟩ : ∃ u, d = u+1 := ⟨d-1, by omega⟩ obtain ⟨p, rfl⟩ : ∃ p, a = (u+1)+p := ⟨a-(u+1), by omega⟩ obtain ⟨m, rfl⟩ : ∃ m, c = m+1 := ⟨c-1, by omega⟩ obtain ⟨r, rfl⟩ : ∃ r, b = (m+1)+r := ⟨b-(m+1), by omega⟩ have hz : 1 ≤ u+p+m+r := by by_contra h; push_neg at h; apply hne; omega rcases Nat.eq_zero_or_pos u with hu0 | hu1 · rcases Nat.eq_zero_or_pos p with hp0 | hp1 · rcases Nat.eq_zero_or_pos m with hm0 | hm1 · obtain ⟨r', rfl⟩ : ∃ r', r = r'+1 := ⟨r-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨m', rfl⟩ : ∃ m', m = m'+1 := ⟨m-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨p', rfl⟩ : ∃ p', p = p'+1 := ⟨p-1, by omega⟩ push_cast; ring_nf; positivity · obtain ⟨u', rfl⟩ : ∃ u', u = u'+1 := ⟨u-1, by omega⟩ push_cast; ring_nf; positivitylemma b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQ (a b c d : ℕ) (ha:1≤a)(hb:1≤b)(hc:1≤c)(hd:1≤d) (hbc : b ≤ c) (hQP : a+b ≤ c+d) (hne : ¬(a=1∧b=1∧c=1∧d=1)) : ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((c:ℝ)+(d:ℝ))-1)^2 - (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) * ((c:ℝ)+(d:ℝ))^2 ≥ 0 := by have h := b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP c d a b hc hd ha hb (by omega) (by omega) (by rintro ⟨hc1,hd1,ha1,hb1⟩; exact hne ⟨ha1,hb1,hc1,hd1⟩) convert h using 2 <;> ringlemma b4_sqrt_trace_quotient_sq_le_clique_bound_key (a b c d : ℕ) (ha:1≤a)(hb:1≤b)(hc:1≤c)(hd:1≤d) (hne : ¬(a=1∧b=1∧c=1∧d=1)) : Real.sqrt (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) ≤ ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) * (1 - 1/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)) := by have hD : ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)-1)^2 - (((a:ℝ)+(b:ℝ))^2 + ((c:ℝ)+(d:ℝ))^2 + 2*(b:ℝ)*(d:ℝ) - 2*((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) + 4) * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ))^2 ≥ 0 := by by_cases hRtop : a+b ≤ b+d ∧ c+d ≤ b+d · have hOm : max (max (a+b) (b+d)) (c+d) = b+d := by rw [max_eq_right hRtop.1, max_eq_left hRtop.2] have hωeq : ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) = (b:ℝ)+(d:ℝ) := by rw [hOm]; push_cast; ring rw [hωeq] exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeR a b c d ha hb hc hd (by omega) (by omega) hne · have hRle : b+d ≤ max (a+b) (c+d) := by rcases (not_and_or.mp hRtop) with h | h · exact le_trans (by omega) (le_max_left _ _) · exact le_trans (by omega) (le_max_right _ _) have hOm2 : max (max (a+b) (b+d)) (c+d) = max (a+b) (c+d) := by apply le_antisymm · exact max_le (max_le (le_max_left _ _) hRle) (le_max_right _ _) · exact max_le (le_trans (le_max_left _ _) (le_max_left _ _)) (le_max_right _ _) rw [hOm2] rcases le_total (c+d) (a+b) with hPQ | hQP · have hOmP : max (a+b) (c+d) = a+b := max_eq_left hPQ have hωeq : ((max (a+b) (c+d) : ℕ) : ℝ) = (a:ℝ)+(b:ℝ) := by rw [hOmP]; push_cast; ring rw [hωeq] have hdad : d ≤ a := by rw [hOmP] at hRle; omega exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeP a b c d ha hb hc hd hdad hPQ hne · have hOmQ : max (a+b) (c+d) = c+d := max_eq_right hQP have hωeq : ((max (a+b) (c+d) : ℕ) : ℝ) = (c:ℝ)+(d:ℝ) := by rw [hOmQ]; push_cast; ring rw [hωeq] have hbc : b ≤ c := by rw [hOmQ] at hRle; omega exact b4_sqrt_trace_quotient_sq_le_clique_bound_regimeQ a b c d ha hb hc hd hbc hQP hne have hωpos : (0:ℝ) < ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) := by have hM2 : 2 ≤ max (max (a+b) (b+d)) (c+d) := le_trans (by omega : 2 ≤ c+d) (le_max_right _ _) exact_mod_cast (by omega : (0:ℕ) < max (max (a+b) (b+d)) (c+d)) have hω1 : (1:ℝ) ≤ ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) := by have hM2 : 2 ≤ max (max (a+b) (b+d)) (c+d) := le_trans (by omega : 2 ≤ c+d) (le_max_right _ _) exact_mod_cast (by omega : (1:ℕ) ≤ max (max (a+b) (b+d)) (c+d)) have hNnn : (0:ℝ) ≤ (a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ) := by positivity have hRHSnn : (0:ℝ) ≤ ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) * (1 - 1/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)) := by apply mul_nonneg hNnn have h1 : (1:ℝ)/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) ≤ 1 := by rw [div_le_one hωpos]; exact hω1 linarith rw [Real.sqrt_le_left hRHSnn] have hωne : ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ) ≠ 0 := ne_of_gt hωpos have hpow : (((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ)) * (1 - 1/((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)))^2 = ((a:ℝ)+(b:ℝ)+(c:ℝ)+(d:ℝ))^2 * (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)-1)^2 / (((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ))^2 := by field_simp rw [hpow] rw [le_div_iff₀ (by positivity : (0:ℝ) < ((max (max (a+b) (b+d)) (c+d) : ℕ) : ℝ)^2)] nlinarith [hD]/-- Strengthened spectral clique bound for the graph family B_4(n_1, n_2, n_3, n_4). -/theorem b4_sqrt_trace_quotient_sq_le_clique_bound (n : Fin 4 → ℕ) (hpos : ∀ i, 1 ≤ n i) (hne : ¬ (n 0 = 1 ∧ n 1 = 1 ∧ n 2 = 1 ∧ n 3 = 1)) : Real.sqrt ((b4_quotient_matrix n ^ 2).trace) ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ)) := by rw [b4_quotient_trace_sq, b4_cliqueNum, Fin.sum_univ_four] exact b4_sqrt_trace_quotient_sq_le_clique_bound_key (n 0) (n 1) (n 2) (n 3) (hpos 0) (hpos 1) (hpos 2) (hpos 3) hne