Número de Dedekind

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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:

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 ≤ 8.[6]

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 ≤ 8. 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 conocidos, 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 7581 1940[7]
6 7828354 1946[8]
7 2414682040998 1965[9] y 1976[10]
8 56130437228687557907788 1991[6]
(sucesión A000372 en OEIS)

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

Fórmula con sumatoria[editar]

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

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_k^k \prod_{m=0}^{\log_2 i} (1-b_m^i+b_m^i b_m^j)\right),

donde

b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\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[editar]

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

{n\choose \lfloor n/2\rfloor}\le \log_2 M(n)\le {n\choose \lfloor n/2\rfloor}\left(1+O\left(\frac{\log n}{n}\right)\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.[2]

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

M(n) = (1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp a(n)

para n par, y

M(n) = (1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp (b(n)+c(n))

para n impar, donde

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

y

c(n)={n\choose (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.[13] 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.[14]

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 Church, Randolph (1940), «Numerical analysis of certain free distributive structures», Duke Mathematical Journal 6: 732–734, MR0002842 .
  8. Ward, Morgan (1946), «Note on the order of free distributive lattices», Bulletin of the American Mathematical Society 52: 423 .
  9. 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.
  10. Berman, Joel; Köhler, Peter (1976), «Cardinalities of finite distributive lattices», Mitt. Math. Sem. Giessen 121: 103–124, MR0485609 .
  11. Yamamoto, Koichi (1953), «Note on the order of free distributive lattices», Science Reports of the Kanazawa University 2 (1): 5–6, MR0070608 .
  12. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5–108, MR0640855 .
  13. Zaguia, Nejib (1993), «Isotone maps: enumeration and structure», en Sauer, N. W.; Woodrow, R. E.; Sands, B., 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 .
  14. Brown, K. S., Generating the monotone Boolean functions, http://www.mathpages.com/home/kmath094.htm .