Дедекиндово число

Не следует путать с дедекиндовыми сечениями — способом построения действительных чисел.

Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно

Дедекиндово число — число $M(n)$, равное количеству монотонных булевых функций от $n$ переменных. Эквивалентные определения: число антицепей подмножеств $n$-элементного множества; число элементов в свободной дистрибутивной решётке^[en] с $n$ производящими; число абстрактных симплициальных комплексов^[en] с $n$ элементами.

Свойства

Последовательность $\{M(n)\}$ — быстрорастущая, и хотя известны асимптотические оценки $M(n)$ и точное выражение в виде суммы, но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию на 2023 год точные значения известны для $n\leqslant 9$:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.

Числа от $M(0)$ до $M(4)$ вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число $M(5)$ вычислил Чёрч в 1940 году, результат опроверг гипотезу Биркгофа, что $M(n)$ всегда делится на $(2n-1)(2n-2)$. Числа $M(6)$, $M(7)$, $M(8)$, $M(9)$ были вычислены соответственно в 1946, 1965, 1991 и 2023 годах.

Для нахождения $M(8)$ использовался суперкомпьютер Cray 2^[en]. Число $M(9)$ было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100^[en]); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Stratix^[en] 10 GX под управлением суперкомпьютера Noctua 2, занявших около трёх месяцев. Обе группы получили одинаковый результат вычислений числа $M(9)$, Якель опубликовал препринт на три дня раньше бельгийских коллег.

Если $n$ чётно, то $M(n)$ также должно быть чётным.

Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 году:

$M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right)$,

где $b_{i}^{k}$ является $i$-м битом числа $k$, который может быть записан с помощью округления вниз:

$b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor$,

однако она бесполезна для практического вычисления значений $M(n)$ для больших $n$ ввиду большого числа членов суммирования.

В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:

$M(n+2)=\sum _{\alpha ,\beta \in M_{n}}\left(|[\bot ,\alpha ]|2^{C_{\alpha },\beta }|[\beta ,\top ]|\right)$

Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.

Логарифм дедекиндова числа можно оценить с помощью границ:

${n \choose \lfloor n/2\rfloor }\leqslant \log _{2}M(n)\leqslant {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right)$,

где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности $\lfloor n/2\rfloor$ элементов; правая часть неравенства установлена в 1975 году.

В 1981 году были даны более точные оценки:

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)$

для чётных $n$ и:

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))$

для нечётных $n$, где

$a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4})$,

$b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3})$,

$c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4})$.

Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к $n/2$. Для $n=2,4,6,8$ формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственно.

Пример

Для $n=2$ существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества $\{x,y\}$:

• функция $f(x,y)=\bot$, игнорирующая входные значения и всегда возвращающая $\bot$, соответствует пустой антицепи $\varnothing$;
• логическая конъюнкция $f(x,y)=x\wedge y$ соответствует антицепи $\{\{x,y\}\}$, содержащей единственное множество $\{x,y\}$;
• функция $f(x,y)=x$, игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи $\{\{x\}\}$, содержащей единственное множество $\{x\}$;
• функция $f(x,y)=y$, игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи $\{\{y\}\}$, содержащей единственное множество $\{y\}$;
• логическая дизъюнкция $f(x,y)=x\vee y$ соответствует антицепи $\{\{x\},\{y\}\}$, содержащей два множества $\{x\}$ и $\{y\}$;
• функция $f(x,y)=\top$, игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи $\{\varnothing \}$, содержащей только пустое множество.

Литература

• Joel Berman, Peter Köhler Cardinalities of finite distributive lattices // Mitt. Math. Sem. Giessen. — 1976. — Vol. 121. — С. 103–124.
• Randolph Church Numerical analysis of certain free distributive structures // Duke Mathematical Journal. — 1940. — Vol. 6. — С. 732–734. — DOI:10.1215/s0012-7094-40-00655-x.
• Randolph Church Enumeration by rank of the free distributive lattice with 7 generators // Notices of the American Mathematical Society. — 1965. — Vol. 11. — С. 724.. Как процитировано Видерманом (Wiedemann (1991)).
• Richard Dedekind Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // Gesammelte Werke. — 1897. — Т. 2. — С. 103–148.
• Jeff Kahn Entropy, independent sets and antichains: a new approach to Dedekind's problem // Proceedings of the American Mathematical Society. — 2002. — В. 2. — Vol. 130. — С. 371–378. — DOI:10.1090/S0002-9939-01-06058-0
• Andrzej Kisielewicz A solution of Dedekind's problem on the number of isotone Boolean functions // Journal für die Reine und Angewandte Mathematik. — 1988. — Vol. 386. — С. 139–144. — DOI:10.1515/crll.1988.386.139
• Kleitman D., Markowsky G. On Dedekind's problem: the number of isotone Boolean functions. II // Transactions of the American Mathematical Society. — 1975. — Vol. 213. — С. 373–390. — DOI:10.2307/1998052.
• Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. — 1981. — Vol. 38. — С. 5–108.
• Morgan Ward Note on the order of free distributive lattices // Bulletin of the American Mathematical Society. — 1946. — Vol. 52. — С. 423. — DOI:10.1090/S0002-9904-1946-08568-7
• Doug Wiedemann A computation of the eighth Dedekind number // Order^[en]. — 1991. — В. 1. — Vol. 8. — С. 5–6. — DOI:10.1007/BF00385808.
• Koichi Yamamoto Note on the order of free distributive lattices // Science Reports of the Kanazawa University. — 1953. — В. 1. — Vol. 2. — С. 5–6.
• Nejib Zaguia Isotone maps: enumeration and structure // Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991) / Sauer N. W., Woodrow R. E., Sands B.. — Kluwer Academic Publishers, 1993. — С. 421–430.

Одним из источников этой статьи является статья в википроекте «Руниверсалис» («Руни», руни.рф), называющаяся «Дедекиндово число». Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC BY-SA. Всем участникам Руниверсалиса предлагается прочитать «Обращение к участникам Руниверсалиса» основателя Циклопедии и «Почему Циклопедия?».