ГИПОТЕЗА 1969 ГОДА О СУММАХ, КОТОРЫЕ ВЗАИМНО КОМПЕНСИРУЮТСЯ, ОКАЗАЛАСЬ ЛОЖНОЙ
Возьмите циферблат на шесть часов и список ходов: «перевести стрелку вперёд на 1 час», «вперёд на 4 часа» и так далее. При пяти ходах по одному часу никакая их группа никогда не вернёт стрелку точно в исходное положение. При шести ходах, какими бы они ни были, какая-то группа всегда это сделает. Математики записывают эту арифметику циферблата как C₆, а число шесть здесь — константа Дэвенпорта этого циферблата.
Теперь поставьте r таких циферблатов рядом, и пусть каждый ход поворачивает каждую стрелку на свою величину. Константа Дэвенпорта этого набора циферблатов, обозначаемая D(C₆^r), — наименьшее число ходов, которое гарантирует группу, чья сумма возвращает все стрелки в исходное положение одновременно, — подпоследовательность с нулевой суммой, по выражению статьи. Эта константа связана с задачами теории графов, конечной геометрии, комбинаторики и теории факторизации.
Формула 1969 года
Существует простая нижняя граница. На каждом циферблате возьмите пять ходов по одному часу, затрагивающих только этот циферблат: при r циферблатах это даёт 5r ходов, среди которых ни одна группа не компенсирует сама себя. Значит, нужно не меньше 5r + 1 ходов. В общем случае, для циферблатов с n часами, — не меньше r(n − 1) + 1.
В 1969 году ван Эмде Боас (van Emde Boas) и Кройсвейк (Kruyswijk) высказали гипотезу, что эта простая граница всегда и есть точный ответ:
D(C_n^r) = r(n − 1) + 1.
Для некоторых случаев она была доказана в 1960-х годах — например, для циферблатов, число часов на которых является степенью простого числа, или не более чем для двух циферблатов. Дальше точное значение оставалось недосягаемым: ещё в 2018 году не был известен даже случай четырёх циферблатов на шесть часов. Тем не менее гипотеза стала «известной давней проблемой» этой области, и от неё ожидали, что она верна.
116 ходов, которые никогда не компенсируются
Вэйдун Гао (Weidong Gao, Тяньцзиньский университет), Альфред Герольдингер (Alfred Geroldinger, Грацский университет), Гоцин Ван (Guoqing Wang, Университет Тяньгун) и Сяннэн Цзэн (Xiangneng Zeng, Университет Сунь Ятсена) теперь показывают, что она неверна.
Команда собирает ходы, как из строительных блоков:
- список из 24 ходов на пяти циферблатах на шесть часов, построенный по небольшой таблице: любая их группа, сумма которой попадает в небольшое множество из трёх положений, всегда оказывается в одном и том же ненулевом из них;
- два таких списка, у которых эти три положения общие, что даёт 48 ходов без единой группы, которая бы компенсировала сама себя;
- отдельный список из 20 ходов, в котором тоже ни одна группа не компенсирует сама себя.
Поставленные рядом, они дают 2 × 48 + 20 = 116 ходов на 23 циферблатах на шесть часов, и ни одна их группа не возвращает все стрелки в исходное положение. Согласно гипотезе, 23 × 5 = 115 — самый длинный возможный такой список. Значит, для 23 циферблатов константа Дэвенпорта не меньше 117, а не 116.
Копии этого блока можно ставить друг на друга: общий результат состоит в том, что D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, где ⌊r/23⌋ показывает, сколько целых блоков по 23 помещается в r. Следовательно, гипотеза ложна для циферблатов на шесть часов, как только r достигает 23, и для всех бо́льших r. Авторы отмечают, что та же теорема опровергает и предполагавшийся результат о покрытиях.
Что остаётся открытым
Доказательство не даёт истинного значения D(C₆^r), а лишь границу, которую гипотеза запрещает. Оно не говорит ничего нового ни для менее чем 23 циферблатов, где новая граница совпадает со старой формулой, ни для циферблатов с числом часов, отличным от шести. Заметка занимает пять страниц, а рецензирование ещё впереди.
