Число Дедекинда - Dedekind number

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

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

Известны точные асимптотические оценки M ( n ) и точное выражение в виде суммы . Однако задача Дедекинда о вычислении значений M ( n ) остается сложной: нет выражения в замкнутой форме для M ( n ), а точные значения M ( n ) были найдены только для n ≤ 8.

Определения

Функции булева это функция , которая принимает в качестве входных п булевых переменных (то есть значения , которые могут быть либо ложным или истинным, или , что эквивалентно двоичных значений , которые могут быть либо 0 , либо 1), а также производит в качестве выходного сигнала другой логической переменной. Это монотонно, если для каждой комбинации входов переключение одного из входов с ложного на истинное может только вызвать переключение вывода с ложного на истинное, а не с истинного на ложное. Число Дедекинда M ( n ) - это количество различных монотонных булевых функций от n переменных.

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

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

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

пример

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

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

Значения

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

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

Первые шесть из этих чисел даны Черчем (1940) . M (6) был рассчитан Ward (1946) , M (7) был рассчитан Черчем (1965) и Berman & Köhler (1976) , а M (8) Wiedemann (1991) .

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

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

Киселевич (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 из-за большого количества членов в суммировании.

Асимптотика

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

{\ 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 п / 2 \ rfloor}$

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

{\ Displaystyle М (п) = (1 + о (1)) 2 ^ {п \ выбрать \ lfloor п / 2 \ rfloor} \ ехр а (п)}

для четных 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 б (п) = {п \ выбрать (п-3) / 2} (2 ^ {- (п + 3) / 2} + п ^ {2} 2 ^ {- п-6} -n2 ^ {-n-3}),}

и

{\ displaystyle 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% соответственно.

Languages

In other projects

Число Дедекинда - Dedekind number

Содержание

Определения

пример

Значения

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

Асимптотика

Ноты

Рекомендации