Математики нашли девятое дедекиндово число. В нем оказалось 42 знака

Группа математиков из Бельгии и Германии и немец Кристиан Якель независимо друг от друга рассчитали значение девятого числа Дедекинда — то есть количества монотонных булевых функций девяти переменных. Предыдущее, восьмое число нашли еще в 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.

Простым перебором дедекиндовы числа для большого числа аргументов не найти, поэтому для их поиска используют либо асимптотические решения, которые позволяют определить интервал, в который попадает нужное значения, либо через точную формулу, для использования которой нужны значительные вычислительные ресурсы. Формула представляют из себя сумму, которая выражается из второго определения чисел Дедекинда — через антицепи, то есть подмножества упорядоченного множества, в котором (в отличие от цепи) любые пары элементов несравнимы. Дедекиндово число в этом случае определяет число элементов в решетке из антицепей в частично упорядоченном множестве.

Результаты суммирования по этим формулам ищут с помощью суперкомпьютеров. Последнее из уже найденных дедекиндовых чисел — восьмое, D(8). Это 23-значное число вычислили еще в 1991 году. В 2014 году бельгийские математики Патрик де Каусмекер (Patrick De Causmaecker) и Стефан де Ваннемакер (Stefan De Wannemacker) из Лёвенского католического университета предложили еще один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа.

Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности. Шестимерных подрешеток оказалось достаточно, чтобы вычислить на суперкомпьютере D(8) и подтвердить уже известное значение, однако для вычисления следующего коэффициента компьютерных мощностей уже не хватило.

Теперь группа де Каусмекера, в частности его студент Леннарт ван Хиртум (Lennart Van Hirtum), совместно с группой Кристиана Плессля из Падерборнского университета нашли способ адаптировать эту формулу к существующим компьютерным возможностям. Только программными средствами эту задачу решить не удалось, поэтому ученые собрали программируемую пользователем вентильную матрицу. Чтобы получить значения необходимых 5,574 × 10¹⁸ коэффициентов в формуле суммирования, ученым потребовалось около трех месяцев на суперкомпьютерном кластере Noctua 2.

В результате им удалось получить девятое число Дедекинда, которое оказалось равным 286386577668298411128469151667598498812366. В этом числе 42 знака. Кроме самого числа, ученые предоставили данные для полученных коэффициентов, описали способ проверки вычисленного значения, а также обсудили возможные источники ошибок.

Параллельно с бельгийскими математиками девятое число Дедекинда вычислял Кристиан Якель (Christian Jäkel) из Технического университета Дрездена, который опубликовал препринт на три дня раньше коллег из Лёвенского католического университета. Ключевые аспекты решения Якеля — умножение матриц и анализ симметрий антицепей, которые удалось найти с помощью анализа формальных понятий. В отличие от ван Хиртума, Якель для своих расчетов использовал параллельные вычисления не на центральных процессорах, а на графических. В результате вычислений немецкий математик получил то же 42-значное число.

Числа Дедекинда используют, в частности, в теории алгоритмов и теории графов, но на данный момент их поиск носит скорее фундаментальное значение.

Недавно математики, которые занимаются комбинаторикой, сдвинули с мертвой точки оценку для другого числа, имеющего отношение к графам. Математики показали, что верхнюю границу для диагонального числа Рамсея R(n,n) можно сдвигать вниз относительно известного экспоненциального предела 4ⁿ. Правда, в этом случае речь идет об асимптотических оценках, а не вычислении точного значения.