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

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

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

Точні асимптотичні оцінки M(n)^[1][2][3] і точний вираз у вигляді суми^[4] відомі. Однак задача Дедекінда обчислення значень M(n) залишається складною — невідомий вираз у замкнутій формі для M(n) і точні значення M(n) знайдено лише для ${\displaystyle n\leqslant 9}$^[5].

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

Визначення

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

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

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

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

Приклад

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

• функція ${\displaystyle f(x,y)=false}$, що нехтує вхідні значення і завжди повертає false, відповідає порожньому антиланцюгу ${\displaystyle \varnothing }$;
• логічна кон'юнкція ${\displaystyle f(x,y)=x\wedge y}$ відповідає антиланцюгу {{x, y}}, що містить єдину множину {x, y};
• функція ${\displaystyle f(x,y)=x}$, що нехтує другий аргумент і повертає перший аргумент, відповідає антиланцюгу {{x}}, що містить єдину множину {x}4
• функція ${\displaystyle f(x,y)=y}$, що нехтує перший аргумент і повертає другий аргумент, відповідає антиланцюгу {{y}}, що містить єдину множину {y};
• логічна диз'юнкція ${\displaystyle f(x,y)=x\vee y}$ відповідає антиланцюгу {{x}, {y}}, що містить дві множини {x} і {y};
• функція ${\displaystyle f(x,y)=true}$, що нехтує вхідні значення і завжди повертає true, відповідає антиланцюгу ${\displaystyle \{\varnothing \}}$, що містить тільки порожню множину.

Значення

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

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

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

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

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

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

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

${\displaystyle 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),}$

де ${\displaystyle b_{i}^{k}}$ є ${\displaystyle i}$-им бітом числа ${\displaystyle k}$, який може бути записаний за допомогою округлення вниз

${\displaystyle b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .}$

Однак ця формула непридатна для обчислення значень M(n) для великих n, зважаючи на велику кількість членів підсумовування.

Асимптотика

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

${\displaystyle {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).}$

Тут нерівність зліва підраховує число антиланцюгів, у яких кожна множина має рівно ${\displaystyle \lfloor n/2\rfloor }$ елементів, а праву нерівність довели Кляйтман і Марковський^[1].

Коршунов^[2] дав навіть точніші оцінки^[10]

${\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)}$

для парних n, і

${\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))}$

для непарних n, де

${\displaystyle a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),}$

${\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),}$

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

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

Примітки

1. Kleitman, Markowsky, 1975.
2. Коршунов, 1981.
3. Kahn, 2002.
4. Kisielewicz, 1988.
5. Van Hirtum, Lennart (6 квітня 2023). A computation of D(9) using FPGA Supercomputing. arXiv:2304.03039 [cs.DM].
6. Після 32 років пошуків математики знайшли секретне число Дедекінда. // Автор: Anna Nevolina. 28.06.2023
7. Визначення вільної дистрибутивної ґратки, що використовується тут, дозволяє як операції на ґратці будь-яке скінченне число сходжень і розходжень, включно з порожніми. Для вільної дистрибутивної ґратки, в якій дозволено тільки попарні сходження і розходження, слід виключити верхній і нижній елемент ґратки і відняти два від чисел Дедекінда.
8. Church, 1940.
9. Church, 1965.
10. Zaguia, 1993.
11. Ward, 1946.
12. Berman, Köhler, 1976.
13. Wiedemann, 1991.
14. Yamamoto, 1953.
15. 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.