Número de Dedekind

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.[1]​ El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

contradicciónA y B y CA y BA y CB y C(A y B) o (A y C)(A y B) o (B y C)(A y C) o (B y C)ABC(A o B) y (A o C) y (B o C) <==> (A y B) o (A y C) o (B y C)(A o B) y (A o C)(A o B) y (B o C)(A o C) y (B o C)A o BA o CB o CA o B o Ctautología
Los retículos distributivos libres de funciones booleanas monótonas sobre 0, 1, 2 y 3 argumentos.

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,[2][3][4]​ y una expresión exacta en forma de sumatoria,[5]​ el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 9.[6][7][8]

Ejemplo

editar

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) = xy 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) = xy 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

editar

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]
1 3 1940[1]
2 6 1940[1]
3 20 1940[1]
4 168 1940[1]
5 7 581 1940[9]
6 7 828 354   1946[10]
7 2 414 682 040 998   1965[11]​ y 1976[12]
8 56 130 437 228 687 557 907 788   1991[6]
9 286 386 577 668 298 411 128 469 151 667 598 498 812 366   2023[7][8]
(sucesión A000372 en OEIS)

Si n es un número par, entonces M(n) también debería serlo.[13]​ 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).[9]

Fórmula con sumatoria

editar

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

 

donde

 

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

editar

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

 

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

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

 

para n par, y

 

para n impar, donde

 
 

y

 

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.[15]​ 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.[16]

Referencias

editar
  1. a b c d e f Dedekind, Richard (1897), Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler 2, Gesammelte Werke, pp. 103-148 ..
  2. a b Kleitman, D.; Markowsky, G. (1975), «On Dedekind's problem: the number of isotone Boolean functions. II», Transactions of the American Mathematical Society 213: 373-390, MR0382107 ..
  3. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
  4. Kahn, Jeff (2002), «Entropy, independent sets and antichains: a new approach to Dedekind's problem», Proceedings of the American Mathematical Society 130 (2): 371-378, doi:10.1090/S0002-9939-01-06058-0, MR1862115 ..
  5. a b Kisielewicz, Andrzej (1988), «A solution of Dedekind's problem on the number of isotone Boolean functions», Journal für die Reine und Angewandte Mathematik 386: 139-144, doi:10.1515/crll.1988.386.139, MR936995 ..
  6. a b Wiedemann, Doug (1991), «A computation of the eighth Dedekind number», Order 8 (1): 5-6, doi:10.1007/BF00385808, MR1129608 ..
  7. a b Jäkel, Christian (5 de abril de 2023). «A computation of the ninth Dedekind Number». arXiv:2304.00895 [math]. 
  8. a b Van Hirtum, Lennart (6 de abril de 2023). «A computation of D(9) using FPGA Supercomputing». arXiv:2304.03039 [math]. 
  9. a b Church, Randolph (1940), «Numerical analysis of certain free distributive structures», Duke Mathematical Journal 6: 732-734, MR0002842 ..
  10. Ward, Morgan (1946), «Note on the order of free distributive lattices», Bulletin of the American Mathematical Society 52: 423 ..
  11. Church, Randolph (1965), «Enumeration by rank of the free distributive lattice with 7 generators», Notices of the American Mathematical Society 11: 724 .. Citado por Wiedemann, 1991.
  12. Berman, Joel; Köhler, Peter (1976), «Cardinalities of finite distributive lattices», Mitt. Math. Sem. Giessen 121: 103-124, MR0485609 ..
  13. Yamamoto, Koichi (1953), «Note on the order of free distributive lattices», Science Reports of the Kanazawa University 2 (1): 5-6, MR0070608 ..
  14. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
  15. Zaguia, Nejib (1993), «Isotone maps: enumeration and structure», en Sauer, N. W.; Woodrow, R. E.; Sands, B., eds., Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421-430, MR1261220 ..
  16. Brown, K. S., Generating the monotone Boolean functions, archivado desde el original el 18 de diciembre de 2010, consultado el 3 de octubre de 2010 ..