nonclairvoyant_scheduling_offline_opt_zero
For any natural number n, the offline optimal total completion time of the all-zero job processing vector (fun (_ : Fin n) => (0 : ℝ)) is equal to zero.
Statement
theorem nonclairvoyant_scheduling_offline_opt_zero (n : ℕ) : nonclairvoyant_scheduling_offline_opt (fun (_ : Fin n) => (0 : ℝ)) = 0
- Source
- arXiv:2610.29037 Section 4
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nonclairvoyant_scheduling_offline_optFor any natural number n and job processing vector w : Fin n → ℝ, the offline optimal total completion time…
- Used by 2
- is_feasible_flow_zeroFor any natural number k, the zero flow (fun _ _ => 0) on Fin k is a feasible flow for the zero demand vector 0 : Fin k → ℝ.
- electrical_flow_energy_zeroFor any natural number k and any resistance matrix d on Fin k, the electrical energy of the zero flow (fun _ _ => 0) is 0.
Read back from the Lean
For every natural number $n$, the offline optimum scheduling cost (nonclairvoyant_scheduling_offline_opt) for the constant zero weight/length vector on Fin n (the function mapping every element of Fin n to $0 : ℝ$) is equal to $0$.
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 offline optimal total completion time is defined as the infimum of the weighted completion times over all job permutations. When every job has processing time zero, each term in the sum vanishes, so every permutation incurs a total cost of zero. The infimum of this identically zero function over the nonempty set of permutations is therefore zero.
For every permutation, the objective sum evaluates to 0, reducing the optimal cost to the infimum of the constant zero function.
Unfolding the definition of `nonclairvoyant_scheduling_offline_opt` expresses the offline optimum as the infimum over all permutations $\pi$ of the sum $\sum_i (n - i) w(\pi(i))$. Since the processing times $w$ are identically zero, each summand $(n - i) \cdot 0$ is zero by `mul_zero`, and the sum of zeroes is zero by `Finset.sum_const_zero`.
uses
mul_zero,Finset.sum_const_zerounfold nonclairvoyant_scheduling_offline_opt simp only [mul_zero, Finset.sum_const_zero]
The infimum of the constant zero function over the permutations is 0.
Since the set of permutations of $n$ elements is nonempty (containing the identity permutation), the infimum of the constant function with value $0$ over this set is $0$, by `Finset.inf'_const`.
uses
Finset.inf'_constexact Finset.inf'_const _ 0
mul_zero- Multiplying any element by zero on the right yields zero ($a \cdot 0 = 0$).
Finset.sum_const_zero- The sum of the constant zero function over any finite set is zero ($\sum_{x \in s} 0 = 0$).
Finset.inf'_const- The infimum of a constant function with value $a$ over any nonempty finite set equals $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
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.
/-- The offline optimal total completion time of the all-zero processing times vector is zero. -/theorem nonclairvoyant_scheduling_offline_opt_zero (n : ℕ) : nonclairvoyant_scheduling_offline_opt (fun (_ : Fin n) => (0 : ℝ)) = 0 := by unfold nonclairvoyant_scheduling_offline_opt simp only [mul_zero, Finset.sum_const_zero] exact Finset.inf'_const _ 0