Números de Dedekind

Los números de Dedekind son una secuencia de números enteros de rápido crecimiento que lleva el nombre de Richard Dedekind , quien los definió en 1897. El número de Dedekind M ( n ) cuenta el número de funciones booleanas monótonas de n variables. De manera equivalente, estos números cuentan 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 , o el número de complejos simpliciales abstractos con n elementos.

Se conocen las estimaciones asintóticas exactas de M ( n ) [1] [2] [3] y la expresión exacta como suma [4] . Sin embargo , el problema de Dedekind de calcular los valores de M ( n ) sigue siendo difícil: no se conoce ninguna expresión de forma cerrada para M ( n ), y los valores exactos de M ( n ) se han encontrado solo para [5] .

Definiciones

Una función booleana es una función que toma como entrada n variables booleanas (es decir, valores que pueden ser falso (falso) o verdadero (verdadero), o, de manera equivalente, valores binarios , que pueden ser 0 o 1), y da otra variable booleana como salida. Una función es monótona si, para cualquier combinación de entradas, cambiar una variable de entrada de falso a verdadero solo puede cambiar la salida de falso a verdadero, pero no de verdadero a falso. El número de Dedekind M ( n ) es el número de diferentes funciones booleanas monótonas de n variables.

Una anticadena de conjuntos (también conocida como familia Spencer ) es una familia de conjuntos, ninguno de los cuales está contenido en ningún otro conjunto. Si V es un conjunto de n variables booleanas, la anticadena A de subconjuntos de V define una función booleana monótona f cuando el valor de f es verdadero para el conjunto dado de entradas si algún subconjunto de entradas de la función f es verdadero si pertenece a A y falso en caso contrario. Por el contrario, cualquier función booleana monótona define una anticadena, los subconjuntos mínimos de variables booleanas que obligan a la función a evaluarse como verdadera. Por lo tanto, el número de Dedekind M ( n ) es igual al número de diferentes anticadenas de subconjuntos del conjunto de n elementos [3] .

Una tercera forma equivalente de describir la misma clase utiliza la teoría de la red . A partir de dos funciones booleanas monótonas f y g , podemos encontrar otras dos funciones booleanas monótonas y , su conjunción lógica y disyunción lógica , respectivamente. La familia de todas las funciones booleanas monótonas de n entradas, junto con estas dos operaciones, forma un retículo distributivo definido por el teorema de representación de Birkhoff a partir de un conjunto parcialmente ordenado de subconjuntos de n variables con un orden de inclusión parcial de conjuntos . Esta construcción da una red distributiva libre con n generadores [6] . Por lo tanto, los números de Dedekind cuentan el número de elementos en redes distributivas libres [7] [8] [9] .

Los números de Dedekind también cuentan (uno más) el número de complejos simpliciales abstractos sobre n elementos, una familia de conjuntos con la propiedad de que cualquier subconjunto de un conjunto en la familia también pertenece a la familia. Cualquier anticadena define un complejo simplicial , una familia de subconjuntos de miembros de anticadenas, y viceversa, los simples máximos en complejos forman una anticadena [4] .

Ejemplo

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

• Una función que ignora los valores de entrada y siempre devuelve falso corresponde a una anticadena vacía .
• Una conjunción lógica corresponde a una anticadena { { x , y } } que contiene un único conjunto { x , y }.
• Una función que ignora el segundo argumento y devuelve el primer argumento corresponde a una anticadena { { x } } que contiene un único conjunto { x }.
• Una función que ignora el primer argumento y devuelve el segundo argumento corresponde a una anticadena { { y } } que contiene un único conjunto { y }.
• Una disyunción lógica corresponde a una anticadena { { x }, { y } } que contiene dos conjuntos { x } y { y }.
• Una función que ignora los valores de entrada y siempre devuelve verdadero corresponde a una anticadena que contiene solo el conjunto vacío.

Valores

Los valores exactos de los números de Dedekind son conocidos por :

Los primeros seis de estos números fueron dados por Church [7] . Ward [10] calculó M (6) , Church [8] Berman y Köhler [11] calculó M (7) y Wiederman [5] calculó M (8) .

Si n es par, entonces M ( n ) también debe ser par [12] . Calcular el quinto número de Dedekind refuta la conjetura de Garrett Birkhoff de que M ( n ) siempre es divisible por [7] .

Fórmula de suma

Kiselevich [4] reescribió la definición lógica de anticadenas en la siguiente fórmula aritmética para los números de Dedekind:

donde está el -ésimo bit de , que se puede escribir redondeando hacia abajo

Sin embargo, esta fórmula es inútil para calcular los valores de M ( n ) para n grande debido a la gran cantidad de términos de suma.

