ratio_add_le_max_of_nonneg
For real numbers A, C, D, rho with 0 < C and 0 ≤ D, (A + rho * D) / (C + D) ≤ max (A / C) rho.
Statement
theorem ratio_add_le_max_of_nonneg (A C D rho : ℝ) (hC : 0 < C) (hD : 0 ≤ D) :
(A + rho * D) / (C + D) ≤ max (A / C) rho- Source
- arXiv:2610.29037 Lemma 4.2 proof step (5)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratioLet n be a natural number and let x, a, z : Fin n → ℝ with x = a + z, where a and z have non-negative coordinates (∀ i, 0 ≤ a i and ∀ i, 0…
Read back from the Lean
For all real numbers $A$, $C$, $D$, and $\rho$, if $C > 0$ and $D \ge 0$, then $(A + \rho D) / (C + D) \le \max(A / C, \rho)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by clearing the denominator and bounding each term of the numerator separately. Since $C > 0$ and $D \ge 0$, the denominator $C + D$ is strictly positive, reducing the claim to $A + \rho D \le \max(A / C, \rho) \cdot (C + D)$. Setting $M = \max(A / C, \rho)$, the definition of the maximum gives $A \le M \cdot C$ and $\rho D \le M \cdot D$. Adding these two inequalities and factoring out $M$ completes the proof.
It suffices to show that $A + \rho D \le \max(A / C, \rho) \cdot (C + D)$.
Since $C > 0$ and $D \ge 0$, their sum $C + D$ is strictly positive (`add_pos_of_pos_of_nonneg`). Because this denominator is positive, clearing it via `div_le_iff₀` reduces the ratio inequality $(A + \rho D) / (C + D) \le \max(A / C, \rho)$ to $A + \rho D \le \max(A / C, \rho) \cdot (C + D)$.
uses
add_pos_of_pos_of_nonneg,div_le_iff₀have hCD : 0 < C + D := add_pos_of_pos_of_nonneg hC hD rw [div_le_iff₀ hCD]
$A \le \max(A / C, \rho) \cdot C$ and $\rho D \le \max(A / C, \rho) \cdot D$.
Let $M = \max(A / C, \rho)$. By the definition of the maximum, $A / C \le M$ (`le_max_left`) and $\rho \le M$ (`le_max_right`). Since $C > 0$, multiplying $A / C \le M$ by $C$ gives $A \le M \cdot C$ (`div_le_iff₀`). Since $D \ge 0$, multiplying $\rho \le M$ by $D$ on the right preserves the inequality (`mul_le_mul_of_nonneg_right`), yielding $\rho D \le M \cdot D$.
uses
le_max_left,le_max_right,div_le_iff₀,mul_le_mul_of_nonneg_righthave h1 : A / C ≤ max (A / C) rho := le_max_left (A / C) rho have h2 : rho ≤ max (A / C) rho := le_max_right (A / C) rho have h3 : A ≤ max (A / C) rho * C := (div_le_iff₀ hC).mp h1 have h4 : rho * D ≤ max (A / C) rho * D := mul_le_mul_of_nonneg_right h2 hD
$A + \rho D \le \max(A / C, \rho) \cdot (C + D)$.
Summing the two bounds $A \le M \cdot C$ and $\rho D \le M \cdot D$ gives $A + \rho D \le M \cdot C + M \cdot D$ (`add_le_add`). Distributivity (handled by `ring`) factors the right-hand side into $M \cdot (C + D)$, which establishes the target inequality.
uses
add_le_addcalc A + rho * D ≤ max (A / C) rho * C + max (A / C) rho * D := add_le_add h3 h4 _ = max (A / C) rho * (C + D) := by ring
add_pos_of_pos_of_nonneg- The sum of a strictly positive number and a non-negative number is strictly positive ($a > 0$ and $b \ge 0$ implies $a + b > 0$).
div_le_iff₀- For a strictly positive denominator $c > 0$, $b / c \le a$ if and only if $b \le a \cdot c$.
le_max_left- An element is at most the maximum of itself and another element ($a \le \max(a, b)$).
le_max_right- An element is at most the maximum of another element and itself ($b \le \max(a, b)$).
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality by a non-negative number preserves the inequality ($b \le c$ and $0 \le a$ implies $b \cdot a \le c \cdot a$).
add_le_add- Adding two inequalities preserves the order ($a \le b$ and $c \le d$ implies $a + c \le b + d$).
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.
/-- Mediant ratio bound: (A + rho * D) / (C + D) <= max (A / C) rho for C > 0 and D >= 0. -/theorem ratio_add_le_max_of_nonneg (A C D rho : ℝ) (hC : 0 < C) (hD : 0 ≤ D) : (A + rho * D) / (C + D) ≤ max (A / C) rho := by have hCD : 0 < C + D := add_pos_of_pos_of_nonneg hC hD rw [div_le_iff₀ hCD] have h1 : A / C ≤ max (A / C) rho := le_max_left (A / C) rho have h2 : rho ≤ max (A / C) rho := le_max_right (A / C) rho have h3 : A ≤ max (A / C) rho * C := (div_le_iff₀ hC).mp h1 have h4 : rho * D ≤ max (A / C) rho * D := mul_le_mul_of_nonneg_right h2 hD calc A + rho * D ≤ max (A / C) rho * C + max (A / C) rho * D := add_le_add h3 h4 _ = max (A / C) rho * (C + D) := by ring