AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_term_U_one_eq_term_L_one

theoremverified

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

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.

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

    lines 4–5

      unfold nonclairvoyant_scheduling_term_U nonclairvoyant_scheduling_term_L
      push_cast
  2. $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}$.

    line 6

      have hn0 : (n : ℝ) ≠ 0 := by positivity
  3. 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$.

    lines 7–8

      have h_denom_sub : (n : ℝ) - 1 + 1 = (n : ℝ) := by ring
      rw [h_denom_sub]
  4. 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.

    lines 9–13

    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]
  5. 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$.

    lines 14–16

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

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

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