Меню Главная Случайная статья Настройки Дедекиндово число Материал из https://ru.wikipedia.org Дедекиндово число — число ${\displaystyle M(n)}$, равное количеству монотонных булевых функций от ${\displaystyle n}$ переменных. Эквивалентные определения: число антицепей подмножеств ${\displaystyle n}$-элементного множества; число элементов в свободной дистрибутивной решётке[англ.] с ${\displaystyle n}$ производящими; число абстрактных симплициальных комплексов[англ.] с ${\displaystyle n}$ элементами. Последовательность ${\displaystyle (M(n))}$ — быстрорастущая, и хотя известны асимптотические оценки ${\displaystyle M(n)}$[1][2][3] и точное выражение в виде суммы[4], но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию на 2023 год точные значения известны для ${\displaystyle n\leqslant 9}$[5]: 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366. Числа от ${\displaystyle M(0)}$ до ${\displaystyle M(4)}$ вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число ${\displaystyle M(5)}$ вычислил Чёрч в 1940 году[6], результат опроверг гипотезу Биркгофа, что ${\displaystyle M(n)}$ всегда делится на ${\displaystyle (2n-1)(2n-2)}$[6]. Числа ${\displaystyle M(6)}$, ${\displaystyle M(7)}$, ${\displaystyle M(8)}$, ${\displaystyle M(9)}$ были вычислены соответственно в 1946[7], 1965[8][9], 1991[10] и 2023[11] годах. Для нахождения ${\displaystyle M(8)}$ использовался суперкомпьютер Cray 2. Число ${\displaystyle M(9)}$ было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Stratix[англ.] 10 GX под управлением суперкомпьютера Noctua 2[12], занявших около трёх месяцев[13][14]. Обе группы получили одинаковый результат вычислений числа ${\displaystyle M(9)}$, Якель опубликовал препринт на три дня раньше бельгийских коллег. Если ${\displaystyle n}$ чётно, то ${\displaystyle M(n)}$ также должно быть чётным[15]. Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 году[4]: ${\displaystyle 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)}$, где ${\displaystyle b_{i}^{k}}$ является ${\displaystyle i}$-м битом числа ${\displaystyle k}$, который может быть записан с помощью округления вниз: ${\displaystyle b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor }$, однако она бесполезна для практического вычисления значений ${\displaystyle M(n)}$ для больших ${\displaystyle n}$ ввиду большого числа членов суммирования. В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа: ${\displaystyle M(n+2)=\sum _{\alpha ,\beta \in M_{n}}\left(|[\bot ,\alpha ]|2^{C_{\alpha },\beta }|[\beta ,\top ]|\right)}$ Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности. Логарифм дедекиндова числа можно оценить с помощью границ: ${\displaystyle {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)}$, где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности ${\displaystyle \lfloor n/2\rfloor }$ элементов; правая часть неравенства установлена в 1975 году[1]. В 1981 году[2] были даны более точные оценки[16]: ${\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)}$ для чётных ${\displaystyle n}$ и: ${\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))}$ для нечётных ${\displaystyle n}$, где ${\displaystyle a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4})}$, ${\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3})}$, ${\displaystyle c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4})}$. Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к ${\displaystyle n/2}$[16]. Для ${\displaystyle n=2,4,6,8}$ формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и 3,3 % соответственно[17]. Пример Для ${\displaystyle n=2}$ существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества ${\displaystyle \{x,y\}}$: функция ${\displaystyle f(x,y)=\bot }$, игнорирующая входные значения и всегда возвращающая ${\displaystyle \bot }$, соответствует пустой антицепи ${\displaystyle \varnothing }$; логическая конъюнкция ${\displaystyle f(x,y)=x\wedge y}$ соответствует антицепи ${\displaystyle \{\{x,y\}\}}$, содержащей единственное множество ${\displaystyle \{x,y\}}$; функция ${\displaystyle f(x,y)=x}$, игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи ${\displaystyle \{\{x\}\}}$, содержащей единственное множество ${\displaystyle \{x\}}$; функция ${\displaystyle f(x,y)=y}$, игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи ${\displaystyle \{\{y\}\}}$, содержащей единственное множество ${\displaystyle \{y\}}$; логическая дизъюнкция ${\displaystyle f(x,y)=x\vee y}$ соответствует антицепи ${\displaystyle \{\{x\},\{y\}\}}$, содержащей два множества ${\displaystyle \{x\}}$ и ${\displaystyle \{y\}}$; функция ${\displaystyle f(x,y)=\top }$, игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи ${\displaystyle \{\varnothing \}}$, содержащей только пустое множество. Примечания 1 2 Kleitman, Markowsky, 1975. 1 2 Коршунов, 1981. Kahn, 2002. 1 2 Kisielewicz, 1988. последовательность A000372 в OEIS 1 2 Church, 1940. Ward, 1946. Church, 1965. Berman, Khler, 1976. Wiedemann, 1991. Christian Jkel. A computation of the ninth Dedekind Number // Arxiv.org. — 2023. — arXiv:2304.00895. Noctua 2 - BullSequana XH2000, AMD EPYC 7763 64C 2.45GHz, InfiniBand HDR100 | TOP500 . Дата обращения: 29 июня 2023. Архивировано 29 июня 2023 года. Александр Дубов. Математики нашли девятое дедекиндово число. В нем оказалось 42 знака. Это 286386577668298411128469151667598498812366 . N + 1 (27 июня 2023). Дата обращения: 28 июня 2023. Архивировано 28 июня 2023 года. Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, Christian Plessl. A computation of D(9) using FPGA Supercomputing. — arXiv:2304.03039. Yamamoto, 1953. 1 2 Zaguia, 1993. Brown, K. S., Generating the monotone Boolean functions Литература Joel Berman, Peter Khler. Cardinalities of finite distributive lattices // Mitt. Math. Sem. Giessen. — 1976. — Т. 121. — С. 103–124. Randolph Church. Numerical analysis of certain free distributive structures // Duke Mathematical Journal. — 1940. — Т. 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. — Т. 11. — С. 724.. Как процитировано Видерманом (Wiedemann (1991) harvtxt error: якоря не существует: CITEREFWiedemann1991 (помощь)). Jeff Kahn. Entropy, independent sets and antichains: a new approach to Dedekind's problem // Proceedings of the American Mathematical Society. — 2002. — Т. 130, вып. 2. — С. 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 fr die Reine und Angewandte Mathematik. — 1988. — Т. 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. — Т. 213. — С. 373–390. — doi:10.2307/1998052.. Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. — 1981. — Т. 38. — С. 5–108. Morgan Ward. Note on the order of free distributive lattices // Bulletin of the American Mathematical Society. — 1946. — Т. 52. — С. 423. — doi:10.1090/S0002-9904-1946-08568-7. Doug Wiedemann. A computation of the eighth Dedekind number // Order[англ.]. — 1991. — Т. 8, вып. 1. — С. 5–6. — doi:10.1007/BF00385808.. Koichi Yamamoto. Note on the order of free distributive lattices // Science Reports of the Kanazawa University. — 1953. — Т. 2, вып. 1. — С. 5–6.