Lemma 13 (used in the proof of Theorem 4) — reduction to ten tasks
OpenRealPinwheel.FiveSixths.Supplement.potential_reductionp2o-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 there exists an ordered real-period instance such that
The witness has exactly ten tasks. This reduction supports Theorem 4 and includes , where is permitted. It asserts ordinary schedulability transfer; the quantitative period control for Theorem 4 remains an additional proof obligation.
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 13, printed p. 11 (PDF p. 12); proof printed p. 12 (PDF p. 13).
The ten-task witness retains both the minimum-period and potential bounds. -/
theorem potential_reduction {n : ℕ} (A : Instance n) (hn : 10 ≤ n)
(hmin : 4 ≤ A.period ⟨0, A.positive_dimension⟩)
(hP : potential A ≤ (17 : ℝ) / 20) :
∃ B : Instance 10,
4 ≤ B.period ⟨0, B.positive_dimension⟩ ∧
potential B ≤ (17 : ℝ) / 20 ∧
(Schedulable B.period → 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 13, printed p. 11 (PDF p. 12); proof printed p. 12 (PDF p. 13)