AFTD Auto-Formalizing Theoretical Domains

exists_bin_packing_of_total_capacity_ge

theoremverifiedformalization

If b bins have capacities C_j and current loads L_j ≤ C_j with Σ L_j + (m + b)η ≤ Σ C_j (η > 0), then m items of size η can be added to the bins without exceeding any capacity.

Statement

theorem exists_bin_packing_of_total_capacity_ge {b m : ℕ} (C L : Fin b → ℝ) (η : ℝ)
    (hη : 0 < η) (hL : ∀ j, L j ≤ C j) (h : ∑ j, L j + (m + b) * η ≤ ∑ j, C j) :
    ∃ f : Fin m → Fin b, ∀ j, L j + (Finset.univ.filter (fun i => f i = j)).card * η ≤ C j
Formalizes
arXiv:2610.15520 (Improving the bounds on approximating weighted maximin shares of chores), Lemma 5.4.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by induction on the number of items m, universally quantified over the load vector L. In the inductive step from m to m + 1, assuming b > 0 (as b = 0 contradicts the capacity inequality), an averaging argument proves that at least one bin j₀ has room for an item of size η, because otherwise all bins would strictly exceed their capacity. Placing one item into bin j₀ increases the total load by η, which exactly matches the reduction of the remaining slack term from (m + 1 + b)η to (m + b)η. Applying the induction hypothesis to the updated loads packs the remaining m items, and prepending j₀ yields a valid packing of all m + 1 items.

  1. The base case m = 0 holds: with zero items to place, the empty assignment leaves the loads L_j ≤ C_j unchanged.

    We universally quantify over the initial loads L and induct on the number of items m. When m = 0, no items need to be assigned, so we choose the empty assignment function (from Fin 0). Since the preimage of any bin j under this function is empty, the item count in each bin is 0, and the capacity check reduces directly to the initial hypothesis L_j ≤ C_j.

    lines 4–15

    uses Finset.filter_eq_empty_iff, Finset.card_empty, Nat.cast_zero, MulZeroClass.zero_mul, add_zero

      revert L
      induction m with
      | zero =>
        intro L hL h
        refine ⟨fun i => i.elim0, ?_⟩
        intro j
        have : (Finset.univ.filter (fun (i : Fin 0) => (fun _ => i.elim0) i = j)) = ∅ := by
          rw [Finset.filter_eq_empty_iff]
          intro i
          exact i.elim0
        rw [this, Finset.card_empty, Nat.cast_zero, MulZeroClass.zero_mul, add_zero]
        exact hL j
  2. For the inductive step m + 1, we may assume b > 0, since b = 0 contradicts the total capacity condition.

    We assume the inductive hypothesis for m and introduce the loads L for m + 1 items. If there are no bins (b = 0), all sums over bins are empty and vanish, reducing the hypothesis to (m + 1)η ≤ 0. But m + 1 ≥ 1 and η > 0 imply (m + 1)η > 0, yielding a contradiction. Hence b > 0.

    lines 16–22

    uses Nat.eq_zero_or_pos, Finset.univ_eq_empty, Finset.sum_empty, zero_add

      | succ m ih =>
        intro L hL h
        rcases Nat.eq_zero_or_pos b with rfl | hb
        · simp only [Finset.univ_eq_empty, Finset.sum_empty, zero_add] at h
          have hpos : 0 < ((m + 1 : ℝ) * η) := by positivity
          push_cast at h
          linarith
  3. There exists at least one bin j₀ that can accommodate an item of size η, that is, L_{j₀} + η ≤ C_{j₀}.

    Suppose, for contradiction, that every bin satisfies C_j < L_j + η. Because b > 0, the set of bins is nonempty. Summing these strict inequalities across all b bins gives ∑ C_j < ∑ L_j + bη. However, the total capacity hypothesis guarantees ∑ L_j + (m + 1 + b)η ≤ ∑ C_j. Since (m + 1)η > 0, this implies ∑ L_j + bη < ∑ C_j ≤ ∑ C_j - (m + 1)η, a contradiction. We obtain a bin j₀ satisfying L_{j₀} + η ≤ C_{j₀}.

    lines 23–34

    uses Finset.univ_nonempty_iff.mpr, Fin.pos_iff_nonempty.mp, Finset.sum_lt_sum_of_nonempty, Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, Nat.cast_nonneg

        · have hex : ∃ j₀ : Fin b, L j₀ + η ≤ C j₀ := by
            by_contra! h_all
            have h_ne : (Finset.univ : Finset (Fin b)).Nonempty :=
              Finset.univ_nonempty_iff.mpr (Fin.pos_iff_nonempty.mp hb)
            have h1 : ∑ j, C j < ∑ j, (L j + η) := Finset.sum_lt_sum_of_nonempty h_ne (fun j _ => h_all j)
            rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h1
            have hm : 0 ≤ (m : ℝ) := Nat.cast_nonneg m
            have h_exp : (↑(m + 1) + ↑b : ℝ) * η = (m : ℝ) * η + η + (b : ℝ) * η := by
              push_cast
              ring
            nlinarith
          rcases hex with ⟨j₀, hj₀⟩
  4. Updating the load of bin j₀ by η yields loads L' that respect every bin capacity (L'_j ≤ C_j for all j).

    We define the new load function L' by increasing bin j₀'s load to L_{j₀} + η and keeping all other bin loads unchanged. For j = j₀, L'_{j₀} = L_{j₀} + η ≤ C_{j₀} by the choice of j₀. For j ≠ j₀, L'_j = L_j ≤ C_j by the initial load hypothesis.

    lines 35–43

    uses Function.update_self, Function.update_of_ne

          set L' := Function.update L j₀ (L j₀ + η) with hL'_def
          have hL' : ∀ j, L' j ≤ C j := by
            intro j
            by_cases hj : j = j₀
            · subst hj
              rw [hL'_def, Function.update_self]
              exact hj₀
            · rw [hL'_def, Function.update_of_ne hj]
              exact hL j
  5. The updated loads L' satisfy the total capacity condition for the remaining m items: ∑ L'_j + (m + b)η ≤ ∑ C_j.

    Because L' differs from L only at j₀ where its load increases by η, the total load increases by exactly η: ∑ L'_j = ∑ L_j + η. Rewriting (m + 1 + b)η as (m + b)η + η, the original inequality ∑ L_j + (m + 1 + b)η ≤ ∑ C_j rearranges via linear arithmetic to ∑ L'_j + (m + b)η ≤ ∑ C_j.

    lines 44–55

    uses Finset.mem_univ, Finset.sum_update_of_mem, Finset.sdiff_singleton_eq_erase, Finset.add_sum_erase

          have h_sum' : ∑ j, L' j + ((m : ℝ) + (b : ℝ)) * η ≤ ∑ j, C j := by
            have hi : j₀ ∈ (Finset.univ : Finset (Fin b)) := Finset.mem_univ j₀
            have h1 := Finset.sum_update_of_mem hi L (L j₀ + η)
            rw [Finset.sdiff_singleton_eq_erase] at h1
            have h2 := Finset.add_sum_erase Finset.univ L hi
            have h_sum : ∑ j, L' j = (∑ j, L j) + η := by
              rw [hL'_def, h1]
              linarith
            have : (↑(m + 1) + ↑b : ℝ) * η = (↑m + ↑b) * η + η := by
              push_cast
              ring
            linarith
  6. By the induction hypothesis, there is a packing f' for the remaining m items, and assigning the first item to j₀ decomposes each bin's count into the first item plus the rest.

    Applying the induction hypothesis to the loads L' and remaining m items gives a valid packing f' : Fin m → Fin b. We define an assignment for all m + 1 items by mapping the first item (index 0) to j₀ and the remaining m items according to f'. Using the counting lemma Fin.card_filter_univ_succ, the total number of items assigned to bin j is |(f')⁻¹(j)| + 1 if j = j₀, and |(f')⁻¹(j)| if j ≠ j₀.

    lines 56–61

    uses Fin.card_filter_univ_succ, Fin.cons_zero, Fin.cons_succ

          rcases ih L' hL' h_sum' with ⟨f', hf'⟩
          refine ⟨Fin.cons (α := fun _ => Fin b) j₀ f', ?_⟩
          intro j
          have h_card := @Fin.card_filter_univ_succ m (fun (i : Fin (m + 1)) => (Fin.cons (α := fun _ => Fin b) j₀ f') i = j) _
          simp only [Fin.cons_zero, Fin.cons_succ] at h_card
          have h_ih_j := hf' j
  7. Every bin j respects its capacity under the extended packing: L_j + |f⁻¹(j)|η ≤ C_j.

    We split into cases on whether j = j₀: if j = j₀, the bin receives the first item, so its load is L_{j₀} + (|(f')⁻¹(j₀)| + 1)η = (L_{j₀} + η) + |(f')⁻¹(j₀)|η = L'_{j₀} + |(f')⁻¹(j₀)|η ≤ C_{j₀}, which holds by the induction hypothesis on f'. If j ≠ j₀, the bin receives no additional item, so its load is L_j + |(f')⁻¹(j)|η = L'_j + |(f')⁻¹(j)|η ≤ C_j, which also holds by the induction hypothesis on f'.

    lines 62–70

    uses Function.update_self, if_pos, Function.update_of_ne, Ne.symm, if_neg

          by_cases hj : j₀ = j
          · subst hj
            rw [hL'_def, Function.update_self] at h_ih_j
            rw [h_card, if_pos rfl]
            push_cast
            linarith
          · rw [hL'_def, Function.update_of_ne (Ne.symm hj)] at h_ih_j
            rw [h_card, if_neg hj]
            exact h_ih_j
add_zero
Adding zero to an element leaves it unchanged (a + 0 = a).
Fin.cons_zero
Evaluating the tuple extension `Fin.cons x p` at index 0 yields the head element x.
Fin.cons_succ
Evaluating the tuple extension `Fin.cons x p` at a successor index i.succ yields p(i).
Fin.card_filter_univ_succ
The count of elements in Fin (n + 1) satisfying predicate p is the count on Fin n (via successor) plus 1 if 0 satisfies p, and 0 otherwise.
Fin.pos_iff_nonempty.mp
If n > 0, then the type Fin n is nonempty.
Finset.add_sum_erase
Adding f(a) to the sum of f over a finset s with a erased yields the full sum over s.
Finset.card_empty
The cardinality of the empty finset is 0.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.filter_eq_empty_iff
A filtered finset is empty if and only if no element in the finset satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.sdiff_singleton_eq_erase
Removing a singleton {a} from a finset by set difference is equivalent to erasing a.
Finset.sum_add_distrib
The sum of a pointwise sum of functions over a finset equals the sum of the individual sums.
Finset.sum_const
Summing a constant over a finset equals the cardinality of the finset multiplied by the constant.
Finset.sum_empty
The sum of any function over the empty finset is 0.
Finset.sum_lt_sum_of_nonempty
If a finset is nonempty and f(i) < g(i) for all elements i in the finset, then the sum of f is strictly less than the sum of g.
Finset.sum_update_of_mem
The sum over a finset s of a function updated at i ∈ s with value b equals b plus the sum of the original function over s with i removed.
Finset.univ_eq_empty
The universal finset of an empty type is the empty finset.
Finset.univ_nonempty_iff.mpr
If a finite type is nonempty, then its universal finset is nonempty.
Fintype.card_fin
The cardinality of Fin n is n.
Function.update_self
An updated function f[a ↦ v] evaluated at a equals v.
Function.update_of_ne
An updated function f[a' ↦ v] evaluated at an input a ≠ a' equals the original value f(a).
if_neg
If condition c is false, then `if c then t else e` reduces to e.
if_pos
If condition c is true, then `if c then t else e` reduces to t.
MulZeroClass.zero_mul
Zero multiplied by any element is zero (0 * a = 0).
Nat.cast_zero
The coercion of the natural number 0 into an additive monoid with one is 0.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is non-negative (0 ≤ n).
Nat.eq_zero_or_pos
Every natural number is either equal to 0 or strictly positive.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
nsmul_eq_mul
Scalar multiplication by a natural number n • a is equal to the ring product (n : R) * a.
zero_add
Adding zero on the left leaves an element unchanged (0 + a = 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

theorem exists_bin_packing_of_total_capacity_ge {b m : ℕ} (C L : Fin b → ℝ) (η : ℝ)    (hη : 0 < η) (hL : ∀ j, L j ≤ C j) (h : ∑ j, L j + (m + b) * η ≤ ∑ j, C j) :    ∃ f : Fin m → Fin b, ∀ j, L j + (Finset.univ.filter (fun i => f i = j)).card * η ≤ C j := by  revert L  induction m with  | zero =>    intro L hL h    refine ⟨fun i => i.elim0, ?_⟩    intro j    have : (Finset.univ.filter (fun (i : Fin 0) => (fun _ => i.elim0) i = j)) = ∅ := by      rw [Finset.filter_eq_empty_iff]      intro i      exact i.elim0    rw [this, Finset.card_empty, Nat.cast_zero, MulZeroClass.zero_mul, add_zero]    exact hL j  | succ m ih =>    intro L hL h    rcases Nat.eq_zero_or_pos b with rfl | hb    · simp only [Finset.univ_eq_empty, Finset.sum_empty, zero_add] at h      have hpos : 0 < ((m + 1 : ℝ) * η) := by positivity      push_cast at h      linarith    · have hex : ∃ j₀ : Fin b, L j₀ + η ≤ C j₀ := by        by_contra! h_all        have h_ne : (Finset.univ : Finset (Fin b)).Nonempty :=          Finset.univ_nonempty_iff.mpr (Fin.pos_iff_nonempty.mp hb)        have h1 : ∑ j, C j < ∑ j, (L j + η) := Finset.sum_lt_sum_of_nonempty h_ne (fun j _ => h_all j)        rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h1        have hm : 0 ≤ (m : ℝ) := Nat.cast_nonneg m        have h_exp : (↑(m + 1) + ↑b : ℝ) * η = (m : ℝ) * η + η + (b : ℝ) * η := by          push_cast          ring        nlinarith      rcases hex with ⟨j₀, hj₀⟩      set L' := Function.update L j₀ (L j₀ + η) with hL'_def      have hL' : ∀ j, L' j ≤ C j := by        intro j        by_cases hj : j = j₀        · subst hj          rw [hL'_def, Function.update_self]          exact hj₀        · rw [hL'_def, Function.update_of_ne hj]          exact hL j      have h_sum' : ∑ j, L' j + ((m : ℝ) + (b : ℝ)) * η ≤ ∑ j, C j := by        have hi : j₀ ∈ (Finset.univ : Finset (Fin b)) := Finset.mem_univ j₀        have h1 := Finset.sum_update_of_mem hi L (L j₀ + η)        rw [Finset.sdiff_singleton_eq_erase] at h1        have h2 := Finset.add_sum_erase Finset.univ L hi        have h_sum : ∑ j, L' j = (∑ j, L j) + η := by          rw [hL'_def, h1]          linarith        have : (↑(m + 1) + ↑b : ℝ) * η = (↑m + ↑b) * η + η := by          push_cast          ring        linarith      rcases ih L' hL' h_sum' with ⟨f', hf'⟩      refine ⟨Fin.cons (α := fun _ => Fin b) j₀ f', ?_⟩      intro j      have h_card := @Fin.card_filter_univ_succ m (fun (i : Fin (m + 1)) => (Fin.cons (α := fun _ => Fin b) j₀ f') i = j) _      simp only [Fin.cons_zero, Fin.cons_succ] at h_card      have h_ih_j := hf' j      by_cases hj : j₀ = j      · subst hj        rw [hL'_def, Function.update_self] at h_ih_j        rw [h_card, if_pos rfl]        push_cast        linarith      · rw [hL'_def, Function.update_of_ne (Ne.symm hj)] at h_ih_j        rw [h_card, if_neg hj]        exact h_ih_j
See it in the graphDiscuss this resultChallenge it