Transformación de Nielsen

Dejar${\textstyle F_{n}}$ser un grupo libre finitamente generado de rango${\textstyle n}$Una transformación elemental de Nielsen mapea una base ordenada .${\textstyle [x_{1},\ldots ,x_{n}]}$a una nueva base${\textstyle [y_ {1},\ldots,y_ {n}]}$mediante una de las siguientes operaciones:

1. Permuta el${\textstyle x_{i}}$s por alguna permutación${\textstyle \sigma \in S_{n}}$, es decir${\textstyle [y_{1},\ldots ,y_{n}]=[x_{\sigma (1)},\ldots ,x_{\sigma (n)}]}$
2. Invierte algunos${\textstyle x_{i}}$, es decir${\textstyle [y_{1},\ldots ,y_{n}]=[x_{1},\ldots ,x_{i}^{-1},\ldots ,x_{n}]}$
3. Reemplazar algunos${\textstyle x_{i}}$con${\displaystyle x_{i}x_{j}}$para algunos${\textstyle j\neq i}$, es decir${\textstyle [y_{1},\ldots ,y_{n}]=[x_{1},\ldots ,x_{i}x_{j},\ldots ,x_{n}]}$.

Una transformación de Nielsen es una composición finita de transformaciones elementales de Nielsen. Dado que los automorfismos de${\displaystyle F_{n}}$están determinadas por la imagen de una base, las transformaciones elementales de Nielsen corresponden a un subconjunto finito del grupo de automorfismos.${\textstyle \mathrm {Aut} (F_ {n})}$, que de hecho es un conjunto generador (véase más abajo). Por lo tanto, la transformación de Nielsen puede definirse alternativamente simplemente como la acción de un automorfismo de${\textstyle F_{n}}$en bases.

Las transformaciones elementales de Nielsen son análogas a las operaciones elementales de fila . Las transformaciones de primer tipo son análogas a las permutaciones de filas. Las transformaciones de segundo tipo corresponden a escalar una fila mediante un escalar invertible. Las transformaciones de tercer tipo corresponden a adiciones de filas ( transvecciones ).

Dado que el grupo de permutaciones finito${\displaystyle S_{n}}$se genera mediante transposiciones, como se observa en la cadena de transformaciones elementales de Nielsen de tipo 2 y 3:$${\displaystyle (x_{i},x_{i+1})\mapsto {(x_{i},x_{i+1}^{-1})}\mapsto {{(x_{i}x_{i+1}^{-1}},x_{i+1}^{-1})}\mapsto ({{x_{i+1}x_{i}^{-1}},x_{i+1}^{-1}})\mapsto {({x_{i+1}x_{i}^{-1}},x_{i}^{-1})}\mapsto (x_{i+1}x_{i}^{-1},x_{i})\mapsto (x_{i+1},x_{i})}$$que las transformaciones elementales de Nielsen de tipo 2 y 3 son, de hecho, suficientes para generar todas las transformaciones de Nielsen.

Utilizando los dos generadores${\textstyle (12)}$y${\textstyle (1\ldots n)}$de${\textstyle S_{n}}$Alternativamente, se puede restringir la atención a solo cuatro operaciones:

• cambiar${\textstyle x_{1}}$y${\textstyle x_{2}}$
• permutar cíclicamente el${\textstyle x_{i}}$s
• invertir${\textstyle x_{1}}$
• reemplazar${\textstyle x_{1}}$con${\textstyle x_{1}x_{2}}$.

Cuando se trabaja con grupos que no son libres, estas transformaciones se aplican a subconjuntos finitos y ordenados del grupo. En este caso, las composiciones de las transformaciones elementales se denominan regulares . Si se permite eliminar elementos del subconjunto que sean el elemento identidad , la transformación se denomina singular .

La imagen obtenida mediante una transformación de Nielsen (elemental o no, regular o no) de un conjunto generador de un grupo G es también un conjunto generador de G. Dos conjuntos generadores se denominan equivalentes de Nielsen si existe una transformación de Nielsen que los transforma en el otro (tenga en cuenta que esto no es una relación de equivalencia ). Si los conjuntos generadores tienen el mismo tamaño, basta con considerar composiciones de transformaciones regulares de Nielsen.

El teorema de Nielsen-Schreier establece que cada subgrupo${\textstyle F'\leq F}$de un grupo libre${\textstyle F}$también es libre. La prueba moderna se basa en el hecho de que un grupo (finitamente generado o no) es libre si y solo si es el grupo fundamental de un grafo (finito o no). Esto permite encontrar explícitamente una base de${\textstyle F'}$, puesto que se realiza geométricamente como el grupo fundamental de un recubrimiento de un grafo cuyo grupo fundamental es${\displaystyle F}$.

