Дедекиндово число — число , равное количеству монотонных булевых функций от переменных. Эквивалентные определения: число антицепей подмножеств -элементного множества; число элементов в с производящими; число с элементами.
Последовательность — быстрорастущая, и хотя известны асимптотические оценки и точное выражение в виде суммы, но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию точные значения известны для : 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.
Числа от до вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число вычислил Чёрч в 1940 году, результат опроверг гипотезу Биркгофа, что всегда делится на . Числа , , , были вычислены соответственно в 1946, 1965, 1991 и 2023 годах.
Для нахождения использовался суперкомпьютер Cray 2. Число было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС 10 GX под управлением суперкомпьютера Noctua 2, занявших около трёх месяцев. Обе группы получили одинаковый результат вычислений числа , Якель опубликовал препринт на три дня раньше бельгийских коллег.
Если чётно, то также должно быть чётным.
Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 году: , где является -м битом числа , который может быть записан с помощью округления вниз: , однако она бесполезна для практического вычисления значений для больших ввиду большого числа членов суммирования.
В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:
Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.
Логарифм дедекиндова числа можно оценить с помощью границ: , где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности элементов; правая часть неравенства установлена в 1975 году.
В 1981 году были даны более точные оценки:
для чётных и:
для нечётных , где , , . Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к . Для формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственно.
Пример Для существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества : функция , игнорирующая входные значения и всегда возвращающая , соответствует пустой антицепи ; логическая конъюнкция соответствует антицепи , содержащей единственное множество ; функция , игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи , содержащей единственное множество ; функция , игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи , содержащей единственное множество ; логическая дизъюнкция соответствует антицепи , содержащей два множества и ; функция , игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи , содержащей только пустое множество.
Примечания
Литература
. . Как процитировано Видерманом ().
.
.
Ссылки Математики нашли девятое дедекиндово число. В нем оказалось 42 знака
Категория:Целочисленные последовательности Категория:Перечислительная комбинаторика Категория:Математическая логика Категория:Теория решёток Категория:Семейства множеств