Magmas

Seguimos la serie de posts sobre estructuras algebraicas.  En este hablamos sobre magmas y sobre su diferencia con otras estructuras, cómo los semigrupos (de transformaciones). No he podido resistirme a dar algunas pinceladas humorísticas, cómo siempre que trato de temas tan áridos. Espero no ofender a nadie.

Cómo en los dos anteriores posts el hilo conductor es ver cómo se formalizan  problemas científicos o matemáticos mediante acciones de estructuras algebraicas sobre conjuntos finitos (u otros objetos más estructurados que los conjuntos), y cómo se pueden representar estas acciones de estructuras algebraicas sobre conjuntos mediante digrafos, similares a los Digrafos de Cayley (nos interesan más las estructuras y digrafos finitos). Nos permitiremos alguna disgresión sobre otras estructuras relacionadas de alguna manera con los magmas, por ejemplo Álgebras no asociativas.

1. Concepto de Magma:

Un magma es una de las estructuras algebraicas sencillas menos restrictivas  (ver por ejemplo esta entrada de Wikipedia sobre estructuras algebraicas o esta otra sobre el mismo tema, también de Wikipedia). Consta de un  conjunto Q (que puede ser finito) dotado de una operación  binaria QxQ ->Q, sin axiomas adicionales. Recordemos que un semigrupo es un magma con operación binaria asociativa.

Nos interesaría obtener un modelo general para magmas finitos, el equivalente a Sn para grupos de finitos de permutaciones o a Tn para semigrupos finitos de transformaciones (recordemos que un modelo muy general para semigrupos finitos son los semigrupos finitos de transformaciones, de los que hemos hablado en el post anterior; otros “modelos” o ejemplos de semigrupos, no necesariamente finitos, son determinados autómatas y/o Cadenas de Markov).

Entonces ¿ Existen  “modelos” generales similares a Sn o Tn para magmas  (sobre todo de magmas no asociativos) ?

Intentaremos contestar a esto en el punto 5.  Primero veamos que distingue a los magmas de los semigrupos  (básicamente, la propiedad de operaciones llamada asociatividad), luego algunos ejemplos de magmas y finalmente que tienen todos ellos en común.

2. Sobre la asociatividad:

a) Sobre la  propiedad asociativa: http://groupprops.subwiki.org/wiki/Associative_binary_operation.

b) Otras estructuras no asociativas (algebras no asociativas):

c) No asociatividad y complejidad computacional:

http://www.santafe.edu/media/workingpapers/97-01-007.pdf

3. Ejemplos de magmas no asociativos:

a) un par de breves  drafts  sobre magmas: http://jimmysalvatore.com/magma.pdf y http://www.jimmysalvatore.com/magma2.pdf. El autor se pregunta ¿ porqué teoria de grupos y no una teoria de magmas ?.

b) Magmas en juegos: primero un ejemplo, muy curioso, de magma  no asociativo pero conmutativo (basado en el juego infantil piedra, papel y tijera): http://en.wikipedia.org/wiki/Example_of_a_commutative_non-associative_magma.

c) Magmas en combinatoria (Steiner magmas, squags y sloops): http://en.wikipedia.org/wiki/Steiner_system. Conocía los sistemas de Steiner (aparecen en geometrias finitas), pero no en este contexto.

d)  Magmas en lógica (Equivalential algebra, Implicational calculus, Equivalence algebra):

e) Magmas en  topología (racks,  quandles, keis): http://en.wikipedia.org/wiki/Racks_and_quandles, que aparecen en teoria de invariantes de nudos (ver: http://www.varf.ru/rudn/manturov/book.pdf; un buen link de teoria de nudos: http://www.math.uic.edu/~kauffman/569.html).

Señalar que  a los racks se los ha llamado  en ocasiones wracks automorphic sets y sí (no podía faltar este nombre, ver  post anterior), distributive…¡¡ groupoids !! (me imagino que se refieren a al-groupoids, pero no estoy seguro de momento) y crystals (¡¡ si los llegan a llamar quasycristals la monto !!).

“A quandle is a set equipped with two operations, . and .-1 satisfying the following three conditions for all elements x, y, and z.

Q1. x . x = x. (idempotency)

Q2. (x . y) .-1 y = x = (x .-1 y) . y. (right cancellation)

Q3. (x . y) . z = (x . z) .(y . z). (distributivity)

The symbol. is pronounced through, and .-1 backthrough.

Exercise 4.19. Prove that if Q is a conjugacy class in a group G then Q is a quandle”.

Extracto de http://math.clarku.edu/~djoyce/ma225/algebra.pdf, pg. 97.

Un rack satisface solo Q2 y Q3.

Sobre racks y quandles y su relación con la  teoria de invariantes de nudos ver también:

— survey sobre racks de Fenn y Rourke, muy completo, pero de 1991: http://arxiv.org/PS_cache/arxiv/pdf/1101/1101.1937v1.pdf 

–survey de 2002: http://arxiv.org/PS_cache/math/pdf/0211/0211096v1.pdf

–un survey más reciente, de 2010: http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.4429v2.pdf

