グラハムの55年来の並べ替え予想、ついに証明される

数がすべて正、あるいは正負が混在する場合は答えが「はい」だと知られていた。難しいのは、素数pで数が繰り返される「時計の算術」の世界だ。グラハムはここでも答えは「はい」だと予想したが、数十年間証明できなかった。

ランダム性が鍵

オックスフォード大学のアルプ・ミュイェセル氏とユニバーシティ・カレッジ・ロンドンのアレクセイ・ポクロフスキー氏は、pまでのほぼすべての数を含む大きな集合を扱った。特別な数をいくつか取り分け、残りをランダムに並べ、和が0になる区間があれば取り分けた数を挿入して直す手法で、2022年に発表した。

一方、オックスフォード大学のノア・クラヴィッツ氏とベンジャミン・ベダート氏は、pに比べて集合が極めて小さい場合を証明し、2024年9月に公表した。両者は協力し、2025年8月の論文で大きな集合のさらなるケースを扱ったが、中間サイズの集合は残っていた。それを埋めたのが2026年2月の最終論文だ。

プリンストン大学のノガ・アロン氏は、解決を導いたのは「協力、若い世代、確率的手法の力」だと述べている。