AFTD Auto-Formalizing Theoretical Domains

b3_sq_le

theoremverified

For positive naturals a, b, c with (a, b) ≠ (1, 1): sqrt(a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)) ≤ (a+b+c)(1 - 1/max(a+c, b+c)).

Statement

theorem b3_sq_le (a b c : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) (hc : 1 ≤ c) (h11 : ¬ (a = 1 ∧ b = 1)) :
    Real.sqrt ((a:ℝ)^2 + b^2 - c^2 + 2*(a+b+c)*c + 3 - 2*(a+b+c))
      ≤ ((a:ℝ)+b+c) * (1 - 1 / ((max (a + c) (b + c) : ℕ) : ℝ))
Source
arXiv:2610.21388 (Stronger spectral bound for clique number), proof of Theorem 3.1; serves b3_sqrt_trace_quotient_sq_le_clique_bound
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • b3_core_ineqFor naturals a ≥ 2, 1 ≤ b ≤ a, c ≥ 1: (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)) (a+c)^2 ≤ (a+b+c)^2 (a+c-1)^2.
Used by 1

The proof, explained

The inequality is symmetric with respect to a and b, so by totality of linear order (le_total), the proof splits into the cases b ≤ a and a ≤ b. When b ≤ a, the condition (a, b) ≠ (1, 1) forces a ≥ 2, and the maximum max(a + c, b + c) simplifies to a + c. Squaring both sides via Real.sqrt_le_iff.2 and clearing denominators reduces the inequality directly to the auxiliary lemma b3_core_ineq. The case a ≤ b is solved symmetrically by applying b3_core_ineq with a and b interchanged and concluding by polynomial symmetry.

  1. It suffices to consider the two cases b ≤ a and a ≤ b.

    By totality of the linear order on ℕ (le_total), either b ≤ a or a ≤ b holds.

    line 4

    uses le_total

      rcases le_total b a with hab | hab
  2. In the case b ≤ a, we have a ≥ 2, max(a + c, b + c) = a + c, and the right-hand side rewrites to (a + b + c)(a + c - 1) / (a + c).

    Because a ≥ 1, b ≥ 1, and (a, b) ≠ (1, 1), having b ≤ a forces a ≥ 2 by linear arithmetic (omega). Furthermore, b ≤ a implies max(a + c, b + c) = a + c. Putting 1 - 1/(a + c) over the common denominator a + c > 0 rewrites the right-hand side as (a + b + c)(a + c - 1) / (a + c).

    lines 5–11

      · have h2 : 2 ≤ a := by omega
        have hm : max (a + c) (b + c) = a + c := by omega
        rw [hm]
        have hw : (0:ℝ) < ((a + c : ℕ) : ℝ) := by positivity
        have heq : ((a:ℝ)+b+c) * (1 - 1 / ((a + c : ℕ) : ℝ)) = ((a:ℝ)+b+c) * ((a:ℝ)+c-1) / ((a:ℝ)+c) := by
          push_cast; field_simp
        rw [heq]
  3. The right-hand side is non-negative, so taking square roots reduces the inequality to (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)) ≤ ((a + b + c)(a + c - 1) / (a + c))^2.

    By Real.sqrt_le_iff.2, establishing √X ≤ Y reduces to showing 0 ≤ Y and X ≤ Y^2. The right-hand side is a quotient of non-negative reals (div_nonneg), since a ≥ 2 and c ≥ 1 ensure both the numerator and the denominator are non-negative, leaving only the squared inequality.

    lines 12–15

    uses Real.sqrt_le_iff.2, div_nonneg

        apply Real.sqrt_le_iff.2
        have hw' : (0:ℝ) < (a:ℝ) + c := by push_cast at hw; exact hw
        have ha' : (2:ℝ) ≤ a := by exact_mod_cast h2
        refine ⟨by apply div_nonneg <;> nlinarith, ?_⟩
  4. Clearing the denominator reduces the goal to the core inequality b3_core_ineq, completing the case b ≤ a.

    Distributing the square over the quotient with div_pow and mul_pow and clearing the positive denominator (a + c)^2 > 0 via le_div_iff₀ transforms the squared inequality into (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c))(a + c)^2 ≤ (a + b + c)^2(a + c - 1)^2. This is precisely the statement of b3_core_ineq.

    lines 16–17

    uses div_pow, le_div_iff₀, mul_pow, b3_core_ineq

        rw [div_pow, le_div_iff₀ (by positivity), mul_pow]
        exact b3_core_ineq a b c hb hc hab h2
  5. In the symmetric case a ≤ b, we have b ≥ 2, max(a + c, b + c) = b + c, and the right-hand side rewrites to (b + a + c)(b + c - 1) / (b + c).

    Symmetrically, from 1 ≤ a, 1 ≤ b, (a, b) ≠ (1, 1), and a ≤ b, linear arithmetic yields b ≥ 2. The maximum simplifies to b + c, and putting 1 - 1/(b + c) over the common denominator followed by rearranging terms gives (b + a + c)(b + c - 1) / (b + c).

    lines 18–24

      · have h2 : 2 ≤ b := by omega
        have hm : max (a + c) (b + c) = b + c := by omega
        rw [hm]
        have hw : (0:ℝ) < ((b + c : ℕ) : ℝ) := by positivity
        have heq : ((a:ℝ)+b+c) * (1 - 1 / ((b + c : ℕ) : ℝ)) = ((b:ℝ)+a+c) * ((b:ℝ)+c-1) / ((b:ℝ)+c) := by
          push_cast; field_simp; ring
        rw [heq]
  6. The right-hand side is non-negative, reducing the square root inequality to (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c)) ≤ ((b + a + c)(b + c - 1) / (b + c))^2.

    Applying Real.sqrt_le_iff.2 again reduces the inequality to verifying that the right-hand side is non-negative and establishing the squared inequality. Non-negativity follows by div_nonneg since b ≥ 2 and c ≥ 1.

    lines 25–28

    uses Real.sqrt_le_iff.2, div_nonneg

        apply Real.sqrt_le_iff.2
        have hw' : (0:ℝ) < (b:ℝ) + c := by push_cast at hw; exact hw
        have hb' : (2:ℝ) ≤ b := by exact_mod_cast h2
        refine ⟨by apply div_nonneg <;> nlinarith, ?_⟩
  7. Clearing the denominator and applying b3_core_ineq with a and b swapped completes the proof.

    Clearing the denominator (b + c)^2 > 0 using div_pow, mul_pow, and le_div_iff₀ produces (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c))(b + c)^2 ≤ (b + a + c)^2(b + c - 1)^2. Applying b3_core_ineq with the roles of a and b exchanged establishes this inequality up to commutativity of addition and multiplication, which nlinarith verifies.

    lines 29–31

    uses div_pow, le_div_iff₀, mul_pow, b3_core_ineq

        rw [div_pow, le_div_iff₀ (by positivity), mul_pow]
        have := b3_core_ineq b a c ha hc hab h2
        nlinarith [this]
