nonclairvoyant_scheduling_ratio_bound_of_large_index
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
- cycle_gap_merge_pairMerging two unit gaps at index 0 on a cycle yields a single gap of length 2.
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.
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.
have hnR : (2 : ℝ) ≤ n := by norm_cast
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.
have hden : 0 < 2 * (n : ℝ) * (s : ℝ) := by have : 0 < (s : ℝ) := by linarith positivity
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.
uses
div_lt_iff₀rw [div_lt_iff₀ hden]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.
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$.
- The final step uses the `nlinarith` decision procedure to verify the non-linear real inequality $(n + 1)(n + 1 - s) < 3ns$ directly from $n \ge 2$ and $4s > n + 3$ without requiring manual algebraic expansion.
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.
/-- 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