Sin embargo, la demostración original de Nielsen para el caso de subgrupos finitamente generados, presentada en ( Nielsen 1921 ) , es diferente y más combinatoria. Se basa en la noción de conjunto generador reducido de Nielsen , que en términos generales significa uno para el cual no hay demasiada cancelación en los productos. El artículo muestra que todo conjunto generador finito de un subgrupo de un grupo libre es (singularmente) equivalente a un conjunto generador reducido de Nielsen, y que un conjunto generador reducido de Nielsen es una base libre para el subgrupo, por lo que el subgrupo es libre. Esta demostración se presenta con cierto detalle en ( Magnus, Karrass y Solitar 2004 , Cap. 3.2) .

En ( Nielsen 1924 ) , se demuestra que las transformaciones elementales de Nielsen generan el grupo de automorfismos completo de un grupo libre finitamente generado . Nielsen, y posteriormente Bernhard Neumann, utilizaron estas ideas para proporcionar presentaciones finitas de los grupos de automorfismos de grupos libres. Esto también se describe en libros de texto estándar como ( Magnus, Karrass y Solitar 2004 , p. 131, Teorema 3.2) . 

Para un conjunto generador dado de un grupo finitamente generado, no es necesariamente cierto que cada automorfismo sea una transformación de Nielsen , pero para cada automorfismo, hay un conjunto generador donde el automorfismo está dado por una transformación de Nielsen, ( Rapaport 1959 ) .

La generalización adecuada de las transformaciones de Nielsen para automorfismos de productos libres de grupos libremente indescomponibles son los automorfismos de Whitehead. Junto con los automorfismos de los factores de Grushko , forman un conjunto generador del grupo de automorfismos de cualquier grupo finitamente generado, conocido como generadores de Fouxe-Rabinovitch. ^{[ 2 ]}

Un caso particularmente simple del problema de la palabra para grupos y el problema del isomorfismo para grupos pregunta si un grupo finitamente presentado es el grupo trivial . Se sabe que esto es intratable en general, aunque existe una secuencia finita de transformaciones elementales de Tietze que llevan la presentación a la presentación trivial si y solo si el grupo es trivial. Un caso especial es el de las "presentaciones balanceadas", aquellas presentaciones finitas con igual número de generadores y relatores. Para estos grupos, existe una conjetura de que las transformaciones requeridas son bastante más simples (en particular, no implican agregar ni eliminar relatores). Si se permite llevar el conjunto de relatores a cualquier conjunto equivalente de Nielsen, y se permite conjugar los relatores, entonces se obtiene una relación de equivalencia en subconjuntos ordenados de relatores de un grupo finitamente presentado. La conjetura de Andrews-Curtis es que los relatores de cualquier presentación balanceada del grupo trivial son equivalentes a un conjunto de relatores triviales, afirmando que cada generador es el elemento identidad.

En el libro de texto ( Magnus, Karrass y Solitar 2004 , págs. 131-132) , se presenta una aplicación de las transformaciones de Nielsen para resolver el problema generalizado de la palabra para grupos libres, también conocido como el problema de pertenencia para subgrupos dados por conjuntos generadores finitos en grupos libres. 

Un caso especial particularmente importante del problema del isomorfismo para grupos concierne a los grupos fundamentales de nudos tridimensionales , que pueden resolverse utilizando transformaciones de Nielsen y un método de JW Alexander ( Magnus, Karrass y Solitar 2004 , Cap. 3.4) .

En la teoría de grupos computacional , es importante generar elementos aleatorios de un grupo finito . Los métodos más comunes para lograrlo aplican métodos de cadenas de Markov para generar conjuntos generadores aleatorios del grupo. El "algoritmo de reemplazo de producto" simplemente utiliza transformaciones de Nielsen elegidas aleatoriamente para realizar un recorrido aleatorio sobre el grafo de conjuntos generadores del grupo. El algoritmo está bien estudiado y se ofrece una revisión en ( Pak 2001 ) . Una versión del algoritmo, llamada "shake", es:

• Toma cualquier conjunto generador ordenado y agrega algunas copias del elemento identidad, de modo que haya n elementos en el conjunto.
• Repita lo siguiente un número determinado de veces (llamado período de calentamiento ).
  • Elija números enteros i y j uniformemente al azar de 1 a n , y elija e uniformemente al azar de { 1, -1 }.
  • Reemplaza el i -ésimo generador con el producto del i- ésimo generador y el j -ésimo generador elevado a la e- ésima potencia.
• Cada vez que se desee un nuevo elemento aleatorio, repita los dos pasos anteriores y, a continuación, devuelva uno de los elementos generadores como el elemento aleatorio deseado.

Se puede demostrar que el conjunto generador utilizado durante este algoritmo varía uniformemente sobre todos los conjuntos generadores equivalentes de Nielsen. Sin embargo, este algoritmo presenta varios problemas estadísticos y teóricos. Por ejemplo, puede haber más de una clase de equivalencia de Nielsen para los generadores. Además, los elementos de los conjuntos generadores deben estar distribuidos uniformemente (por ejemplo, los elementos del subgrupo de Frattini nunca pueden aparecer en un conjunto generador de tamaño mínimo, pero también surgen problemas más sutiles).

