AFTD Auto-Formalizing Theoretical Domains

parallel_mw_balancing_transfer_bound

theoremverified

For 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 2(B-A)(sd+t) ≤ Bd(s+t).

Statement

theorem parallel_mw_balancing_transfer_bound (s t A B d : ℝ)
    (hs : 0 ≤ s) (ht : 2*s ≤ t) (hA : 0 ≤ A) (hB : A ≤ B)
    (hcases : (d = 1 ∧ B = 2*A) ∨ (d = 2 ∧ B = 4*A) ∨
      (d = 3 ∧ B = 8*A) ∨ 4 ≤ d) :
    2*(B-A)*(s*d+t) ≤ B*d*(s+t)
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 proof proceeds by case analysis on the four alternatives for d and B. When d = 1 and B = 2A, both sides are algebraically identical. When (d, B) is (2, 4A) or (3, 8A), the difference between the right- and left-hand sides decomposes into nonnegative terms proportional to A(t - 2s) and As. Finally, when d ≥ 4, the difference rearranges as B(d(s + t) - 2(sd + t)) + 2A(sd + t), where the first factor is proved nonnegative by expressing it as (d - 2)(t - 2s) + (d - 4)s.

  1. The variables t and B are nonnegative: 0 ≤ t and 0 ≤ B.

    From the hypotheses 0 ≤ s and 2s ≤ t, linear arithmetic gives 0 ≤ t. Similarly, from 0 ≤ A and A ≤ B, linear arithmetic gives 0 ≤ B.

    lines 6–7

      have ht0 : 0 ≤ t := by linarith
      have hB0 : 0 ≤ B := by linarith
  2. The inequality holds in the first case, where d = 1 and B = 2A.

    We perform a case analysis on the four alternatives in hcases. In the first case, substituting d = 1 and B = 2A into 2(B - A)(sd + t) and Bd(s + t) yields 2A(s + t) on both sides. Ring normalization (ring_nf) reduces both sides to identical polynomials, and the inequality holds by reflexivity (le_rfl).

    lines 8–9

    uses le_rfl

      rcases hcases with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | hd
      · ring_nf; exact le_rfl
  3. The inequality holds in the second case, where d = 2 and B = 4A.

    Here d = 2 and B = 4A. The left-hand side expands to 12As + 6At and the right-hand side to 8As + 8At. The difference (RHS - LHS) is 2A(t - 2s). Since 0 ≤ A and 0 ≤ t - 2s, their product A(t - 2s) is nonnegative by mul_nonneg. Nonlinear arithmetic (nlinarith) uses this product to conclude that the inequality holds.

    lines 10–11

    uses mul_nonneg

      · have hh := mul_nonneg hA (show 0 ≤ t-2*s by linarith)
        nlinarith
  4. The inequality holds in the third case, where d = 3 and B = 8A.

    Here d = 3 and B = 8A. The left-hand side is 42As + 14At and the right-hand side is 24As + 24At. The difference (RHS - LHS) is 10At - 18As = 10A(t - 2s) + 2As. By mul_nonneg, both A(t - 2s) ≥ 0 and As ≥ 0 hold. Nonlinear arithmetic (nlinarith) concludes that the difference is nonnegative.

    lines 12–14

    uses mul_nonneg

      · have hh := mul_nonneg hA (show 0 ≤ t-2*s by linarith)
        have hh2 := mul_nonneg hA hs
        nlinarith
  5. When d ≥ 4, the factor d(s + t) - 2(sd + t) is nonnegative.

    The expression d(s + t) - 2(sd + t) can be rewritten as (d - 2)(t - 2s) + (d - 4)s. Since d ≥ 4, we have d - 2 ≥ 0 and d - 4 ≥ 0; since 2s ≤ t and 0 ≤ s, both t - 2s ≥ 0 and s ≥ 0 hold. By mul_nonneg, the products (d - 2)(t - 2s) and (d - 4)s are both nonnegative. Nonlinear arithmetic (nlinarith) verifies that their sum equals d(s + t) - 2(sd + t) and is nonnegative.

    lines 15–18

    uses mul_nonneg

      · have hsub : 0 ≤ d*(s+t)-2*(s*d+t) := by
          have h1 := mul_nonneg (show 0 ≤ d-2 by linarith) (show 0 ≤ t-2*s by linarith)
          have h2 := mul_nonneg (show 0 ≤ d-4 by linarith) hs
          nlinarith
  6. The inequality holds in the fourth case, where d ≥ 4.

    The difference Bd(s + t) - 2(B - A)(sd + t) rearranges into B(d(s + t) - 2(sd + t)) + 2A(sd + t). The first term is nonnegative by mul_nonneg from B ≥ 0 and the lemma hsub. The second term is nonnegative by mul_nonneg because A ≥ 0 and sd + t ≥ 0 (by positivity). Nonlinear arithmetic (nlinarith) combines these two nonnegative terms to complete the proof.

    lines 19–21

    uses mul_nonneg

        have h1 := mul_nonneg hB0 hsub
        have h2 := mul_nonneg hA (show 0 ≤ s*d+t by positivity)
        nlinarith
le_rfl
Every element in a preorder is less than or equal to itself: a ≤ a.
mul_nonneg
The product of two nonnegative elements in an ordered algebraic structure is nonnegative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * b.

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_transfer_bound (s t A B d : ℝ)    (hs : 0 ≤ s) (ht : 2*s ≤ t) (hA : 0 ≤ A) (hB : A ≤ B)    (hcases : (d = 1 ∧ B = 2*A) ∨ (d = 2 ∧ B = 4*A) ∨      (d = 3 ∧ B = 8*A) ∨ 4 ≤ d) :    2*(B-A)*(s*d+t) ≤ B*d*(s+t) := by  have ht0 : 0 ≤ t := by linarith  have hB0 : 0 ≤ B := by linarith  rcases hcases with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | hd  · ring_nf; exact le_rfl  · have hh := mul_nonneg hA (show 0 ≤ t-2*s by linarith)    nlinarith  · have hh := mul_nonneg hA (show 0 ≤ t-2*s by linarith)    have hh2 := mul_nonneg hA hs    nlinarith  · have hsub : 0 ≤ d*(s+t)-2*(s*d+t) := by      have h1 := mul_nonneg (show 0 ≤ d-2 by linarith) (show 0 ≤ t-2*s by linarith)      have h2 := mul_nonneg (show 0 ≤ d-4 by linarith) hs      nlinarith    have h1 := mul_nonneg hB0 hsub    have h2 := mul_nonneg hA (show 0 ≤ s*d+t by positivity)    nlinarith
See it in the graphDiscuss this resultChallenge it