AFTD Auto-Formalizing Theoretical Domains

parallel_mw_balancing_base_polynomial

theoremverified

A polynomial lower bound under natural-number-style lower bounds on real a and c and exponential proxies A and C.

Statement

theorem parallel_mw_balancing_base_polynomial (a c A C : ℝ)
    (ha : 1 ≤ a) (hc : 1 ≤ c) (hA : a + 1 ≤ A) (hC : c + 1 ≤ C)
    (hquad : a^2 + a ≤ 2*A) (hgap : a = 1 ∨ 2 ≤ a)
    (hsmall : a = 1 → A = 2) :
    0 ≤ 4*A^2*C - 10*A - 2*C + 6 - A*(a*(a+2)+2*(a+1)*c)
Source
Algebraic reduction for parallel_mw_ratio_decreasing_triple and OP-670.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

The theorem establishes a non-negative polynomial lower bound in a, c, A, C from lower bounds on the variables and quadratic relations. The proof first controls the dependence on C and c by showing that their respective coefficients are non-negative, effectively reducing the problem to the boundary values of c and C. It then splits into cases depending on whether a = 1 or 2 ≤ a: when a = 1, A is forced to 2 and the expression simplifies directly; when 2 ≤ a, non-linear arithmetic closes the inequality by combining the non-negativity of 2*A - (a^2 + a) and (a - 2)^2.

  1. A is at least 2, and in particular A is non-negative.

    From the assumptions 1 ≤ a and a + 1 ≤ A, linear arithmetic gives 2 ≤ A, which immediately implies 0 ≤ A.

    lines 6–7

      have hA0 : 0 ≤ A := by linarith
      have hA2 : 2 ≤ A := by linarith
  2. 0 ≤ 4*A^2 - 2 - 2*A*(a + 1)

    Since A ≥ a + 1 and A ≥ 0, the product 2*A*(A - (a + 1)) is non-negative by mul_nonneg. Combining this with the non-negativity of (A - 1)^2 from sq_nonneg and 2 ≤ A, non-linear arithmetic establishes the bound.

    lines 8–10

    uses mul_nonneg, sq_nonneg

      have hcoef : 0 ≤ 4*A^2 - 2 - 2*A*(a+1) := by
        have hh := mul_nonneg (show 0 ≤ 2*A by positivity) (show 0 ≤ A-(a+1) by linarith)
        nlinarith [sq_nonneg (A-1)]
  3. 0 ≤ 4*A^2 - 2

    Since A ≥ 2, non-linear arithmetic using (A - 1)^2 ≥ 0 from sq_nonneg proves 4*A^2 - 2 ≥ 0.

    line 11

    uses sq_nonneg

      have hcoef2 : 0 ≤ 4*A^2 - 2 := by nlinarith [sq_nonneg (A-1)]
  4. The terms (c - 1)*(4*A^2 - 2 - 2*A*(a + 1)) and (C - c - 1)*(4*A^2 - 2) are non-negative.

    From 1 ≤ c and c + 1 ≤ C, the factors c - 1 and C - c - 1 are non-negative. Multiplying them by the non-negative coefficients proven in the previous steps via mul_nonneg yields both inequalities.

    lines 12–13

    uses mul_nonneg

      have hm := mul_nonneg (show 0 ≤ c-1 by linarith) hcoef
      have hn := mul_nonneg (show 0 ≤ C-c-1 by linarith) hcoef2
  5. The inequality holds in the case a = 1.

    Case analysis on hgap (a = 1 ∨ 2 ≤ a) begins with a = 1. Under this assumption, hypothesis hsmall gives A = 2. Substituting a = 1 and A = 2 into the target polynomial reduces it to an expression in c and C that non-linear arithmetic verifies is non-negative using the previously established bounds.

    lines 14–18

      rcases hgap with h | h
      · have hs := hsmall h
        subst a
        subst A
        nlinarith
  6. The inequality holds in the case 2 ≤ a, completing the proof.

    In the second branch where 2 ≤ a, the quadratic hypothesis a^2 + a ≤ 2*A gives 2*A - (a^2 + a) ≥ 0, so multiplying by 4*A ≥ 0 via mul_nonneg yields 4*A*(2*A - (a^2 + a)) ≥ 0. Similarly, 2 ≤ a implies 3*a^2 - 12 ≥ 0 (from (a - 2)^2 ≥ 0 via sq_nonneg), so A*(3*a^2 - 12) ≥ 0 by mul_nonneg. Non-linear arithmetic combines these inequalities with the bounds on the c and C terms to close the goal.

    lines 19–21

    uses mul_nonneg, sq_nonneg

      · have hp := mul_nonneg (show 0 ≤ 4*A by positivity) (show 0 ≤ 2*A-(a^2+a) by linarith)
        have hq := mul_nonneg hA0 (show 0 ≤ 3*a^2-12 by nlinarith [sq_nonneg (a-2)])
        nlinarith
mul_nonneg
The product of two non-negative elements is non-negative.
sq_nonneg
The square of any real number is non-negative.

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 parallel_mw_balancing_base_polynomial (a c A C : ℝ)    (ha : 1 ≤ a) (hc : 1 ≤ c) (hA : a + 1 ≤ A) (hC : c + 1 ≤ C)    (hquad : a^2 + a ≤ 2*A) (hgap : a = 1 ∨ 2 ≤ a)    (hsmall : a = 1 → A = 2) :    0 ≤ 4*A^2*C - 10*A - 2*C + 6 - A*(a*(a+2)+2*(a+1)*c) := by  have hA0 : 0 ≤ A := by linarith  have hA2 : 2 ≤ A := by linarith  have hcoef : 0 ≤ 4*A^2 - 2 - 2*A*(a+1) := by    have hh := mul_nonneg (show 0 ≤ 2*A by positivity) (show 0 ≤ A-(a+1) by linarith)    nlinarith [sq_nonneg (A-1)]  have hcoef2 : 0 ≤ 4*A^2 - 2 := by nlinarith [sq_nonneg (A-1)]  have hm := mul_nonneg (show 0 ≤ c-1 by linarith) hcoef  have hn := mul_nonneg (show 0 ≤ C-c-1 by linarith) hcoef2  rcases hgap with h | h  · have hs := hsmall h    subst a    subst A    nlinarith  · have hp := mul_nonneg (show 0 ≤ 4*A by positivity) (show 0 ≤ 2*A-(a^2+a) by linarith)    have hq := mul_nonneg hA0 (show 0 ≤ 3*a^2-12 by nlinarith [sq_nonneg (a-2)])    nlinarith
See it in the graphDiscuss this resultChallenge it