A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel Scheduling
In the authors' words
In pinwheel scheduling with real periods, an instance consists of tasks with real periods . The goal is to find a schedule that assigns one task to each day indefinitely such that, for every task and every positive integer , task occurs at least times in every block of consecutive days. Given an instance , its dimension is , its density is , and its potential is . We prove that every real-valued instance of density at most 5/6 admits a periodic schedule of period length less than . For integer periods, the 5/6 density bound was a long-standing conjecture settled by Kawamura using a computer-assisted proof [STOC 2024, PNAS 2026]. Our result confirms the real-period conjecture of Fujiwara, Miyagi, and Ouchi [DMTCS 2026]. Our computer-assisted proof builds on Kawamura's ideas while using fewer explicit schedules. It combines dimension reduction by folding with nine satisfiability modulo theories (SMT) checks over linear real arithmetic. A set of 14287 explicit periodic schedules contains a schedule for every instance of dimension at most 8 and density at most 5/6, and for every instance of dimension 9 and potential at most 5/6. Folding is used to reduce every instance of larger dimension and potential at most 5/6 to an instance of dimension 9 and the same potential bound. We also prove that every real-valued instance with minimum period at least 4 and density at most 17/20=0.85 admits a periodic schedule of period length less than . The density bound 17/20 is tight and improves the 0.84-bound of Mishra, Rho, and Kleinberg [arXiv 2025] for integer periods. It also resolves the case of Kawamura's 2025 conjecture that integer-valued instances of density at most are schedulable.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.