AFTD Auto-Formalizing Theoretical Domains

drf_prop1_opt_bound

def

For two natural numbers D and m, drf_prop1_opt_bound D m is defined as the real number (D : ℝ) * (m : ℝ) * ((m : ℝ) + 1) / 2 + (m : ℝ) * (drf_prop1_k D m : ℝ) + (drf_prop1_k D m : ℝ) * ((drf_prop1_k D m : ℝ) + 1) / 2.

Statement

noncomputable def drf_prop1_opt_bound (D m : ℕ) : ℝ
Defined in
arXiv:2611.07905 Proposition 1
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • 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)).
Used by 2
  • 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.
  • 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

A definition of a function drf_prop1_opt_bound that takes two natural numbers $D$ and $m$ and returns the real number: $$\frac{D \cdot m \cdot (m + 1)}{2} + m \cdot k + \frac{k \cdot (k + 1)}{2}$$ where $k = \text{drf\_prop1\_k}(D, m)$ (coerced 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.

Lean source view module on GitHub

/-- Offline schedule total completion time bound for the lower-bound instance with D resources and parameter m. -/
noncomputable def drf_prop1_opt_bound (D m : ℕ) : ℝ := (D : ℝ) * (m : ℝ) * ((m : ℝ) + 1) / 2 + (m : ℝ) * (drf_prop1_k D m : ℝ) + (drf_prop1_k D m : ℝ) * ((drf_prop1_k D m : ℝ) + 1) / 2
See it in the graphDiscuss this resultChallenge it