|
Математики нашли девятое дедекиндово число
|
|
|
|
Группа математиков из Бельгии и Германии и немец Кристиан Якель независимо друг от друга рассчитали значение девятого числа Дедекинда — то есть количества монотонных булевых функций девяти переменных. Предыдущее, восьмое число нашли еще в 1991 году. Чтобы найти девятое число, состоящее из 42 знаков, математикам пришлось адаптировать уже известные формулы для параллельных вычислений. Первая группа специально для расчетов сделала программируемую вентильную матрицу, а немецкий математик — использовал вычисления на графических процессоры, пишут ученые в препринтах на arXiv.org. Дедекиндово число — число монотонных булевых функций, которые можно задать для определенного числа переменных. И переменные, и функции могут принимать только два значения: 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^18 коэффициентов в формуле суммирования, ученым потребовалось около трех месяцев на суперкомпьютерном кластере Noctua 2. В результате им удалось получить девятое число Дедекинда, которое оказалось равным 286386577668298411128469151667598498812366. В этом числе 42 знака. Кроме самого числа, ученые предоставили данные для полученных коэффициентов, описали способ проверки вычисленного значения, а также обсудили возможные источники ошибок.
|
|
|
|
Параллельно с бельгийскими математиками девятое число Дедекинда вычислял Кристиан Якель (Christian Jakel) из Технического университета Дрездена, который опубликовал препринт на три дня раньше коллег из Лёвенского католического университета. Ключевые аспекты решения Якеля — умножение матриц и анализ симметрий антицепей, которые удалось найти с помощью анализа формальных понятий. В отличие от ван Хиртума, Якель для своих расчетов использовал параллельные вычисления не на центральных процессорах, а на графических. В результате вычислений немецкий математик получил то же 42-значное число. Числа Дедекинда используют, в частности, в теории алгоритмов и теории графов, но на данный момент их поиск носит скорее фундаментальное значение.
|
|
|
|
Источник
|
