AFTD Auto-Formalizing Theoretical Domains

bivalued_rounding_odd_mms_arithmetic

theoremverified

The odd-count MMS lower bound dominates the cost bound for a balanced bundle.

Statement

theorem bivalued_rounding_odd_mms_arithmetic(k h : ℕ) (d : ℝ) (hd : 0 ≤ d) :
    (k + 1 : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤
      (1 + d / 2) * ((k + 1 : ℝ) + d * ((h - k : ℕ) : ℝ))
Source
Elementary arithmetic for the bivalued two-agent rounding route in IN-570.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof reduces the real inequality to integer arithmetic on natural numbers. It first proves 2 * ⌊(h + 1) / 2⌋ ≤ k + 1 + 2 * (h - k) in ℕ using Presburger arithmetic and casts the result to ℝ. Multiplying by d ≥ 0 and combining with the non-negativity of d^2 * (h - k), expanding the right-hand side verifies the bound via non-linear arithmetic.

  1. In the real numbers, 2 * ⌊(h + 1) / 2⌋ ≤ k + 1 + 2 * (h - k).

    First, the inequality 2 * ((h + 1) / 2) ≤ k + 1 + 2 * (h - k) holds in ℕ: if h ≥ k, then k + 1 + 2 * (h - k) = 2 * h - k + 1 ≥ h + 1 ≥ 2 * ⌊(h + 1) / 2⌋; if h < k, truncated subtraction gives h - k = 0, so the right-hand side is k + 1, which strictly exceeds h ≥ 2 * ⌊(h + 1) / 2⌋. The `omega` tactic discharges this integer arithmetic inequality, which is then cast into ℝ using `exact_mod_cast`.

    lines 4–7

      have hc : 2 * ((h + 1) / 2) ≤ k + 1 + 2 * (h - k) := by omega
      have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤
          (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) := by
        exact_mod_cast hc
  2. The scaled difference d * ((k + 1 + 2 * (h - k)) - 2 * ⌊(h + 1) / 2⌋) is non-negative.

    Rearranging the previous real inequality via linear arithmetic (`linarith`) gives (k + 1 + 2 * (h - k)) - 2 * ⌊(h + 1) / 2⌋ ≥ 0. Since d ≥ 0 by hypothesis, `mul_nonneg` yields that the product of d and this non-negative difference is non-negative.

    lines 8–10

    uses mul_nonneg

      have harr : 0 ≤ (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) -
          2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith
      have hmul := mul_nonneg hd harr
  3. The quadratic term d * d * (h - k) is non-negative.

    Because d ≥ 0 and the cast of the natural number h - k into ℝ is non-negative, the product d * d * (h - k) is non-negative, as discharged by `positivity`.

    line 11

      have hsq : 0 ≤ d * d * ((h - k : ℕ) : ℝ) := by positivity
  4. (k + 1) + d * ⌊(h + 1) / 2⌋ ≤ (1 + d / 2) * ((k + 1) + d * (h - k)). automation

    Expanding the right-hand side yields (k + 1) + (d / 2) * (k + 1) + d * (h - k) + (d^2 / 2) * (h - k). Combining this expansion with the non-negativity of d * ((k + 1 + 2 * (h - k)) - 2 * ⌊(h + 1) / 2⌋) and d^2 * (h - k) establishes the theorem via non-linear arithmetic (`nlinarith`).

    line 12

      nlinarith
mul_nonneg
if a ≥ 0 and b ≥ 0, then a * b ≥ 0

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 bivalued_rounding_odd_mms_arithmetic(k h : ℕ) (d : ℝ) (hd : 0 ≤ d) :    (k + 1 : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤      (1 + d / 2) * ((k + 1 : ℝ) + d * ((h - k : ℕ) : ℝ)) := by  have hc : 2 * ((h + 1) / 2) ≤ k + 1 + 2 * (h - k) := by omega  have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤      (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) := by    exact_mod_cast hc  have harr : 0 ≤ (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) -      2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith  have hmul := mul_nonneg hd harr  have hsq : 0 ≤ d * d * ((h - k : ℕ) : ℝ) := by positivity  nlinarith
See it in the graphDiscuss this resultChallenge it