AFTD Auto-Formalizing Theoretical Domains

parallel_mw_ratio_decreasing_triple

theoremverified

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
Used by 1

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

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

    lines 7–18

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

    lines 19–28

    uses Nat.succ_le_iff.mpr, parallel_mw_two_pow_quadratic_bound

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

    lines 29–35

    uses pow_add, Nat.pow_le_pow_right

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

    lines 36–46

    uses parallel_mw_balancing_numerator_bound

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

    lines 47–59

    uses mul_nonneg

        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
  6. 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).

    lines 60–68

    uses mul_comm, parallel_mw_balancing_strict_core

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

    lines 69–79

    uses pow_succ, pow_add

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

    lines 80–84

    uses div_lt_div_iff₀, sq_pos_of_pos

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

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

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