В мире математики, где доказуемость имеет решающее значение, последовательность чисел Дедекінда считается одной из самых сложных для вычисления. Ещё в 1897 году Рихард Дедекинд предложил свою знаменитую последовательность, которая началась с пяти чисел: 0, 1, 4, 18 и 166. Он заметил, что эти числа «кажутся, очень быстро растут», и с тех пор вычисление каждого следующего члена этой последовательности стало настоящим вызовом для математиков всего мира.
Об этом сообщает ProIT
Числа Дедекінда: сложность и способы вычисления
Числа Дедекінда можно описать несколькими эквивалентными способами, каждый из которых связан с значительными вычислительными трудностями. Один из вариантов заключается в подсчёте способов раскрашивания вершин n-мерного куба в белый или красный цвет так, чтобы белый угол не находился над красным. Например, для n = 0 существует 2 способа, для n = 1 — 3, для n = 2 — 6, а для n = 3 — 20. В четвёртом измерении это число равно 168, если учитывать современную нумерацию с учётом всех случаев.
Ещё один подход определяет эти числа как количество антисетей в решётке подмножеств, где ни одно из подмножеств не содержится в другом. Третий способ, предложенный самим Дедекиндом, основан на подсчёте количества монотонных булевых функций для n бинарных переменных, когда изменение с 0 на 1 не может повлиять на выход в обратном направлении.
«Числа Дедекінда можно представить тремя эквивалентными способами, каждый из которых является вычислительно сложным. Наиболее наглядный заключается в игре с n-мерным кубом, где необходимо подсчитать количество способов раскрашивания углов в белый или красный цвет так, чтобы белый угол никогда не находился над красным».
32 года поисков: как удалось найти девятое число
Несмотря на растущую сложность, исследователи неустанно работали над поиском новых чисел Дедекінда. Пятое число (7581) удалось найти лишь через 40 лет после работы Дедекінда, шестое (7 828 354) — в 1946 году, а седьмое (2 414 682 040 998) — в 1965-м. Восьмое число, состоящее из 23 цифр (56 130 437 228 687 557 907 788), было вычислено в 1991 году с помощью суперкомпьютера за 200 часов. Бартломей Павельский из Гданьского университета назвал этот процесс «вычислительным вызовом», который решается каждые 20–30 лет. Поэтому D(9) оставалось «открытой проблемой» вплоть до 2023 года.
Решить эту задачу удалось сразу двум независимым командам учёных. Группа Леннарта Ван Гиртума из Падерборнского университета, воспользовавшись симметриями в формуле, сократила вычисления до 5,5×1018 терминов, выполнив их на суперкомпьютере Noctua 2. Параллельно Кристиан Екель из Дрезденского технического университета разработал собственный метод на основе умножения матриц, который позволил получить результат за месяц на обычном компьютере. В марте 2023 года Екель опубликовал своё решение — 42-значное число: 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Через три дня команда Ван Гиртума подтвердила идентичность результата, завершив 32-летний поиск девятого числа Дедекінда.
Теперь охота за D(10) стала новой амбициозной целью. Однако учёные отмечают, что сложность этой задачи возрастает до «абсолютно астрономического» уровня. По оценкам Ван Гиртума, для вычисления D(10) потребовалась бы энергия, сопоставимая с мощностью Солнца, а само число может быть близким к количеству атомов в видимом Вселенной. Екель также считает, что найти следующий член последовательности удастся не раньше, чем через несколько сотен лет. Таким образом, числа Дедекінда остаются одной из самых сложных и захватывающих задач современной математики.