Asintóticos

El logaritmo de los números de Dedekind se puede estimar exactamente usando límites

Aquí, la desigualdad de la izquierda cuenta el número de anticadenas en las que cada conjunto tiene elementos exactos, y la desigualdad de la derecha fue demostrada por Kleitman y Markovsky [1] .

Korshunov [2] dio estimaciones aún más precisas [9]

para n par , y

para n impar , donde

y

La idea principal de estas estimaciones es que en la mayoría de las anticadenas todos los conjuntos tienen tamaños muy cercanos a n /2 [9] . Para n = 2, 4, 6, 8, la fórmula de Korshunov da una estimación que tiene un error de 9,8 %, 10,2 %, 4,1 % y -3,3 %, respectivamente [13] .

Notas

1. ↑ 1 2 Kleitman, Markowsky, 1975 .
2. ↑ 1 2 Korshunov, 1981 .
3. ↑ 12 Kahn , 2002 .
4. ↑ 1 2 3 Kisielewicz, 1988 .
5. ↑ 12 Wiedemann , 1991 .
6. ↑ La definición de un enrejado distributivo libre que se usa aquí permite convergencias y divergencias finitas, incluidas las vacías, como operaciones en el enrejado. Para una red distributiva libre, en la que solo se permiten convergencias y divergencias por pares, se deben excluir los elementos superior e inferior de la red y restar dos de los números de Dedekind.
7. ↑ Iglesia 123 , 1940 .
8. ↑ Iglesia 12 , 1965 .
9. ↑ 1 2 3 Zaguia, 1993 .
10. ↑ Ward, 1946 .
11. ↑ Berman, Köhler, 1976 .
12. ↑ Yamamoto, 1953 .
13. ↑ Brown, Kansas, < https://www.mathpages.com/home/kmath094/kmath094.htm > 

Literatura

• Joel Berman, Peter Kohler. Cardinalidades de redes distributivas finitas // Mitt. Matemáticas. Sem. Giessen. - 1976. - T. 121 . — S. 103–124 .
• Iglesia Randolph. Análisis numérico de ciertas estructuras distributivas libres  // Duke Mathematical Journal. - 1940. - T. 6 . — S. 732–734 . -doi : 10.1215 / s0012-7094-40-00655-x . .
• Iglesia Randolph. Enumeración por rango de la red distributiva libre con 7 generadores // Avisos de la American Mathematical Society. - 1965. - T. 11 . - S. 724 . . Como lo cita Wiedemann (1991 ).
• Richard Dedekind . Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // Gesammelte Werke. - 1897. - T. 2. - S. 103-148.
• Jeff Khan. Entropía, conjuntos independientes y anticadenas: un nuevo enfoque para el problema de Dedekind // Actas de la American Mathematical Society. - 2002. - T. 130 , núm. 2 . — S. 371–378 . -doi : 10.1090 / S0002-9939-01-06058-0 .
• Andrzej Kisielewicz. Una solución al problema de Dedekind sobre el número de funciones booleanas isotónicas // Journal für die Reine und Angewandte Mathematik. - 1988. - T. 386 . — S. 139–144 . -doi : 10.1515/ crll.1988.386.139 .
• Kleitman D., Markowsky G. Sobre el problema de Dedekind: el número de funciones booleanas isotónicas. II // Transacciones de la Sociedad Matemática Americana. - 1975. - T. 213 . — S. 373–390 . -doi : 10.2307/ 1998052 . .
• Korshunov AD Sobre el número de funciones booleanas monótonas // Problemas de cibernética. - 1981. - T. 38 . — Pág. 5–108 .
• Barrio Morgan. Nota sobre el orden de los retículos distributivos libres // Bulletin of the American Mathematical Society. - 1946. - T. 52 . - art. 423 . -doi : 10.1090 / S0002-9904-1946-08568-7 .
• Doug Wiedemann. Un cálculo del octavo número de Dedekind // Orden . - 1991. - T. 8 , núm. 1 . — Pág. 5–6 . -doi : 10.1007/ BF00385808 . .
• Koichi Yamamoto. Nota sobre el orden de los retículos distributivos libres // Informes científicos de la Universidad de Kanazawa. - 1953. - Vol. 2 , número. 1 . — Pág. 5–6 .
• Nejib Zaguia. Mapas de isótonos: enumeración y estructura // Combinatoria finita e infinita en conjuntos y lógica (Proc. Inst. de estudios avanzados de la OTAN, Banff, Alberta, Canadá, 4 de mayo de 1991) / Sauer NW, Woodrow RE, Sands B.. — Kluwer Academic Editores, 1993, págs. 421–430.