Число Дедекинда

Комбинаторная последовательность чисел

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

В математике числа Дедекинда — это быстро растущая последовательность целых чисел, названная в честь Ричарда Дедекинда , который определил их в 1897 году. Число Дедекинда M ( n ) — это число монотонных булевых функций от n переменных. Эквивалентно, это число антицепей подмножеств множества из n элементов, число элементов в свободной дистрибутивной решетке с n образующими и на единицу больше числа абстрактных симплициальных комплексов на множестве из n элементов.

Известны точные асимптотические оценки M ( n ) и точное выражение в виде суммы . ^[1] Однако задача Дедекинда по вычислению значений M ( n ) остается сложной: не известно никакого замкнутого выражения для M ( n ), а точные значения M ( n ) были найдены только для n  ≤ 9 (последовательность A000372 в OEIS ).

Определения

Булева функция — это функция, которая принимает на вход n булевых переменных (то есть значения, которые могут быть либо ложными, либо истинными, или, что эквивалентно, двоичные значения , которые могут быть либо 0, либо 1), и производит на выходе другую булеву переменную. Она монотонна , если для каждой комбинации входов переключение одного из входов с ложного на истинное может только вызвать переключение выхода с ложного на истинное, но не с истинного на ложное. Число Дедекинда M ( n ) — это количество различных монотонных булевых функций от n переменных. ^[2]

Антицепь множеств (также известная как семейство Шпернера ) — это семейство множеств, ни одно из которых не содержится ни в каком другом множестве. Если V — множество из n булевых переменных, антицепь A подмножеств V определяет монотонную булеву функцию f , где значение f истинно для заданного множества входов, если некоторое подмножество истинных входов f принадлежит A , и ложно в противном случае. Наоборот, каждая монотонная булева функция определяет таким образом антицепь минимальных подмножеств булевых переменных, которые могут заставить значение функции стать истинным. Следовательно, число Дедекинда M ( n ) равно количеству различных антицепей подмножеств множества из n элементов. ^[3]

Третий, эквивалентный способ описания того же класса объектов использует теорию решеток . Из любых двух монотонных булевых функций f и g мы можем найти две другие монотонные булевы функции f ∧ g и f ∨ g , их логическую конъюнкцию и логическую дизъюнкцию соответственно. Семейство всех монотонных булевых функций на n входах вместе с этими двумя операциями образует дистрибутивную решетку , решетку, заданную теоремой Биркгофа о представлении из частично упорядоченного множества подмножеств n переменных с включением множеств в качестве частичного порядка. Эта конструкция создает свободную дистрибутивную решетку с n образующими. ^[4] Таким образом, числа Дедекинда подсчитывают элементы в свободных дистрибутивных решетках. ^[5]

Числа Дедекинда также насчитывают на единицу больше, чем число абстрактных симплициальных комплексов на множестве с n элементами, семейств множеств со свойством, что любое непустое подмножество множества в семействе также принадлежит семейству. Любая антицепь (кроме {Ø}) определяет симплициальный комплекс, семейство подмножеств членов антицепи, и наоборот, максимальные симплексы в комплексе образуют антицепь. ^[6]

Пример

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

• Функция f ( x , y ) = false , которая игнорирует свои входные значения и всегда возвращает false , соответствует пустой антицепи Ø.
• Логическая конъюнкция f ( x , y ) =  x  ∧  y соответствует антицепи { { x , y } }, содержащей единственный набор { x , y }.
• Функция f ( x , y ) =  x , которая игнорирует свой второй аргумент и возвращает первый аргумент, соответствует антицепи { { x } }, содержащей единственный набор { x }
• Функция f ( x , y ) =  y , которая игнорирует свой первый аргумент и возвращает второй аргумент, соответствует антицепи { { y } }, содержащей единственный набор { y }
• Логическая дизъюнкция f ( x , y ) =  x  ∨  y соответствует антицепи { { x }, { y } }, содержащей два множества { x } и { y }.
• Функция f ( x , y ) = true , которая игнорирует свои входные значения и всегда возвращает true , соответствует антицепи {Ø}, содержащей только пустое множество. ^[7]

Ценности

Точные значения чисел Дедекинда известны для 0 ≤ n ≤ 9:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 (последовательность A000372 в OEIS ).

Первые пять из этих чисел (т. е. от M (0) до M (4)) даны Дедекиндом (1897). ^[8] M (5) было вычислено Чёрчем (1940). M (6) было вычислено Уордом (1946), M (7) было вычислено Чёрчем (1965) и Берманом и Кёлером (1976), M (8) было вычислено Видеманном (1991), а M (9) было одновременно открыто в 2023 году Кристианом Йекелем ^{[9] [10]} и Леннартом Ван Хиртумом и др. ^[11]

Если n четное, то M ( n ) также должно быть четным. ^[12] Вычисление пятого числа Дедекинда M (5) = 7581 опровергло гипотезу Гаррета Биркгофа о том, что M ( n ) всегда делится на (2 n  − 1)(2 n  − 2). ^[13]

Формула суммирования

Киселевич (1988) переписал логическое определение антицепей в следующую арифметическую формулу для чисел Дедекинда:

${\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 из-за большого количества членов в сумме. ^[14]

Асимптотика

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

${\displaystyle {n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).}$

Здесь левое неравенство учитывает антицепи, в которых каждое множество содержит ровно элементов, а правое неравенство было доказано Клейтманом и Марковским (1975). ${\displaystyle \lfloor n/2\rfloor }$

Коршунов (1981) дал еще более точные оценки ^[15]

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

и

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

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

Примечания

1. Клейтман и Марковский (1975); Коршунов (1981); Кан (2002); Киселевич (1988).
2. Киселевич (1988).
3. Кан (2002).
4. Определение свободных дистрибутивных решеток, используемое здесь, допускает в качестве решеточных операций любые конечные встречи и соединения, включая пустые встречи и пустые соединения. Для свободной дистрибутивной решетки, в которой разрешены только попарные встречи и соединения, следует исключить верхний и нижний элементы решетки и вычесть два из чисел Дедекинда.
5. Чёрч (1940); Чёрч (1965); Загия (1993).
6. Киселевич (1988).
7. То, что эта антицепь соответствует верхнему элементу решетки, можно увидеть, рассмотрев определение meet в статье об антицепях .
8. Томбак, Мати (2001). «О логическом методе подсчета дедекиндовых чисел». Основы теории вычислений . Конспект лекций по информатике. Том 2138. С. 424–427. doi :10.1007/3-540-44669-9_48. ISBN 978-3-540-42487-1.
9. Йекель, Кристиан (03.04.2023). «Вычисление девятого числа Дедекинда». arXiv : 2304.00895 [math.CO].
10. Jäkel, Christian (2023). «Вычисление девятого числа Дедекинда». Журнал вычислительной алгебры . 6–7 . arXiv : 2304.00895 . doi : 10.1016/j.jaca.2023.100006 .
11. Ван Хиртум, Леннарт (2023-04-06). «Вычисление D(9) с использованием суперкомпьютеров FPGA». arXiv : 2304.03039 [cs.DM].
12. Ямамото (1953).
13. Церковь (1940).
14. Например, для сумма содержит члены, которые намного превосходят те, которые можно просуммировать численно. ${\displaystyle n=10}$ ${\displaystyle 2^{2^{10}}=2^{1024}}$
15. Zaguia (1993).
16. Браун, К.С., Генерация монотонных булевых функций

Ссылки

• Берман, Джоэл; Кёлер, Питер (1976), «Мощности конечных дистрибутивных решёток», Mitt. Math. Sem. Giessen , 121 : 103–124, MR  0485609.
• Чёрч, Рэндольф (1940), «Численный анализ некоторых свободных дистрибутивных структур», Duke Mathematical Journal , 6 (3): 732–734, doi :10.1215/s0012-7094-40-00655-x, MR  0002842.
• Чёрч, Рэндольф (1965), «Перечисление по рангу свободной дистрибутивной решётки с 7 образующими», Notices of the American Mathematical Society , 11 : 724. Как цитирует Видеманн (1991).
• Дедекинд, Рихард (1897), «Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler», Gesammelte Werke , vol. 2, стр. 103–148..
• Кан, Джефф (2002), «Энтропия, независимые множества и антицепи: новый подход к проблеме Дедекинда», Труды Американского математического общества , 130 (2): 371–378, doi : 10.1090/S0002-9939-01-06058-0 , MR  1862115.
• Киселевич, Анджей (1988), «Решение проблемы Дедекинда о количестве изотонных булевых функций», Journal für die Reine und Angewandte Mathematik , 1988 (386): 139–144, doi : 10.1515/crll.1988.386.139, MR  0936995, S2CID  115293297
• Клейтман, Д .; Марковски, Г. (1975), «О проблеме Дедекинда: число изотонных булевых функций. II», Труды Американского математического общества , 213 : 373–390, doi : 10.2307/1998052, JSTOR  1998052, MR  0382107.
• Коршунов, А.Д. (1981), «Число монотонных булевых функций», Проблемы кибернет. , 38 : 5–108, MR  0640855.
• Томбак, Мати (2001), «О логическом методе подсчета дедекиндовых чисел», Основы теории вычислений , Конспект лекций по информатике, т. 2138, стр. 424–427, doi :10.1007/3-540-44669-9_48, ISBN 978-3-540-42487-1.
• Уорд, Морган (1946), «Заметка о порядке свободных дистрибутивных решеток», Бюллетень Американского математического общества , 52 : 423, doi : 10.1090/S0002-9904-1946-08568-7.
• Видеманн, Дуг (1991), «Вычисление восьмого числа Дедекинда», Order , 8 (1): 5–6, doi :10.1007/BF00385808, MR  1129608, S2CID  120878757.
• Ямамото, Коити (1953), «Заметка о порядке свободных дистрибутивных решеток», Научные отчеты Университета Каназавы , 2 (1): 5–6, MR  0070608.
• Zaguia, Nejib (1993), «Изотонные карты: перечисление и структура», в Sauer, NW; Woodrow, RE; Sands, B. (ред.), Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, 4 мая 1991 г.) , Kluwer Academic Publishers, стр. 421–430, MR  1261220.