le_total
In any linear order, any two elements satisfy a ≤ b or b ≤ a.
Real.sqrt_le_iff.2
For real numbers x and y, if 0 ≤ y and x ≤ y^2, then √x ≤ y.
div_nonneg
If a ≥ 0 and b ≥ 0, then a / b ≥ 0.
div_pow
The power of a quotient is the quotient of the powers: (a / b)^n = a^n / b^n.
le_div_iff₀
For a strictly positive denominator c > 0, a ≤ b / c holds if and only if a * c ≤ b.
mul_pow
The power of a product is the product of the powers: (a * b)^n = a^n * b^n.
b3_core_ineq
For positive naturals b ≥ 1, c ≥ 1 and 2 ≤ a with b ≤ a, (a^2 + b^2 - c^2 + 2(a+b+c)c + 3 - 2(a+b+c))(a+c)^2 ≤ (a+b+c)^2(a+c-1)^2.

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

theorem b3_sq_le (a b c : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) (hc : 1 ≤ c) (h11 : ¬ (a = 1 ∧ b = 1)) :    Real.sqrt ((a:ℝ)^2 + b^2 - c^2 + 2*(a+b+c)*c + 3 - 2*(a+b+c))      ≤ ((a:ℝ)+b+c) * (1 - 1 / ((max (a + c) (b + c) : ℕ) : ℝ)) := by  rcases le_total b a with hab | hab  · have h2 : 2 ≤ a := by omega    have hm : max (a + c) (b + c) = a + c := by omega    rw [hm]    have hw : (0:ℝ) < ((a + c : ℕ) : ℝ) := by positivity    have heq : ((a:ℝ)+b+c) * (1 - 1 / ((a + c : ℕ) : ℝ)) = ((a:ℝ)+b+c) * ((a:ℝ)+c-1) / ((a:ℝ)+c) := by      push_cast; field_simp    rw [heq]    apply Real.sqrt_le_iff.2    have hw' : (0:ℝ) < (a:ℝ) + c := by push_cast at hw; exact hw    have ha' : (2:ℝ) ≤ a := by exact_mod_cast h2    refine ⟨by apply div_nonneg <;> nlinarith, ?_⟩    rw [div_pow, le_div_iff₀ (by positivity), mul_pow]    exact b3_core_ineq a b c hb hc hab h2  · have h2 : 2 ≤ b := by omega    have hm : max (a + c) (b + c) = b + c := by omega    rw [hm]    have hw : (0:ℝ) < ((b + c : ℕ) : ℝ) := by positivity    have heq : ((a:ℝ)+b+c) * (1 - 1 / ((b + c : ℕ) : ℝ)) = ((b:ℝ)+a+c) * ((b:ℝ)+c-1) / ((b:ℝ)+c) := by      push_cast; field_simp; ring    rw [heq]    apply Real.sqrt_le_iff.2    have hw' : (0:ℝ) < (b:ℝ) + c := by push_cast at hw; exact hw    have hb' : (2:ℝ) ≤ b := by exact_mod_cast h2    refine ⟨by apply div_nonneg <;> nlinarith, ?_⟩    rw [div_pow, le_div_iff₀ (by positivity), mul_pow]    have := b3_core_ineq b a c ha hc hab h2    nlinarith [this]
See it in the graphDiscuss this resultChallenge it