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

28.03.2021

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

Точные асимптотические оценки M(n) и точное выражение в виде суммы известны. Однако задача Дедекинда вычисления значений M(n) остаётся сложной — не известно выражения в замкнутой форме для M(n) и точные значения M(n) найдены только для n ⩽ 8 {displaystyle nleqslant 8} .

Определения

Булева функция — это функция, которая принимает в качестве входа 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 ∧ g {displaystyle fwedge g} и f ∨ g {displaystyle fvee g} , их логическую конъюнкцию и логическую дизъюнкцию соответственно. Семейство всех монотонных булевых функций от n входов вместе с этими двумя операциями образует дистрибутивную решётку, задаваемую теоремой Биркгофа о представлении из частично упорядоченного множества подмножеств n переменных с частичным порядком включения множеств. Это построение даёт свободную дистрибутивную решётку с n генераторами. Таким образом, числа Дедекинда подсчитывают число элементов в свободных дистрибутивных решётках .

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

Пример

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

  • Функция f ( x , y ) = f a l s e {displaystyle f(x,y)=false} , игнорирующая входные значения и всегда возвращающая false, соответствует пустой антицепи ∅ {displaystyle varnothing } .
  • Логическая конъюнкция f ( x , y ) = x ∧ y {displaystyle f(x,y)=xwedge y} соответствует антицепи { {x,y} }, содержащей единственное множество {x,y}.
  • Функция f ( x , y ) = x {displaystyle f(x,y)=x} , игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи { {x} }, содержащей единственное множество {x}.
  • Функция f ( x , y ) = y {displaystyle f(x,y)=y} , игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи { {y} }, содержащей единственное множество {y}.
  • Логическая дизъюнкция f ( x , y ) = x ∨ y {displaystyle f(x,y)=xvee y} соответствует антицепи { {x}, {y} }, содержащей два множества {x} и {y}.
  • Функция f ( x , y ) = t r u e {displaystyle f(x,y)=true} , игнорирующая входные значения и всегда возвращающая true, соответствует антицепи { ∅ } {displaystyle {varnothing }} , содержащей только пустое множество.

Значения

Точные значения чисел Дедекинда известны для 0 ⩽ n ⩽ 8 {displaystyle 0leqslant nleqslant 8} :

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

Первые шесть этих чисел дал Чёрч. M(6) вычислил Уорд, M(7) вычислили Чёрч Берман и Кёлер, а M(8) вычислил Видерман.

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

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

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

M ( n ) = ∑ k = 1 2 2 n ∏ j = 1 2 n − 1 ∏ i = 0 j − 1 ( 1 − b i k b j k ∏ m = 0 log 2 ⁡ i ( 1 − b m i + b m i b m j ) ) , {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}) ight),}

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

b i k = ⌊ k 2 i ⌋ − 2 ⌊ k 2 i + 1 ⌋ . {displaystyle b_{i}^{k}=leftlfloor {frac {k}{2^{i}}} ight floor -2leftlfloor {frac {k}{2^{i+1}}} ight floor .}

Однако эта формула бесполезна для вычисления значений M(n) для больших n ввиду большого числа членов суммирования.

Асимптотика

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

( n ⌊ n / 2 ⌋ ) ⩽ log 2 ⁡ M ( n ) ⩽ ( n ⌊ n / 2 ⌋ ) ( 1 + O ( log ⁡ n n ) ) . {displaystyle {n choose lfloor n/2 floor }leqslant log _{2}M(n)leqslant {n choose lfloor n/2 floor }left(1+Oleft({frac {log n}{n}} ight) ight).}

Здесь неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности ⌊ n / 2 ⌋ {displaystyle lfloor n/2 floor } элементов, а правое неравенство доказали Кляйтман и Марковский.

Коршунов дал даже более точные оценки

M ( n ) = ( 1 + o ( 1 ) ) 2 ( n ⌊ n / 2 ⌋ ) exp ⁡ a ( n ) {displaystyle M(n)=(1+o(1))2^{n choose lfloor n/2 floor }exp a(n)}

для чётных n, и

M ( n ) = ( 1 + o ( 1 ) ) 2 ( n ⌊ n / 2 ⌋ + 1 ) exp ⁡ ( b ( n ) + c ( n ) ) {displaystyle M(n)=(1+o(1))2^{n choose lfloor n/2 floor +1}exp(b(n)+c(n))}

для нечётных n, где

a ( n ) = ( n n / 2 − 1 ) ( 2 − n / 2 + n 2 2 − n − 5 − n 2 − n − 4 ) , {displaystyle a(n)={n choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),} b ( n ) = ( n ( n − 3 ) / 2 ) ( 2 − ( n + 3 ) / 2 + n 2 2 − n − 6 − n 2 − n − 3 ) , {displaystyle b(n)={n choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),}

и

c ( n ) = ( n ( n − 1 ) / 2 ) ( 2 − ( n + 1 ) / 2 + n 2 2 − n − 4 ) . {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 %, соответственно.