Theorem 4.1 — for ,
ProvedBinPacking.SmallItems.ffd_le_seventy_one_sixtiethsLet be a list of real numbers, each lying in , and let be the minimum number of unit-capacity bins into which can be packed. Then First-Fit Decreasing uses
bins.
The constant is best possible: the Remark after the theorem gives lists with whose elements are all below . The theorem is the model case of the weighting-function method that proves the general bound for FFD.
Formalization Note is First-Fit applied to the nonincreasing rearrangement of , and is optBins L; see the model definition file.
import Mathlib import Definitions.Def_BinPacking_SmallItems_Model
namespace BinPacking.SmallItems
/-- Theorem 4.1 (p. 314): for all lists `L ⊆ (0, 1/2]`, `FFD(L) ≤ (71/60)L* + 5`. -/
theorem ffd_le_seventy_one_sixtieths (L : List ℝ) (hL : IsList L) (hhalf : ∀ a ∈ L, a ≤ 1 / 2) :
(FFD L : ℝ) ≤ 71 / 60 * (optBins L : ℝ) + 5 := by sorry
end BinPacking.SmallItems
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every list of real numbers that satisfies the predicate and in which every entry satisfies , the statement asserts
Objects involved.
- is a finite list of real numbers. Its length is arbitrary. Order and repeated values are allowed.
- is a hypothesis about . It comes from the imported module
Definitions.Def_BinPacking_SmallItems_Model, and that module's text is not part of the code given here. So this read-back cannot say what the hypothesis requires, for example whether it forces every entry to be strictly positive or bounds the entries in some other way. It is exactly the condition that module defines, nothing more or less. - and also come from that imported module, and their definitions are not shown either. From the names, one would guess that is the number of bins the First-Fit-Decreasing heuristic uses on , and that is the least number of bins that can hold . The code itself does not confirm either guess. What the statement does show is that both are converted to real numbers before being compared, so they are presumably natural-number (or integer) counts. The inequality is checked in .
- The only other explicit hypothesis is the upper bound for every entry of . The statement itself sets no lower bound on the entries. Any lower bound, such as , exists only if imposes it.
- The constants are exact. The multiplicative factor is and the additive constant is . The inequality is non-strict (). It is claimed for every admissible , not only in the limit as .
The comment attached to the declaration says "for all lists ". That comment is documentation, not part of the formal statement. The formal hypotheses are exactly and for every .
Degenerate cases.
- Empty list. If is empty and accepts it, the upper-bound hypothesis holds vacuously. The statement then asserts , whatever values the imported definitions give for the empty list. If both are , this reads .
- One-element list. For with , the claim is .
- Zero or negative entries. Whether entries equal to or below are admitted depends only on . If they are admitted, the statement covers them too, with whatever values and assign to such lists.
- Vacuous cases. If can never hold together with the bound, the statement is vacuously true. The code shown does not let one decide this.
- Small inputs. Because of the additive , the inequality holds automatically for any admissible with , provided .
- No junk values. The statement contains no division by a variable, no subtraction of naturals, and no suprema or integrals. The only operations whose behaviour is not visible here are those inside the imported definitions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.