AFTD Auto-Formalizing Theoretical Domains

bivalued_rounding_even_mms_arithmetic

theoremverified

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

Statement

theorem bivalued_rounding_even_mms_arithmetic(k h : ℕ) (d : ℝ) (hk : 1 ≤ k) (hd : 0 ≤ d) :
    (k : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤
      (1 + d / 2) * ((k : ℝ) + d * (h : ℝ) / 2)
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 inequality is proved by expanding the difference between the right-hand side and the left-hand side into $\frac{1}{2} d (k + h - 2 \lfloor (h + 1) / 2 \rfloor) + \frac{1}{4} d^2 h$. From the integer division bound $2 \lfloor (h + 1) / 2 \rfloor \le h + 1$ and the hypothesis $k \ge 1$, the first term is non-negative when multiplied by $d \ge 0$. Together with the non-negativity of $d^2 h$, non-linear arithmetic verifies that the difference is non-negative.

  1. In the real numbers, $2 \lfloor (h + 1) / 2 \rfloor \le h + 1$ and $1 \le k$.

    By properties of integer division, $2 \lfloor (h + 1) / 2 \rfloor \le h + 1$ holds in $\mathbb{N}$ (verified by `omega`). Casting this inequality and the hypothesis $1 \le k$ into $\mathbb{R}$ establishes the bounds over the reals.

    lines 4–7

      have hc : 2 * ((h + 1) / 2) ≤ h + 1 := by omega
      have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤ (h : ℝ) + 1 := by
        exact_mod_cast hc
      have hkr : (1 : ℝ) ≤ k := by exact_mod_cast hk
  2. $0 \le k + h - 2 \lfloor (h + 1) / 2 \rfloor$.

    Combining the real inequalities $2 \lfloor (h + 1) / 2 \rfloor \le h + 1$ and $1 \le k$, linear arithmetic shows that $k + h - 2 \lfloor (h + 1) / 2 \rfloor \ge 1 + h - (h + 1) = 0$.

    line 8

      have harr : 0 ≤ (k : ℝ) + (h : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith
  3. $0 \le d (k + h - 2 \lfloor (h + 1) / 2 \rfloor)$.

    Since $d \ge 0$ by assumption and $k + h - 2 \lfloor (h + 1) / 2 \rfloor \ge 0$, their product is non-negative by `mul_nonneg`.

    line 9

    uses mul_nonneg

      have hmul := mul_nonneg hd harr
  4. $0 \le d^2 h$.

    The product $d^2 h$ is non-negative because $h$ is a natural number ($h \ge 0$) and $d^2 \ge 0$.

    line 10

      have hsq : 0 ≤ d * d * (h : ℝ) := by positivity
  5. $k + d \lfloor (h + 1) / 2 \rfloor \le (1 + d / 2)(k + d h / 2)$.

    Expanding the difference $(1 + d / 2)(k + d h / 2) - (k + d \lfloor (h + 1) / 2 \rfloor)$ yields $\frac{1}{2} d (k + h - 2 \lfloor (h + 1) / 2 \rfloor) + \frac{1}{4} d^2 h$. Because both constituent terms are non-negative, non-linear arithmetic confirms the inequality.

    line 11

      nlinarith
mul_nonneg
The product of two non-negative numbers is non-negative: if $0 \le a$ and $0 \le b$, then $0 \le 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 bivalued_rounding_even_mms_arithmetic(k h : ℕ) (d : ℝ) (hk : 1 ≤ k) (hd : 0 ≤ d) :    (k : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤      (1 + d / 2) * ((k : ℝ) + d * (h : ℝ) / 2) := by  have hc : 2 * ((h + 1) / 2) ≤ h + 1 := by omega  have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤ (h : ℝ) + 1 := by    exact_mod_cast hc  have hkr : (1 : ℝ) ≤ k := by exact_mod_cast hk  have harr : 0 ≤ (k : ℝ) + (h : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith  have hmul := mul_nonneg hd harr  have hsq : 0 ≤ d * d * (h : ℝ) := by positivity  nlinarith
See it in the graphDiscuss this resultChallenge it