drf_prop1_ratio_tendsto
For every natural number D with 1 ≤ D, the sequence fun m : ℕ => drf_prop1_ratio D m converges to 1 + Real.sqrt (D : ℝ) along Filter.atTop.
Statement
theorem drf_prop1_ratio_tendsto (D : ℕ) (hD : 1 ≤ D) : Filter.Tendsto (fun m : ℕ => drf_prop1_ratio D m) Filter.atTop (nhds (1 + Real.sqrt (D : ℝ)))
- Formalizes
- arXiv:2611.07905 Proposition 1
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_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,
- Used by 1
- drf_competitive_ratio_lower_boundFor 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 ≤ ρ *…
Read back from the Lean
For every natural number $D$ satisfying $1 \le D$, the function mapping $m : \mathbb{N}$ to $\text{drf\_prop1\_ratio}(D, m)$ tends to $1 + \sqrt{D}$ (with respect to the standard topology on $\mathbb{R}$) as $m$ tends to infinity along Filter.atTop.
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
We first show k(D, m)/m converges to sqrt(D) using the squeeze theorem on the floor function bounds. Then, dividing the algorithm cost and optimal bound by m^2 expresses the ratio in terms of k(D, m)/m and 1/m. Applying limit laws and simplifying the algebraic expression proves the ratio converges to 1 + sqrt(D).
k/m tends to sqrt D
By the squeeze theorem, k/m converges to sqrt D.
set c := Real.sqrt (D : ℝ) have hc : 0 ≤ c := Real.sqrt_nonneg _ have h_lower : Filter.Tendsto (fun m : ℕ => c - (m : ℝ)⁻¹) Filter.atTop (nhds c) := by have h := (tendsto_inv_atTop_nhds_zero_nat (𝕜 := ℝ)).const_sub c simpa using h have h_upper : Filter.Tendsto (fun _ : ℕ => c) Filter.atTop (nhds c) := tendsto_const_nhds refine tendsto_of_tendsto_of_tendsto_of_le_of_le' h_lower h_upper ?_ ?_ · filter_upwards [Filter.eventually_gt_atTop 0] with m hm have hm_pos : 0 < (m : ℝ) := Nat.cast_pos.mpr hm dsimp [drf_prop1_k] have h1 := Nat.sub_one_lt_floor ((m : ℝ) * c) rw [inv_eq_one_div] have : c - 1 / (m : ℝ) = ((m : ℝ) * c - 1) / (m : ℝ) := by rw [sub_div, mul_div_cancel_left₀ c hm_pos.ne'] rw [this] exact (div_le_div_iff_of_pos_right hm_pos).mpr h1.le · filter_upwards [Filter.eventually_gt_atTop 0] with m hm have hm_pos : 0 < (m : ℝ) := Nat.cast_pos.mpr hm dsimp [drf_prop1_k] have h2 : (Nat.floor ((m : ℝ) * c) : ℝ) ≤ (m : ℝ) * c := Nat.floor_le (mul_nonneg hm_pos.le hc) rw [div_le_iff₀ hm_pos] linarith
ratio tends to 1 + sqrt D
By algebraic limit laws, the ratio tends to 1 + sqrt D.
uses
Filter.Tendsto.divset u := fun m : ℕ => (drf_prop1_k D m : ℝ) / (m : ℝ) set v := fun m : ℕ => 1 / (m : ℝ) have hu : Filter.Tendsto u Filter.atTop (nhds (Real.sqrt (D : ℝ))) := drf_prop1_ratio_tendsto_k_div D have hv : Filter.Tendsto v Filter.atTop (nhds (0 : ℝ)) := by have h : Filter.Tendsto (fun m : ℕ => (m : ℝ)⁻¹) Filter.atTop (nhds (0 : ℝ)) := tendsto_inv_atTop_nhds_zero_nat (𝕜 := ℝ) simpa [v, one_div] using h set num := fun m : ℕ => ((D : ℝ) + u m) * (1 + u m) set den := fun m : ℕ => (D : ℝ) * (1 + v m) / 2 + u m + u m * (u m + v m) / 2 have hnum : Filter.Tendsto num Filter.atTop (nhds (((D : ℝ) + Real.sqrt (D : ℝ)) * (1 + Real.sqrt (D : ℝ)))) := by exact ((tendsto_const_nhds (x := (D : ℝ))).add hu).mul ((tendsto_const_nhds (x := (1 : ℝ))).add hu) have hden_raw : Filter.Tendsto den Filter.atTop (nhds ((D : ℝ) * (1 + 0) / 2 + Real.sqrt (D : ℝ) + Real.sqrt (D : ℝ) * (Real.sqrt (D : ℝ) + 0) / 2)) := by refine (((tendsto_const_nhds (x := (D : ℝ))).mul ((tendsto_const_nhds (x := (1 : ℝ))).add hv)).div_const (2 : ℝ)).add hu |>.add ?_ exact (hu.mul (hu.add hv)).div_const (2 : ℝ) have hden_eq : (D : ℝ) * (1 + 0) / 2 + Real.sqrt (D : ℝ) + Real.sqrt (D : ℝ) * (Real.sqrt (D : ℝ) + 0) / 2 = (D : ℝ) + Real.sqrt (D : ℝ) := by have hsq : Real.sqrt (D : ℝ) * Real.sqrt (D : ℝ) = (D : ℝ) := Real.mul_self_sqrt (Nat.cast_nonneg D) linear_combination 1/2 * hsq rw [hden_eq] at hden_raw have hden_ne_zero : (D : ℝ) + Real.sqrt (D : ℝ) ≠ 0 := by have : 1 ≤ (D : ℝ) := by exact_mod_cast hD positivity have hdiv := hnum.div hden_raw hden_ne_zero have hdiv_simp : (((D : ℝ) + Real.sqrt (D : ℝ)) * (1 + Real.sqrt (D : ℝ))) / ((D : ℝ) + Real.sqrt (D : ℝ)) = 1 + Real.sqrt (D : ℝ) := mul_div_cancel_left₀ (1 + Real.sqrt (D : ℝ)) hden_ne_zero rw [hdiv_simp] at hdiv refine Filter.Tendsto.congr' ?_ hdiv filter_upwards [Filter.eventually_ge_atTop 1] with m hm dsimp [num, den, u, v, drf_prop1_ratio, drf_prop1_alg, drf_prop1_opt_bound] have hm_pos : (m : ℝ) ≠ 0 := by have : 0 < m := hm positivity field_simp
Filter.Tendsto.div- limit of quotient
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.
lemma drf_prop1_ratio_tendsto_k_div (D : ℕ) : Filter.Tendsto (fun m : ℕ => (drf_prop1_k D m : ℝ) / (m : ℝ)) Filter.atTop (nhds (Real.sqrt (D : ℝ))) := by set c := Real.sqrt (D : ℝ) have hc : 0 ≤ c := Real.sqrt_nonneg _ have h_lower : Filter.Tendsto (fun m : ℕ => c - (m : ℝ)⁻¹) Filter.atTop (nhds c) := by have h := (tendsto_inv_atTop_nhds_zero_nat (𝕜 := ℝ)).const_sub c simpa using h have h_upper : Filter.Tendsto (fun _ : ℕ => c) Filter.atTop (nhds c) := tendsto_const_nhds refine tendsto_of_tendsto_of_tendsto_of_le_of_le' h_lower h_upper ?_ ?_ · filter_upwards [Filter.eventually_gt_atTop 0] with m hm have hm_pos : 0 < (m : ℝ) := Nat.cast_pos.mpr hm dsimp [drf_prop1_k] have h1 := Nat.sub_one_lt_floor ((m : ℝ) * c) rw [inv_eq_one_div] have : c - 1 / (m : ℝ) = ((m : ℝ) * c - 1) / (m : ℝ) := by rw [sub_div, mul_div_cancel_left₀ c hm_pos.ne'] rw [this] exact (div_le_div_iff_of_pos_right hm_pos).mpr h1.le · filter_upwards [Filter.eventually_gt_atTop 0] with m hm have hm_pos : 0 < (m : ℝ) := Nat.cast_pos.mpr hm dsimp [drf_prop1_k] have h2 : (Nat.floor ((m : ℝ) * c) : ℝ) ≤ (m : ℝ) * c := Nat.floor_le (mul_nonneg hm_pos.le hc) rw [div_le_iff₀ hm_pos] linarith/-- As m tends to infinity, the ratio of DRF completion time to the offline bound converges to 1 + sqrt(D). -/theorem drf_prop1_ratio_tendsto (D : ℕ) (hD : 1 ≤ D) : Filter.Tendsto (fun m : ℕ => drf_prop1_ratio D m) Filter.atTop (nhds (1 + Real.sqrt (D : ℝ))) := by set u := fun m : ℕ => (drf_prop1_k D m : ℝ) / (m : ℝ) set v := fun m : ℕ => 1 / (m : ℝ) have hu : Filter.Tendsto u Filter.atTop (nhds (Real.sqrt (D : ℝ))) := drf_prop1_ratio_tendsto_k_div D have hv : Filter.Tendsto v Filter.atTop (nhds (0 : ℝ)) := by have h : Filter.Tendsto (fun m : ℕ => (m : ℝ)⁻¹) Filter.atTop (nhds (0 : ℝ)) := tendsto_inv_atTop_nhds_zero_nat (𝕜 := ℝ) simpa [v, one_div] using h set num := fun m : ℕ => ((D : ℝ) + u m) * (1 + u m) set den := fun m : ℕ => (D : ℝ) * (1 + v m) / 2 + u m + u m * (u m + v m) / 2 have hnum : Filter.Tendsto num Filter.atTop (nhds (((D : ℝ) + Real.sqrt (D : ℝ)) * (1 + Real.sqrt (D : ℝ)))) := by exact ((tendsto_const_nhds (x := (D : ℝ))).add hu).mul ((tendsto_const_nhds (x := (1 : ℝ))).add hu) have hden_raw : Filter.Tendsto den Filter.atTop (nhds ((D : ℝ) * (1 + 0) / 2 + Real.sqrt (D : ℝ) + Real.sqrt (D : ℝ) * (Real.sqrt (D : ℝ) + 0) / 2)) := by refine (((tendsto_const_nhds (x := (D : ℝ))).mul ((tendsto_const_nhds (x := (1 : ℝ))).add hv)).div_const (2 : ℝ)).add hu |>.add ?_ exact (hu.mul (hu.add hv)).div_const (2 : ℝ) have hden_eq : (D : ℝ) * (1 + 0) / 2 + Real.sqrt (D : ℝ) + Real.sqrt (D : ℝ) * (Real.sqrt (D : ℝ) + 0) / 2 = (D : ℝ) + Real.sqrt (D : ℝ) := by have hsq : Real.sqrt (D : ℝ) * Real.sqrt (D : ℝ) = (D : ℝ) := Real.mul_self_sqrt (Nat.cast_nonneg D) linear_combination 1/2 * hsq rw [hden_eq] at hden_raw have hden_ne_zero : (D : ℝ) + Real.sqrt (D : ℝ) ≠ 0 := by have : 1 ≤ (D : ℝ) := by exact_mod_cast hD positivity have hdiv := hnum.div hden_raw hden_ne_zero have hdiv_simp : (((D : ℝ) + Real.sqrt (D : ℝ)) * (1 + Real.sqrt (D : ℝ))) / ((D : ℝ) + Real.sqrt (D : ℝ)) = 1 + Real.sqrt (D : ℝ) := mul_div_cancel_left₀ (1 + Real.sqrt (D : ℝ)) hden_ne_zero rw [hdiv_simp] at hdiv refine Filter.Tendsto.congr' ?_ hdiv filter_upwards [Filter.eventually_ge_atTop 1] with m hm dsimp [num, den, u, v, drf_prop1_ratio, drf_prop1_alg, drf_prop1_opt_bound] have hm_pos : (m : ℝ) ≠ 0 := by have : 0 < m := hm positivity field_simp