AFTD Auto-Formalizing Theoretical Domains

oneshot_drf_bound_le_five_sqrt

theoremverified

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

    lines 3–5

    uses Real.one_le_sqrt

      have hsqrt : (1 : ℝ) ≤ Real.sqrt (D : ℝ) := by
        rw [Real.one_le_sqrt]
        exact_mod_cast hD
  2. 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.

    line 6

      have h1 : 4 * Real.sqrt (D : ℝ) + 1 ≤ 5 * Real.sqrt (D : ℝ) := by linarith
  3. (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.

    lines 7–8

    uses mul_le_mul_of_nonneg_right

      have 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

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