Yandex Metrika
1
1 репост, 1 голос

В математике, пожалуй, больше чем в любой другой науке, репутация почти ничего не значит. Точнее, она имеет значение — но лишь в крайне редких случаях. Если у вас нет строгого доказательства, вашу идею не примут просто потому, что под ней стоит известное имя.

Никто не верил в этот принцип сильнее, чем Рихард Дедекинд (Richard Dedekind) — выдающийся математик XIX века, однажды сформулировавший жесткое правило: «В науке нельзя верить в то, что доказуемо, без самого доказательства». И все же ирония истории в том, что именно он сумел увлечь несколько поколений математиков поиском загадочной последовательности чисел, которые казались почти невозможными для вычисления. Причем сам Дедекинд располагал лишь первыми пятью членами этой последовательности — и те вызывали сомнения.

Девятое число Дедекинда
Пока неясно, удастся ли нам когда-нибудь найти десятое число. Изображение: patpitchaya/Shutterstock

Все началось в 1897 году с работы, которая поначалу осталась практически незамеченной.

«Если взять конечную систему натуральных чисел и вычислить все наибольшие общие делители двух или более из них, — писал Дедекинд, — то исходные числа раскладываются на множители самыми разными способами. Хотя эти множители, как правило, не являются простыми числами, они оказываются полезными в ряде исследований, и потому стоит изложить законы, возникающие в этом процессе, в связной форме […] Надеюсь, в этом отношении моя работа будет интересна некоторым математикам.»

Спустя примерно 44 страницы он подошел к тому, что сегодня называют числами Дедекинда. В его формулировке первые значения выглядели так: 0, 1, 4, 18 и — «если я не ошибаюсь», как он осторожно добавил, — 166. Он отметил, что эти числа «растут, по-видимому, очень быстро», но признался: «Я пока не пытался найти для них общее выражение».

Прошло более 125 лет, а общей формулы для чисел Дедекинда у нас нет до сих пор. Более того, лишь совсем недавно человечество сумело вычислить девятое число в этой последовательности. Почему же эти числа оказались настолько труднодостижимыми?

Что такое числа Дедекинда

Существует как минимум три способа понять, что представляют собой числа Дедекинда — хотя стоит сразу предупредить: ни один из них нельзя назвать по-настоящему простым.

Самый наглядный подход — геометрический.

«Проще всего представить это как игру с n-мерным кубом, — объяснял в 2023 году Леннарт ван Хиртум, исследователь Центра параллельных вычислений Падерборнского университета. — Вы ставите куб на один из его углов и окрашиваете все остальные углы либо в белый, либо в красный цвет. Есть лишь одно правило: нельзя располагать белый угол выше красного.»

В результате возникает своеобразная «вертикальная граница» между красными и белыми вершинами. Задача игры — посчитать, сколькими различными способами можно провести такую границу. Это количество и есть число Дедекинда.

Проще всего начать с нулевой размерности. При n = 0 у нас есть всего одна точка, которая может быть либо белой, либо красной — значит, нулевое число Дедекинда равно 2. В одном измерении появляется отрезок с двумя «углами» и уже три допустимых варианта окраски. В двух измерениях таких вариантов шесть, в трех — двадцать.

Математика высокого уровня
Возможные варианты для n = 0 и n = 1. Изображение: © IFLScience
N-мерный куб визуализация
Шесть возможных вариантов в двух измерениях. Изображение: © IFLScience

Дальше воображение начинает подводить: человеческий мозг плохо приспособлен к представлению пространств выше трех измерений. Тем не менее Дедекинду удалось продвинуться еще на шаг: при n = 4 число Дедекинда равно 168. Если вы заметили расхождение с его оригинальными значениями — все в порядке: современные математики просто включают пару случаев, которые сам Дедекинд считал тривиальными.

Другой способ — через теорию множеств и решеток. Возьмем множество из n элементов, например {1, 2, 3, …, n}. Его булеан — то есть множество всех возможных подмножеств — будет содержать 2ⁿ элементов. Эти элементы можно организовать в структуру, называемую решеткой подмножеств.

Числа Дедекинда в этом случае определяются как количество антицепей в такой решетке — то есть наборов элементов, которые нельзя выстроить в цепочку включений. Например, при n = 3 множество {{1}, {2, 3}} является антицепью, а {∅, {1}, {1, 2, 3}} — нет.

Наконец, третий — и исторически первый — подход связан с монотонными булевыми функциями. Здесь все выглядит особенно логично для компьютеров. Мы берем n переменных, каждая из которых может принимать значение 0 или 1 (ложь или истина), и применяем к ним функцию, которая также выдает 0 или 1. Такая функция называется монотонной, если при замене любого входа с 0 на 1 выход может либо остаться прежним, либо измениться с 0 на 1, но никогда — в обратную сторону. Количество таких функций для n переменных и есть n-е число Дедекинда.

Все эти определения эквивалентны — вопрос лишь в том, какое из них вам ближе. Но в одном Дедекинд был совершенно прав:

«Эти числа очень быстро становятся гигантскими, — подчеркивал ван Хиртум. — Восьмое число Дедекинда уже состоит из 23 цифр.»

Поиск чисел Дедекинда

Отсутствие общей формулы и стремительный рост значений быстро сделали вычисление очередных чисел почти невозможным. На поиск шестого числа ушло более 40 лет: им оказалось 7 581.

Седьмое число (шестое по современной нумерации) было найдено в 1946 году и произвело эффект разорвавшейся бомбы — последовательность прыгнула с четырехзначного числа сразу к семизначному: 7 828 354. В 1965 году появилось восьмое число Дедекинда: 2 414 682 040 998. А девятое долго оставалось мечтой: восьмое, найденное в 1991 году, равно 56 130 437 228 687 557 907 788 и по порядку величины сопоставимо с диаметром Солнечной системы, измеренным в микронах. Его вычисление заняло 200 часов работы одного из самых мощных суперкомпьютеров своего времени.

«Исторически новое число Дедекинда удается найти раз в 20–30 лет, — говорил в 2023 году Бартломей Павельский (Bartłomiej Pawelski), специалист по вычислительным методам из Гданьского университета. — Это колоссальный вычислительный вызов.»

К 2023 году девятое число Дедекинда так и не было найдено — прошло уже 32 года с момента предыдущего успеха.

«Вычисление D(9) считалось открытой задачей, — отмечал ван Хиртум. — И было неясно, удастся ли вообще когда-нибудь получить это число.»

И вдруг это удалось — причем сразу двум независимым группам.

Невероятное совпадение

Закон Мура гласит, что вычислительная мощность компьютеров удваивается примерно каждые два года. За три десятилетия прогресс должен был стать решающим.

«Казалось вполне возможным, что теперь девятое число можно вычислить на крупном суперкомпьютере», — говорил ван Хиртум.

Однако реальность оказалась суровой. Его команда смогла пересчитать восьмое число Дедекинда всего за восемь минут на обычном ноутбуке.

Но «то, что занимает восемь минут для D(8), для D(9) превращается в сотни тысяч лет», — пояснял он. — «Даже если задействовать мощнейший суперкомпьютер, расчет занял бы многие годы».

Выходом стало упрощение задачи. Используя симметрии формулы, исследователи сократили число слагаемых до «всего лишь» 5,5 × 10¹⁸. Для сравнения: по оценкам, на всей Земле около 7,5 × 10¹⁸ песчинок.

К счастью, у них был доступ к Noctua 2 — одному из немногих суперкомпьютеров в мире, способных справиться с такой задачей. После трех лет теоретической подготовки вычисления начались. Риск был немалым: вероятность того, что космические лучи нарушат работу специализированных схем, оценивалась в 25-30 процентов.

Но они были не одни.

Параллельно над задачей работал Кристиан Ёкель (Christian Jäkel) из Дрезденского технического университета. Он заинтересовался проблемой еще во время работы над докторской диссертацией и буквально «загорелся» идеей найти D(9). Его метод был совершенно другим — основанным на матричных вычислениях, хорошо известных в математике. Суперкомпьютер ему не понадобился, но один полный расчет занял целый месяц.

Именно Ёкель первым опубликовал результат — в марте 2023 года. Девятое число Дедекинда оказалось 42-значным гигантом:

286 386 577 668 298 411 128 469 151 667 598 498 812 366

Проверить вычисления он не мог:

«Я сделал все, что было в моих силах, чтобы избежать ошибок, — признавался он, — но без независимой проверки уверенности не было.»

И вдруг — всего через три дня — появилось подтверждение: команда из Падерборна получила точно такое же число.

Два независимых решения фактически подтвердили друг друга.

«Столь быстрое подтверждение результата стало для меня настоящим потрясением», — вспоминал Ёкель.

Увидим ли мы D(10)?

После 32 лет ожидания задача была решена. Но когда же ждать десятое число Дедекинда?

Возможно — никогда. Несмотря на прогресс в вычислительной технике, «скачок сложности остается абсолютно астрономическим», — говорил ван Хиртум. По его оценкам, для вычисления D(10) потребовалась бы энергия, сравнимая с мощностью Солнца, а само число по величине было бы сопоставимо с количеством атомов во видимой Вселенной.

«Можно с уверенностью сказать, что десятое число не будет вычислено в ближайшее время, — отмечал он. — И под “ближайшим” я имею в виду следующие несколько сотен лет.»

Ёкель придерживается схожего мнения.

«От D(7) к D(8) и от D(8) к D(9) каждый раз проходило около 30 лет, — говорит он. — Я не вижу причин, почему переход от D(9) к D(10) должен быть быстрее.»

Тем не менее он не теряет интереса:

«Я, конечно, буду внимательно следить за развитием исследований чисел Дедекинда. У меня есть идеи, которые хочется проверить, но я не питаю иллюзий, что смогу вычислить D(10).»

Так что девятое число Дедекинда, возможно, останется не только математическим рекордом, но и символом предела того, на что сегодня способна наука.

Заметили ошибку в тексте? Выделите её мышкой и нажмите Ctrl + Enter

Следите за нашими новостями:


Понравилось? Поделитесь с друзьями!

✏️ Сообщить об ошибке

Вы заметили ошибку в следующем тексте: