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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
противоречиеA и B и CA и BA и CB и C(A и B) или (A и C)(A и B) или (B и C)(A и C) или (B и C)ABC(A или B) и (A или C) и (B или C) <====> (A и B) или (A и C) или (B и C)(A или B) и (A или C)(A или B) и (B или C)(A или C) и (B или C)A или BA или CB или CA или B или Cтавтология
Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно (наведите мышь на правую диаграмму, чтобы видеть описание)

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

Последовательность  — быстрорастущая, и хотя известны асимптотические оценки [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[en]. Число было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100[en]); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Stratix[en] 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. 1 2 Kleitman, Markowsky, 1975.
  2. 1 2 Коршунов, 1981.
  3. Kahn, 2002.
  4. 1 2 Kisielewicz, 1988.
  5. последовательность A000372 в OEIS
  6. 1 2 Church, 1940.
  7. Ward, 1946.
  8. Church, 1965.
  9. Berman, Köhler, 1976.
  10. Wiedemann, 1991.
  11. Christian Jäkel. A computation of the ninth Dedekind Number // Arxiv.org. — 2023. — arXiv:2304.00895.
  12. Noctua 2 - BullSequana XH2000, AMD EPYC 7763 64C 2.45GHz, InfiniBand HDR100 | TOP500. Дата обращения: 29 июня 2023. Архивировано 29 июня 2023 года.
  13. Александр Дубов. Математики нашли девятое дедекиндово число. В нем оказалось 42 знака. Это 286386577668298411128469151667598498812366. N + 1 (27 июня 2023). Дата обращения: 28 июня 2023. Архивировано 28 июня 2023 года.
  14. 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.
  15. Yamamoto, 1953.
  16. 1 2 Zaguia, 1993.
  17. 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[en]. — 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.