33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限

人工衛星の地上局が直面した「一つしか選べない」問題

1989年、テキサス大学オースティン校のRobert Holteたちは、ある実務上の困りごとを数学の問題として定式化した。複数の人工衛星がそれぞれ決まった間隔でデータを送信してくる。地上局のアンテナは一度に一つの衛星しか受信できない。各衛星について「連続する$a_i$日間に必ず1回は受信する」という条件を満たしつつ、無限に続く受信スケジュールを組めるか。この問いが輪番割当問題（pinwheel scheduling problem）の始まりだった。

問題の構造は単純だ。$k$個の仕事があり、仕事$i$は$a_i$日ごとに必ず1回実行しなければならない。1日に実行できる仕事はちょうど1つ。スケジュールが存在するか否かを判定したい。

密度$\mathrm{D}(A)={\sum }_{i=1}^k\frac{1}{a_i}$という量がこの問題の核心を握る。各仕事の「1日あたりの実行頻度」の合計であり、これが1を超えれば物理的にスケジュール不可能である。1日に1つしか仕事をこなせないのに、要求される総仕事量が1日あたり1を超えるのだから当然だ。

ところが密度1以下という条件は、スケジュール可能性を保証しない。最も有名な反例は$(2, 3, m)$（$m\ge 6$）である。密度は$\frac{1}{2}+\frac{1}{3}+\frac{1}{m}=\frac{5}{6}+\frac{1}{m}$であり、$m$を大きくすれば1にいくらでも近づけられるが、この組はどんな$m$を選んでもスケジュール不可能だ。2日周期の仕事と3日周期の仕事が互いに干渉し、3番目の仕事を割り込む隙間が永遠に残らない。

0.5から0.75へ、四半世紀かけて0.083だけ進んだ密度閾値

密度が十分小さければスケジュール可能であることは早い段階でわかっていた。Holteたちは1989年に密度$\le \frac{1}{2}$で十分であることを示した。ここから「どこまで密度を上げても大丈夫か」という閾値の引き上げ競争が始まる。

ChanとChinは1992年に二重整数削減により密度$\le 0.7$を達成し、翌1993年のAlgorithmica論文で貪欲スケジューリングに基づく$\le \frac{2}{3}$の結果を報告した。2002年、Bell研究所のPeter FishburnとJeffrey Lagariasが$\le \frac{3}{4}$に到達する。しかしそこから先が遠かった。

年	研究者	密度閾値	手法
1989	Holte, Mok, Rosier, Tulchinsky, Varvel	1/2 ≈ 0.500	周期の2べき乗への丸め
1992	Chan, Chin	0.700	二重整数削減
1993	Chan, Chin	2/3 ≈ 0.667	貪欲スケジューリング
2002	Fishburn, Lagarias	3/4 = 0.750	組合せ論的解析
2026	Kawamura	5/6 ≈ 0.833	実数周期への拡張＋計算機全探索

ChanとChinは1993年、Algorithmica誌に掲載した論文の中で一つの予想を立てた。密度$\le \frac{5}{6}$ならば必ずスケジュール可能であり、$(2,3,m)$の反例がある以上これ以上は望めない、と。この「6分の5予想」は、以後30年以上にわたって実時間スケジューリング理論の中心的未解決問題として残り続けた。

部分的な成果はあった。周期値が3種類以下の場合（Lin & Lin, 1997）、最小周期が2の場合（Fishburn & Lagarias, 2002）、各周期値に5つ以上の仕事がある場合（Baruah & Lin, 1998）、仕事数が12以下の場合（Gąsieniec, Smith & Wild, 2022）。特殊な場合に予想が正しいことは確認されていったが、一般的な証明には誰も到達しなかった。

無限を有限にたたむ「折りたたみ」という発想の転換

河村彰星が2024年6月、バンクーバーで開催されたSTOC（ACM計算理論シンポジウム）で証明の概略を発表したとき、その手法の核心は意外なほど素朴な操作にあった。

証明の全体像は二段構えである。第一段階で、無限に存在する「スケジュール不可能な候補」を、有限個の小さな实例に帰着させる。第二段階で、その有限個の实例を計算機で実際に検証する。

