Interested Article - Дедекиндово число

противоречие A и B и C A и B A и C B и C (A и B) или (A и C) (A и B) или (B и C) (A и C) или (B и C) A B C (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 или B A или C B или C A или B или C тавтология
Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно (наведите мышь на правую диаграмму, чтобы видеть описание)

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

Последовательность — быстрорастущая, и хотя известны асимптотические оценки и точное выражение в виде суммы , но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию на 2023 год точные значения известны для :

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

Числа от до вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число вычислил Чёрч в 1940 году , результат опроверг гипотезу Биркгофа , что всегда делится на . Числа , , , были вычислены соответственно в 1946 , 1965 , 1991 и 2023 годах.

Для нахождения использовался суперкомпьютер . Число было получено двумя независимыми группами математиков: из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на * ); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС 10 GX под управлением суперкомпьютера Noctua 2 , занявших около трёх месяцев . Обе группы получили одинаковый результат вычислений числа , Якель опубликовал препринт на три дня раньше бельгийских коллег.

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

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

,

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

,

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

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

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

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

,

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

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

для чётных и:

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

,
,
.

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

Пример

Для существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества :

  • функция , игнорирующая входные значения и всегда возвращающая , соответствует пустой антицепи ;
  • логическая конъюнкция соответствует антицепи , содержащей единственное множество ;
  • функция , игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи , содержащей единственное множество ;
  • функция , игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи , содержащей единственное множество ;
  • логическая дизъюнкция соответствует антицепи , содержащей два множества и ;
  • функция , игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи , содержащей только пустое множество.

Примечания

  1. .
  2. .
  3. .
  4. .
  5. последовательность в OEIS
  6. .
  7. .
  8. .
  9. .
  10. .
  11. Christian Jäkel. A computation of the ninth Dedekind Number // Arxiv.org. — 2023. — arXiv : .
  12. . Дата обращения: 29 июня 2023. 29 июня 2023 года.
  13. Александр Дубов. . 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 : .
  15. .
  16. .
  17. Brown, K. S.,

Литература

  • Joel Berman, Peter Köhler. Cardinalities of finite distributive lattices // Mitt. Math. Sem. Giessen. — 1976. — Т. 121 . — С. 103–124 .
  • Randolph Church. // Duke Mathematical Journal. — 1940. — Т. 6 . — С. 732–734 . — doi : . .
  • Randolph Church. Enumeration by rank of the free distributive lattice with 7 generators // Notices of the American Mathematical Society. — 1965. — Т. 11 . — С. 724 . . Как процитировано Видерманом ( ).
  • 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 : .
  • 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 : .
  • 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 : . .
  • Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. — 1981. — Т. 38 . — С. 5–108 .
  • Morgan Ward. Note on the order of free distributive lattices // Bulletin of the American Mathematical Society. — 1946. — Т. 52 . — С. 423 . — doi : .
  • Doug Wiedemann. A computation of the eighth Dedekind number // . — 1991. — Т. 8 , вып. 1 . — С. 5–6 . — doi : . .
  • 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.
Источник —

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