nonclairvoyant_scheduling_term_U_one_eq_term_L_one
For every natural number n ≥ 1 and every real parameter t, the upper bound sequence term nonclairvoyant_scheduling_term_U n t 1 at index 1 is identically equal to the lower bound sequence term nonclairvoyant_scheduling_term_L n t 1 at index 1.
Statement
theorem nonclairvoyant_scheduling_term_U_one_eq_term_L_one (n : ℕ) (t : ℝ) (hn : 1 ≤ n) :
nonclairvoyant_scheduling_term_U n t 1 = nonclairvoyant_scheduling_term_L n t 1- Source
- arXiv:2610.29037, Appendix C.2, Proof of Theorem 4.6 (Step 6)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- nonclairvoyant_scheduling_term_UThe sequence U_i(t) = (2*t*n^2 + (1-t)*i*(2*n+1-i)) / (t*n*(n+1) + (1-t)*i*(i+1)) for n jobs, index i, and parameter t.
- nonclairvoyant_scheduling_term_LThe lower bound sequence L_s(t) = (s*(2*n+1-s) + 2*t*n*(n-1)) / (s*(s+1) + t*n*(n-1)*(n+s+1)/(n-s+1)) for index s.
Read back from the Lean
For every natural number $n$ and every real number $t$, if $1 \le n$, then nonclairvoyant_scheduling_term_U n t 1 equals nonclairvoyant_scheduling_term_L n t 1.
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 verifies that the upper bound term $U_1(t)$ and the lower bound term $L_1(t)$ coincide by direct algebraic simplification. After unfolding the definitions at index 1, the nested subexpression $n - 1 + 1$ in the lower-bound denominator simplifies to $n$, which allows canceling a factor of $n$ using the hypothesis $1 \le n$. With both sides reduced to simple rational expressions, their numerators and denominators are shown to be algebraically identical by expanding polynomials.
Evaluating the definitions at index 1 expresses both sides as rational expressions in $n$ and $t$.
Unfolding `nonclairvoyant_scheduling_term_U` and `nonclairvoyant_scheduling_term_L` substitutes the index $1$ for $i$ and $s$, and `push_cast` converts all occurrences of the natural number $1$ into the real number $1$.
unfold nonclairvoyant_scheduling_term_U nonclairvoyant_scheduling_term_L push_cast
$n \neq 0$ as a real number.
From the assumption $1 \le n$, the `positivity` tactic deduces that $n$ is strictly positive and therefore non-zero in $\mathbb{R}$.
have hn0 : (n : ℝ) ≠ 0 := by positivity
The subexpression $n - 1 + 1$ in the denominator of the right-hand side simplifies to $n$.
By real arithmetic, $n - 1 + 1 = n$. Rewriting with this identity simplifies the denominator of the nested fraction on the right-hand side to $n$.
have h_denom_sub : (n : ℝ) - 1 + 1 = (n : ℝ) := by ring rw [h_denom_sub]
The nested fraction $\frac{t \cdot n \cdot (n - 1) \cdot (n + 1 + 1)}{n}$ cancels the factor of $n$ to become $t \cdot (n - 1) \cdot (n + 1 + 1)$.
Using commutativity to move $n$ to the rightmost position in the product, the common factor of $n$ in the numerator and denominator cancels via `mul_div_cancel_right₀` because $n \neq 0$. Rewriting with this cancellation eliminates the division within the right-hand denominator.
uses
mul_div_cancel_right₀have h_cancel : t * ↑n * (↑n - 1) * (↑n + 1 + 1) / ↑n = t * (↑n - 1) * (↑n + 1 + 1) := by have h : t * ↑n * (↑n - 1) * (↑n + 1 + 1) = (t * (↑n - 1) * (↑n + 1 + 1)) * ↑n := by ring rw [h] exact mul_div_cancel_right₀ _ hn0 rw [h_cancel]
The numerators and denominators of the two fractions are respectively identical, completing the proof.
Applying congruence (`congr 1`) reduces the equality between the two rational expressions to showing separately that their numerators match and their denominators match. Ring polynomial arithmetic (`ring`) confirms both: both numerators expand to $2t n^2 - 2t n + 2n$, and both denominators expand to $t n^2 + t n - 2t + 2$.
congr 1 · ring · ring
mul_div_cancel_right₀- For an element $a$ and a non-zero element $b$ in a structure with multiplication, zero, and division, $(a \cdot b) / b = a$.
- The natural number $n$ is coerced to a real number (denoted $\uparrow n$ in Lean); properties like $n \neq 0$ must be verified over $\mathbb{R}$ using the assumption $1 \le n$ before performing division cancellation.
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.
/-- At index s = 1, the upper bound term U_1(t) coincides with the lower bound term L_1(t). -/theorem nonclairvoyant_scheduling_term_U_one_eq_term_L_one (n : ℕ) (t : ℝ) (hn : 1 ≤ n) : nonclairvoyant_scheduling_term_U n t 1 = nonclairvoyant_scheduling_term_L n t 1 := by unfold nonclairvoyant_scheduling_term_U nonclairvoyant_scheduling_term_L push_cast have hn0 : (n : ℝ) ≠ 0 := by positivity have h_denom_sub : (n : ℝ) - 1 + 1 = (n : ℝ) := by ring rw [h_denom_sub] have h_cancel : t * ↑n * (↑n - 1) * (↑n + 1 + 1) / ↑n = t * (↑n - 1) * (↑n + 1 + 1) := by have h : t * ↑n * (↑n - 1) * (↑n + 1 + 1) = (t * (↑n - 1) * (↑n + 1 + 1)) * ↑n := by ring rw [h] exact mul_div_cancel_right₀ _ hn0 rw [h_cancel] congr 1 · ring · ring