nonclairvoyant_scheduling_offline_opt_superadditive
For any natural number n and job processing vectors a, z : Fin n → ℝ, the offline optimal total completion time satisfies superadditivity: nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤ nonclairvoyant_scheduling_offline_opt (a + z).
Statement
theorem nonclairvoyant_scheduling_offline_opt_superadditive {n : ℕ}
(a z : Fin n → ℝ) :
nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤
nonclairvoyant_scheduling_offline_opt (a + z)- Formalizes
- arXiv:2610.29037 Lemma 4.2 proof step (1)
- 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 1
- nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratioLet n be a natural number and let x, a, z : Fin n → ℝ with x = a + z, where a and z have non-negative coordinates (∀ i, 0 ≤ a i and ∀ i, 0…
Read back from the Lean
For any natural number $n$ and any functions $a, z : \text{Fin } n \to \mathbb{R}$, the offline optimal scheduling cost of $a$ plus the offline optimal scheduling cost of $z$ is less than or equal to the offline optimal scheduling cost of their pointwise sum $a + z$.
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 OPT(w) is defined as the minimum over all permutations π of the linear cost ∑ i, (n - i) * w(π(i)). For any fixed permutation π, this cost is linear and therefore additive in the job vector: the cost of a + z equals the cost of a plus the cost of z. Since OPT(a) and OPT(z) are lower bounds for the respective costs under π, their sum is a lower bound for the cost of a + z under every permutation π. Taking the minimum over all permutations yields OPT(a) + OPT(z) ≤ OPT(a + z).
Expand the definition of the offline optimal completion time.
Unfolding nonclairvoyant_scheduling_offline_opt expresses the optimal total completion time for any job vector w as the infimum (minimum) over all permutations π ∈ Equiv.Perm (Fin n) of the weighted completion time sum ∑ i, (n - i) * w (π i).
simp only [nonclairvoyant_scheduling_offline_opt]For any permutation π, the scheduling cost of a + z is the sum of the individual costs of a and z.
For any fixed permutation π, rewrite the sum of the two sums into a single sum using Finset.sum_add_distrib. By Finset.sum_congr, it suffices to show that the summands match pointwise for every index i, which follows by expanding pointwise addition (Pi.add_apply) and distributing multiplication over addition (mul_add).
uses
Finset.sum_add_distrib,Finset.sum_congr,Pi.add_apply,mul_addhave key : ∀ π : Equiv.Perm (Fin n), (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * (a + z) (π i)) = (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * a (π i)) + (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * z (π i)) := by intro π rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl ?_ intro i _ simp only [Pi.add_apply, mul_add]
To show OPT(a) + OPT(z) ≤ OPT(a + z), it suffices to show OPT(a) + OPT(z) ≤ ∑ i, (n - i) * (a + z) (π i) for an arbitrary permutation π.
By Finset.le_inf', a lower bound for every value in a nonempty finite set is a lower bound for its infimum (minimum). Thus, we fix an arbitrary permutation π and show the bound holds for π.
uses
Finset.le_inf'refine Finset.le_inf' _ _ (fun π hπ => ?_)
For the fixed permutation π, OPT(a) is at most the cost of a under π, and OPT(z) is at most the cost of z under π.
By Finset.inf'_le, the infimum over all permutations is less than or equal to the value at any specific permutation π. Applying this to a yields h1, and applying it to z yields h2.
uses
Finset.inf'_lehave h1 := Finset.inf'_le (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * a (π i)) hπ have h2 := Finset.inf'_le (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * z (π i)) hπ
The sum OPT(a) + OPT(z) is bounded by the cost of a + z under π, concluding the proof.
Rewriting the cost of a + z under π into the sum of the individual costs of a and z using the additivity identity key, linear arithmetic (linarith) combines the two lower bounds h1 and h2 to close the goal.
rw [key π] linarith
Finset.sum_add_distrib- The sum over a finite set of a sum of two functions equals the sum of the individual sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
mul_add- Multiplication distributes over addition from the left: a * (b + c) = a * b + a * c.
Pi.add_apply- Pointwise addition of functions satisfies (f + g) i = f i + g i.
Finset.le_inf'- A value is less than or equal to the infimum (minimum) of a nonempty finite set if it is less than or equal to every element in that set.
Finset.inf'_le- The infimum (minimum) of a function over a finite set is less than or equal to its value at any member of that set.
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.
/-- Superadditivity of the offline optimal total completion time: OPT(a + z) >= OPT(a) + OPT(z). -/theorem nonclairvoyant_scheduling_offline_opt_superadditive {n : ℕ} (a z : Fin n → ℝ) : nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤ nonclairvoyant_scheduling_offline_opt (a + z) := by simp only [nonclairvoyant_scheduling_offline_opt] have key : ∀ π : Equiv.Perm (Fin n), (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * (a + z) (π i)) = (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * a (π i)) + (∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * z (π i)) := by intro π rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl ?_ intro i _ simp only [Pi.add_apply, mul_add] refine Finset.le_inf' _ _ (fun π hπ => ?_) have h1 := Finset.inf'_le (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * a (π i)) hπ have h2 := Finset.inf'_le (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * z (π i)) hπ rw [key π] linarith