drf_competitive_ratio_lower_bound
For every natural number D with 1 ≤ D and every real number ρ, if for all natural numbers m with 1 ≤ m we have drf_prop1_alg D m ≤ ρ * drf_prop1_opt_bound D m, then 1 + Real.sqrt (D : ℝ) ≤ ρ.
Statement
theorem drf_competitive_ratio_lower_bound (D : ℕ) (hD : 1 ≤ D) (ρ : ℝ) (hρ : ∀ m : ℕ, 1 ≤ m → drf_prop1_alg D m ≤ ρ * drf_prop1_opt_bound D m) : 1 + Real.sqrt (D : ℝ) ≤ ρ- Formalizes
- arXiv:2611.07905 Proposition 1
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- drf_prop1_ratio_tendstoFor every natural number D with 1 ≤ D, the sequence
fun m : ℕ => drf_prop1_ratio D mconverges to1 + Real.sqrt (D : ℝ)along… - drf_prop1_algGiven two natural numbers D and m,
drf_prop1_alg D mis defined as the real number… - drf_prop1_opt_boundFor two natural numbers D and m,
drf_prop1_opt_bound D mis defined as the real number… - drf_prop1_kIn the lower-bound instance with D resources and parameter m, the number of shared jobs demanding all resources is k = floor(m * sqrt(D)).
- drf_prop1_ratioFor two natural numbers D and m,
drf_prop1_ratio D mis defined as the real numberdrf_prop1_alg D m / drf_prop1_opt_bound D m.
- drf_prop1_ratio_tendstoFor every natural number D with 1 ≤ D, the sequence
Read back from the Lean
For any natural number $D \ge 1$ and any real number $\rho$, if for all natural numbers $m \ge 1$, $\text{drf\_prop1\_alg}(D, m) \le \rho \cdot \text{drf\_prop1\_opt\_bound}(D, m)$, then $1 + \sqrt{D} \le \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 lower bound 1 + √D ≤ ρ is proved by taking the limit of the competitive ratio as the parameter m tends to infinity. By a previously proved convergence theorem, the ratio of the algorithm's objective bound to the optimal bound converges to 1 + √D. Since the ratio is bounded above by ρ for every m ≥ 1, passing to the limit establishes that 1 + √D ≤ ρ.
It suffices to show that drf_prop1_ratio D m ≤ ρ holds eventually as m tends to infinity.
By the limit theorem drf_prop1_ratio_tendsto, the ratio drf_prop1_ratio D m converges to 1 + √D as m → ∞. By le_of_tendsto, if the terms of a convergent sequence are eventually bounded above by ρ, then their limit is also at most ρ.
uses
drf_prop1_ratio_tendsto,le_of_tendstohave htend := drf_prop1_ratio_tendsto D hD refine le_of_tendsto htend ?_
For an arbitrary m ≥ 1, it suffices to show that drf_prop1_alg D m / drf_prop1_opt_bound D m ≤ ρ.
The condition m ≥ 1 holds eventually as m → ∞ by Filter.eventually_ge_atTop. Unfolding the definition of drf_prop1_ratio, the expression to bound is the quotient drf_prop1_alg D m / drf_prop1_opt_bound D m.
uses
Filter.eventually_ge_atTopfilter_upwards [Filter.eventually_ge_atTop 1] with m hm dsimp [drf_prop1_ratio]
The denominator drf_prop1_opt_bound D m is strictly positive.
Expanding drf_prop1_opt_bound D m reveals a sum of terms involving D, m, and drf_prop1_k D m. Since D ≥ 1 and m ≥ 1, both D and m are strictly positive real numbers, and the positivity tactic confirms that the entire sum is strictly positive.
have hopt : 0 < drf_prop1_opt_bound D m := by dsimp [drf_prop1_opt_bound] have : (0 : ℝ) < (D : ℝ) := by positivity have : (0 : ℝ) < (m : ℝ) := by positivity positivity
The ratio drf_prop1_alg D m / drf_prop1_opt_bound D m is at most ρ.
Because drf_prop1_opt_bound D m > 0, dividing by it preserves the inequality order via div_le_iff₀. The goal is thus equivalent to drf_prop1_alg D m ≤ ρ * drf_prop1_opt_bound D m, which is directly given by the hypothesis hρ for m ≥ 1.
uses
div_le_iff₀exact (div_le_iff₀ hopt).mpr (hρ m hm)
drf_prop1_ratio_tendsto- For any natural number D ≥ 1, the ratio drf_prop1_ratio D m converges to 1 + √D as m tends to infinity.
le_of_tendsto- If a sequence or function converges to a limit a and is eventually bounded above by b, then a ≤ b.
Filter.eventually_ge_atTop- For any element a in a preorder, x ≥ a holds eventually as x tends to infinity atTop.
div_le_iff₀- For any element c > 0 in a group with zero and partial order, b / c ≤ a if and only if b ≤ a * c.
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.
/-- Lower bound of 1 + sqrt(D) on the competitive ratio of Dominant Resource Fairness (Proposition 1, arXiv:2611.07905). -/theorem drf_competitive_ratio_lower_bound (D : ℕ) (hD : 1 ≤ D) (ρ : ℝ) (hρ : ∀ m : ℕ, 1 ≤ m → drf_prop1_alg D m ≤ ρ * drf_prop1_opt_bound D m) : 1 + Real.sqrt (D : ℝ) ≤ ρ := by have htend := drf_prop1_ratio_tendsto D hD refine le_of_tendsto htend ?_ filter_upwards [Filter.eventually_ge_atTop 1] with m hm dsimp [drf_prop1_ratio] have hopt : 0 < drf_prop1_opt_bound D m := by dsimp [drf_prop1_opt_bound] have : (0 : ℝ) < (D : ℝ) := by positivity have : (0 : ℝ) < (m : ℝ) := by positivity positivity exact (div_le_iff₀ hopt).mpr (hρ m hm)