La mayoría de estos problemas se solucionan rápidamente con la siguiente modificación denominada "traqueteo" ( Leedham-Green y Murray, 2002 ) :

• Además del conjunto generador, almacene un elemento adicional del grupo, inicializado con la identidad.
• Cada vez que se reemplaza un generador, elija k uniformemente al azar y reemplace el elemento adicional por el producto del elemento adicional con el k -ésimo generador.

Para comprender la equivalencia de Nielsen de conjuntos generadores no mínimos, las investigaciones basadas en la teoría de módulos han sido útiles, como en ( Evans 1989 ) . Siguiendo esta línea, se describió una formulación basada en la teoría K de la obstrucción a la equivalencia de Nielsen en ( Lustig 1991 ) y ( Lustig & Moriah 1993 ) . Estas formulaciones muestran una conexión importante entre el grupo de Whitehead del anillo de grupos y las clases de equivalencia de Nielsen de los generadores.

• Cohen, Daniel E. (1989), Teoría de grupos combinatorios: un enfoque topológico , London Mathematical Society Student Texts, vol.  14, Cambridge University Press , doi : 10.1017/CBO9780511565878 , ISBN 978-0-521-34133-2, MR 1020297 
• Fine, Benjamin; Rosenberger, Gerhard; Stille, Michael (1995), "Transformaciones y aplicaciones de Nielsen: una revisión" , en Kim, Ann Chi; Kim, AC; Johnson, DL (eds.), Groups—Korea '94: Actas de la Conferencia Internacional celebrada en la Universidad Nacional de Pusan, Pusan, Corea, del 18 al 25 de agosto de 1994 , Walter de Gruyter, pp. 69–105 , ISBN  978-3-11-014793-3, MR 1476950 
• Schupp, Paul E .; Lyndon, Roger C. (2001), Teoría combinatoria de grupos , Springer-Verlag , ISBN 978-3-540-41158-1, MR 0577064 
• Magnus, Wilhelm ; Karrass, Abraham; Solitar, Donald (2004), Teoría combinatoria de grupos , Dover Publications , ISBN 978-0-486-43830-6, MR 0207802 

• Alexander, JW (1928), "Invariantes topológicos de nudos y enlaces", Transactions of the American Mathematical Society , 30 (2): 275–306 , doi : 10.2307/1989123 , JFM 54.0603.03 , JSTOR 1989123  
• Evans, Martin J. (1989), "Elementos primitivos en grupos libres", Actas de la Sociedad Matemática Americana , 106 (2): 313– 6, doi : 10.2307/2048805 , JSTOR 2048805 , MR 0952315  
• Fenchel, Werner ; Nielsen, Jakob (2003), Schmidt, Asmus L. (ed.), Grupos discontinuos de isometrías en el plano hiperbólico , Estudios De Gruyter en matemáticas, vol.  29, Berlín: Walter de Gruyter & Co.
• Leedham-Green, CR ; Murray, Scott H. (2002), "Variantes de reemplazo de productos", Teoría de grupos computacional y estadística (Las Vegas, NV/Hoboken, NJ, 2001) , Contemp. Math., vol.  298, Providence, RI: American Mathematical Society , pp. 97–104 , doi : 10.1090/conm/298/05116 , MR 1929718  
• Lustig, Martin (1991), "Equivalencia de Nielsen y tipo de homotopía simple", Actas de la Sociedad Matemática de Londres , 3.ª serie, 62 (3): 537– 562, doi : 10.1112/plms/s3-62.3.537 , MR 1095232 
• Lustig, Martin; Moriah, Yoav (1993), "Generación de sistemas de grupos y torsión de Reidemeister-Whitehead", Journal of Algebra , 157 (1): 170–198 , doi : 10.1006/jabr.1993.1096 , MR 1219664 
• Nielsen, Jakob (1921), "Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien", Math. Tidsskrift B (en danés), 1921 : 78– 94, JFM 48.0123.03 , JSTOR 24529483  
• Nielsen, Jakob (1924), "Die Isomorphismengruppe der freien Gruppen", Mathematische Annalen (en alemán), 91 ( 3– 4): 169– 209, doi : 10.1007/BF01556078 , JFM 50.0078.04 
• Pak, Igor (2001), "¿Qué sabemos sobre el algoritmo de reemplazo de productos?", Grupos y computación, III (Columbus, OH, 1999) , Ohio State Univ. Math. Res. Inst. Publ., vol.  8, Walter de Gruyter, pp. 301–347 , MR 1829489  
• Rapaport, Elvira Strasser (1959), "Nota sobre las transformaciones de Nielsen", Actas de la Sociedad Matemática Americana , 10 (2): 228– 235, doi : 10.2307/2033582 , JSTOR 2033582 , MR 0104724