Користувач:Таня Бабійчук/Дедекіндові числа

Вільні дистрибутивні решітки монотонних булевих функцій від 0, 1, 2 і 3 аргументів з 2, 3, 6 і 20 елементами відповідно (наведіть курсор на праву діаграму, щоб бачити опис)

Дедекіндові числа - це швидко зростаюча послідовність цілих чисел [en], названа на честь Річарда Дедекинда, який визначив їх в 1897. Число Дедекінда M (n) підраховує число монотонних булевих функцій від n змінних. Еквівалентно, ці числа підраховують число антиланцюжків [en] підмножин n -елементних множин, число елементів у вільній дистрибутивній ришітці [en] з n виробляють, або число абстрактних симплиціальних комплексів [en] з n елементами.

Точні асимптотичні оцінки M (n) і влучний вислів у вигляді суми відомі. Однак завдання Дедекінда обчислення значень M (n) залишається складною - невідомий вираз в замкненій формі [en] для M (n) і точні значення M (n) знайдені лише для $n\leqslant 8$ .

Визначення

Булева функція - це функція, яка приймає в якості входу n булевских змінних (тобто значень, які можуть бути або false (брехня), або true (істина), або, еквівалентно, бінарними значеннями, які можуть бути або 0, або 1), і дає в якості виходу іншу булевську змінну. Функція монотонна якщо для будь-якої комбінації входу зміна однієї вхідної змінної з false на true може призвести тільки до зміни виходу з false на true, але не з true на false. Число Дедекінда M (n) число різних монотонних булевих функцій від n змінних.

Антиланцюжок[en] множин (відоме також як сімейство Спенсера[en]) — це сімейство множин, яке ні одне з яких не має вмісту в будь якій іншій множині. Якщо V є безліччю n булевих змінних, антиланцюжок A підмножин V визначає монотонну булеву функцію f, коли значення f одне true для даної множини входів, якщо деяка підмножина true входів функції f належить A і false в іншому випадку. Назад, будь-яка монотонна булева функція визначає таким чином антиланцюжок, мінімальних підмножин булевских змінних, які змушують функцію дати значення true. Тому число Дедекінда M (n) дорівнює числу різних антиланцюжків підмножин n-елементного безлічі.

Третій еквівалентний спосіб опису того ж класу використовує теорію решіток . З двох монотонних булевих функцій f і g ми можемо знайти дві інші монотонні булеві функції $f\wedge g$ і $f\vee g$, Їх логічну кон'юнкцію і логічну диз'юнкцію відповідно. Сімейство всіх монотонних булевих функцій від n входів разом з цими двома операціями утворює дистрибутивную ришітку [en], що задається теоремою Биркгофа о представленні [en] з частково впорядкованої множини підмножин n змінних з частковим порядком включення множин. Це побудова дає вільну дистрибутивну ришітку [en] з n генераторами . Таким чином, числа Дедекінда підраховують число елементів в вільних дистрибутивних решітках .

Числа Дедекінда підраховують також (на одиницю більше) число абстрактних симпліціальних комплексів [en] на n елементах, сімейства множин з властивістю, що будь-яка підмножина безлічі в сімействі також належить сімейству. Будь-який антиланцюжок визначає симпліціальний комплекс, сімейство підмножин членів антиланцюгів, і назад, максимальні симплекси в комплексах утворюють антиланцюг .

Приклад

Для n = 2 існує шість монотонних булевих функцій і шість антиланцюжків підмножин двоелементної множини {x, y}:

• функція $f(x,y)=false$, Ігнорує вхідні значення і завжди повертає false, відповідає порожньому антиланцюжку $\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)=true$, ігнорує вхідні значення і завжди повертає true, відповідає антиланцжки $\{\varnothing \}$, що містить тільки порожня множина.

Значення

Точні значення чисел Дедекінда відомі для $0\leqslant n\leqslant 8$ :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, +56130437228687557907788 послідовність.

A000372 в OEIS.

Перші шість цих чисел дав Черч . M (6) обчислив Уорд , M (7) вирахували Черч Берман і Келер , а M (8) обчислив Відерман .

Якщо n парне, то M (n) також має бути парним . Обчислення п'ятого числа Дедекінда $M(5)=7581$ спростовує гіпотезу Гаррета Біркгофа, що M (n) завжди ділиться на $(2n-1)(2n-2)$ .

Формула підсумовування

Киселевич переписав логічне визначення антіцепей в наступну арифметичну формулу для чисел Дедекинда:

$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 зважаючи на велике число членів підсумовування.

Асимптотика

Логарифм чисел Дедекінда можна оцінити точно за допомогою кордонів

${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$ елементів, а праве нерівність довели Кляйтман і Марковський .

Коршунов дав навіть більш точні оцінки

$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%, відповідно .

Література

• Joel Berman, Peter Köhler.  // Mitt. Math. Sem. Giessen. — 1976. — Т. 121. — С. 103–124.
• Randolph Church.  // Duke Mathematical Journal. — 1940. — Т. 6. — С. 732–734..
• Randolph Church.  // Notices of the American Mathematical Society. — 1965. — Т. 11. — С. 724.. Как процитировано Видерманом ().
• Richard Dedekind. Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // {{{Заголовок}}}. — 1897. — Т. 2. — С. 103–148.
• Jeff Kahn.  // Proceedings of the American Mathematical Society. — 2002. — Т. 130, вип. 2. — С. 371–378.
• Andrzej Kisielewicz.  // Journal für die Reine und Angewandte Mathematik. — 1988. — Т. 386. — С. 139–144.
• Kleitman D., Markowsky G.  // Transactions of the American Mathematical Society. — 1975. — Т. 213. — С. 373–390..
• Коршунов А. Д.  // Проблемы кибернетики. — 1981. — Т. 38. — С. 5–108.
• Morgan Ward.  // Bulletin of the American Mathematical Society. — 1946. — Т. 52. — С. 423.
• Doug Wiedemann.  // Order. — 1991. — Т. 8, вип. 1. — С. 5–6..
• Koichi Yamamoto.  // Science Reports of the Kanazawa University. — 1953. — Т. 2, вип. 1. — С. 5–6.
• Nejib Zaguia. Isotone maps: enumeration and structure // {{{Заголовок}}} / Sauer N. W., Woodrow R. E., Sands B. — Kluwer Academic Publishers, 1993. — С. 421–430.

[[Категорія:Математична логіка]] [[Категорія:Нумераційна комбінаторика]] [[Категорія:Цілочисельні послідовності]] [[Категорія:Сімейство множин]] [[Категорія:Теорія решіток]]