AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_offline_opt_zero

theoremverified

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

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

    lines 4–5

    uses mul_zero, Finset.sum_const_zero

      unfold nonclairvoyant_scheduling_offline_opt
      simp only [mul_zero, Finset.sum_const_zero]
  2. 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`.

    line 6

    uses Finset.inf'_const

      exact 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

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