Дедекиндово число
Дедекиндово число — число , равное количеству монотонных булевых функций от переменных. Эквивалентные определения: число антицепей подмножеств -элементного множества; число элементов в свободной дистрибутивной решётке[англ.] с производящими; число абстрактных симплициальных комплексов[англ.] с элементами.
Последовательность — быстрорастущая, и хотя известны асимптотические оценки [1][2][3] и точное выражение в виде суммы[4], но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию на 2023 год точные значения известны для [5]:
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.
Числа от до вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число вычислил Чёрч в 1940 году[6], результат опроверг гипотезу Биркгофа, что всегда делится на [6]. Числа , , , были вычислены соответственно в 1946[7], 1965[8][9], 1991[10] и 2023[11] годах.
Для нахождения использовался суперкомпьютер Cray 2[англ.]. Число было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100[англ.]*); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Stratix[англ.] 10 GX под управлением суперкомпьютера Noctua 2[12], занявших около трёх месяцев[13][14]. Обе группы получили одинаковый результат вычислений числа , Якель опубликовал препринт на три дня раньше бельгийских коллег.
Если чётно, то также должно быть чётным[15].
Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 году[4]:
- ,
где является -м битом числа , который может быть записан с помощью округления вниз:
- ,
однако она бесполезна для практического вычисления значений для больших ввиду большого числа членов суммирования.
В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:
Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.
Логарифм дедекиндова числа можно оценить с помощью границ:
- ,
где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности элементов; правая часть неравенства установлена в 1975 году[1].
В 1981 году[2] были даны более точные оценки[16]:
для чётных и:
для нечётных , где
- ,
- ,
- .
Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к [16]. Для формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственно[17].
Пример
[править | править код]Для существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества :
- функция , игнорирующая входные значения и всегда возвращающая , соответствует пустой антицепи ;
- логическая конъюнкция соответствует антицепи , содержащей единственное множество ;
- функция , игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи , содержащей единственное множество ;
- функция , игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи , содержащей единственное множество ;
- логическая дизъюнкция соответствует антицепи , содержащей два множества и ;
- функция , игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи , содержащей только пустое множество.
Примечания
[править | править код]- ↑ 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, Köhler, 1976.
- ↑ Wiedemann, 1991.
- ↑ Christian Jäkel. 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 Köhler. 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) ).
- 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. — Т. 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 für 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.
- 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.