oneshot_drf_bound_le_five_sqrt
For every natural number D ≥ 1 and every non-negative real number opt, (4 * Real.sqrt D + 1) * opt ≤ 5 * Real.sqrt D * opt.
Statement
theorem oneshot_drf_bound_le_five_sqrt (D : ℕ) (hD : 1 ≤ D) (opt : ℝ) (hopt : 0 ≤ opt) : (4 * Real.sqrt (D : ℝ) + 1) * opt ≤ 5 * Real.sqrt (D : ℝ) * opt- Source
- arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Theorem 1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every natural number $D$ with $1 \le D$ and every real number $\mathrm{opt}$ with $0 \le \mathrm{opt}$, $(4 \sqrt{D} + 1) \cdot \mathrm{opt} \le 5 \sqrt{D} \cdot \mathrm{opt}$, where $\sqrt{D}$ denotes the real square root of $D$ (cast to $\mathbb{R}$).
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 proof first establishes that 1 ≤ Real.sqrt D from the assumption D ≥ 1. Combining this with 4 * Real.sqrt D via linear arithmetic gives 4 * Real.sqrt D + 1 ≤ 5 * Real.sqrt D. Finally, multiplying both sides by the non-negative factor opt yields the desired result.
1 ≤ Real.sqrt D
Since D ≥ 1 as natural numbers, its coercion to the real numbers also satisfies 1 ≤ D. By Real.one_le_sqrt, this is equivalent to 1 ≤ Real.sqrt D.
uses
Real.one_le_sqrthave hsqrt : (1 : ℝ) ≤ Real.sqrt (D : ℝ) := by rw [Real.one_le_sqrt] exact_mod_cast hD
4 * Real.sqrt D + 1 ≤ 5 * Real.sqrt D
Using 1 ≤ Real.sqrt D, linear arithmetic bounds 4 * Real.sqrt D + 1 by 4 * Real.sqrt D + Real.sqrt D = 5 * Real.sqrt D.
have h1 : 4 * Real.sqrt (D : ℝ) + 1 ≤ 5 * Real.sqrt (D : ℝ) := by linarith
(4 * Real.sqrt D + 1) * opt ≤ 5 * Real.sqrt D * opt
Multiplying both sides of the inequality 4 * Real.sqrt D + 1 ≤ 5 * Real.sqrt D by the non-negative real number opt (using mul_le_mul_of_nonneg_right) produces the desired inequality, which linarith uses to close the goal.
uses
mul_le_mul_of_nonneg_righthave h2 := mul_le_mul_of_nonneg_right h1 hopt linarith
Real.one_le_sqrt- For any real number x, 1 ≤ √x if and only if 1 ≤ x.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality b ≤ c by a non-negative quantity a preserves the inequality, giving b * a ≤ c * a.
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.
/-- Arithmetic simplification bounding 4*sqrt(D) + 1 by 5*sqrt(D) when D ≥ 1. -/theorem oneshot_drf_bound_le_five_sqrt (D : ℕ) (hD : 1 ≤ D) (opt : ℝ) (hopt : 0 ≤ opt) : (4 * Real.sqrt (D : ℝ) + 1) * opt ≤ 5 * Real.sqrt (D : ℝ) * opt := by have hsqrt : (1 : ℝ) ≤ Real.sqrt (D : ℝ) := by rw [Real.one_le_sqrt] exact_mod_cast hD have h1 : 4 * Real.sqrt (D : ℝ) + 1 ≤ 5 * Real.sqrt (D : ℝ) := by linarith have h2 := mul_le_mul_of_nonneg_right h1 hopt linarith