Lemma 11 (used in the proof of Theorem 4) — density base through nine tasks
OpenRealPinwheel.FiveSixths.Supplement.density_basep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pinwheel-schedulingreal-periods
Let be a nonempty ordered real-period instance with . Periods may be irrational, and equal periods label distinct tasks. Write for density and for potential. Schedulability means that a single schedule assigns exactly one task to each day and, for every task , positive integer and starting day , executes at least times in .
If , and , then
This is the density base case supporting Theorem 4, including every nonempty dimension from one through nine and equality at both bounds.
Differences from the source:
- encoding: positive days and task labels 1 through n → natural days starting at zero and task positions Fin n; reason: day t encodes source day t+1 and position i encodes source task i+1; all windows and distinct task identities are preserved
Preamble
import Definitions.Def_RealPinwheel_FiveSixths_Instance
Formal statement
namespace RealPinwheel.FiveSixths.Supplement
/-- Lemma 11, printed p. 11 (PDF p. 12); proof printed p. 12 (PDF p. 13).
The first position is the minimum period because Instance includes monotonicity. -/
theorem density_base {n : ℕ} (A : Instance n) (hn : n ≤ 9)
(hmin : 4 ≤ A.period ⟨0, A.positive_dimension⟩)
(hD : density A ≤ (17 : ℝ) / 20) :
Schedulable A.period := by sorry
end RealPinwheel.FiveSixths.Supplement
Source
Hiroshi Fujiwara, Grzegorz Gutowski, Katsuhisa Ouchi, Alexander Wolff, STOC 2027 submission #885 (October 2026), Lemma 11, printed p. 11 (PDF p. 12); proof printed p. 12 (PDF p. 13)