parallel_mw_ratio_decreasing_triple
For positive integers a, b, c with a + 2 ≤ b, replacing (a, b) with (a + 1, b - 1) strictly decreases the rational formula for parallel_mw_ratio 2.
Statement
theorem parallel_mw_ratio_decreasing_triple (a b c : ℕ) (ha : 0 < a) (hij : a + 2 ≤ b) (hc : 0 < c) :
6 * ((2 : ℝ) ^ (a + b + c) - 2 * ((2 : ℝ) ^ (a + 1) + (2 : ℝ) ^ (b - 1) + (2 : ℝ) ^ c) + 6) /
(((a + 1 : ℝ) * (b - 1) + (a + 1 : ℝ) * c + (b - 1 : ℝ) * c) ^ 2) <
6 * ((2 : ℝ) ^ (a + b + c) - 2 * ((2 : ℝ) ^ a + (2 : ℝ) ^ b + (2 : ℝ) ^ c) + 6) /
(((a : ℝ) * b + (a : ℝ) * c + (b : ℝ) * c) ^ 2)- Source
- step towards parallel_uniform_merino_welsh_strict_balancing_three_two
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- parallel_mw_balancing_base_polynomialA polynomial lower bound under natural-number-style lower bounds on real a and c and exponential proxies A and C.
- parallel_mw_balancing_transfer_boundFor nonnegative s and A, t at least 2s, B at least A and the stated four cases for d and B, the exact balancing increment satisfies…
- 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_balancing_strict_coreThe stated transfer and numerator bounds imply the strict cross-multiplied balancing inequality when d and N are positive.
- parallel_mw_two_pow_quadratic_boundFor every natural a, the real inequality a²+a ≤ 2·2^a holds.
- Used by 1
- parallel_uniform_merino_welsh_strict_balancing_three_twoFor any function q : Fin 3 → ℕ with 0 < q i for all i : Fin 3, and any indices i, j : Fin 3 with q i + 2 ≤ q j, parallel_mw_ratio 2…
The proof, explained
The theorem proves that transferring weight from coordinate b to coordinate a (with a + 2 ≤ b) strictly decreases the 3-variable Merino-Welsh ratio formula. Setting d = b - a - 1 ≥ 1, the denominators become (u + d)^2 and u^2 for u = a*b + a*c + b*c = s*d + t, while the numerators become 6*(N + 2*(B - A)) and 6*N with A = 2^a, B = 2^(b-1), C = 2^c, and N = 2^(a+b+c) - 2*(2^a + 2^b + 2^c) + 6. Clearing positive denominators reduces the statement to the core algebraic inequality 2*(B - A)*u^2 < N*(2*u*d + d^2), which is established by `parallel_mw_balancing_strict_core` using the bound B*(s+t) ≤ 2*N from `parallel_mw_balancing_numerator_bound`.
Introduce the displacement d = b - a - 1 ≥ 1 and define algebraic shorthands for the powers of 2, the linear coefficients, and the unnormalized numerator.
Since a + 2 ≤ b, setting d = b - a - 1 ensures 1 ≤ d, which gives b = a + d + 1 and b - 1 = a + d by linear integer arithmetic (`omega`). We abbreviate A = 2^a, B = 2^(b-1), C = 2^c, s = a + c, t = a*(a+1) + (2*a+1)*c, u = s*d + t, and N = 2*A*B*C - 2*A - 4*B - 2*C + 6.
set_option maxHeartbeats 1000000 in let d : ℕ := b-a-1 have hd : 1 ≤ d := by dsimp [d]; omega have hb : b = a+d+1 := by dsimp [d]; omega have hbm : b-1 = a+d := by dsimp [d]; omega let A : ℝ := 2^a let B : ℝ := 2^(b-1) let C : ℝ := 2^c let s : ℝ := (a : ℝ)+c let t : ℝ := (a : ℝ)*((a : ℝ)+1)+(2*(a : ℝ)+1)*(c : ℝ) let u : ℝ := s*d+t let N : ℝ := 2*A*B*C-2*A-4*B-2*C+6
Cast integer bounds to the reals, establish linear lower bounds a + 1 ≤ A and c + 1 ≤ C, and invoke the quadratic bound a^2 + a ≤ 2*A.
The positivity conditions a > 0, c > 0, and d ≥ 1 cast to 1 ≤ a, 1 ≤ c, and 1 ≤ d in ℝ, and positivity confirms 0 < A. For any natural number k, k < 2^k implies k + 1 ≤ 2^k via `Nat.succ_le_iff.mpr`, giving a + 1 ≤ A and c + 1 ≤ C. The quadratic bound a^2 + a ≤ 2*A is imported from `parallel_mw_two_pow_quadratic_bound`.
uses
Nat.succ_le_iff.mpr,parallel_mw_two_pow_quadratic_boundhave ha' : (1 : ℝ) ≤ a := by exact_mod_cast ha have hc' : (1 : ℝ) ≤ c := by exact_mod_cast hc have hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd have hApos : 0 < A := by dsimp [A]; positivity have hlin (k : ℕ) : (k : ℝ)+1 ≤ (2 : ℝ)^k := by have hn : k+1 ≤ 2^k := Nat.succ_le_iff.mpr k.lt_two_pow_self exact_mod_cast hn have hA : (a : ℝ)+1 ≤ A := hlin a have hC : (c : ℝ)+1 ≤ C := hlin c have hquad : (a : ℝ)^2+a ≤ 2*A := parallel_mw_two_pow_quadratic_bound a
Factor B as A * 2^d and deduce 2*A ≤ B.
Because b - 1 = a + d, the exponent rule `pow_add` gives B = 2^(b-1) = 2^a * 2^d = A * 2^d. Since d ≥ 1, monotonicity of powers (`Nat.pow_le_pow_right`) yields 2 ≤ 2^d, and nonlinear arithmetic concludes 2*A ≤ B.
uses
pow_add,Nat.pow_le_pow_righthave hBfactor : B=A*(2:ℝ)^d := by dsimp [A,B]; rw [hbm,pow_add] have hdPow : (2:ℝ) ≤ 2^d := by have hn : (2 : ℕ) ≤ 2^d := by calc 2=2^1 := by norm_num _ ≤ 2^d := Nat.pow_le_pow_right (by norm_num) hd exact_mod_cast hn have hB : 2*A ≤ B := by rw [hBfactor]; nlinarith
Establish the upper bound B*(a*(a+2) + 2*(a+1)*c) ≤ 2*N on the numerator.
Integer arithmetic gives the dichotomy a = 1 ∨ 2 ≤ a, and if a = 1 then A = 2^1 = 2. With all required bounds verified, `parallel_mw_balancing_numerator_bound` proves B*(a*(a+2) + 2*(a+1)*c) ≤ 2*N.
uses
parallel_mw_balancing_numerator_boundhave hgap : (a : ℝ) = 1 ∨ 2 ≤ (a : ℝ) := by have hNat : a = 1 ∨ 2 ≤ a := by omega rcases hNat with h | h · left; exact_mod_cast h · right; exact_mod_cast h have hsmall : (a : ℝ)=1 → A=2 := by intro h have : a=1 := by exact_mod_cast h subst a norm_num [A] have hbound0 := parallel_mw_balancing_numerator_bound (a:ℝ) (c:ℝ) A B C ha' hc' hA hC hquad hgap hsmall hB
Verify the side conditions s > 0, 2*s ≤ t, B*(s+t) ≤ 2*N, and N > 0.
Positivity gives s = a + c > 0. The difference t - 2*s expands to a*(a-1) + (2*a-1)*c, which is nonnegative as a sum of products of nonnegative factors via `mul_nonneg`, so 2*s ≤ t. A ring calculation identifies s + t with a*(a+2) + 2*(a+1)*c, translating the numerator bound to B*(s+t) ≤ 2*N. Since B > 0 and s + t > 0, we have 2*N ≥ B*(s+t) > 0, which implies N > 0.
uses
mul_nonneghave hs : 0 < s := by dsimp [s]; positivity have ht : 2*s ≤ t := by dsimp [s,t] have h1 := mul_nonneg (show 0 ≤ (a : ℝ)-1 by linarith) (show 0 ≤ (a : ℝ) by positivity) have h2 := mul_nonneg (show 0 ≤ 2*(a : ℝ)-1 by linarith) (show 0 ≤ (c : ℝ) by positivity) nlinarith have hst : s+t = (a:ℝ)*((a:ℝ)+2)+2*((a:ℝ)+1)*(c:ℝ) := by dsimp [s,t]; ring have hbound : B*(s+t) ≤ 2*N := by dsimp [N]; rw [hst]; exact hbound0 have hBpos : 0 < B := by dsimp [B]; positivity have hN : 0 < N := by have htpos : 0 < t := by linarith have hh : 0 < B*(s+t) := by positivity linarith
Analyze d into small cases and deduce the core inequality 2*(B-A)*u^2 < N*(2*u*d + d^2).
We case split on whether d ≤ 3. For d ∈ {1, 2, 3}, B = A * 2^d specializes to B = 2*A, B = 4*A, or B = 8*A (using `mul_comm`); otherwise 4 ≤ d. Feeding these cases and the side conditions (s > 0, 2*s ≤ t, 0 ≤ A ≤ B, 0 < d, 0 < N, and B*(s+t) ≤ 2*N) into `parallel_mw_balancing_strict_core` produces the strict inequality 2*(B-A)*(s*d+t)^2 < N*(2*(s*d+t)*d + d^2).
uses
mul_comm,parallel_mw_balancing_strict_corehave hcases : ((d:ℝ)=1 ∧ B=2*A) ∨ ((d:ℝ)=2 ∧ B=4*A) ∨ ((d:ℝ)=3 ∧ B=8*A) ∨ 4 ≤ (d:ℝ) := by by_cases hh : d ≤ 3 · interval_cases d · left; constructor <;> norm_num [hBfactor, mul_comm] · right; left; constructor <;> norm_num [hBfactor, mul_comm] · right; right; left; constructor <;> norm_num [hBfactor, mul_comm] · right; right; right; exact_mod_cast (show 4 ≤ d by omega) have hcore := parallel_mw_balancing_strict_core s t A B (d:ℝ) N hs ht hApos.le (by linarith) (by linarith) hN hcases hbound
Express the original denominators and power terms in terms of u, d, A, B, and C.
Substituting b = a + d + 1 shows that u = a*b + a*c + b*c, and the shifted denominator base (a+1)*(b-1) + (a+1)*c + (b-1)*c reduces to u + d. Positivity of u and u + d follows from the bounds on a, b, c, d. Using `pow_succ` and `pow_add`, the power terms rewrite as 2^b = 2*B, 2^(a+1) = 2*A, and 2^(a+b+c) = 2*A*B*C.
uses
pow_succ,pow_addhave hdcast : (b:ℝ)=(a:ℝ)+(d:ℝ)+1 := by exact_mod_cast hb have hu : u=(a:ℝ)*b+(a:ℝ)*c+(b:ℝ)*c := by dsimp [u,s,t]; rw [hdcast]; ring have hnew : (a+1:ℝ)*(b-1)+(a+1:ℝ)*c+(b-1:ℝ)*c = u+d := by rw [hu,hdcast]; ring have hu_pos : 0 < u := by rw [hu]; positivity have hnew_pos : 0 < u+(d:ℝ) := by linarith have hbp : (2:ℝ)^b=2*B := by dsimp [B]; conv_lhs => rw [show b=(b-1)+1 by omega]; rw [pow_succ, mul_comm] have hap : (2:ℝ)^(a+1)=2*A := by dsimp [A]; rw [pow_succ, mul_comm] have hprod : (2:ℝ)^(a+b+c)=2*A*B*C := by dsimp [A,B,C] rw [show a+b+c=a+(b-1)+c+1 by omega, pow_succ, pow_add, pow_add] ring
Clear denominators and conclude the strict inequality via nonlinear arithmetic.
Since u > 0 and u + d > 0, their squares are strictly positive by `sq_pos_of_pos`. We clear denominators using `div_lt_div_iff₀` and rewrite all expressions in terms of u, d, A, B, C. In these variables, the cross-multiplied goal is algebraically equivalent to multiplying the core inequality 2*(B-A)*u^2 < N*(2*u*d + d^2) by 6, which `nlinarith` closes directly.
uses
div_lt_div_iff₀,sq_pos_of_posrw [div_lt_div_iff₀ (sq_pos_of_pos (by rw [hnew]; exact hnew_pos)) (sq_pos_of_pos (by rw [←hu]; exact hu_pos))] rw [hnew, ←hu, hprod, hbp, hap] change 2*(B-A)*u^2 < N*(2*u*(d:ℝ)+(d:ℝ)^2) at hcore dsimp [N] at hcore nlinarith only [hcore]
Nat.succ_le_iff.mpr- For natural numbers, if m < n, then m + 1 ≤ n.
parallel_mw_two_pow_quadratic_bound- For any natural number a, a^2 + a ≤ 2 * 2^a.
pow_add- In any monoid (including the real numbers), a^(m + n) = a^m * a^n.
Nat.pow_le_pow_right- For n > 0, if i ≤ j then n^i ≤ n^j.
parallel_mw_balancing_numerator_bound- Under the real bounds 1 ≤ a, 1 ≤ c, a + 1 ≤ A, c + 1 ≤ C, a^2 + a ≤ 2*A, a = 1 ∨ 2 ≤ a, a = 1 → A = 2, and 2*A ≤ B, the bound B*(a*(a+2) + 2*(a+1)*c) ≤ 2*(2*A*B*C - 2*A - 4*B - 2*C + 6) holds.
mul_nonneg- The product of two nonnegative numbers is nonnegative.
mul_comm- Multiplication is commutative: a * b = b * a.
parallel_mw_balancing_strict_core- Given s > 0, 2*s ≤ t, 0 ≤ A ≤ B, d > 0, N > 0, the case split on (d, B/A), and B*(s+t) ≤ 2*N, the strict inequality 2*(B-A)*(s*d+t)^2 < N*(2*(s*d+t)*d + d^2) holds.
pow_succ- In any monoid, a^(n + 1) = a^n * a.
div_lt_div_iff₀- For positive denominators b and d, a / b < c / d is equivalent to a * d < c * b.
sq_pos_of_pos- If a real number a is strictly positive, then its square a^2 is strictly positive.
- The proof increases Lean's heartbeat limit (`set_option maxHeartbeats 1000000`) on line 7 because nonlinear arithmetic verification and case exhaustion require substantial computation.
- The core analytic and algebraic reductions are encapsulated in the two helper lemmas `parallel_mw_balancing_numerator_bound` and `parallel_mw_balancing_strict_core`, proved earlier in the development.
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.
/-- Strict decrease of the 3-variable Merino-Welsh ratio formula under transferring weight from a larger coordinate to a smaller coordinate. -/theorem parallel_mw_ratio_decreasing_triple (a b c : ℕ) (ha : 0 < a) (hij : a + 2 ≤ b) (hc : 0 < c) : 6 * ((2 : ℝ) ^ (a + b + c) - 2 * ((2 : ℝ) ^ (a + 1) + (2 : ℝ) ^ (b - 1) + (2 : ℝ) ^ c) + 6) / (((a + 1 : ℝ) * (b - 1) + (a + 1 : ℝ) * c + (b - 1 : ℝ) * c) ^ 2) < 6 * ((2 : ℝ) ^ (a + b + c) - 2 * ((2 : ℝ) ^ a + (2 : ℝ) ^ b + (2 : ℝ) ^ c) + 6) / (((a : ℝ) * b + (a : ℝ) * c + (b : ℝ) * c) ^ 2) := by set_option maxHeartbeats 1000000 in let d : ℕ := b-a-1 have hd : 1 ≤ d := by dsimp [d]; omega have hb : b = a+d+1 := by dsimp [d]; omega have hbm : b-1 = a+d := by dsimp [d]; omega let A : ℝ := 2^a let B : ℝ := 2^(b-1) let C : ℝ := 2^c let s : ℝ := (a : ℝ)+c let t : ℝ := (a : ℝ)*((a : ℝ)+1)+(2*(a : ℝ)+1)*(c : ℝ) let u : ℝ := s*d+t let N : ℝ := 2*A*B*C-2*A-4*B-2*C+6 have ha' : (1 : ℝ) ≤ a := by exact_mod_cast ha have hc' : (1 : ℝ) ≤ c := by exact_mod_cast hc have hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd have hApos : 0 < A := by dsimp [A]; positivity have hlin (k : ℕ) : (k : ℝ)+1 ≤ (2 : ℝ)^k := by have hn : k+1 ≤ 2^k := Nat.succ_le_iff.mpr k.lt_two_pow_self exact_mod_cast hn have hA : (a : ℝ)+1 ≤ A := hlin a have hC : (c : ℝ)+1 ≤ C := hlin c have hquad : (a : ℝ)^2+a ≤ 2*A := parallel_mw_two_pow_quadratic_bound a have hBfactor : B=A*(2:ℝ)^d := by dsimp [A,B]; rw [hbm,pow_add] have hdPow : (2:ℝ) ≤ 2^d := by have hn : (2 : ℕ) ≤ 2^d := by calc 2=2^1 := by norm_num _ ≤ 2^d := Nat.pow_le_pow_right (by norm_num) hd exact_mod_cast hn have hB : 2*A ≤ B := by rw [hBfactor]; nlinarith have hgap : (a : ℝ) = 1 ∨ 2 ≤ (a : ℝ) := by have hNat : a = 1 ∨ 2 ≤ a := by omega rcases hNat with h | h · left; exact_mod_cast h · right; exact_mod_cast h have hsmall : (a : ℝ)=1 → A=2 := by intro h have : a=1 := by exact_mod_cast h subst a norm_num [A] have hbound0 := parallel_mw_balancing_numerator_bound (a:ℝ) (c:ℝ) A B C ha' hc' hA hC hquad hgap hsmall hB have hs : 0 < s := by dsimp [s]; positivity have ht : 2*s ≤ t := by dsimp [s,t] have h1 := mul_nonneg (show 0 ≤ (a : ℝ)-1 by linarith) (show 0 ≤ (a : ℝ) by positivity) have h2 := mul_nonneg (show 0 ≤ 2*(a : ℝ)-1 by linarith) (show 0 ≤ (c : ℝ) by positivity) nlinarith have hst : s+t = (a:ℝ)*((a:ℝ)+2)+2*((a:ℝ)+1)*(c:ℝ) := by dsimp [s,t]; ring have hbound : B*(s+t) ≤ 2*N := by dsimp [N]; rw [hst]; exact hbound0 have hBpos : 0 < B := by dsimp [B]; positivity have hN : 0 < N := by have htpos : 0 < t := by linarith have hh : 0 < B*(s+t) := by positivity linarith have hcases : ((d:ℝ)=1 ∧ B=2*A) ∨ ((d:ℝ)=2 ∧ B=4*A) ∨ ((d:ℝ)=3 ∧ B=8*A) ∨ 4 ≤ (d:ℝ) := by by_cases hh : d ≤ 3 · interval_cases d · left; constructor <;> norm_num [hBfactor, mul_comm] · right; left; constructor <;> norm_num [hBfactor, mul_comm] · right; right; left; constructor <;> norm_num [hBfactor, mul_comm] · right; right; right; exact_mod_cast (show 4 ≤ d by omega) have hcore := parallel_mw_balancing_strict_core s t A B (d:ℝ) N hs ht hApos.le (by linarith) (by linarith) hN hcases hbound have hdcast : (b:ℝ)=(a:ℝ)+(d:ℝ)+1 := by exact_mod_cast hb have hu : u=(a:ℝ)*b+(a:ℝ)*c+(b:ℝ)*c := by dsimp [u,s,t]; rw [hdcast]; ring have hnew : (a+1:ℝ)*(b-1)+(a+1:ℝ)*c+(b-1:ℝ)*c = u+d := by rw [hu,hdcast]; ring have hu_pos : 0 < u := by rw [hu]; positivity have hnew_pos : 0 < u+(d:ℝ) := by linarith have hbp : (2:ℝ)^b=2*B := by dsimp [B]; conv_lhs => rw [show b=(b-1)+1 by omega]; rw [pow_succ, mul_comm] have hap : (2:ℝ)^(a+1)=2*A := by dsimp [A]; rw [pow_succ, mul_comm] have hprod : (2:ℝ)^(a+b+c)=2*A*B*C := by dsimp [A,B,C] rw [show a+b+c=a+(b-1)+c+1 by omega, pow_succ, pow_add, pow_add] ring rw [div_lt_div_iff₀ (sq_pos_of_pos (by rw [hnew]; exact hnew_pos)) (sq_pos_of_pos (by rw [←hu]; exact hu_pos))] rw [hnew, ←hu, hprod, hbp, hap] change 2*(B-A)*u^2 < N*(2*u*(d:ℝ)+(d:ℝ)^2) at hcore dsimp [N] at hcore nlinarith only [hcore]