AFTD Auto-Formalizing Theoretical Domains

b5_clique_bound_fails_of_exceptional

theoremverified

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.

  1. 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.

    lines 1–4

    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)]
  2. 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`).

    lines 5–6

    uses sq_nonneg

      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)]
  3. 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.

    lines 8–11

    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)]
  4. 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.

    lines 12–13

      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]
  5. 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)$.

    lines 15–23

    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⟩
  6. 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`.

    lines 24–25

    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'
  7. 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`.

    lines 26–27

    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'
  8. 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`.

    lines 28–29

    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.

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

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'
See it in the graphDiscuss this resultChallenge it