parallel_mw_balancing_base_polynomial
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
- parallel_mw_balancing_numerator_boundUnder the displayed size and power inequalities, the triple numerator is at least B times the balanced-endpoint benchmark divided by two.
- parallel_mw_ratio_decreasing_tripleFor positive integers a, b, c with a + 2 ≤ b, replacing (a, b) with (a + 1, b - 1) strictly decreases the rational formula for…
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.
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.
have hA0 : 0 ≤ A := by linarith have hA2 : 2 ≤ A := by linarith
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.
uses
mul_nonneg,sq_nonneghave 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)]
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.
uses
sq_nonneghave hcoef2 : 0 ≤ 4*A^2 - 2 := by nlinarith [sq_nonneg (A-1)]
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.
uses
mul_nonneghave hm := mul_nonneg (show 0 ≤ c-1 by linarith) hcoef have hn := mul_nonneg (show 0 ≤ C-c-1 by linarith) hcoef2
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.
rcases hgap with h | h · have hs := hsmall h subst a subst A nlinarith
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.
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
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.
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