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

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

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

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

В 2023 році, в результаті складної обчислювальної роботи та застосування спеціальних алгоритмів, математики знайшли дев’яте число Дедекінда. Згідно з дослідженням, яке було опубліковано в “Анналах математики”, команда математиків з Німеччини, Великобританії та Австралії виявила, що дев’яте число Дедекінда дорівнює 286386577668298411128469151667598498812366.

Визначення

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

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

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

Числа Дедекінда підраховують також (на одиницю більше) число абстрактних симпліційних комплексів на 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}4
• функція $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 9$:

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

Послідовність A000372 в OEIS.

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

Якщо 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}),$

Основна ідея цих оцінок полягає в тому, що в більшості антиланцюгів усі множини мають розміри, дуже близькі до n/2. Для n = 2, 4, 6, 8 формула Коршунова дає оцінку, яка має похибку 9,8 %, 10,2 %, 4,1 % і -3,3 %, відповідно.

$c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).$

Література

• 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.