От D(8) до D(9) — путь в 30 лет. Почему следующее число Дедекинда человечество может не узнать никогда.

В математике иногда случаются новости, которые звучат как чистая фантастика: ученые десятилетиями ищут одно число, а когда находят, оно выглядит как телефонный справочник для Вселенной. Именно так в 2023 году произошло с D(9) - девятым числом Дедекинда, которое смогли вычислить сразу две независимые команды.

История у последовательности почти детективная. В 1897 году немецкий математик Рихард Дедекинд упомянул первые значения в трактате 1897 года. Тогда же он заметил, что числа растут очень быстро, и не стал выводить общую формулу. Спустя более века ее по-прежнему нет, а каждый новый шаг приходится добывать вычислениями.

Что именно считают числа Дедекинда, можно представить как игру с n-мерным кубом. Вы ставите такой куб на угол и красите вершины в белый или красный цвет так, чтобы белая вершина никогда не оказалась "выше" красной. Разных допустимых границ между цветами получается очень много, и их количество и есть D(n). Это популярное объяснение в 2023 году давал исследователь Леннарт Ван Хиртум в заметке университета Падерборна в 2023 году.

Есть и другие равноправные интерпретации. Например, через решетки подмножеств и антицепи, или через монотонные булевы функции: это такие бинарные функции, где переключение входа с 0 на 1 не может заставить выход перейти с 1 на 0. В каком бы виде ни объяснять, результат один: значения быстро становятся гигантскими.

Из-за этого прогресс шел рывками. Одно из ранних продвижений описывалось в классической работе по вычислениям дискретных структур в Duke Mathematical Journal. Позже очередной крупный шаг появился в публикации AMS (1946). А вычисление D(8) в 1991 году стало отдельной вехой: тогда на мощном суперкомпьютере ушли сотни часов.

К 2023 году D(9) выглядело "просроченным" рекордом, но в лоб задача не сдавалась. Рост мощности вычислений сам по себе не спасал, даже с учетом закона Мура: то, что для D(8) считается за минуты, для D(9) превращается в сроки, сравнимые с историей цивилизации. Нужно было радикально сокращать объем работы за счет симметрий и специальных формул.

Первая команда делала ставку на суперкомпьютер Noctua 2 и параллельные вычисления. Там даже оценивали риск редких аппаратных сбоев, вплоть до влияния космических лучей. О параллельной "внутренней" гонке стало известно позднее: математик Кристиан Якель из Дрездена шел другим путем, опираясь на матричные вычисления, и смог обойтись без суперкомпьютера, пусть и ценой примерно месяца непрерывного счета. Его историю подробно рассказывали в новостях TU Dresden в 2023 году.

Весной 2023 года Якель опубликовал результат, а буквально через несколько дней получил независимое подтверждение от второй команды. Именно совпадение двух методов стало главным аргументом, что число действительно верное. О вычислении и значении результата рассказывал в том же году и научпоп, включая Scientific American. Итоговое значение D(9) оказалось 42-значным "монстром": 286,386,577,668,298,411,128,469,151,667,598,498,812,366.

Дальше становится еще страннее. По оценкам участников, переход к D(10) - это не просто "еще сложнее", а качественно другой масштаб: требования к ресурсам выглядят астрономическими, а само число обещает быть сопоставимым по порядку величины с числом атомов в наблюдаемой Вселенной. Скепсис по поводу D(10) в 2023 году обсуждался и в New Scientist. Так что D(9) закрывает красивую главу, но следующую страницу математика, похоже, пока не готова перевернуть.