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

<imagemap> Файл:Monotone Boolean functions 0,1,2,3.svg|300px|thumb|right|Вільні дистрибутивні ґратки монотонних булевих функцій від 0, 1, 2 і 3 аргументів з 2, 3, 6 і 20 елементами відповідно (наведіть вказівник на праву діаграму, щоб бачити опис)

circle 659 623 30 circle 658 552 35 circle 587 480 35 circle 659 481 35 circle 729 481 35 circle 588 410 35 circle 658 410 35 circle 729 410 35 circle 548 339 30 circle 604 339 30 circle 758 339 30 circle 661 339 35 circle 588 268 35 circle 659 267 35 circle 729 268 35 circle 588 197 35 circle 658 197 35 circle 729 197 35 circle 658 126 35 circle 659 56 30

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

Точні асимптотичні оцінки M(n)Шаблон:SfnШаблон:SfnШаблон:Sfn і точний вираз у вигляді сумиШаблон:Sfn відомі. Однак задача Дедекінда обчислення значень M(n) залишається складною — невідомий вираз у замкнутій формі для M(n) і точні значення M(n) знайдено лише для $n⩽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 генераторами. Таким чином, числа Дедекінда підраховують число елементів у вільних дистрибутивних ґраткахШаблон:SfnШаблон:SfnШаблон:Sfn.

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

Приклад

Для 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⩽n⩽9$:

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

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

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

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

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

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

$M(n)=\sum _{k=1}^{2^{2^n}}\prod _{j=1}^{2^n-1}\prod _{i=0}^{j-1}(1-b_i^k{b}_j^k\prod _{m=0}^{{\log }_{2}i}(1-b_m^i+b_m^i{b}_m^j)),$

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

$b_i^k=\lfloor \frac{k}{2^i}\rfloor -2\lfloor \frac{k}{2^{i+1}}\rfloor .$

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

Асимптотика

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

$(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })⩽{\log }_{2}M(n)⩽(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })(1+O\left(\frac{\log n}{n}\right)).$

Тут нерівність зліва підраховує число антиланцюгів, у яких кожна множина має рівно $\lfloor n/2\rfloor$ елементів, а праву нерівність довели Кляйтман і МарковськийШаблон:Sfn.

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

$M(n)=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\exp a(n)$

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

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

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

$a(n)=(\genfrac{}{}{0ex}{}{n}{n/2-1})(2^{-n/2}+n^2{2}^{-n-5}-n{2}^{-n-4}),$

$b(n)=(\genfrac{}{}{0ex}{}{n}{(n-3)/2})(2^{-(n+3)/2}+n^2{2}^{-n-6}-n{2}^{-n-3}),$

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

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

Література

• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья. Как процитировано Видерманом (Шаблон:Harvtxt).
• Шаблон:Книга-ру
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Книга-ру