AFTD Auto-Formalizing Theoretical Domains

drf_cap_lower_bound_le_opt

theoremverifiedformalization

For every multidimensional scheduling instance I with D resources and zero release times, the sum over all jobs of processing requirement divided by rate cap, ∑ j, I.p j / I.u j, is at most the offline optimal total completion time multidim_opt I.

Statement

theorem drf_cap_lower_bound_le_opt {D : ℕ} (I : MultidimInstance D) :
    (∑ j : Fin I.n, I.p j / I.u j) ≤ multidim_opt I
Formalizes
arXiv:2611.07905 Section 3.1.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
  • multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
  • multidim_is_feasible_scheduleA rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule I x C for an instance I with D resources if for…

Read back from the Lean

For every natural number $D$ and every multidimensional instance $I$ with $D$ resources, the sum over all jobs $j \in \{0, \dots, I.n - 1\}$ of $I.p(j) / I.u(j)$ is less than or equal to multidim_opt I (the infimum over all feasible schedules $(x, C)$ of the total completion time $\sum_{j} C(j)$).

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 completion time multidim_opt I is defined as the infimum of total completion times ∑ j, C j over all feasible schedules. The theorem proves that ∑ j, p j / u j ≤ multidim_opt I by verifying that the set of feasible schedules is nonempty (witnessed by allocating each job a small constant rate min (u j) (1 / (n + 1))) and showing that every feasible schedule satisfies p j / u j ≤ C j for each job j via integral monotonicity of rates bounded by u j.

  1. To bound multidim_opt I from below, it suffices to show that the set of feasible completion times is nonempty and that every feasible schedule has total completion time at least ∑ j, p j / u j.

    Unfolding the definition of multidim_opt, the optimal total completion time is the infimum of ∑ j, C j over all feasible schedules (x, C). By le_csInf, a value is at most the infimum of a set provided the set is nonempty and the value is a lower bound for every element of the set.

    lines 4–5

    uses le_csInf

      unfold multidim_opt
      apply le_csInf
  2. For c = 1 / (n + 1), we have c > 0 and n * c ≤ 1.

    Since the number of jobs n is non-negative, the denominator n + 1 is strictly positive, so c = 1 / (n + 1) > 0. Multiplying n by c gives n / (n + 1) by mul_one_div, which is at most 1 by div_le_one and linear arithmetic because n ≤ n + 1.

    lines 6–11

    uses mul_one_div, div_le_one

      · -- the set of achievable total completion times is nonempty
        set c : ℝ := 1 / ((I.n : ℝ) + 1) with hc_def
        have hcpos : 0 < c := by positivity
        have hnc : (I.n : ℝ) * c ≤ 1 := by
          rw [hc_def, mul_one_div, div_le_one (by positivity)]
          linarith
  3. The constant rate allocation x j t = min (u j) c satisfies the job rate limits 0 ≤ x j t ≤ u j.

    We propose a witness schedule where each job j runs at constant rate min (u j) c with completion time C j = p j / min (u j) c. Since u j > 0 and c > 0, their minimum is non-negative (by le_min and le_of_lt). Furthermore, min (u j) c ≤ u j holds by min_le_left.

    lines 12–15

    uses le_min, le_of_lt, min_le_left

        refine ⟨∑ j, I.p j / min (I.u j) c, fun j _ => min (I.u j) c, fun j => I.p j / min (I.u j) c,
          ⟨?_, ?_, ?_⟩, rfl⟩
        · intro j t
          exact ⟨le_min (le_of_lt (I.hu j)) (le_of_lt hcpos), min_le_left _ _⟩
  4. The witness schedule respects resource capacities: for every resource d and time t ≥ 0, ∑ j, a j d * x j t ≤ 1.

    For each job j, the resource demand a j d is at most 1, so a j d * min (u j) c ≤ 1 * min (u j) c ≤ c using mul_le_mul_of_nonneg_right, lt_min, le_of_lt, one_mul, and min_le_right. Summing this bound over all n jobs via Finset.sum_le_sum gives a total usage of at most n * c (by Finset.sum_const, Finset.card_univ, Fintype.card_fin, and nsmul_eq_mul), which is at most 1 by the choice of c.

    lines 16–26

    uses mul_le_mul_of_nonneg_right, le_of_lt, lt_min, one_mul, min_le_right, Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul

        · intro d t ht
          have h : ∀ j : Fin I.n, I.a j d * min (I.u j) c ≤ c := by
            intro j
            calc I.a j d * min (I.u j) c ≤ 1 * min (I.u j) c :=
                  mul_le_mul_of_nonneg_right (I.ha_le_one j d) (le_of_lt (lt_min (I.hu j) hcpos))
              _ = min (I.u j) c := one_mul _
              _ ≤ c := min_le_right _ _
          calc ∑ j, I.a j d * min (I.u j) c ≤ ∑ _j : Fin I.n, c := Finset.sum_le_sum (fun j _ => h j)
            _ = (I.n : ℝ) * c := by
                rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]
            _ ≤ 1 := hnc
  5. The completion times C j = p j / min (u j) c are non-negative and satisfy the work requirement ∫ 0..C j, x j t dt = p j for each job, proving that the set of feasible schedules is nonempty.

    Since p j > 0 and min (u j) c > 0 (by lt_min), the completion time C j is strictly positive by div_pos, hence non-negative (by le_of_lt). Because the rate function is constant, it is integrable (by intervalIntegrable_const), and its integral from 0 to C j equals (C j - 0) • min (u j) c = p j by intervalIntegral.integral_const, sub_zero, smul_eq_mul, and div_mul_cancel₀ (using ne_of_gt).

    lines 27–32

    uses lt_min, le_of_lt, div_pos, intervalIntegrable_const, intervalIntegral.integral_const, sub_zero, smul_eq_mul, div_mul_cancel₀, ne_of_gt

        · intro j
          have hpos : 0 < min (I.u j) c := lt_min (I.hu j) hcpos
          exact ⟨le_of_lt (div_pos (I.hp j) hpos), intervalIntegrable_const, by
            rw [intervalIntegral.integral_const]
            simp only [sub_zero, smul_eq_mul]
            exact div_mul_cancel₀ _ (ne_of_gt hpos)⟩
  6. To show that any feasible schedule (x, C) satisfies ∑ j, p j / u j ≤ ∑ j, C j, it suffices to show p j / u j ≤ C j for each job j.

    Let (x, C) be an arbitrary feasible schedule with total completion time b = ∑ j, C j. By Finset.sum_le_sum, it suffices to prove the inequality job by job: p j / u j ≤ C j for each job j.

    lines 33–38

    uses Finset.sum_le_sum

      · -- every achievable total completion time dominates ∑ p_j/u_j
        intro b hb
        obtain ⟨x, C, ⟨hx, hR, hC⟩, rfl⟩ := hb
        apply Finset.sum_le_sum
        intro j _
        obtain ⟨hCj0, hint, hval⟩ := hC j
  7. For every job j, the completion time satisfies p j / u j ≤ C j.

    By feasibility, C j ≥ 0, x j is integrable on [0, C j], and the total work processed is ∫ 0..C j, x j t dt = p j. Since x j t ≤ u j pointwise, monotonicity of the integral (intervalIntegral.integral_mono_on) gives ∫ 0..C j, x j t dt ≤ ∫ 0..C j, u j dt. The right-hand integral is evaluated as u j * C j using intervalIntegral.integral_const, smul_eq_mul, and mul_comm, yielding p j ≤ u j * C j. Since u j > 0, dividing by u j via div_le_iff₀ and linear arithmetic gives p j / u j ≤ C j.

    lines 39–48

    uses intervalIntegral.integral_mono_on, intervalIntegrable_const, intervalIntegral.integral_const, smul_eq_mul, mul_comm, div_le_iff₀

        have hmono : ∫ (t : ℝ) in 0..C j, x j t ≤ ∫ (t : ℝ) in 0..C j, I.u j := by
          refine intervalIntegral.integral_mono_on hCj0 hint intervalIntegrable_const ?_
          intro t ht
          exact (hx j t).2
        rw [intervalIntegral.integral_const] at hmono
        have hle : I.p j ≤ I.u j * C j := by
          rw [← hval]
          simpa [smul_eq_mul, mul_comm] using hmono
        rw [div_le_iff₀ (I.hu j)]
        linarith
