bivalued_rounding_odd_mms_arithmetic
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
- 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 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.
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`.
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
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.
uses
mul_nonneghave harr : 0 ≤ (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith have hmul := mul_nonneg hd harr
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`.
have hsq : 0 ≤ d * d * ((h - k : ℕ) : ℝ) := by positivity
(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`).
nlinarith
mul_nonneg- if a ≥ 0 and b ≥ 0, then a * b ≥ 0
- In Lean, division on natural numbers `(h + 1) / 2` denotes integer floor division ⌊(h + 1) / 2⌋, and natural number subtraction `h - k` truncates to 0 when h < k.
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_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