Richard Laver demostró que existe una única operación binaria $*$ en $\{1,\ldots,2^n\}$ que satisface $$a*1 \equiv a+1 \mod 2^n$$ $$a* (b* c) = (a* b) * (a * c).$$ Esta es la $n$ La mesa Laver $(A_n,*)$ .
Existe un algoritmo para calcular $a * b$ en $A_n$ pero en general (y especialmente para valores pequeños de $a$ ), esto requiere que uno calcule gran parte del resto de $A_n$ . ¿Cuál es el mayor valor de $n$ para el que alguien puede, en un tiempo modesto, calcular una entrada arbitraria en $A_n$ ? Soy capaz de calcular las entradas en $A_{27}$ .
Debo señalar que el mapa que envía $a$ a $a\ \mathrm{mod}\ 2^m$ define un homomorfismo de $A_n$ a $A_m$ para $m < n$ y, por lo tanto, el problema se vuelve estrictamente más difícil para las $n$ .
Edición: En realidad he podido calcular $A_{28}$ , no sólo $A_{27}$ .
0 votos
¿Tiene alguna referencia que pueda dar sobre el algoritmo? Gracias,
2 votos
@Apollo: El que solía llegar a $A_{27}$ se basa en las ideas del libro de Dehornoy "Braids and self distributivity" en el que trata la función $\theta$ . La idea básica de la computación en $A_n$ viene dada por las siguientes identidades: $a*k = (a+1)_{[k+1]}$ para $a < 2^n$ y $2^n * k = k$ . Aquí $a_{[k]}$ es el $k$ la potencia asociada a la izquierda de $a$ . Esto le permite comenzar en la parte inferior de la tabla y trabajar hacia arriba. Implementar esto directamente me permite llegar a $A_{19}$ (hay problemas tanto de tiempo como de memoria para $A_{20}$ ). Contacta conmigo fuera de la lista para obtener el código, si quieres.
0 votos
Gracias. Me sorprendería que hubiera un método más rápido (basado en la necesidad (tal vez) de grandes cardinales muy potentes (al menos más que PRA) para demostrar hechos sobre la periodicidad de la fila superior) para calcular entradas arbitrarias...
0 votos
La velocidad del algoritmo no es tan mala, en realidad, si se tiene en cuenta que $A_n$ tiene $2^n$ filas. No espero llegar a $A_{1000}$ pero tengo curiosidad por saber si existen trucos que permitan realizar un único cálculo en, por ejemplo, $A_{40}$ en un ordenador de sobremesa con una cantidad típica de memoria y 24 horas. El algoritmo ingenuo hace que los cálculos individuales sean muy rápidos (sólo una consulta a la memoria), pero hay un gran precio por adelantado. El algoritmo revisado hace que los cálculos individuales sean un poco más costosos, pero con un precio inicial menor. Pido más compensaciones de este tipo.
1 votos
Puede ser que se pueda ejecutar la distribución "al revés". ¿Sabes cómo encontrar a,b y c, dados m y n, tales que a b = m y a c =n ? Además, ¿puedes dar una referencia para el resultado de Laver de que la autodistributiva izquierda * es única hasta el isomorfismo? Gerhard "Ask Me About System Design" Paseman, 2011.03.11
1 votos
@Gerhard: El libro de Dehornoy es quizás la mejor referencia para los no teóricos del conjunto.
0 votos
@Gerhard:Me equivoqué en la afirmación de único hasta el isomorfismo. Hay que añadir la hipótesis de que alguna potencia no trivial asociada a la izquierda de 1 es 1. Si no, hay un contraejemplo: definir * en {1,2,3} por 1*1 = 2, y a*b = 3 si a y b no son ambos 1. Se puede comprobar que se trata de un sistema LD. He editado mi pregunta adecuadamente.
0 votos
Gracias Andrés. Habiendo tenido algún contacto con la teoría de conjuntos y los fundamentos, ¿hay alguna referencia del resultado de Laver para los teóricos de conjuntos? (Estando en la lista de correo de teoría de estructuras, es posible que pueda manejar tal referencia). Gerhard "También sé algo de álgebra universal" Paseman, 2011.03.11
2 votos
@Gerhard:El libro de Dehornoy es bueno tanto para los teóricos del conjunto como para los que no lo son. Ganó un premio. Lee también los artículos originales de Laver en Advances in Math. (años 90, creo). Están bien escritos. En su mayoría se refieren al álgebra de incrustaciones elementales, pero hay algo al final sobre las tablas de Laver.
0 votos
Gracias Justin. Espero poder llegar pronto al libro de Dehornoy, cuando termine algunos proyectos. ¿Hay otros homomorfismos entre los A_i? Quizás uno o dos de ellos puedan ayudar en los cálculos. Gerhard "Ask Me About System Design" Paseman, 2011.03.12
0 votos
@Gerhard:Cada fila $a$ de $A_n$ define un monomorfismo de algún $A_p$ en $A_n$ : $b \mapsto a * b$ . Aquí $p$ tal que $2^p$ es el período de la fila $a$ . Que esto sea un homomorfismo no es más que la ley de LD: $a * (b * c) = (a * b) * (a * c)$ . Esta idea se reproduce en cierta medida en el libro de Dehornoy.
0 votos
También me interesa por curiosidad saber cuál es la mayor tabla de Laver que se ha computado a mano. Por ejemplo, ¿alguien se ha molestado en calcular a mano una tabla de Laver de 512x512 o de 1024x1024? No es demasiado difícil calcular esas tablas de Laver si se utiliza un sistema numérico hexadecimal o similar en lugar del sistema numérico decimal habitual (sólo lleva un poco de tiempo).