AFTD Auto-Formalizing Theoretical Domains

drf_competitive_ratio_lower_bound

theoremverifiedformalization

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 m converges to 1 + Real.sqrt (D : ℝ) along…
  • drf_prop1_algGiven two natural numbers D and m, drf_prop1_alg D m is defined as the real number…
  • drf_prop1_opt_boundFor two natural numbers D and m, drf_prop1_opt_bound D m is 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 m is defined as the real number drf_prop1_alg D m / drf_prop1_opt_bound D m.

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 ≤ ρ.

  1. 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 ρ.

    lines 3–4

    uses drf_prop1_ratio_tendsto, le_of_tendsto

      have htend := drf_prop1_ratio_tendsto D hD
      refine le_of_tendsto htend ?_
  2. 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.

    lines 5–6

    uses Filter.eventually_ge_atTop

      filter_upwards [Filter.eventually_ge_atTop 1] with m hm
      dsimp [drf_prop1_ratio]
  3. 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.

    lines 7–11

      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
  4. 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.

    line 12

    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

/-- 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)
See it in the graphDiscuss this resultChallenge it