div_mul_cancel₀
Multiplying (a / b) by a nonzero b yields a.
div_le_iff₀
For a strictly positive denominator c, b / c ≤ a if and only if b ≤ a * c.
div_le_one
For a positive denominator b, the fraction a / b is at most 1 if and only if a ≤ b.
div_pos
The quotient of two strictly positive numbers is strictly positive.
Fintype.card_fin
The finite type Fin n has cardinality n.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.sum_const
The sum of a constant over a finite set equals the cardinality of the set times that constant.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
intervalIntegrable_const
A constant function is interval integrable on any interval [a, b].
intervalIntegral.integral_const
The interval integral of a constant c from a to b equals (b - a) • c.
intervalIntegral.integral_mono_on
If a ≤ b, f and g are interval integrable on [a, b], and f(x) ≤ g(x) on [a, b], then ∫_a^b f ≤ ∫_a^b g.
le_csInf
A value a is at most the infimum of a set s if s is nonempty and a ≤ b for all b ∈ s.
le_min
If c ≤ a and c ≤ b, then c ≤ min(a, b).
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
lt_min
If a < b and a < c, then a < min(b, c).
min_le_left
The minimum of two elements is at most the first element.
min_le_right
The minimum of two elements is at most the second element.
mul_comm
Multiplication is commutative.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality b ≤ c on the right by a non-negative number preserves the inequality.
mul_one_div
Multiplying x by 1 / y equals x / y.
ne_of_gt
If b < a, then a ≠ b.
nsmul_eq_mul
Scalar multiplication of a real number by a natural number n equals standard multiplication by n.
one_mul
Multiplying by 1 on the left leaves an element unchanged.
smul_eq_mul
Real scalar multiplication coincides with standard real multiplication.
sub_zero
Subtracting zero leaves an element unchanged.

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 sum over jobs of processing requirement divided by rate cap is at most the offline optimal total completion time. -/theorem drf_cap_lower_bound_le_opt {D : ℕ} (I : MultidimInstance D) :    (∑ j : Fin I.n, I.p j / I.u j) ≤ multidim_opt I := by  unfold multidim_opt  apply le_csInf  · -- the set of achievable total completion times is nonempty    set c : ℝ := 1 / ((I.n : ℝ) + 1) with hc_def    have hcpos : 0 < c := by positivity    have hnc : (I.n : ℝ) * c ≤ 1 := by      rw [hc_def, mul_one_div, div_le_one (by positivity)]      linarith    refine ⟨∑ j, I.p j / min (I.u j) c, fun j _ => min (I.u j) c, fun j => I.p j / min (I.u j) c,      ⟨?_, ?_, ?_⟩, rfl⟩    · intro j t      exact ⟨le_min (le_of_lt (I.hu j)) (le_of_lt hcpos), min_le_left _ _⟩    · intro d t ht      have h : ∀ j : Fin I.n, I.a j d * min (I.u j) c ≤ c := by        intro j        calc I.a j d * min (I.u j) c ≤ 1 * min (I.u j) c :=              mul_le_mul_of_nonneg_right (I.ha_le_one j d) (le_of_lt (lt_min (I.hu j) hcpos))          _ = min (I.u j) c := one_mul _          _ ≤ c := min_le_right _ _      calc ∑ j, I.a j d * min (I.u j) c ≤ ∑ _j : Fin I.n, c := Finset.sum_le_sum (fun j _ => h j)        _ = (I.n : ℝ) * c := by            rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]        _ ≤ 1 := hnc    · intro j      have hpos : 0 < min (I.u j) c := lt_min (I.hu j) hcpos      exact ⟨le_of_lt (div_pos (I.hp j) hpos), intervalIntegrable_const, by        rw [intervalIntegral.integral_const]        simp only [sub_zero, smul_eq_mul]        exact div_mul_cancel₀ _ (ne_of_gt hpos)⟩  · -- every achievable total completion time dominates ∑ p_j/u_j    intro b hb    obtain ⟨x, C, ⟨hx, hR, hC⟩, rfl⟩ := hb    apply Finset.sum_le_sum    intro j _    obtain ⟨hCj0, hint, hval⟩ := hC j    have hmono : ∫ (t : ℝ) in 0..C j, x j t ≤ ∫ (t : ℝ) in 0..C j, I.u j := by      refine intervalIntegral.integral_mono_on hCj0 hint intervalIntegrable_const ?_      intro t ht      exact (hx j t).2    rw [intervalIntegral.integral_const] at hmono    have hle : I.p j ≤ I.u j * C j := by      rw [← hval]      simpa [smul_eq_mul, mul_comm] using hmono    rw [div_le_iff₀ (I.hu j)]    linarith
See it in the graphDiscuss this resultChallenge it