Математики нашли девятое дедекиндово число. В нем оказалось 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),...

Читайте полную новость на nplus1.ru

Опубликовано: 04:00, 28.06.2023

Новость из рубрики: Наука

Поделиться новостью: Поделиться новостью в Facebook Поделиться новостью в Twittere Поделиться новостью в VK Поделиться новостью в Pinterest Поделиться новостью в Reddit

Топ новости часа