第一段階の鍵となるのが「折りたたみ」（folding）と呼ばれる操作だ。周期$a$が閾値$\theta$を超えている仕事について、次の二つの操作を繰り返す。

• 周期$a$の仕事が1つだけなら、その周期を$\theta$より大きい次に大きな周期に縮める（$a$が$\theta$を超える唯一の周期であれば$\theta$に縮める）。
• 周期$a$の仕事が2つ以上あれば、そのうち2つを1つにまとめ、周期を$a/2$にする。

どちらの操作も「スケジュール不可能性を保存する」。つまり、操作後の实例がスケジュール可能なら、元の实例もスケジュール可能である。この操作を繰り返すと、どんな实例も最終的には周期がすべて$\theta$以下の实例に変換される。河村は$\theta =22$を選んだ。この値で折りたたむと、密度の増加は$\frac{1}{22}$以下に抑えられることが示せる。

ここで第二の工夫が入る。折りたたみ後の实例には、整数ではない周期（たとえば$\frac{55}{4}=13.75$）が現れうる。河村は問題自体を「周期が正の実数でもよい」versionに拡張した。非整数周期$r$の仕事は「任意の$t$日間に少なくとも$\lfloor t/r\rfloor$回実行する」と定義し直す。この拡張によって、折りたたみ操作で生じる中間的な实例を数学的に扱えるようになる。

折りたたみ後の非整数周期を$\lceil b\rceil -1$（$b$未満の最大の整数）に置き換えると、最終的に周期がすべて22未満の整数である有限個の实例の集合${\mathcal{C}}_{5/6}^{22}$が得られる。この集合に属するすべての实例がスケジュール可能であることを示せば、元の予想が証明される。

61,616個のスケジュールを計算機が書き下す

第二段階は計算機による全探索である。集合${\mathcal{C}}_{5/6}^{22}$の規模は大きい。河村の補足資料によると、条件を満たす实例の総数は25,592,971個に達する。これを包含関係による最小性で絞り込むと676,224個になり、さらにスケジュールの提示で検証が必要な实例は61,616個に圧縮された。

各实例のスケジュール可能性は「状態グラフ法」で判定する。各仕事の「次回の期限までの残り日数」を状態として表現し、状態遷移グラフに閉路が存在すればスケジュール可能である。状態数は周期の積に比例するため指数オーダーに膨れるが、河村は先行研究（Gąsieniec, Smith & Wild, 2022）の効率化技法を拡張して実装した。

こうして2026年8月7日、論文「Proof of the density threshold conjecture for pinwheel scheduling」がPNAS（米国科学アカデミー紀要）にオンライン掲載された（DOI: 10.1073/pnas.2530214123）。33年間未解決だった予想に終止符が打たれた。

裏返しの被覆型でも最適限界1.264...を確定

河村と小林佑輔は、この手法を「裏返した」問題にも適用した。被覆型輪番割当（pinwheel covering）である。

詰込型（packing）が「仕事$i$を$a_i$日間に少なくとも1回実行せよ」という下限の制約なのに対し、被覆型は「エージェント$i$は$a_i$日間に至多1回しか担当できない」という上限の制約を課す。毎日必ず実行しなければならない一つのタスクを、複数のエージェントで分担する状況に対応する。

被覆型でも密度$\mathrm{D}(A)=\sum \frac{1}{a_i}\ge 1$がスケジュール可能性の必要条件だが、十分ではない。$(2, 3, 5)$は密度$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}=\frac{31}{30}>1$を満たすが、8日間すらカバーし続けられないことが容易に示せる。

2020年、KawamuraとSoejimaは密度$\ge 1.546$でスケジュール可能であることを示し、最適値は${\alpha }^{\text{*}}={\sum }_{i=1}^{\infty }\frac{1}{2^{i-1}+1}=1.264\dots$であろうと予想した。この値は反例の系列$(2,3,5,9,17,\dots )$、すなわち周期が$2^{i-1}+1$の系列の密度が$k \to \infty$で収束する先である。

河村と小林は、詰込型の証明で開発した折りたたみと実数周期の技法を被覆型に適応させ、この予想を肯定的に解決した。2025年10月にarXivにプレプリント（arXiv:2510.06533）を公開し、2026年8〜9月のESA（欧州算法シンポジウム）で発表する。被覆型では検証すべき实例が25,242,331個とさらに多く、並列スケジューリングや対称性による状態削減などの追加技法が必要だった。

竹を刈る問題にも波及した近似比4/3の保証

副産物も小さくない。輪番割当問題と密接に関連する「竹叢伐採問題」（bamboo garden trimming problem, BGT）は、成長速度の異なる$n$本の竹を1日1本だけ刈り、最も高い竹の高さを最小化する問題である。この問題の近似アルゴリズムの性能は、輪番割当の密度閾値と直接結びつく。

密度閾値が$\frac{3}{4}$だった時代、BGTの最良近似比は$\frac{4}{3}+\epsilon$程度にとどまっていた。河村の証明によって密度$\frac{5}{6}$が確定したことで、近似比$\frac{4}{3}$の高速アルゴリズムが理論的に保証されるようになった。なお、この結果に触発された後続研究が近似比$\frac{9}{7}\approx 1.286$への改善を報告している（arXiv:2510.22060）。

指標	従来（2022年時点）	本研究（2026年）
詰込型の密度閾値	3/4 = 0.750（Fishburn & Lagarias, 2002）	5/6 ≈ 0.833（最適値）
被覆型の密度閾値	1.546（Kawamura & Soejima, 2020）	α* = 1.264...（最適値）
BGT近似比（本手法由来）	4/3 + ε（密度3/4ベース）	4/3（密度5/6ベース、高速オンラインスケジューラ）
検証实例数（詰込型）	仕事数≤12の範囲（Gąsieniec et al., 2022）	61,616個（周期 < 22の全範囲）

計算機が書いた証明は「数学」か

この証明は「計算機支援証明」（computer-assisted proof）である。理論部分が「なぜ有限個の検証で十分か」を保障し、計算機が実際にその有限個を検証する。四色定理（1976年）やケプラー予想（1998年、2017年に形式検証完了）と同様の構造を持つが、河村自身はより簡潔な証明の可能性を排除していない。

京都大学の発表の中で河村は「人間が読める『きれいな』証明が今後得られる望みも捨ててはいません」と述べている。同時に「近年のAIをはじめとする計算機技術の著しい進歩は、数学研究に新たな可能性と展開をもたらしつつあります」とも語り、計算機と数学の協働が常態化しつつある現状を認めている。

実際、この証明の理論部分には人間が読める美しい構造がある。折りたたみ操作の保存性、実数周期への拡張、閾値$\theta =22$の選択。これらは計算機に依存しない数学的洞察である。計算機が担ったのは、最終的な有限検証の部分だけだ。

密度の「隙間」に残る問い

証明の過程で、計算機実験から新たな予想が生まれた。密度$\frac{5}{6}$付近でスケジュール不可能な实例は、$(2,3,a_3)$型と$(3,4,4,a_4)$型がほとんどを占める。河村は、最小周期$a_1$ごとに密度閾値$1-\frac{a_1-1}{a_1(a_1+1)}$が成り立つという予想（Conjecture 8）を提起した。$a_1=2$なら$\frac{5}{6}$、$a_1=3$なら$\frac{11}{12}$、$a_1=4$なら$\frac{17}{20}$である。

この予想が正しければ、最小周期が大きい实例ほど高密度でもスケジュール可能ということになり、実装上の自由度がさらに広がる。ただし、この予想の証明には今回の手法とは異なる構造的な理解が必要と考えられている。

もう一つの未解決問題は、輪番割当問題の計算複雑性である。スケジュール可能性の判定がPSPACEに含まれることは1989年から知られていたが、NPに属するか、NP困難であるかは長年未決だった。2026年4月にarXivに投稿された論文（arXiv:2604.13974）がNP困難性を主張しており、この方向の決着も近い。

30年以上にわたって「たぶん正しいだろう」と信じられ続けてきた一つの不等式が、折りたたみという素朴な操作と61,616個のスケジュールの書き下しによって確定した。次の問いは、この確定した事実の上にどんな構造が見えてくるかである。