PSL(2,7).

psl(2,7) (2)

El digrafo de Cayley que aparece en la imagen anterior, de PSL(2,7) isomorfo a GL (3,2) es muy interesante para  mi. En la  imagen aparece con generadores de orden 2 y 3.

Me resulta interesante ya que según nos comentan en la fuente de la que he extraído la imagenthe second smallest non-Abelian simple group is PSL(2,7) (also known as A1(7)) or GL(3,2) (also known as A2(2)) these being isomorphic. It has 168 elements. Its Cayley graph cannot be drawn without the arcs crossing on a sphere, nor on a torus, nor on a genus-2 surface (like a torus but with two holes instead of one). It can be drawn on a surface of genus 3 (three holes)

He intentado conseguir en la web los generadores (con los ordenes indicados) en forma de permutación pero sin éxito. Sí he encontrado generadores de otros ordenes y entiendo que el comentario topológico se aplica a cualquier tipo de generadores de este grupo.

En la imagen siguiente se aprecia que el IAS es de orden 7 y la circunferencia tiene 4 IASES (si no me he equivocado al dibujarla). Es entangled solo por ser uno de los dos generadores de orden 2 y diría (esto todavía no lo tengo 100% claro, tendría que dibujar el entorno de la identidad) que es smooth.

psl(2,7) entorno identidad

 Este gráfico me aclara una duda. ¡¡ Muy interesante !!.

P.s. En 2010, motivados por consideraciones de teoria de complejidad computacional que ya no nos motivan nada (en realidad, por causas evidentes a cualquiera que siga este blog, casi nada relacionado con la solicitud de patente nos motiva nada ya), ya hicimos un par de entradas en la que nos interesábamos por los digrafos del tipo PSL(2, 7) y similares.

Hablamos en ellas de un par de generadores (de orden 3 los dos) que generan  PSL(2,7) y que tenían recorridos hamiltonianos al menos en uno de los vértices finales posibles. Dábamos el RH de manera explícita. El programa había tardado unos 2-3 minutos lo cual indica que el caso, que comentábamos era entangled pero no cycle entangled no era del todo sencillo.

También comentábamos lo siguiente: En la tesis de Effler aclaran …que para 168 (PSL(2,7)) dicen que hay 91 digrafos no isomorfos, 35 de grado 7 y 56 de grado 8. No hay de grado 9 que generen digrafos de cayley de este grupo. En el Atlas, en la lista de posibles generadores aparecen los grados 7 y 8 y luego 14, 21, 24, 28, 42,56,84 y 168. 

Actualización día siguiente.

Por otra parte, y esto lo añado ahora, hay grupos de orden 168 que no son PSL(2,7) o sus grupos isomorfos, con lo cual algunos de los pares de generadores no isomorfos señalados en la tesis de Effler lo serán de estos otros grupos.

En este artículo nos aclaran la situación concreta de PSL(2,7): We first checked all pairs f {a,k} incl. in PSL2(7) where a ^2 = 1 and k is of order >=3. Up to conjugacy there are exactly 21 such pairs to be considered and only 10 of them generate the whole group. Among these there are three pairs {a,k} and {a,k^-1} each pair giving the same Cayley graph. The representatives a and k for the remaining 7 graphs are…y nos facilitan una lista completa de los generadores en forma de matrices. Entre estos 7 casos están los generadores que nos interesan ahora mismo. Y ojo no agotan todos los pares de generadores posibles de este grupo: a estos autores les interesan los grafos cúbicos de PSL(2,7).

¿ Podemos pasar de los generadores en forma matricial a generadores en forma de permutaciones ?.

Obviamente se trata de pasar de una matriz a otra (esta última en forma de permutación). Pero es posible que no se mantenga el orden de la matriz, es decir que la que expresa la permutación sea de orden mayor. En esta entrada de wikipedia nos explican como pasar de la permutación a la matriz (de mismo orden). No es lo que nos interesa.

Este artículo nos permite aterrizar este tema (hay literatura al respecto: se ha investigado o investiga, se puede hacer, seguramente no es sencillo…):

Construction of Large Permutations Representations for Matrix Groups.  Michael Weller.

Y otro similar, aunque anterior: Constructing Permutation Representations for Large Matrix Groups.

En este nos describen un método: A matrix representation will yield a permutation representation by calculating the action of the group on an orbit of vectors (or 1-dimensional subspaces, or k-dimensional subspaces, or any other convenient objects).

Y en un enfoque más práctico, Magma computa esta función:

 

Permutation Representations of Linear Groups

Each of the functions in this family returns two values:

  • A permutation group G corresponding to the action of a designated matrix group M on a vector space V; and

De momento, de nuevo,  como en la ocasión anterior, no terminamos de encontrar los generadores que nos interesan para grupos de este orden…Si los tuviese pondría a trabajar el algoritmo (que he programado) para encontrar los recorridos hamiltonianos correspondientes o determinar que no existen. Iría bastant rápido pues es un tipo de digrafo muy restringido y en estos casos el algoritmo resuelve muy rápidamente el problema de decisión. Esto me obliga a dibujar el entorno de la identidad manualmente para determinar si lo tiene o no.

Fin actualización.

Actualización un par días después.

Un artículo dónde dan bastantes generadores de PSL de varios órdenes.

On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group

Paul E. Schupp Departement of Mathematics, University of Illinois, Urbana, IL 61801, USA

Abstract It is a fairly long standing conjecture that if G is any finite group with IG/ > 2 and if X is any set of generators of G then the Cayley graph T(G : X) should have a Hamiltonian cycle. We present experimental results found by computer calculation that support the conjecture. It turns out that in the case where G is a finite quotient of the modular group the Hamiltonian cycles possess remarkable structural properties. 

También comentar que finalmente estoy aplicando el algoritmo manualmente y si no me he equivocado (creo que no, ya que lo he repetido un par de veces, aunque es posible ya que es el final del día y tengo bastante oxidada la rutina de aplicar el algoritmo manualmente; léase lo que sigue con precaución pues es posible que mañana lo cambie….) este caso no puede tener recorridos hamiltonianos (ni ciclos, por ser de tipo Rankin, ni caminos) . Sólo con identificar un vértice como vértice inicial, se genera necesariamente un ciclo que no contiene a todos los vértices. En la imagen siguiente explico gráficamente el tema:

psl(2,7) (5) digrafo prueba 1

Como se ve al marcar el vértice inicial VI se genera el ciclo que empezaría por t y acabaría por v (ojo, ni t ni v son vértices, pero sirva para que el lector identifique el problema). El  proceso se inicia de la siguiente manera:

–el vértice inicial no puede tener arcos que lleven a el. Se tachan los dos.

–lo anterior fuerza a que el arco que pasa por a (que tampoco es un vértice) saliendo del semicírculo dónde se encuentra a sea marcado.

–si este arco es marcado, el de sentido contrario no puede serlo con lo cual se tiene que marcar el otro que apunta a su mismo vértice.

–al final de esta primera fase, como se ve en la imagen siguiente quedan marcados los arcos que van de a hasta h lo cual provoca que los primeros arcos del ciclo que hemos señalado (el que pasa por t y v).

Y el marcar estos arcos lleva al final a que todo este ciclo quede marcado.  Esto pasa sólo por marcar el vértice inicial, sin elegir ninguna opción adicional, sin elegir ni siquiera el vértice final.

Hay casos que son así, ya los tenía detectados y creo que incluso puse algún ejemplo en la descripción de la patente. Con la primera decisión se desencadena un proceso que genera la “contradicción”. Obviamente el elegir otro vértice inicial no cambiaría nada.

Un ejemplo es el de generadores 234576 y 365724 (identidad 234567) que genera un dígrafo de 24 vértices. Los generadores son de orden 2 y 3 como el que estudiamos. Y sus rasgos estructurales, entangled (de hecho muy entangled, pero no cycle entangled, estos casos no pueden serlo).

Y otro ejemplo 2-3 generado es el de generadores 1234675 y 2156347 (identidad 1234567) que genera S5 (según las anotiaciones que hice, “sin opción”. No es necesario que sea 2-3 generado para que esto suceda y puedo dar varios casos en los que sucede. En general uno de los dos generadores es de orden 2.

¿ Quiere esto decir que los casos (2,3)-generados no tienen en general recorridos hamiltonianos ?. No, por ejemplo el caso de generadores 1243 y 2314 (identidad 1234) sí tiene (camino(s)), como el lector podrá comprobar fácilmente. Relevante por otra parte una proposición atribuida a Milnor:

Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group is generated by two elements and , such that . If , then the Cayley digraph does not have a hamiltonian path.

Si uno va a la referencia parecen afirmar que la proposición de Milnor se refiere a grupos solubles (y los de orden 168 no lo son), pero realmente no me queda claro. De cualquier manera estos casos (2,3)-generados son claramente muy interesantes para el problema que nos ocupa (ojo digrafos).

Queda por confirmar que lo que hemos dicho sucede en el caso que estudiamos y determinar sus rasgos estructurales, cosa que tendré que realizar sin los generadores (es posible, aunque muy trabajoso). Mañana más….

Fin actualización.

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: