b5_clique_bound_fails_of_exceptional
For (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 for B_5.
Statement
theorem b5_clique_bound_fails_of_exceptional (a b c d e : ℕ) (he : 1 ≤ e)
(hx : a = 1 ∧ c = 1 ∧ ((b = 1 ∧ d = 1) ∨ (b = 1 ∧ d = 2) ∨ (b = 2 ∧ d = 1))) :
((a : ℝ) + b + c + d + e) ^ 2 * (1 - 1 / ((e + max (max (a + b) (b + d)) (c + d) : ℕ) : ℝ)) ^ 2
< ((a : ℝ) - 1) ^ 2 + ((b : ℝ) - 1) ^ 2 + ((c : ℝ) - 1) ^ 2 + ((d : ℝ) - 1) ^ 2 + ((e : ℝ) - 1) ^ 2
+ 2 * ((a : ℝ) * b + c * d + b * d + e * (a + b + c + d))- Source
- the failure half of b5_clique_bound_iff; extends the example B_5(1,2,1,1,1) after Theorem 3.5 of arXiv:2610.21388 (Stronger spectral bound for clique number)
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- b5_clique_bound_iffFor 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 proof, explained
The theorem proves that the strong clique bound $n^2(1 - 1/\omega)^2 \ge \operatorname{tr}(M^2)$ fails for the pentagon $B_5$ on the three exceptional configurations $(a,b,c,d) \in \{(1,1,1,1), (1,1,1,2), (1,2,1,1)\}$ with $e \ge 1$. Substituting $a = 1, c = 1$ reduces the clique term $\omega$ to $e + 2$ in the first configuration and $e + 3$ in the other two. The resulting inequalities in $x = e \ge 1$ are established as helper lemmas by clearing denominators and showing that the difference between the right- and left-hand sides expands to a strictly positive polynomial.
For $x \ge 1$, the inequality $(4 + x)^2 (1 - (x + 2)⁻¹)^2 < (x - 1)^2 + 2(3 + 4x)$ is equivalent to the polynomial inequality $(4 + x)^2 (x + 1)^2 < ((x - 1)^2 + 2(3 + 4x))(x + 2)^2$.
We rewrite $1 - (x + 2)⁻¹$ as $(x + 1)/(x + 2)$ by rewriting the inverse as division (`inv_eq_one_div`) and clearing denominators. Squaring the fraction (`div_pow`), associating multiplication and division (`mul_div_assoc`), and clearing the strictly positive denominator $(x + 2)^2 > 0$ via `div_lt_iff₀` (justified by `positivity`) leaves a polynomial inequality.
uses
inv_eq_one_div,div_pow,mul_div_assoc,div_lt_iff₀lemma b5_clique_bound_fails_of_exceptional_case_a (x : ℝ) (hx : 1 ≤ x) : (4 + x) ^ 2 * (1 - (x + 2)⁻¹) ^ 2 < (x - 1) ^ 2 + 2 * (3 + x * 4) := by have h1 : (1 - (x + 2)⁻¹) = (x+1)/(x+2) := by rw [inv_eq_one_div]; field_simp; ring rw [h1, div_pow, ← mul_div_assoc, div_lt_iff₀ (by positivity)]
The inequality of Case A holds for all $x \ge 1$.
Expanding the difference between the right-hand and left-hand sides of the polynomial inequality yields $((x - 1)^2 + 2(3 + 4x))(x + 2)^2 - (4 + x)^2(x + 1)^2 = 2x^2 + 12x + 12$ by ring operations. Since $x \ge 1$, the quadratic $2x^2 + 12x + 12$ is strictly positive; non-linear arithmetic (`nlinarith`) closes the goal using this identity, $1 \le x$, and $(x - 1)^2 \ge 0$ (`sq_nonneg`).
uses
sq_nonneghave key : ((x - 1) ^ 2 + 2 * (3 + x * 4)) * (x + 2) ^ 2 - (4 + x) ^ 2 * (x + 1) ^ 2 = 2 * x ^ 2 + 12 * x + 12 := by ring nlinarith [key, hx, sq_nonneg (x - 1)]
For $x \ge 1$, the inequality $(5 + x)^2 (1 - (x + 3)⁻¹)^2 < 1 + (x - 1)^2 + 2(5 + 5x)$ is equivalent to $(5 + x)^2 (x + 2)^2 < (1 + (x - 1)^2 + 2(5 + 5x))(x + 3)^2$.
Similarly to Case A, we rewrite $1 - (x + 3)⁻¹$ as $(x + 2)/(x + 3)$ using `inv_eq_one_div` and ring operations. Squaring the quotient (`div_pow`) and clearing the positive denominator $(x + 3)^2 > 0$ via `div_lt_iff₀` and `positivity` reduces the problem to an inequality between polynomials.
uses
inv_eq_one_div,div_pow,mul_div_assoc,div_lt_iff₀lemma b5_clique_bound_fails_of_exceptional_case_b (x : ℝ) (hx : 1 ≤ x) : (5 + x) ^ 2 * (1 - (x + 3)⁻¹) ^ 2 < 1 + (x - 1) ^ 2 + 2 * (5 + x * 5) := by have h1 : (1 - (x + 3)⁻¹) = (x+2)/(x+3) := by rw [inv_eq_one_div]; field_simp; ring rw [h1, div_pow, ← mul_div_assoc, div_lt_iff₀ (by positivity)]
The inequality of Case B holds for all $x \ge 1$.
Expanding the difference of the two sides yields $(1 + (x - 1)^2 + 2(5 + 5x))(x + 3)^2 - (5 + x)^2(x + 2)^2 = 4x + 8$ by ring operations. Since $x \ge 1$, $4x + 8 \ge 12 > 0$, so non-linear arithmetic (`nlinarith`) concludes the strict inequality.
have key : (1 + (x - 1) ^ 2 + 2 * (5 + x * 5)) * (x + 3) ^ 2 - (5 + x) ^ 2 * (x + 2) ^ 2 = 4 * x + 8 := by ring nlinarith [key, hx]
Substitute $a = 1$ and $c = 1$, cast $e \ge 1$ to real numbers, and split into the three cases for $(b, d)$.
From the hypothesis `hx`, we extract $a = 1$ and $c = 1$ and substitute them into the main goal. We cast the natural number hypothesis $e \ge 1$ to reals ($1 \le (e : \mathbb{R})$) using `exact_mod_cast`. Finally, case analysis on the disjunction in `hx` yields three subgoals: $(b,d) = (1,1)$, $(b,d) = (1,2)$, and $(b,d) = (2,1)$.
theorem b5_clique_bound_fails_of_exceptional (a b c d e : ℕ) (he : 1 ≤ e) (hx : a = 1 ∧ c = 1 ∧ ((b = 1 ∧ d = 1) ∨ (b = 1 ∧ d = 2) ∨ (b = 2 ∧ d = 1))) : ((a : ℝ) + b + c + d + e) ^ 2 * (1 - 1 / ((e + max (max (a + b) (b + d)) (c + d) : ℕ) : ℝ)) ^ 2 < ((a : ℝ) - 1) ^ 2 + ((b : ℝ) - 1) ^ 2 + ((c : ℝ) - 1) ^ 2 + ((d : ℝ) - 1) ^ 2 + ((e : ℝ) - 1) ^ 2 + 2 * ((a : ℝ) * b + c * d + b * d + e * (a + b + c + d)) := by obtain ⟨ha, hc, h⟩ := hx subst ha; subst hc have he' : (1:ℝ) ≤ (e:ℝ) := by exact_mod_cast he rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
The bound fails when $(a,b,c,d) = (1,1,1,1)$.
When $b = 1$ and $d = 1$, the clique expression $\max(\max(1+1, 1+1), 1+1)$ evaluates to $2$ using `max_def`, and `norm_num` evaluates the constant coefficients. This transforms the goal into the exact statement of Case A evaluated at $x = e$, which is closed by `b5_clique_bound_fails_of_exceptional_case_a`.
uses
max_def,b5_clique_bound_fails_of_exceptional_case_a· norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_a (e:ℝ) he'
The bound fails when $(a,b,c,d) = (1,1,1,2)$.
When $b = 1$ and $d = 2$, $\max(\max(1+1, 1+2), 1+2)$ evaluates to $3$ via `max_def`. Numeric normalization (`norm_num`) reduces the expression to the exact statement of Case B evaluated at $x = e$, which is closed by `b5_clique_bound_fails_of_exceptional_case_b`.
uses
max_def,b5_clique_bound_fails_of_exceptional_case_b· norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_b (e:ℝ) he'
The bound fails when $(a,b,c,d) = (1,2,1,1)$.
When $b = 2$ and $d = 1$, $\max(\max(1+2, 2+1), 1+1)$ also evaluates to $3$ via `max_def`. Numeric simplification (`norm_num`) yields the same inequality as the previous case, which is again closed by `b5_clique_bound_fails_of_exceptional_case_b`.
uses
max_def,b5_clique_bound_fails_of_exceptional_case_b· norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_b (e:ℝ) he'
inv_eq_one_div- The reciprocal $x⁻¹$ is equal to division $1 / x$.
div_pow- A power of a quotient distributes as $(a / b)^n = a^n / b^n$.
mul_div_assoc- Multiplication and division associate as $(a \cdot b) / c = a \cdot (b / c)$.
div_lt_iff₀- For a strictly positive divisor $c > 0$, $b / c < a$ if and only if $b < a \cdot c$.
sq_nonneg- The square of any real number is non-negative: $a^2 \ge 0$.
b5_clique_bound_fails_of_exceptional_case_a- For any real $x \ge 1$, $(4 + x)^2 (1 - (x + 2)⁻¹)^2 < (x - 1)^2 + 2(3 + 4x)$.
b5_clique_bound_fails_of_exceptional_case_b- For any real $x \ge 1$, $(5 + x)^2 (1 - (x + 3)⁻¹)^2 < 1 + (x - 1)^2 + 2(5 + 5x)$.
max_def- The maximum $\max(a, b)$ is defined as $b$ if $a \le b$ and $a$ otherwise.
- The main theorem expands the strong clique bound inequality $n^2(1 - 1/\omega)^2 < \operatorname{tr}(M^2)$ for blow-ups of the pentagon $B_5$, where $n = a+b+c+d+e$ is the total number of vertices and $\omega = e + \max(\max(a+b, b+d), c+d)$ is the clique number.
- The two configurations $(b,d) = (1,2)$ and $(b,d) = (2,1)$ are symmetric under the automorphism of $B_5$ that transposes the two pairs of vertices, and both reduce to the identical algebraic inequality in Case B.
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 b5_clique_bound_fails_of_exceptional_case_a (x : ℝ) (hx : 1 ≤ x) : (4 + x) ^ 2 * (1 - (x + 2)⁻¹) ^ 2 < (x - 1) ^ 2 + 2 * (3 + x * 4) := by have h1 : (1 - (x + 2)⁻¹) = (x+1)/(x+2) := by rw [inv_eq_one_div]; field_simp; ring rw [h1, div_pow, ← mul_div_assoc, div_lt_iff₀ (by positivity)] have key : ((x - 1) ^ 2 + 2 * (3 + x * 4)) * (x + 2) ^ 2 - (4 + x) ^ 2 * (x + 1) ^ 2 = 2 * x ^ 2 + 12 * x + 12 := by ring nlinarith [key, hx, sq_nonneg (x - 1)]lemma b5_clique_bound_fails_of_exceptional_case_b (x : ℝ) (hx : 1 ≤ x) : (5 + x) ^ 2 * (1 - (x + 3)⁻¹) ^ 2 < 1 + (x - 1) ^ 2 + 2 * (5 + x * 5) := by have h1 : (1 - (x + 3)⁻¹) = (x+2)/(x+3) := by rw [inv_eq_one_div]; field_simp; ring rw [h1, div_pow, ← mul_div_assoc, div_lt_iff₀ (by positivity)] have key : (1 + (x - 1) ^ 2 + 2 * (5 + x * 5)) * (x + 3) ^ 2 - (5 + x) ^ 2 * (x + 2) ^ 2 = 4 * x + 8 := by ring nlinarith [key, hx]theorem b5_clique_bound_fails_of_exceptional (a b c d e : ℕ) (he : 1 ≤ e) (hx : a = 1 ∧ c = 1 ∧ ((b = 1 ∧ d = 1) ∨ (b = 1 ∧ d = 2) ∨ (b = 2 ∧ d = 1))) : ((a : ℝ) + b + c + d + e) ^ 2 * (1 - 1 / ((e + max (max (a + b) (b + d)) (c + d) : ℕ) : ℝ)) ^ 2 < ((a : ℝ) - 1) ^ 2 + ((b : ℝ) - 1) ^ 2 + ((c : ℝ) - 1) ^ 2 + ((d : ℝ) - 1) ^ 2 + ((e : ℝ) - 1) ^ 2 + 2 * ((a : ℝ) * b + c * d + b * d + e * (a + b + c + d)) := by obtain ⟨ha, hc, h⟩ := hx subst ha; subst hc have he' : (1:ℝ) ≤ (e:ℝ) := by exact_mod_cast he rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_a (e:ℝ) he' · norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_b (e:ℝ) he' · norm_num [max_def] exact b5_clique_bound_fails_of_exceptional_case_b (e:ℝ) he'