AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_offline_opt_superadditive

theoremverifiedformalization

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
Used by 1

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

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

    line 6

      simp only [nonclairvoyant_scheduling_offline_opt]
  2. 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).

    lines 7–15

    uses Finset.sum_add_distrib, Finset.sum_congr, Pi.add_apply, mul_add

      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]
  3. 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 π.

    line 16

    uses Finset.le_inf'

      refine Finset.le_inf' _ _ (fun π hπ => ?_)
  4. 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.

    lines 17–20

    uses Finset.inf'_le

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

    lines 21–22

      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

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