Sobre el comportamiento asíntotico de la distribución de casos por grados de Sn.

Seguimos copiando (con la función copy a post de WordPress) entradas que contienen investigaciones relacionadas con la patente. En este caso vamos a publicar una serie de tres entradas que muestran el comportamiento asíntotico de la distribución de casos por grado de los pares de permutaciones que generan Sn. La entrada original se publicó el 15/12/2010 y se ha editado mínimamente en su republicación. 

1. Ya veo con claridad cuales son los parámetros importantes de la distribución de casos por grados de la que hablábamos en un post anterior: el grado n en un extremo del rango, el grado maxdegreeSn (es decir el máximo grado que genera Sn, para el n dado) en el otro extremo, y un grado que está entre los dos extremos y que podemos llamar límite de dificultad. Una posible estimación del valor de este parámetro aparece en una actualización que figura al final de éste post.

A la izquierda del límite de dificultad los casos fáciles; a la derecha los potencialemente difíciles (aunque posiblemente el cambio sea gradual). Entonces a medida que n crece unidad a unidad tenemos un secuencia de distribuciones (para cada n, las distribuciones de cada n se van superponiendo) y queremos saber la forma y parámetros de la distribución límite de la secuencia (http://en.wikipedia.org/wiki/Asymptotic_distribution).

2. Sabemos que a medida que n crece el rango (la diferencia entre n y maxdegreeSn) se va haciendo más grande. Las dos preguntas clave son:

–¿ cómo se distribuyen los casos entre las dos zonas a medida que n tiende a infinito ?. Aunque a medida que n crece la “fracción de Dixon” que no genera Sn en los grados a la derecha del grado límite de dificultad tiende a cero, una suma de fracciones muy pequeñas de un conjunto muy grande todavia puede dominar a n!, n+1!..hasta el grado n+m.

–y sobre todo cómo se comporta el limite de dificultad: a medida que n crece ¿ se va acercando más n, a maxdgSn o se queda en un punto intermedio ?

Algunos datos que pueden ayudar a responder estos interrogantes:

–a medida que n crece la fracción de pares de un grado n que no genera el grupo simetrico de su grado n tiende a cero (Dixon).

–para todo grado entre n y maxdgSn los pares de casos que están dentro de esta fracción se distribuyen entre varios de orden inferior generados por grados inferiores. Es decir para un p entre n y maxdegreeSn, los pares que no generan Sp, generarán digrafos de Sn, Sn+1….hasta Sp.

–muchos de los casos que están dentro de esta fracción y que se distribuyen entre diversos grados serán isomorfos a casos de grado inferior que generan el grupos del mismo orden.

Estos tres datos son los que me llevaron a concluir en la solicitud de patente que asíntoticamente todos los pares que generan un digrafo no isomorfo de Sn, de cualquier grado, tenderán a ser fáciles es decir a estar a la izquierda derecha del limite de dificultad en la distribución límite.

Por supuesto hemos analizado este tema con el ejmplo de Sn pero es aplicable también a otras familias infinitas de grupos cómo el grupo alternado An. Ahora mismo no tengo claro si para PSL(t,2) son importantes los mismos parámetros.

Actualización 16/12/2010:

1. El grado límite de dificultad.

Aquí desarrollo una posible expresión cuantitativa del límite de dificultad.

En un post anterior hablábamos de los casos entrelazados o entangled más libres posibles (excluyendo aquellos que tengan generadores que sean involuciones). Llamemosles free-entangled (según una descripción algebraíca serían aquellos en los que la única relación entre el IAS y el DAS es xy^(-1)x=x^(-1)yx^(-1)).

Estos casos son los que permiten un mayor tamaño dado un grado con la restricción de que el caso sea entangled. ¿ Cuan grandes pueden ser estos caso free-entangled para un grado dado ? Una aproximación por debajo (cota inferior) a su tamaño podría ser el ciclo de un generador de orden máximo para el grado dado (es decir la función de Landau) x el orden del IAS máximo correspondiente a ese mismo grado (de nuevo la función de Landau).

Entonces el grado que buscamos para todo n es aquel grado n+m que  iguale el tamaño máximo posible de los casos  free-entangled a n!. Es decir max-size-free-entangled(n+m)=n!. Hay que encontrar la expresión análitica de esta igualdad y despejar m. Entonces podemos expresarlo en función de n, calcularlo para todo n y ver el comportamiento asíntotico del límite de dificultad.

2. Un ejemplo.

El siguiente digrafo ilustra lo que estamos diciendo. Es la representación manual sobre papel de un Digrafo de Cayley de S5 (de 120 vertices) free-entangled.

En rojo el IAS. En verde el DAS. La identidad es 23456 y ambos IAS y DAS están “entangled” o entrelazados en el vértice 23465 (y en la identidad obviamente). Aconsejo al lector que utilice una buena lupa…

Cómo se ve la circunferencia es el generador de linea entrecortada que parte de la identidad.

Nota. Circunferencia es un concepto técnico que se ha definido en anteriores entradas y que conjuntamente con el grado de los generadores y el grado del IAS /DAS, constituye uno de los parámetros (numéricos) que permiten distinguir a los Dígrafos de Cayley biegenerados. Fin de nota.

El máximo orden de este generador viene dado por la cota de Landau. El máximo orden del IAS / DAS también. Cómo es fácil ver un digrafo de este tipo, si se pudiese construir asíntoticamente, tendría mayor número de vértices cuanto más grande sea la circunferencia (el orden de uno de los generadores).

Otro caso free-entangled quizás más representativo es aquel cuya representación gráfica ya hemos puesto en el blog en un post anterior. Este caso es más abierto todavia, puesto que en principio no solo permite un mayor orden de uno de los generadores, sino también del IAS/DAS.

Por ello una manera fácil de estimar una cota inferior del tamaño máximo de estos digrafos, si existiesen es multiplicando el orden máximo de un generador por el tamaño del IAS máximo, lo cúal justifica la ecuación siguiente:

x aquí es m, el entero que hay que sumar al grado inicial n, y nos interesa encontrar una expresión simbólica de la solución para todo x.  Log aquí es el logaritmo de base natural. Todos los digrafos con un valor de x inferior al que haga verdadera la igualdad no podrán o ser entangled si queremos que generen Sn (un digrafo de n! vertices o en general un digrafo de orden dado) y por lo tanto serán fáciles.  Para los digrafos de la misma familia del que aparece en la figura de abajo, la constante 2 desaparecería.

Una manera más exacta de determinar el máximo tamaño posible de los digrafos free-entangled sería estudiándolo cómo un proceso de reproducción. Esto ya lo vimos en uno de los primeros posts de éste blog, post que tengo que releer para recuperar éste método y aplicarlo a estos casos en concreto.

Gracias a la imagen se ve claramente también que pueden existir claramente digrafos en los que uno de los dos generadores es una involución (por ejemplo el de linea continua, y entonces dos arcos ahora separados se fundirian en uno), y también digrafos en los que los dos son una involución y entonces sólo podría haber un IAS que sería idéntico al DAS.

(He intentado introducir la expresión de la ecuación en formato LaTex que parece ser que WordPress admite pero en mi blog no funciona ni para esta expresión ni para otra en la que copiaba literalmente una expresión LaTex del foro de wordpress, así que he copiado la expresión cómo fotografía…en fin esto ya es mejor que la formulas expresadas en lenguaje natural de todos los posts anteriores).

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: