У світі математики, де доказовість має вирішальне значення, послідовність чисел Дедекінда вважається однією з найскладніших для обчислення. Ще в 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) знадобилася б енергія, співмірна з потужністю Сонця, а саме число може бути близьким до кількості атомів у видимому Всесвіті. Єкель також вважає, що знайти наступний член послідовності вдасться не раніше, ніж за кілька сотень років. Таким чином, числа Дедекінда залишаються однією з найскладніших та найзахопливіших задач сучасної математики.