AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_ratio_bound_of_large_index

theoremverified

For any natural number n with 2 ≤ n and any natural number s such that (n : ℝ) + 3 < 4 * (s : ℝ), the quantity ((n : ℝ) + 1) * ((n : ℝ) + 1 - (s : ℝ)) / (2 * (n : ℝ) * (s : ℝ)) is strictly less than 3 / 2.

Statement

theorem nonclairvoyant_scheduling_ratio_bound_of_large_index
    (n : ℕ) (hn : 2 ≤ n) (s : ℕ) (hs : (n : ℝ) + 3 < 4 * (s : ℝ)) :
    ((n : ℝ) + 1) * ((n : ℝ) + 1 - (s : ℝ)) / (2 * (n : ℝ) * (s : ℝ)) < 3 / 2
Source
arXiv:2610.29037, Appendix C.2, Proof of Theorem 4.6 (Step 5)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any natural numbers $n$ and $s$, if $2 \le n$ and $(n : \mathbb{R}) + 3 < 4(s : \mathbb{R})$, then $\frac{(n + 1)(n + 1 - s)}{2ns} < \frac{3}{2}$ (where all operations and numerals in the inequality are evaluated in the real numbers $\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

To prove that $\frac{(n+1)(n+1-s)}{2ns} < \frac{3}{2}$, the argument first establishes that the denominator $2ns$ is strictly positive. Applying `div_lt_iff₀` clears the denominator, reducing the goal to the polynomial inequality $(n+1)(n+1-s) < 3ns$. This inequality is then verified from the conditions $n \ge 2$ and $4s > n + 3$ using non-linear arithmetic.

  1. The inequality $2 \le n$ holds in the real numbers ($2 \le (n : \mathbb{R})$).

    Casts the hypothesis $2 \le n$ from the natural numbers to the real numbers.

    line 5

      have hnR : (2 : ℝ) ≤ n := by norm_cast
  2. The denominator $2ns$ is strictly positive ($0 < 2ns$).

    From $2 \le n$ and $n + 3 < 4s$, linear arithmetic yields $s > 0$. Since $2 > 0$, $n \ge 2 > 0$, and $s > 0$, their product $2ns$ is strictly positive.

    lines 6–8

      have hden : 0 < 2 * (n : ℝ) * (s : ℝ) := by
        have : 0 < (s : ℝ) := by linarith
        positivity
  3. The inequality is equivalent to $(n + 1)(n + 1 - s) < \frac{3}{2} \cdot (2ns)$.

    Because $2ns > 0$, clearing the denominator via `div_lt_iff₀` transforms the division into multiplication on the right-hand side.

    line 9

    uses div_lt_iff₀

      rw [div_lt_iff₀ hden]
  4. The inequality $(n + 1)(n + 1 - s) < 3ns$ holds, completing the proof. automation

    Expanding both sides yields $(n+1)^2 - s(n+1) < 3ns$, or equivalently $(n+1)^2 < (4n+1)s$. Given $n \ge 2$ and $4s > n + 3$, this follows by non-linear arithmetic.

    line 10

      nlinarith
div_lt_iff₀
In a linearly ordered group with zero (such as the real numbers), dividing by a strictly positive element $c$ satisfies $b / c < a \iff b < a \cdot 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

/-- For s > (n + 3) / 4, the ratio ((n + 1)(n + 1 - s)) / (2ns) is strictly less than 3/2. -/theorem nonclairvoyant_scheduling_ratio_bound_of_large_index    (n : ℕ) (hn : 2 ≤ n) (s : ℕ) (hs : (n : ℝ) + 3 < 4 * (s : ℝ)) :    ((n : ℝ) + 1) * ((n : ℝ) + 1 - (s : ℝ)) / (2 * (n : ℝ) * (s : ℝ)) < 3 / 2 := by  have hnR : (2 : ℝ) ≤ n := by norm_cast  have hden : 0 < 2 * (n : ℝ) * (s : ℝ) := by    have : 0 < (s : ℝ) := by linarith    positivity  rw [div_lt_iff₀ hden]  nlinarith
See it in the graphDiscuss this resultChallenge it