У світі математики, де репутація поступається виключно доказовості, незламний принцип Річарда Дедекінда «Те, що можна довести, не повинно вважатися наукою без доказів» став наріжним каменем для пошуку однієї з найскладніших послідовностей чисел. У своєму малопоміченому трактаті 1897 року Дедекінд представив послідовність, що нині носить його ім’я – числа Дедекінда. Він запропонував лише п’ять членів: 0, 1, 4, 18, і, з обережним припущенням, 166, зазначивши, що вони «здається, дуже швидко зростають». Це стало початком епічної подорожі для поколінь математиків, що тривала понад 125 років, оскільки лише нещодавно було знайдено дев’яте число в послідовності, пише T4.
Числа Дедекінда можна уявити трьома еквівалентними способами, кожен з яких є обчислювально складним. Найбільш наочний полягає в грі з n-вимірним кубом, де необхідно підрахувати кількість способів розфарбування кутів у білий або червоний колір так, щоб білий кут ніколи не знаходився над червоним. Для n = 0 (одна точка) існує 2 способи, для n = 1 (лінія) — 3, для n = 2 (квадрат) — 6, а для n = 3 (куб) — 20. У четвертому вимірі число Дедекінда дорівнює 168 (сучасна нумерація включає кілька тривіальних випадків, які Дедекінд виключив). Інший підхід розглядає числа як кількість антиланцюгів у ґратці підмножин, де антиланцюг – це набір підмножин, жодна з яких не є підмножиною іншої. Третій спосіб, запропонований самим Дедекіндом, ґрунтується на монотонних булевих функціях, де для n бінарних змінних функція вважається монотонною, якщо зміна будь-якого входу з 0 на 1 може лише змінити вихід з 0 на 1, але не навпаки. Кількість таких функцій і є n-м числом Дедекінда.
Незважаючи на складність і швидке зростання, послідовність чисел Дедекінда викликала непереборний інтерес. Після Дедекінда, п’яте число (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 років. Тому до 2023 року дев’яте число Дедекінда, або D(9), стало справжньою «відкритою проблемою», і багато хто сумнівався в можливості його обчислення.
Однак, як це часто буває в науці, рішення прийшло майже одночасно від двох незалежних команд. Леннарт Ван Гіртум з Падерборнського університету та його команда, використовуючи симетрії у формулі, скоротили обчислювальну складність до «лише» 5,5×10^18 термінів, що є колосальною, але досяжною кількістю для суперкомп’ютера Noctua 2. Їхня трирічна теоретична робота увінчалася успіхом, незважаючи на 25-30-відсоткову ймовірність впливу космічних променів на обчислення. Паралельно Крістіан Єкель з Дрезденського технічного університету, який працював над цією проблемою понад півдесятиліття, розробив власний метод, заснований на множенні матриць, що вимагав місяця обчислень на звичайному комп’ютері. У березні 2023 року Єкель першим опублікував свій результат – приголомшливе 42-значне число: 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Через три дні команда Ван Гіртума, яка технічно отримала результат раніше, але чекала з публікацією для перевірки, також оприлюднила свої дані. Збіг цих двох незалежних результатів підтвердив їхню коректність і ознаменував тріумфальне вирішення 32-річної проблеми.
Полювання на D(10) тепер є новим «великим питанням». Проте, як зазначають вчені, стрибок у складності між D(9) і D(10) залишається «абсолютно астрономічним». За оцінками Ван Гіртума, для його знаходження знадобилася б потужність, еквівалентна енергії всього Сонця, а саме число може бути за величиною порівнянне з кількістю атомів у видимому Всесвіті. Єкель, який присвятив багато років D(9), також скептично ставиться до швидкого відкриття наступного числа, припускаючи, що це може зайняти ще кілька сотень років. Таким чином, історія чисел Дедекінда продовжується, залишаючись одним із найскладніших і найзахопливіших обчислювальних викликів у сучасній математиці.
Читайте також: Що станеться, якщо відправити різдвяну ялинку в космос
