bivalued_rounding_even_mms_arithmetic
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
- two_agent_common_bivalued_safe_partitionFor any ratio r with 1 ≤ r ≤ 2, any number of chores m, and any two-agent chore cost profile c satisfying is_scaled_bivalued_chores r c,…
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.
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.
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
$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$.
have harr : 0 ≤ (k : ℝ) + (h : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith
$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`.
uses
mul_nonneghave hmul := mul_nonneg hd harr$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$.
have hsq : 0 ≤ d * d * (h : ℝ) := by positivity
$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.
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
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.
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