http://arxiv.org/PS_cache/math/pdf/0606/0606264v2.pdf

— http://www.math.uic.edu/~kauffman/Winker.pdf (este paper de Winker es de 1984 y en el se definen grafos similares a los de Cayley para quandles). Según este paper también se utilizan grupos para analizar nudos, pero los quandles tienen algunas ventajas sobre los grupos: primero, en general o son finitos (los grupos de nudos no lo son) o no  muy infinitos (¿?); segundo el análisis por quandles es más fino ya  que permite distinguir nudos, que los grupos no distinguen y tercero permiten su representación eficiente mediante digrafos similares a los de Cayley (interesante); 

http://math.maconstate.edu/swallace/MAthesis.pdf. Una tesis sobre quandles y kei´s (involutory quandles; no se construyen en base a clases de conjugación de grupos). Hablan de un análogo  al teorema de Cayley, pero que no se cumple para quandles.   

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.4732v2.pdf.

f) Magmas y teoría cúantica: http://arxiv.org/PS_cache/arxiv/pdf/0812/0812.2533v2.pdf

g) medials (http://en.wikipedia.org/wiki/Medial: “Medial magmas need not be associative: for any nontrivial abelian group and integers m ≠ n, replacing the group operation x + y with the binary operation x \cdot y = mx+ny yields a medial magma which in general is neither associative nor commutative“. Ver también: http://www.karlin.mff.cuni.cz/~jezek/medial/03.jpg. No tengo claro en que contexto (aplicaciones) han surgido estos magmas.

4. Nudos y quandles

a) Preliminares:

Para comprender mejor el concepto de magma no asociativo, en lo que sigue intentaremos explicar los quandles con  un  ejemplo de  teoría topológica de nudos. 

Señalemos primero que hay dos enfoques para estudiar nudos, el clásico de corte geometrico-topologico, y uno más reciente de corte algebraico-combinatorio, de gran desarrollo desde el resultado de Vaughan Jones. Aquí vamos a centrarnos en conceptos (quandles) relacionados con la  segunda perspectiva, añadiendo comentarios de complejidad computacional de nudos.

Cómo fuentes, se pueden ver, cómo introducción el artículo de wikipedia  http://en.wikipedia.org/wiki/Knot_theory, un libro muy claro http://books.google.com/books?id=znCLtJKnZXQC&pg=PA23&hl=ja&source=gbs_toc_r&cad=3#v=onepage&q&f=false , y  un blog con múltiples entradas sobre teoria de nudos: http://unapologetic.wordpress.com/category/knot-theory/page/2/ (escrito por alguien que sabe mucho más que yo de este asunto, lo ha tratado de manera más extensa y además divertido).

Para todo lo relacionado con la complejidad computacional de problemas de nudos ver los siguientes papers: sobre nudos ( http://dl.acm.org/citation.cfm?id=301971 y http://arxiv.org/abs/math/9807012) , nudos  y quandles (http://www.thehcmr.org/issue1_2/knot_quandle.pdf)  y  una presentación muy reciente y clarificadora sobre complejidad de nudos y otros problemas topológicos similares (junio 2011): http://www.di.ens.fr/pub/Main/GecoalSeminaire/slides-burton.pdf.

El desarrollo del tema será cómo sigue:

–presentación del objeto de estudio (nudos en un espacio tridimensional / 3-D). A esta sección la llamaremos Nudos,

–presentación de los principales problemas que se estudian en base a estos objetos (problema de equivalencia o reconocimiento de nudos). A esta sección la llamaremos Problemas.

y

–métodos simplificados para atacar estos problemas: asociación de diagramas o proyecciones en el plano  2-D a nudos 3-D , asociación de estructuras algebraicas cómo quandles a diagramas de nudos en 2-D y asociación de matrices a quandles. A esta sección la llamaremos Métodos.

b) Breve introducción a la teoria de nudos:

Nudos:

Un nudo es un tipo de variedad tridimensional (hay otros tipos cómo links, etc…). Hay dos teorias de nudos en todo equivalentes: nudos poligonales y nudos suaves (definición matemática de nudo suavesi una inmersión de un circulo en S^1 en el espacio S^3 es la imagen de cualquier función continua del circulo unidimensional S^1 en el espacio S^3,  f: S^1->S^3  tal que ningún par de puntos distintos en el circulo coincida en el mismo punto del espacio S^3, un nudo suave es la imagen del circulo bajo una inmersión infinitamente diferenciable con un diferencial que tiende a pero diferente de cero). Se puede demostrar que hay un número infinito de nudos diferentes (diferentes en el sentido de que no se pueden transformar el uno en el otro por medio de un tipo de cambios que comentaremos a continuación). Existe el concepto de nudo primo y se puede demostrar que todo nudo se puede descomponer en nudos primos.

El interés de los matemáticos en los nudos nace del hecho de que los nudos en el espacio tridimensional representan soluciones periódicas (órbitas) de sistemas dinámicos 3-D, representados por curvas continuas, cerradas y sin autointersecciones en R^3, de las cuales los nudos son una abstracción.

En la  imagen siguiente un ejemplo de  nudo:

¿Que esto no es un nudo ?  Si no estás convencido, sigue leyendo hasta el final del punto 4.

Problemas de teoría de nudos: equivalencia o reconocimiento de nudos y desanudado:

El problema principal que se estudia en teoría de nudos es el de clasificación, equivalencia o reconocimiento.  Definición matemática de equivalencia de nudos: dos nudos suaves Ko y K1 son equivalentes si existe una isotopismo, es decir una  familia uniparámetrica de difeomorfismos suaves dependientes  de t, ft: R^3 ->R^3, con t elemento de [0,1], tal que f0 es la identidad y f1(Ko)=K1. En definitiva son equivalentes si existe una familia de transformaciones continuas que muevan de manera continua el nudo K0 hasta el nudo K1; se puede demostrar que si existe una isotopia entre cualesquiera K0 y K1, entonces existe un homemorfismo entre K0 y K1, lo cual implica que los complementos de los nudos en R^3 son homeomorfos). El problema de reconocimiento o equivalencia se puede expresar cómo sigue: dados dos nudos suaves (curvas cerradas) inmersos en un espacio 3-D,  ¿ son el mismo nudo ? Luego estudiaremos en que sentido ésto es problemático.

Entre todos los problemas de reconocimiento de nudos, el más sencillo pero todavia no resuelto de manera satisfactoria, y por ello muy estudiado, es el  problema de desanudado: dado un nudo en el espacio 3-D ¿ es equivalente al nudo trivial, al lazo ? Se desconoce de momento la complejidad computacional del problema de desanudado ver: http://en.wikipedia.org/wiki/Unknotting_problem. Se sabe que está en NP, y dentro de NP en AM intersect. co-AM, también está en NP intersect. co-NP y se piensa que finalmente se demostrará que está  en P. Cómo veremos hay un algoritmo que resuelve este problema en el peor caso en 2^(10^11)*n pasos, n=número de cruces, lo cual nos da una cota superior bastante elevada para lo que estamos acostumbrados a ver en problemas con estas propiedades de complejidad computacional.

Métodos.

Modificaciones de nudos en 3-D. Isotopias: para entender mejor el problema de equivalencia o reconocimiento de nudos debemos estudiar que cambios podemos realizar sobre nudos para modificarlos y que tengan forma diferente. Dado un nudo ¿ que tipo de modificaciones podemos realizar sobre él para modificarlo ? Una primera manera en que podemos modificarlo trasladandolo o rotandolo en el espacio 3-D. Traslaciones y rotaciones son transformaciones que ni modifican el  nudo ni modifican su apariencia de tal manera que sea dificil reconocer que son el mismo nudo. Una segundo manera de transformar  el nudo, es retorcer alguna de sus partes o deslizar unas partes sobre otras. Estas transformaciones, llamadas isotopias, no modifican el tipo de nudo, pero si pueden hacer difícil su reconocimiento. Es decir, si nos dan dos copias de un mismo nudo, uno lo dejamos cómo está y al otro le aplicamos una secuencia de isotopias (retorcimientos, deslizamientos), podemos obtener un nudo tal que al darselo a una tercera persona, no le sea fácil reconocer inmediatamente que son el mismo nudo. Hay un tercer tipo de transformaciones que podriamos realizar sobre el nudo, que implican cortar partes y pegarlas de diferente manera. Este ultimo tipo puede modificar tanto la apariencia cómo el tipo de nudo y no nos interesan (están prohibidas en topología).

Diagramas de Nudos 2-D. Proyecciones en el plano.   Atacar los problemas de nudos directamente en su forma 3-D es complicado y se han desarrollado métodos de simplificación. Uno de ellos es la proyección de nudos 3-D en el plano 2-D. Para visualizar la proyección de manera intuitiva, lo mejor es pensar en que el nudo 3-D se ha implementado físicamente cómo una cuerda cerrada flotando en el espacio que se deja caer sobre una mesa plana. Existen determinadas reglas para dibujar estas cuerdas caídas en un plano (ver libro). Al dibujarlas se obtiene un diagrama 2-D (D), del nudo 3-D (N). Un primer dato importante de recordar es que realizar un diagrama 2-D de un nudo 3-D se puede realizar en tiempo polinómico, desde el punto  de vista de complejidad computacional (se  puede pasar de una representación a otra en tiempo polinómico; ver papers sobre complejidad computacional).  Un tabla de nudos pequeños no equivalentes  proyectados en el plano: http://www.math.utoronto.ca/~drorbn/KAtlas/Knots/index.html.

Modificaciones de nudos en 2-D. Movimientos de Reidemeister:  Las isotopias de nudos (N) en el espacio 3-D se corresponden exactamente con tres tipos de movimientos de diagramas (D) en el plano 2-D, los llamados movimientos de Reidemeister (teorema de Reidemeister (1932): dos diagramas de nudos o links en el plano pueden ser continuamente deformados el uno en el otro si y solo si el uno puede obtenerse del otro por una secuencia finita de movimientos de Reidemeister). Para más detalle sobre estos movimientos ver    http://en.wikipedia.org/wiki/Reidemeister_move.

Los movimientos son tres para diagramas de nudos no orientados y ¿ocho? para diagramas orientados. Los 3 movimientos de Reidemeister figuran a continuación (origen imagen: Mathworld):

Es importante ver que los movimientos de Reimeister tienen que ver con la representación de nudos por diagramas.  ¿ Cómo es esto ?

Supongamos que al caer la cuerda en el plano, 3 tramos se cruzan en un punto. Este evento está prohibido por las reglas de dibujo de diagramas. Debemos por lo tanto separar un poco uno de los tramos, por ejemplo el de abajo. Esto se puede hacer de dos maneras equivalentes, separarandolo hacia la izquierda o hacia la derecha. Esto es lo que  indica el tercer movimiento de Reidemeister: independientemente de que separemos el tramo hacia la izquierda o a la derecha obtenemos diagramas equivalentes. Son dos maneras equivalentes de simplificar un punto del plano en el que coinciden tres o más tramos.

El segundo movimiento realiza algo parecido  para puntos donde no está claro si dos tramos se cruzan o simplemente se rozan. Hay dos maneras de eliminar esta ambigüedad, separándolos o cruzándolos.

Finalmente el primer movimiento hace lo mismo para tramos de la cuerda que han generado cúspides ambiguas.

Cualquier elección en cada punto ambiguo nos da diagramas diferentes pero equivalentes. Esto es importante a la hora de definir clases de equivalencia de diagramas e invariantes.

Clases de equivalencia de diagramas / estados de nudos 2-D:

Así,  si a un diagrama D de un nudo N1 dado le llamamos N1D1, al aplicarle secuencias de movimientos de Reidemeister obtenemos otros diagramas (que podemos llamar estados) del mismo nudo en el plano 2-D, N1D2, N1D3…

En base a esto, se pueden definir clases de equivalencia de diagramas o estados: todos los diagramas/estados que se pueden obtener unos de otros mediante movimientos de Reidemeister N1Dx pertenecen a una misma clase de equivalencia.

Por ejemplo, en la imagen siguiente dos diagramas/estados diferentes, a la izquierda N1D1 y a la derecha N1D2, de la clase de equivalencia de nudos llamada nudo trivial o lazo. Podemos obtener N1D2 de N1D1 aplicando 2 retorcimientos o movimientos 1 de Reidmeister a partes diferentes:

  N1D1                       N1D2

Funciones sobre nudos y crossing number: Por otra parte, una de las cosas que podemos hacer una vez tenemos un diagrama, por ejemplo N1D1, es contar el número de cruces, cero en este caso y 2 en el caso N1D2. Es decir a cada estado de una clase de equivalencia de nudos en 2-D, se le puede asignar un número. Nos interesa también asignar un número a cada clase de equivalencia. De todos los numeros asignados a los estados de una misma clase de equivalencia, escogemos cómo representante de cada clase a los diagramas/estados que tengan el mínimo número de cruces. A este número se le llama crossing number (o número de cruce) de la clase de equivalencia de estados de nudos.  http://en.wikipedia.org/wiki/Crossing_number_(knot_theory).

Invariantes: El crossing number es uno de los  invariantes de nudos posibles. En general un invariante de nudo es una cantidad (que se puede obtener contando, coloreando, con polinomios…) que no varia para nudos equivalentes (la equivalencia se puede definir en base a isotopias (movimientos de reidemeister en el caso 2-D), cómo hemos hecho, o en base a otro tipo de transformaciones topológicas más o menos restrictivas cómo homotopias u homeomorfismos. Permiten decidir si dos nudos no pertenecen a la misma clase de equivalencia, pero no siempre si pertenecen a la misma: hay nudos no equivalentes con el mismo crossing number cómo se puede ver en las tablas de nudos. Existen muchos otros invariantes de nudos.

Problema de equivalencia de nudos en 2-D:

El problema de equivalencia de nudos en 2-D se puede expresar cómo sigue: dados 2 diagramas/estados en 2-D, ¿ pertenecen a la  misma clase de equivalencia ?. El problema de desanudado se puede expresar cómo sigue: dado un diagrama/estado en 2-D, ¿ pertenece este estado a la clase de equivalencia del nudo trivial ?

Resumiendo, hasta aquí hemos definido el objeto de estudio, nudos en 3-D, los problemas que se estudian (reconocimiento o equivalencia) y hemos presentado una manera de representar nudos 3-D por diagramas en el plano 2-D. A cada tipo diferente de nudos en 3-D le corresponde una clase de equivalencia de diagramas/estados de nudos en 2-D. A continuación vamos a ver cómo asignar a cada clase de equivalencia de diagramas/estados de nudos en 2-D una estructura algebraica.

c) Representación de diagramas/estados por quandles:

Quandles abstractos y quandles cómo estructura de datos para representar nudos:

Ya se ha definido en un punto anterior que es un quandle abstracto. Ahora vamos a definir un quandle  para diagramas de nudos. Pensemos en un  quandle cómo en  una estructura de datos que permite representar simbólicamente diagramas/estados mínimos de nudos. Esto se realiza en una serie de pasos. Señalemos aquí que si bien los quandles sirven para algebrizar nudos de cuerdas (redondas) existe una generalización de los quandles (los racks) para describir algebraicamente nudos de cintas.

Primer paso. Conjunto de generadores:

El primer paso es etiquetar el diagrama, es decir asignar simbolos (por ejemplo letras del alfabeto) a los arcos o tramos del diagrama (un arco/tramo es cualquier linea continua entre cruces). Sabemos que para todo diagrama el numero de cruces es finito (idem para arcos/tramos) y por lo tanto nos es suficiente con un numero finito de simbolos. Tenemos por lo tanto un alfabeto A con un numero n de simbolos y asignamos un simbolo a cada tramo. A cada uno de estos simbolos se les llama generadores (del quandle). Tenemos por  lo tanto un primer conjunto finito de generadores A.

Segundo paso. Conjunto de relaciones:

Obviamente el etiquetado de arcos/tramos no es suficiente para describir un diagrama. Debemos explicitar también las relaciones de cruzamiento entre arcos/tramos. La relación de cruzamiento es una relación ternaria (recordemos aquí que  a las relaciones ternarias sujetas a determinadas restricciones se les llama operaciones). Existe una serie de convenciones para realizar esto de manera adecuada (que por ejemplo tienen en cuenta la orientación). Al  final obtenemos un conjunto de descripciones de relaciones ternarias del tipo: “el tramo 1 es cortado (cruzado por encima)  por el tramo 2 al ser recorrido en un sentido, y continuado por el tramo 3”, que para simplificar podemos expresar simbolicamente como: 1*2=3. A este conjunto finito de relaciones lo llamamos R.

Definición de Quandle de un diagrama de un nudo:

Un quandle algebraico de un diagrama D de un nudo N (simbolicamente Q(N,D)), se define cómo el conjunto finito de arcos/tramos etiquetados/generadores y el conjunto de relaciones ternarias entre tramos etiquetados/generadores que se obtiene al describir el diagrama del nudo. En breve, un quandle con generadores A sujetos a las relaciones ternarias R.

Comparese los conceptos  de grafo o dígrafo (conjunto de vértices y relaciones binarias entre ellos), grupo (conjunto de elementos /generadores y relaciones ternarias sometidas a unos axiomas) y quandle (parecida a la de grupo pero con axiomas menos restrictivos). Ni un grafo, ni un grupo (sin enriquecimiento) son suficientes para representar nudos.

No es difícil ver que dado un diagrama de un nudo y su quandle son equivalentes desde el punto de vista de la complejidad computacional: obtener el quandle del diagrama y el diagrama del quandle se puede realizar en un tiempo polinómico.  Esto extiende el anterior resultado de que pasar del nudo al diagrama es computacionalmente sencillo (polinómico). Por lo tanto N->D->Q es fácil.

Pero no todo conjunto de relaciones ternarias cumple necesariamente con los axiomas de un quandle abstracto. Que esto sea así  es algo que se debe demostrar.

¿ Cómo sabemos que para todo diagrama de nudos, el conjunto  R de sus quandle asociado  cumple con los axiomas de quandle abstractos ?  

Lo sabemos por los movimientos de Reidemeister.

Demostremos que  el  quandle asociado a un nudo Q (N,D) es independiente del diagrama D elegido (y por lo tanto es un invariante del nudo). Y por el camino contestamos a la pregunta. Para una demostración completa ver teorema 4 del paper http://www.thehcmr.org/issue1_2/knot_quandle.pdf,  ya citado en los preliminares.

Supongamos que tenemos dos estados/diagramas diferentes del mismo nudo N2D1 y N2D2. Están conectados por una secuencia finita de movimientos de Reidmeister (ya hemos visto que todo diagrama /estado de un mismo nudo es Reidmeister equivalente, independientemente de las elecciones que hayamos realizado ante los puntos ambiguos a la hora de dibujarlo, e independientemente de los movimientos de Reidemeister que efectuemos sobre el una vez dibujado, para obtener otro diagrama equivalente). Es decir, a cada tipo de nudo 3-D diferente le corresponde una clase de equivalencia de diagramas/estados. O de otra manera, cada clase de equivalencia es un Digrafo similar a los de Cayley finito, que se obtiene al aplicar secuencias finitas de movimientos de Riedemeister a un estado/diagrama cualquiera de la clase).

Obtengamos Q(N2, D1), el quandle correspondiente diagrama D1 (que es uno cualquiera), realicemos el movimiento 1 de Riedemester retorciendolo y obtengamos el quandle correspondiente al nuevo diagrama Dn.  Veremos que los dos son isomorfos. La clave aquí es ver que pueden recuperar la isomorfía  aun teniendo “provisionalmente” conjuntos de arcos/generadores A de cardinalidad diferente y conjuntos de relaciones R de cardinalidad diferentes. Q(N2,D1) tendrá el arco a entre sus generadores, al que corresponden 2 arcos a1 y a2 en Q(N2,Dn), obtenidos al retorcer a; Q(N2,D1) tendrá un conjunto  de relaciones y Q(N2,Dn) elmismo conjunto (sustituyendo de manera apropiada a por a1 y a2), mas una relación adicional a1*a1=a2, que contradice uno de los axiomas de los Quandles abstractos x*x=x, salvo que a1=a2. Como queremos que se cumplan los axiomas de los quandles abstractos optamos por a1=a2, lo que nos asegura que Q1 y Qn son isomorfos, pese a la cardinalidad (si son el mismo no se deben contar dos veces). Apliquemos ahora a Q1 o a Qn otro de los movimientos de Reidemeister, por ejemplo el 2. Obtendremos dos quandles de nuevo aparentemente diferentes, pero que gracias al axioma de 2 de Quandles abstractos, se garantiza que son isomorfos. Lo mismo con el movimiento 3 y el axioma 3.

Por lo tanto a cada modificación del Quandle por un movimiento de Reidemeister que altera el isomorfismo, le corresponde un axioma de los Quandles abstractos que compensa esta modificación manteniendo el isomorfismo. Podemos concluir primero que todos los Quandles correspondientes a Diagramas son invariantes ante movimientos de Reidmeister, y por lo tanto isomorfos. Por otra parte esta posibilidad de aplicar  los axiomas de Quandles abstractos nos garantiza que los quandles de nudos cumplen con estos.

En definitiva, al igual que hemos asociado un invariante, el número de cruce o  crossing number a la clase de equivalencia de diagramas estados de un nudo dado, podemos asociar un nuevo invariante, un Quandle a la misma clase de equivalencia. El crossing number cambia al cambiar de diagrama por movimientos de Reidmeister, y por lo tanto debemos seleccionar un representante para cada clase, el de mínimo número de cruces (esto supone un problema de minimización que hace del crossing number un invariante difícil de computar), todos los Quandles de diferentes diagramas son isomorfos. 

El quandle cómo invariante:

El  quandle es un invariante de nudos completo salvo orientación (no distingue dos nudos iguales pero orientados de diferente manera). A partir del quandle  se pueden construir otros invariantes conocidos pero menos completos (grupo del nudo, n-coloreado, polinomios de Alexander y Conway, etc…).

¿ Cual es entonces el problema de los Quandles cómo invariante a la hora de utilizarlos para el problema de equivalencia ?  El primer problema de un quandle es el matiz “salvo orientación”: dos nudos iguales en todo salvo en la orientación  tienen exactamente el mismo quandle, salvo isomorfia de quandles. Esto no debe sorprender a los que hayan comprendido cómo se construye un quandle dado un nudo. ¿ No habrá una estructura algebraica más general que los quandles que permita diferenciar la orientación ? 

El segundo problema tiene que ver con la complejidad computacional de computar un isomorfismo de quandles y lo desarrollamos en el siguiente punto.

d) Representación de Quandles mediante matrices y complejidad

El isomorfismo de quandles no se puede computar de manera eficiente (problema de complejidad computacional). Supongamos que nos dan dos diagramas y nos plantean el problema de equivalencia. Según el método de quandles, construimos el quandle asociado a cada uno de ellos y averiguamos si son isomorfos o no. Si los quandles son isomorfos, entonces los diagramas representan al mismo nudo.

Los quandles se pueden representar (mediante transformación de coste computacional cómo mucho polinómico en peor caso) por matrices de enteros. Un paper muy interesante sobre esto: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.hha/1139839513.

Un ejemplo de una matriz del quandle del diagrama de un nudo:

¿ Era la matriz que enseñé al principio un nudo o no ?

Teorema: dos quandles son equivalentes si y solo si son p-equivalentes por una permutación p elemento de Sn, el grupo simétrico de n elementos (los mismos que tramos/arcos/generadores del quandle). La definición de p-equivalencia se puede ver en el paper citado.

El problema de isomorfismo de quandles es equivalente al problema de isomorfismo de un tipo de matrices enteras. El problema más general de isomorfismo de matrices enteras es GI-completo, es decir de la misma complejidad que el problema para matrices binarias (digrafos): http://bioinformatics.oxfordjournals.org/content/18/3/465.full.pdf.

Por supuesto es posible que casos especiales cómo el de matrices de  quandles o grupos tengan una complejidad diferente del caso general. En un post anterior hemos hablado sobre la complejidad de isomorfismo de grupos dados por su tabla de Cayley (de multiplicación), GROUP-ISO, que es el caso que nos interesa, y en el blog de Lipton-Regan hay un reciente post sobre este mismo problema: http://rjlipton.wordpress.com/2011/10/08/an-annoying-open-problem/ .

Sobre GROUP-ISO, no se sabe si está en P o es GI-completo y  la mejor cota superior es N^(log n +O(1)). Recordemos que sobre el problema de desanudado (caso especial del problema de quandle matrix isomorphism), no se sabe tampoco si está en P o es GI-completo, pero sabemos que está en NP intersect co-NP, y en AM intersect co-AM y se espera que se acabe demostrando que está en P.

Para la cota superior del problema de desanudado existe el siguiente teorema:

Theorem 1.1.

There is a positive constant c1, such that for each n >=1 , any unknotted knot diagram D with n crossings can be transformed to the trivial knot diagram using at most 2^c1n Reidemeister moves. We obtain the explicit value of 10^11 for c1.

Tras ver todos estos datos, me surgen dos interrogantes. Primera, para el problema de isomorfismo de quandles, puede ser interesante ver la estructura de su grupo de automorfismos. Segunda, sabemos que para grupos hay maneras más sucintas de representarlos que la tabla de Cayley: un conjunto finito de generadores nos permiten reconstruir todo el grupo. ¿ Podemos igualmente representar quandles de una manera más sucinta ? Estos dos interrogantes nos llevan al punto siguiente

e) Quandles: generación y grupos de automorfismos.

Quandles y sus grupos de automorfismos.

Para estudiar el problema de isomorfismo de cualquier estructura, por ejemplo quandles, es interesante conocer la estructura de su grupo de automorfismos.

Recordemos que según el primer teorema de isomorfismos del algebra universal (ver http://en.wikipedia.org/wiki/Isomorphism_theorem) el conjunto de automorfismos de una estructura algebraica siempre forma un grupo.

Se conoce el grupo de automorfismos de algunas clase interesantes de quandles finitos:  http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2456v2.pdf, http://arxiv.org/PS_cache/arxiv/pdf/1012/1012.5291v1.pdf   y     sobre los quandles de Alexander:  http://u.cs.biu.ac.il/~tahl/quandle.pdfUn extracto  de este último paper:

“1. All finite connected quandles with a prime number of elements or with a square of a prime number of elements is isomorphic to an Alexander quandle.  

2. Every Alexander quandle of prime order can be generated by a pair of its elements”.

Es una clase bastante general y son bigenerados. Interesante, aunque sobre generación todavia no he encontrado nada más concreto.

f) Quandles y dígrafos:

Si queremos pensar en un nudo y sus modificaciones (isotopias de ambiente, movimientos de Reidemeister…) completamente en terminos de dígrafos podemos hacerlo de la siguiente manera.

Digrafo del quandle / estado del nudo:

En el punto anterior hemos visto que  al igual que los grupos, los quandles admiten una representación sucinta por medio de generadores (el objetivo principal de este post, que era representar estos generadores por medio de transformaciones, no está conseguido).

Así podemos construir un Dígrafo de Quandles similar a los Digrafos de Cayley para grupos dónde los vértices son los elementos del magma y los arcos representan la acción de los generadores sobre estos vértices para obtener otro elemento. Esto es una representación del estado del nudo, alternativa y al mismo nivel (igual de sucinta) que la representación por matrices.

Digrafo de la dinámica del nudo:

Este es bastante más complicado de explicar (no de entender) y es un digrafo, diferente del anterior, que representa la acción de los movimientos de Reidemeister, de los axiomas de quandle y de las permutaciones de matrices de quandles sobre el nudo. En lo que sigue voy a explicar todo en base matrices de quandles y no en base a Digrafos de Cayley de Quandles, ya que de momento lo tengo más claro de esta primera manera.

Los vértices de este segundo dígrafo pueden ser de dos tipos: vértices etiquetados con matrices de quandles (o digrafos de cayley del quandle), que representan el nudo en estado “no excitado”, y vértices etiquetados con matrices que representan al nudo en estado excitado, tras haberle aplicado algún movimiento de Reidemeister. Los arcos pueden ser de tres tipos: movimientos de Reidemeister, aplicaciones de axiomas o permutaciones de matrices.

Partiendo de una Matriz nxn en estado no excitado, podemos bien aplicarle — cada uno de los axiomas de los quandles y no cambiará nada (aplicados a estas, son loops);

–bien aplicarle un movimiento de Reidemeister (cada movimiento viene representado por un arco del digrafo), por ejemplo el movimiento número 1, a un tramo, y pasamos de la matriz inicial nxn no excitada a una matriz (n+1)x(n+1) excitada (por  no cumplir con los axiomas de Quandle).

Quede claro que aplicando el mismo movimiento u otro a cualquier otro tramo hubíesemos obtenido otra matriz excitada del mismo o mayor tamaño (numero de arcos de salida de cada nodo = numero de tramos x numero de movimientos de Reidemeister).

A esta nueva matriz podemos bien aplicarle el axioma de quandle correspondiente y obtener otra matriz no excitada de nxn, no exactamente la misma que la inicial, sino una permutación de esta (pero una permutación tal que si nos diesen las dos matrices encontraríamos fácilmente la permutación), podemos por lo tanto trazar un arco permutación entre las dos matrices no excitadas; bien aplicarle otro movimiento de Reidmester (¿puede ser el mismo sobre el mismo tramo ? Una iteración de este tipo podría llevar a infinitos o a la matriz inicial) diferente, en cuyo caso la excitamos o alteramos más (obtendriamos una matriz (n+y)x(n+y).

Este segundo digrafo es finito y nos permite visualizar de alguna manera la estructura algebraica que generan los movimientos de Reidmeister (¿ que nombre tiene esta estructura: espacio de….?) todavia no tengo claro sus propiedades ( ¿ regular ?). Y entiendo que contiene a un digrafo de Cayley (el de las permutaciones de matrices).

g) Resumen gráfico,  incluyendo complejidad computacional.

S3-SD DES1<—¿?——————————————————->DES2

          ¿?                                                                                                                      ¿?

G3-D: N1<—-ambient isotopies /¿P o  GI-completo?——>N2<—>N3….

         Pol                                                                                                                   Pol

G2-D: D1<—Reidemeister moves/¿P o GI-completo?—–>D2<—>D4….

          Pol                                                                                                                   Pol

SEA: Q1<—axioms aplications /¿P o GI-completo?——–>Q2<—>Q3….

          Pol                                                                                                                 Pol

STM: M1<—quandle matrix permutation/¿P o GI-completo?—>M2<—>M3…

          ¿?                                                                                                                     ¿?

SGen: G1<—¿?———————————————————–>G?<—>G

Explicación del gráfico anterior:

Flechas horizontales: representan el hecho de que en un nivel geometrico/topológico (G) de 3-D se puede pasar de un nudo N1 a otro equivalente N2 y viceversa mediante isotopias de ambiente; en un nivel geometrico /topológico (G) de 2-D se puede pasar de un diagrama de nudo D1 a  otro equivalente y viceversa D2 mediante movimientos de Reidemeister y en un nivel simbólico (SEA) de estructuras algebraicas, de un quandle Q1 a otro isomorfo y viceversa Q2 aplicando los axiomas de quandles y finalmente, en otro nivel simbólico de teoría de matrices (STM) de una matriz M1 que representa al quandle a otra isomorfa M2 computando una permutación de una matriz en otra.

Al aplicar de nuevo estas transformaciones se pueden obtener nuevos N, D, Q M, pero no infinitos. Al lado figura la supuesta complejidad computacional del problema de isomorfismo para cada una de estas estructuras.

He añadido dos niveles más, que iré completando cuando confirme la  información que falta:

–por arriba otro nivel simbólico, el de sistemas dinámicos en 3-d (SD), representado por  una ecuación diferencial (Differential Equation) y sus soluciones. Se pasa de una solución a otra  (¿equivalente?, ya que no cambia la topología del sistema dinámico) por medio de ¿?. 

–por abajo el de representación sucinta de Quandles por generadores. 

Quizás resulte que estos dos nuevos niveles sean el  mismo y se puedan fundir en uno cerrando el gráfico en círculo:-).   

En el gráfico faltan las flechas de verticales (pol significa polinómico y ¿? de complejidad desconocida):

–cómo las transformaciones verticales (pasar del nudo al diagrama, del diagrama al quandle y del quandle a la matriz y viceversa) son de complejidad polinómica, la complejidad de las transformaciones horizontales debe de ser equivalente o superior y cómo mucho GI-complete (es decir, cómo mucho tan difíciles cómo el problema de isomorfismo de grafos (lo cual se indica en el gráfico cómo. <GI-complete).

–la complejidad de las transformaciones de los objetos de los dos niveles añadidos despúes (el primero y el último) a objetos inmediatamente adyacentes  me es desconocida.

h) No hemos hablado de los grupos de trenzas (Braid groups), una generalización de los grupos de permutaciones. Quizás desarrollemos el tema en otra ocasión. Sólo adelantar que todo nudo se puede obtener de trenzas y que el equivalente a lo movimientos de Reidemeister en trenzas son los movimientos de Markov.

 5. Modelos generales de magmas y Dígrafos de Magmas:

En el punto anterior ya hemos mostrado un primer ejemplo de cómo se pueden representar determinados problemas matemáticos (de teoría topológica de nudos) con magmas no asociativos, llamados quandles, y cómo se puede representar estos quandles por Dígrafos similares a los de Cayley.

Así cómo los grupos de simetría asociados a figuras geométricas no agotan todos los grupos posibles los magmas asociados a nudos (llamados quandles) tampoco agotan todos los magmas no asociativos posibles. Por eso, nos interesa encontrar el modelo más general posible para magmas, el equivalente a Sn para grupos de permutaciones o a Tn para semigrupo de transformaciones.

Una  pregunta similar en mathoverflow: http://mathoverflow.net/questions/21152/do-non-associative-objects-have-a-natural-notion-of-representation, cuyas respuestas no me aclaran mucho, aunque citan  este resultado de 1996: http://www.springerlink.com/content/33167ux0p52622m6/ (al que no tengo acceso). Es una generalización a magmas del teorema Krohn-Rhodes de descomposición estructural de semigrupos.

Finalizamos el post dejando abierta ésta cuestión.

P.s. Este post se terminó el 18 de octubre. Posiblemente sea el post más largo y denso de la corta historia del blogging. Si has llegado hasta aquí, te mereces un premio. Escoge el bombon musical que más te guste:

http://www.youtube.com/watch?v=jKgADiSNvnQ&feature=related

http://www.youtube.com/watch?v=vL3raxfj1oo&feature=list_related&playnext=1&list=PLE5F5EF7CCEDF746F

http://www.youtube.com/watch?v=O2xNTzlFSk0

http://www.youtube.com/watch?v=BR4xfQ28N00

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: