Иллюстрация: N + 1; Watchduck / Wikimedia Commons; Lennart Van Hirtum et al. / arXiv, 2023. Многие загадки математики управляют нашей реальностью. Например, золотое сечение лежит в основе многих природных процессов и систем не переставая удивлять человека своим совершенством, определяя самые сложные из известных естественных явлений. Среди известных математике сущностей есть удивительные числа, открытые Рихардом Дедекиндом в конце 19 века. Нахождение этих чисел относится к сложным математическим задачам, касающимся “монотонных булевых функций”, которые долгое время хранили свои секреты. Восемь из этих чисел были найдены лишь недавно. Однако проблема “девятого числа Дедекинда” остается неуловимой уже более трех десятилетий, представляя собой серьезную проблему для математического сообщества.
Числа Дедекинда – это особые математические единицы, целые числа, которые играют центральную роль в изучении монотонных булевых функций. Булевы функции – это форма математической логики, которая оперирует двоичными значениями, то есть значениями, которые могут принимать два различных состояния.
Эти состояния могут быть представлены различными способами: истина и ложь или 0 и 1. В контексте чисел Дедекинда эти булевы функции используются для определения выхода из набора двоичных входов. Монотонные булевы функции являются их подкатегорией. У них есть особенность: они устроены таким образом, что замена 0 на 1 на входе приводит только к изменению выхода с 0 на 1, но не наоборот. Другими словами, эти функции “монотонны” в том смысле, что они не “возвращаются назад”: после того, как значение было изменено с 0 на 1, оно не может быть изменено в обратном направлении.
Группа математиков из Бельгии и Германии и немец Кристиан Якель независимо друг от друга рассчитали значение девятого числа Дедекинда — то есть количества монотонных булевых функций девяти переменных. Предыдущее, восьмое число нашли еще в 1991 году. Чтобы найти девятое число, состоящее из 42 знаков, математикам пришлось адаптировать уже известные формулы для параллельных вычислений. Первая группа специально для расчетов сделала программируемую вентильную матрицу, а немецкий математик — использовал вычисления на графических процессорах, пишут ученые в препринтах на arXiv.org (1, 2).
Дедекиндово число — число монотонных булевых функций, которые можно задать для определенного числа переменных. И переменные, и функции могут принимать только два значения: 0 и 1 (или true и false).
Чем больше переменных, тем больше число. Например, если переменных 0, то функций может быть только две: f = 0 и f = 1. Для одной переменной — три функции: f(x) = 0, f(x) = 1 и f(x) = x. Для двух переменных к ним прибавляются еще три: вторая переменная f(x,y) = y, а также логическое И (x ∧ y), и логическое ИЛИ (x ∨ y). Для трех аргументов число функций возрастает уже до D(4) = 20, для пяти — до D(5) = 168.
Монотонные булевы функции для 0, 1, 2 и 3 переменных. Watchduck / Wikimedia Commons
Результаты суммирования по этим формулам ищут с помощью суперкомпьютеров. Последнее из уже найденных дедекиндовых чисел — восьмое, D(8). Это 23-значное число вычислили еще в 1991 году. В 2014 году бельгийские математики Патрик де Каусмекер (Patrick De Causmaecker) и Стефан де Ваннемакер (Stefan De Wannemacker) из Лёвенского католического университета предложили еще один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа.
Сумма для вычисления дедекиндовых чисел. Lennart Van Hirtum et al. / arXiv, 2023
Теперь группа де Каусмекера, в частности его студент Леннарт ван Хиртум (Lennart Van Hirtum), совместно с группой Кристиана Плессля из Падерборнского университета нашли способ адаптировать эту формулу к существующим компьютерным возможностям. Только программными средствами эту задачу решить не удалось, поэтому ученые собрали программируемую пользователем вентильную матрицу. Чтобы получить значения необходимых 5,574 × 1018 коэффициентов в формуле суммирования, ученым потребовалось около трех месяцев на суперкомпьютерном кластере Noctua 2.
В результате им удалось получить девятое число Дедекинда, которое оказалось равным 286386577668298411128469151667598498812366. В этом числе 42 знака. Кроме самого числа, ученые предоставили данные для полученных коэффициентов, описали способ проверки вычисленного значения, а также обсудили возможные источники ошибок.
Параллельно с бельгийскими математиками девятое число Дедекинда вычислял Кристиан Якель (Christian Jäkel) из Технического университета Дрездена, который опубликовал препринт на три дня раньше коллег из Лёвенского католического университета. Ключевые аспекты решения Якеля — умножение матриц и анализ симметрий антицепей, которые удалось найти с помощью анализа формальных понятий. В отличие от ван Хиртума, Якель для своих расчетов использовал параллельные вычисления не на центральных процессорах, а на графических. В результате вычислений немецкий математик получил то же 42-значное число.
Числа Дедекинда используют, в частности, в теории алгоритмов и теории графов, но на данный момент их поиск носит скорее фундаментальное значение.
Недавно математики, которые занимаются комбинаторикой, сдвинули с мертвой точки оценку для другого числа, имеющего отношение к графам. Математики показали, что верхнюю границу для диагонального числа Рамсея R(n,n) можно сдвигать вниз относительно известного экспоненциального предела 4n. Правда, в этом случае речь идет об асимптотических оценках, а не вычислении точного значения.
Автор: Александр Дубов
Источники: https://nplus1.ru/, https://new-science.ru/
