Complejidad computacional peor caso del problema RH I. El orden de los grupos finitos bigenerados.

1. Introducción:

En el último post, dábamos por concluida, al menos provisionalmente la clasificación del problema y en este iniciamos otro objetivo de la investigación que se desdobla en dos subobjetivos:

– primero intentar determinar si existen grupos bigenerados que cumplan con los requisitos para ser los peores casos. En posts anteriores deciamos que los peores casos son pares de permutaciones de Sn que no generan Sn, que tienen un IAS subexponencial con respecto a n, el grado de la identidad dada y que generen un subgrupo de orden subexponencial con respecto a n. Recordemos que el IAS es el orden que se obtiene al comparar los dos generadores. Exigimos que el IAS sea subexponencial por que si no lo fuese posiblemente los casos generados por estos pares no podrian ser entangled, asíntoticamente. Exigimos que el orden del digrafo sea Subexponencial por estar en la clase PSPACE-complete. Resumiendo, los casos difíciles deben cumplir dos condiciones: IAS subexponencial y orden subexponencial. Alguien podría pensar que con que cumplan la primera, IAS subexponencial ya cumplen la segunda. No necesariamente. Podrian tener IAS subexponencial y orden exponencial o superior y entonces no nos valdrian. Luego intentaremos expresar estas dos restricciones de una manera más matematica.

– segundo, si existiesen, determinar su frecuencia con respecto al grado de la permutación para poder determinar la complejidad caso medio del problema que nos interesa.

Abro el post con el fin de ir recopilando links relacionados con este tema. Este es por lo tanto un post abierto, en construcción. Cuando tenga toda la información que haya recopilado y la haya asimilado y tenga todo más claro, le daré la forma definitiva.  De momento doy por terminada la fase de recopilación.

2. Grupos finitos. Primera exploración:

La estructura matemática más sencilla es el número natural (entero, positivo). Es una representación abstracta y sucinta de la cantidad. A cada cantidad (que podemos representar por una multilicidad de barras iguales) se le asigna un cierto un nombre o simbolo arbitrario. Los diferentes sistemas numéricos permiten expresar cualquier numero posible con un numero finito de simbolos, la base (hoy la base decimal es de uso corriente).

Una estructura un poco más complicada es la de conjunto finito, que se puede representar como un lista de números diferentes.  Si además del conjunto damos una lista de relaciones binarias entre los elementos del conjunto obtenemos una estructura de digrafo (la teoria de relaciones binarias es equivalente a la teoria de digrafos). Si en vez de relaciones binarias, sobre un conjunto finito consideramos un determinado tipo de relaciones ternarias (también llamadas operaciones), sujetas a determinadas restricciones, obtenemos la más sencilla de las estructuras algebraicas, la estructura de grupo finito. No es la estructura algebraica o combinatoria más libre que se puede definir con relaciones ternarias (por ejemplo semigrupos y otras), pero posiblemente si la más interesante.  Una manera alternativa que ya conocemos, menos abstracta, de representar los grupos finitos es mediante permutaciones, grupos de permutaciones.

Para cada grado n (numero de elementos del conjunto a permutar), llamamos Sn (grupo simetrico de grado n) al grupo que contiene todas las permutaciones (biyecciones) posibles de un conjunto  de n elementos en sí mismo. Sn obviamente tiene n! elementos, tantos como permutaciones diferentes. Por el teorema de Cayley (http://en.wikipedia.org/wiki/Cayley%27s_theorem) sabemos que todo grupo finito se puede representar como un subgrupo de Sn. Entonces es para nosotros de maximo interés estudiar la estructura (asíntoticamente si fuese posible) de los subgrupos de Sn. Entonces un primer enlace de interés es:  http://en.wikipedia.org/wiki/Symmetric_group (wikipedia, siempre wikipedia), y dentro de este artículo y del apartado “subgroup structure” encontramos el siguiente enlace:   http://en.wikipedia.org/wiki/Permutation_group. Este artículo (sobre grupos de permutaciones) es bastante poco informativo, o por lo menos a nosotros no nos es de gran ayuda. Parece dan a entender que la estructura de subgrupos de Sn se puede entender en términos de grupos normales, maximales o de Sylow.

Normales: Seguimos y nos informan que asíntoticamente (n>4) los únicos grupos normales serán An o la identidad (el subgrupo de todas las permutaciones pares), que para todo n sabemos tiene orden n!/2, más grande que lo que buscamos.

Maximales: El siguiente subsubapartado si que parece más interesante: maximal subgroups o http://en.wikipedia.org/wiki/Maximal_subgroup. No veo ninguna razón para que los grupos que nos interesan sean necesariamente maximales. Pero podrian serlo y deberemos profundizar sobre este tipo de subgrupos, y más concretamente en la clasificación de grupos finitos simples, y en el teorema O´nan-Scott. Pero antes seguimos con la exploración y desde este último artículo pasamos a http://en.wikipedia.org/wiki/Finite_group_theory , en el que señalan unos datos a tener e cuenta:

–“During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of solvable groups and nilpotent groups. A complete determination of the structure of all finite groups is too much to hope for; the number of possible structures soon becomes overwhelming. However, the complete classification of the finite simple groups was achieved, meaning that the “building blocks” from which all finite groups can be built are now known, as each finite group has a composition series“. Una de cal y otra de arena.

–“Given a positive integer n, it is not at all a routine matter to determine how many isomorphism types of groups of order n there are.” Pero a nosotros nos interesa más otro problema: para todo conjunto de grado n, encontrar todos los ordenes de grupos bigenerados, en función de n. Es decir tenemos que centrar el tema en grupos de permutaciones.

Sylow. aquí parece que utilizan un lenguaje (permutaciones) que nos satisface más. Copiemos pues enteramente esta parte:

The Sylow subgroups of the symmetric groups are important examples p-groups. They are more easily described in special cases first:

The Sylow p-subgroups of the symmetric group of degree p are just the cyclic subgroups generated by p-cycles. There are (p−1)!/(p−1) = (p−2)! such subgroups simply by counting generators. The normalizer therefore has order p·(p-1) and is known as a Frobenius group Fp(p-1) (especially for p=5), and as the affine general linear group, AGL(1,p).

The Sylow p-subgroups of the symmetric group of degree p2 are the wreath product of two cyclic groups of order p. For instance, when p=3, a Sylow 3-subgroup of Sym(9) is generated by a=(1,4,7)(2,5,8)(3,6,9) and the elements x=(1,2,3), y=(4,5,6), z=(7,8,9), and every element of the Sylow 3-subgroup has the form aixjykzl for 0 ≤ i,j,k,l ≤ 2.

The Sylow p-subgroups of the symmetric group of degree pn are sometimes denoted Wp(n), and using this notation one has that Wp(n+1) is the wreath product of Wp(n) and Wp(1).

In general, the Sylow p-subgroups of the symmetric group of degree n are a direct product of ai copies of Wp(i), where 0 ≤ ai ≤ p−1 and n = a0 + p·a1 + … + pk·ak.

For instance, W2(1) = C2 and W2(2) = D8, the dihedral group of order 8, and so a Sylow 2-subgroup of the symmetric group of degree 7 is generated by { (1,3)(2,4), (1,2), (3,4), (5,6) } and is isomorphic to D8 × C2.

These calculations are attributed to (Kaloujnine 1948) and described in more detail in (Rotman 1995, p. 176). Note however that (Kerber 1971, p. 26) attributes the result to an 1844 work of Cauchy, and mentions that it is even covered in textbook form in (Netto 1882, §39–40).”

La vía wikipedia parece agotada. Crucemos “symmetric group”x”subgroup structure”. Encontramos cómo enlaces destacados:

unos teoremas clave para encontrar la estructura de subgrupos de un grupo dado, Sylow theorems: http://en.wikipedia.org/wiki/Sylow_theorems.

–lo que parece ser un buen resumen de la situación (es una revisión de un libro): http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183657067.

–y lo que parece un curso sobre el tema: http://users.dimi.uniud.it/~mario.mainardis/scuolaestiva2008/venotes.pdf

–o la muy interesante presentación http://www.soton.ac.uk/~tb1u06/docs/helsinki_08.pdf.

–o este otro que también parece relevante http://pages.uoregon.edu/kantor/PAPERS/CWInotes.pdf.

3. Grupos de permutaciones:l

En esta parte vamos a introducir brevemente los conceptos fundamentales sobre grupos de permutaciones (transitividad, primitividad).

4. Método 1. Enumeración de grupos bigenerados, candidatos a casos (asíntoticamente) difíciles: Todo lo descrito en los apartados anteriores es muy teorico e interesante pero debemos ajustar más la busqueda a lo que nos interesa: grupos (preferiblemente de permutaciones) bigenerados y de tamaño subexponencial. En este apartado vamos a ir poniendo posibles candidatos a casos asintóticamente difíciles, que iremos confirmando o descartando. Su inclusión en este apartado depende de momento del criterio de que sean bigenerables.

4.1 Grupos de permutaciones bigenerados: en este subapartado intentaré reunir toda la información posible sobre cómo caracterizar todos los grupos (preferentemente de permutaciones) que sean bigenerados, que son los que nos interesan. De momento sabemos que para cada n, Sn, An, Dihedrico(n), Cuaternonico(n), Semi-dihedrico(n) y todos los grupos finitos simples  son bigenerados, pero lo que nos interesa es una caracterización lo más general posible.

Cruzando “permutation group”x”two generated” encontramos:

– esta muy interesante presentación: http://www.soton.ac.uk/~tb1u06/docs/usc_08.pdf

–un paper de Kantor (otro especialista en grupos de permutaciones):http://citeseerx.ist.psu.edu/showciting?cid=8082677.

4.2 Grupos de tamaño subexponencial: si en el apartado anterior intentabamos acotar la busqueda limitandonos a grupos bigenerados, ahora acotamos limitamos a grupos de tamaño subexponencial. Cruzamos “permutation group”x”subexponential size” y obtenemos papers muy interesantes Parece que este tipo de preguntas (sobre el orden del grupo dado el grado de la permutación) era frecuente en los inicios de la teoria de Grupos, es decir en el siglo XIX, con los pioneros (Galois, Jordan , Cauchy etc…):

–cómo ejemplos, este paper de Jordan: http://archive.numdam.org/ARCHIVE/BSMF/BSMF_1872-1873__1_/BSMF_1872-1873__1__40_1/BSMF_1872-1873__1__40_1.pdf;  en el comenta sobre el teorema de Sylow, que generaliza uno de Cauchy: “cette proposition mérite assurément par sa simplicité, sa netteté et sa generalité d´être considerée comme fondamentale; et nous ne doutons pas qu´elle ne donne lieu à d´importantes conséquences”. La historia le dió la razón.  Otro paper de Jordan:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.6315. Muy interesante.

http://www.jstor.org/pss/2006997. Promete ser también muy interesante pero solo puedo acceder a la primera página.

–y curiosamente del campo de  QC: http://arxiv.org/PS_cache/quant-ph/pdf/0406/0406046v1.pdf. El resultado de este paper va en la linea que apuntabamos en el post anterior (ver última parte). De casi los mismos autores http://www.cs.tau.ac.il/~kempe/papers/Anerp-journal-corr2.pdf.

4.3 Candidatos Abelianos:

–familia de grupos cíclicos bigenerados. El ciclo debe ser de orden subexponencial. Además se debe seleccionar los generadores de manera que se pueda obtener un IAS subexponencial.

–familia de grupos del tipo producto directo de dos ciclos. En principio se podrian construir obteniendo el producto directo de dos ciclos subexponenciales.

4.4 Candidatos no abelianos simples:

–grupos finitos simples del tipo Lie clásicos. Por lo visto es un hecho bien conocido (no por mi) que todos los grupos finitos simples son bigenerables. Hoy (29 de septiembre) he averiguado que este hecho proviene de un teorema de Steinberg para grupos de Lie clásicos (1962) y de Aschbacher-Guralnick (1984) para esporadicos. Por el (todavia discutido) teorema de clasificación de grupos finitos simples (http://en.wikipedia.org/wiki/Classification_of_finite_simple_groups) sabemos que todo grupo finito simple es:  o un grupo de orden primo (y esta clase no nos vale como familia asintotica de casos difíciles.¿porque?); o un grupo  alternado An (tampoco nos sirve); o un grupo esporádico (hay 26, cada uno es único y tampoco valen para un análisis asímptotico);  o un grupo del tipo de Lie (excepto los que no constituyan familias infinitas). Para más información:http://en.wikipedia.org/wiki/Simple_Lie_group.

4.5 Otros candidatos no abelianos:

–familia de grupos dihédrico generalizados. Son siempre bigenerados. Dudas: entiendo que el orden del ciclo puede ser el máximo para el grado dado (confirmar); lo  que no está tan claro es el comportamiento asíntotico del IAS (comprobar).

–familia de grupos cuaternonicos generalizados. idem. Mismas dudas.  Quizás las relaciones de la presentación limiten el crecimiento del orden de estos grupos.

–familia de grupos semi-dihédricos generalizados. comprende a las otras dos. idem. Mismas dudas.

5. Método 2. Construcción directa:

En este apartado exploraremos un método diferente del utilizado en el punto anterior. En vez de hacer una lista de todos los grupos bigenerados posibles y comprobar si pueden cumplir con los requisitos, intentamos construir directamente una familia de casos asíntoticamente difíciles.

4.1 Ejemplo 1 de posible construcción directa: En un post anterior ya dabamos un primer avance sobre este método. Dada la identidad de grado n, puede ser que los dos generadores tengan x puntos fijos comunes. Entonces, la condición de que generen un grupo de orden subexponencial con respecto a n se puede expresar de la siguiente manera: (n-x)!=Subexp(n). Nos interesaría despejar x, ver cómo varía con n y ver si esta condición es compatible con la segunda condición de que el IAS sea subexponencial. Recordemos que para obtener el IAS debemos comparar los dos generadores. Comparar los dos generadores no es otra cosa que encontrar la permutación equivalente desde la identidad. Está claro que cuando los dos generadores tienen x puntos fijos comunes el IAS podrá tener un orden máximo de Subexp(n-x) y no de subexp n. Entonces, si a medida que n crece x también crece, para cumplir con la igualdad,  es posible que la familia no sea asíntoticamente difícil, pues llegará un momento en que el IAS será pequeño con respecto al orden del grupo. Es decir, es posible que con esta construcción, las tres condiciones (orden subexponencial del grupo, orden subexponencial del IAS y familia asíntoticamente difícil) sean incompatibles.

4.2 Ejemplo 2 de construcción directa: Otra alternativa a la anterior para cumplir con el primer requisito de obtener un grupo de orden subexponencial podría seleccionar los dos generadores de tal manera que tengan un orden subexponencial y la misma estructura de ciclos.  Continuará cuando lo tenga claro.

6. Otros links relacionados:

Aquí voy a recopilar links indirectamente relacionados con el tema de este post.

–Por ejemplo un blog que desconocía y que está hablando últimamente de la teoria de representaciones de grupos de permutaciones (que trata de como representar objetos del “lenguaje” de permutaciones en el “lenguaje” de espacios vectoriales y transformaciones lineales (matrices), asociando a  cada permutación de un conjunto en si mismo, una transformación lineal de un espacio vectorial en si mismo):  Blog Unapologetic Mathematician.

–o este otro blog de uno de los grandes especialistas actuales en grupos de permutaciones, que sí que conocía y con unas entradas muy interesantes sobre el grupo simetrico: Peter Cameron´s Blog.

–en Mathoverflow: http://mathoverflow.net/questions/15707/largest-possible-order-of-a-nilpotent-permutation-group

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


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: