Número de Dedekind

<imagemap> Archivo:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|derecha|Los retículos distributivos libres de funciones booleanas monótonas sobre 0, 1, 2 y 3 argumentos.

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> En combinatoria, los números de Dedekind son una sucesión entera de rápido crecimiento cuyo nombre se dio póstumamente en honor a Richard Dedekind, quien las definió por primera vez en 1897. El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

• El número de funciones booleanas monótonas de n variables.
• El número de anticadenas de subconjuntos de un conjunto de n elementos.
• El número de elementos en un retículo distributivo libre con n generadores.
• El número de juegos simples irredundantes definibles sobre n jugadores.
• El número de hipergrafos minimales completos, definibles sobre un conjunto base de cardinalidad n.
• El número de familias de Sperner sobre un conjunto de n elementos.

Encontrar una expresión matemática de forma cerrada para M(n) se conoce como el Problema de Dedekind. Aunque existen aproximaciones asintóticas que estiman este número, y una expresión exacta en forma de sumatoria, el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 9.

Ejemplo

Para n = 2, existen seis funciones booleanas monótonas y seis anticadenas de subconjuntos del conjunto de dos elementos {x,y}:

• La función f(x,y) = falso, que ignora sus valores de entrada y siempre retorna falso, corresponde a la anticadena vacía Ø.
• La conjunción lógica f(x,y) = x ∧ y corresponde a la anticadena { {x,y} }, que contiene al conjunto {x,y}.
• La función f(x,y) = x, que ignora su segundo argumento y retorna el primero, corresponde a la anticadena { {x} } que contiene al conjunto {x}.
• La función f(x,y) = y, que ignora su primer argumento y retorna el segundo, corresponde a la anticadena { {y} } que contiene al conjunto {y}.
• La disyunción lógica f(x,y) = x ∨ y corresponde a la anticadena { {x}, {y} }, que contiene a los dos conjuntos {x} e {y}.
• La función f(x,y) = verdadero, que ignora sus valores de entrada y siempre retorna verdadero, corresponde a la anticadena {Ø} que contiene sólo al conjunto vacío.

Valores conocidos

Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 9. La siguiente tabla muestra tales números, junto con el año y la publicación en que fueron calculados:

Gráfica de los números de Dedekind hasta n = 8, donde se aprecia el crecimiento exponencial de la sucesión.

n	Número M(n)	Año
0	2	1940
1	3	1940
2	6	1940
3	20	1940
4	168	1940
5	7 581	1940
6	7 828 354 $\approx 7.83\times 10^6$	1946
7	2 414 682 040 998 $\approx 2.41\times 10^{12}$	1965 y 1976
8	56 130 437 228 687 557 907 788 $\approx 5.61\times 10^{22}$	1991
9	286 386 577 668 298 411 128 469 151 667 598 498 812 366 $\approx 2.86\times 10^{41}$	2023
Plantilla:OEIS

Si n es un número par, entonces M(n) también debería serlo. El cálculo de M(5) = 7581 fue el contraejemplo que desaprobó una conjetura realizada por Garrett Birkhoff que decía que M(n) es siempre divisible por (2n - 1)(2n - 2).

Fórmula con sumatoria

Andrzej Kisielewicz en 1988 demostró la siguiente fórmula para los números de Dedekind:

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

donde

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

Sin embargo, esta fórmula no es útil para el cómputo de los valores de M(n) para n grandes, debido al gran número de términos en la sumatoria.

Asíntotas

El logaritmo de los números de Dedekind puede ser estimado exactamente mediante las cotas

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

La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente $\lfloor n/2\rfloor$ elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.

A. D. Korshunov encontró en 1981 una estimación aún mejor:

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

para n par, y

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

para n impar, donde

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

y

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

La principal idea detrás de estas estimaciones, es que en la mayoría de las anticadenas, todos los conjuntos tienen tamaños muy cercanos a n/2. Para n = 2, 4, 6 y 8, la fórmula de Korshunov provee una estimación imprecisa por un factor de 9.8%, 10.2%, 4.1%, y -3.3%, respectivamente.