Teorema de Müller-Schupp

En matemáticas, el teorema de Muller-Schupp establece que un grupo G generado finitamente tiene un problema verbal libre de contexto si y sólo si G es prácticamente libre . El teorema fue demostrado por David Muller y Paul Schupp en 1983. ^[1]

Problema verbal para grupos

Sea G un grupo finitamente generado con un conjunto generador finito marcado X , es decir, un conjunto X junto con el mapa tal que el subconjunto genera G . Sea el alfabeto del grupo y sea el monoide libre , es decir , el conjunto de todas las palabras (incluida la palabra vacía) sobre el alfabeto . El mapa se extiende a un homomorfismo monoide sobreyectivo, todavía denotado por ,. El problema verbal de G con respecto a X se define como ${\displaystyle \pi :X\to G}$ ${\displaystyle \pi (X)\subseteq G}$ ${\displaystyle \Sigma _{X}:=X\sqcup X^{-1}}$ ${\displaystyle \Sigma _{X}^{\ast }}$ ${\displaystyle \Sigma _{X},}$ ${\displaystyle \Sigma _{X}^{\ast }}$ ${\displaystyle \Sigma _{X}}$ ${\displaystyle \pi :X\to G}$ ${\displaystyle \pi }$ ${\displaystyle \pi :\Sigma _{X}^{\ast }\to G}$ ${\displaystyle {\mathcal {W}}(G,X)}$

${\displaystyle {\mathcal {W}}(G,X):=\{w\in \Sigma _{X}^{\ast }\mid \pi (w)=e{\text{ in }}G\},}$

donde está el elemento identidad de G . ${\displaystyle e\in G}$

Es decir, si G viene dado por una presentación con X finita, entonces consta de todas las palabras del alfabeto que son iguales a en G. ${\displaystyle G=\langle X\mid R\rangle }$ ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle X\sqcup X^{-1}}$ ${\displaystyle e}$

Grupos prácticamente gratuitos

Se dice que un grupo G es prácticamente libre si existe un subgrupo de índice finito H en G tal que H sea isomorfo a un grupo libre . Si G es un grupo virtualmente libre generado finitamente y H es un subgrupo libre de índice finito en G , entonces H mismo se genera finitamente, de modo que H está libre de rango finito. El grupo trivial se considera el grupo libre de rango 0 y, por tanto, todos los grupos finitos son prácticamente libres.

Un resultado básico de la teoría de Bass-Serre dice que un grupo G generado finitamente es prácticamente libre si y sólo si G se divide como grupo fundamental de un gráfico finito de grupos finitos . ^[2]

Declaración precisa del teorema de Muller-Schupp

La formulación moderna del teorema de Muller-Schupp es la siguiente: ^[3]

Sea G un grupo finitamente generado con un conjunto generador finito marcado X. Entonces G es prácticamente libre si y sólo si es un lenguaje libre de contexto. ${\displaystyle {\mathcal {W}}(G,X)}$

Bosquejo de la prueba

La exposición de esta sección sigue la prueba original de 1983 de Muller y Schupp. ^[1]

Supongamos que G es un grupo generado finitamente con un conjunto generador finito X tal que el problema verbal es un lenguaje libre de contexto . Primero se observa que para cada subgrupo H de G generado finitamente es finitamente presentable y que para cada conjunto generador finito marcado Y de H el problema verbal también está libre de contexto. En particular, para un grupo finitamente generado, la propiedad de tener un problema verbal contextual no depende de la elección de un conjunto generador finito marcado para el grupo, y dicho grupo es finitamente presentable. ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle {\mathcal {W}}(H,Y)}$

Muller y Schupp luego muestran, utilizando la gramática libre de contexto para el lenguaje , que el gráfico de Cayley de G con respecto a X es K-triangulable para algún número entero K >0. Esto significa que cada camino cerrado en puede ser, agregando varias "diagonales", descompuesto en triángulos de tal manera que la etiqueta de cada triángulo sea una relación en G de longitud como máximo K sobre X. ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle \Gamma (G,X)}$ ${\displaystyle \Gamma (G,X)}$

Luego utilizan esta propiedad de triangulabilidad del gráfico de Cayley para mostrar que G es un grupo finito o G tiene más de un extremo. Por lo tanto, según un teorema de Stallings , G es finito o G se divide de manera no trivial como un producto libre amalgamado o una extensión HNN donde C es un grupo finito. Luego, nuevamente se generan grupos finitamente con problemas de palabras libres de contexto, y se les puede aplicar todo el argumento anterior. ${\displaystyle G=A\ast _{C}B}$ ${\displaystyle G=A\ast _{C}}$ ${\displaystyle A,B}$

Dado que G es finitamente presentable y, por lo tanto, accesible, ^[4] el proceso de iteración de este argumento finalmente termina con grupos finitos y produce una descomposición de G como el grupo fundamental de un gráfico de grupos finito con grupos finitos de vértices y aristas. Por un resultado básico de la teoría de Bass-Serre se deduce que G es prácticamente libre.

La dirección inversa del teorema de Muller-Schupp es más sencilla. Si G es un grupo virtualmente libre generado finitamente, entonces G admite un subgrupo normal de índice finito N tal que N es un grupo libre de rango finito . Muller y Schupp utilizan este hecho para verificar directamente que G tiene un problema verbal libre de contexto.

Comentarios y novedades

• El teorema de Muller-Schupp es una generalización de gran alcance de un teorema de Anisimov de 1971 que establece que para un grupo G generado finitamente con un conjunto generador finito marcado X, el problema verbal es un lenguaje regular si y sólo si el grupo G es finito. ^[5] ${\displaystyle {\mathcal {W}}(G,X)}$
• En el momento en que se publicó el artículo de Muller y Schupp de 1983, aún no se había establecido la accesibilidad de los grupos presentados de forma finita. Por lo tanto, la formulación original del teorema de Muller-Schupp decía que un grupo generado finitamente es prácticamente libre si y sólo si este grupo es accesible y tiene un problema verbal libre de contexto. Un artículo de Dunwoody de 1985 demostró que todos los grupos presentados de forma finita son accesibles. ^[4] Dado que los grupos finitamente generados con problemas verbales libres de contexto son finitamente presentables, el resultado de Dunwoody junto con el teorema original de Muller-Schupp implican que un grupo generado finitamente es virtualmente libre si y sólo si tiene un problema verbal libre de contexto (que es la formulación moderna del teorema de Muller-Schupp).
• Un artículo de Linnell ^[6] de 1983 estableció la accesibilidad de grupos generados de forma finita donde los órdenes de subgrupos finitos están acotados. Más tarde se observó (ver ^[7] ) que el resultado de Linnell junto con el teorema de Muller-Schupp original eran suficientes para derivar el enunciado moderno del teorema de Muller-Schupp, sin tener que utilizar el resultado de Dunwoody.
• En el caso de grupos libres de torsión , la situación se simplifica ya que no se necesitan los resultados de accesibilidad y en su lugar se utiliza el teorema de Grushko sobre el rango de un producto libre. En este contexto, como se señala en el artículo original de Muller y Schupp, ^[1] el teorema de Muller-Schupp dice que un grupo libre de torsión generado finitamente tiene un problema verbal libre de contexto si y sólo si este grupo es libre. ^[1]
• En un artículo relacionado posterior, Muller y Schupp demostraron que un gráfico Γ "finitamente generado" tiene un número finito de tipos de isomorfismos finales si y sólo si Γ es el gráfico de transición de un autómata push-down . ^[8] Como consecuencia, muestran que la teoría monádica de un grafo "libre de contexto" (como el grafo de Cayley de un grupo virtualmente libre) es decidible, generalizando un resultado clásico de Rabin para árboles binarios. ^[9] Más tarde, Kuske y Lohrey ^[10] demostraron que los grupos virtualmente libres son los únicos grupos finitamente generados cuyos grafos de Cayley tienen una teoría monádica decidible.
• Bridson y Gilman ^[11] aplicaron el teorema de Muller-Schupp para demostrar que un grupo generado finitamente admite un peinado "tipo escoba" si y sólo si ese grupo es prácticamente libre.

• Sénizergues utilizó el teorema de Muller-Schupp para demostrar ^[12] que el problema de isomorfismo para un grupo virtualmente libre generado finitamente es recursivo primitivo .
• Gilman, Hermiller , Holt y Rees utilizaron el teorema de Muller-Schupp para demostrar que un grupo G generado finitamente es virtualmente libre si y sólo si existe un conjunto generador finito X para G y un conjunto finito de reglas de reescritura reductoras de longitud sobre X cuyo La aplicación reduce cualquier palabra a una palabra geodésica. ^[13]
• Ceccherini-Silberstein y Woess consideran la configuración de un grupo G generado finitamente con un conjunto generador finito X y un subgrupo K de G tal que el conjunto de todas las palabras del alfabeto que representan elementos de H es un lenguaje libre de contexto. ^[14] ${\displaystyle \Sigma _{X}}$
• Generalizando el escenario del teorema de Muller-Schupp, Brough ^[15] estudió grupos con problemas verbales poli-libres de contexto, es decir, donde el problema verbal es la intersección de un número finito de lenguajes libres de contexto. Los grupos poli-libres de contexto incluyen todos los grupos finitamente generados conmensurables con grupos integrables en un producto directo de un número finito de grupos libres, y Brough conjeturó que cada grupo poli-libre de contexto surge de esta manera. Ceccherini-Silberstein, Coornaert, Fiorenzi, Schupp y Touikan ^[16] introdujeron la noción de autómata de múltiples pasos , que son autómatas no deterministas que aceptan precisamente todas las intersecciones finitas de lenguajes libres de contexto. También obtuvieron resultados que proporcionaron evidencia significativa a favor de la conjetura de Brough anterior.
• Nyberg-Brodda ^[17] generalizó el teorema de Muller-Schupp de grupos a "monoides especiales", una clase de semigrupos que contiene, pero estrictamente mayor que, la clase de grupos, caracterizando dichos semigrupos con un problema verbal libre de contexto como precisamente aquellos con un subgrupo máximo prácticamente libre.
• Posteriormente al artículo de 1983 de Muller y Schupp, varios autores obtuvieron demostraciones alternativas o simplificadas del teorema de Muller-Schupp. ^{[18] [14] [3]}

Ver también

• Autómata de árbol infinito
• Problema verbal (matemáticas)
• Lenguaje formal

Referencias

1. David E. Muller y Paul E. Schupp, Grupos, la teoría de los fines y lenguajes libres de contexto. Revista de Ciencias de la Computación y Sistemas 26 (1983), no. 3, 295–310
2. A. Karrass, A. Pietrowski y D. Solitar, Extensiones cíclicas finitas e infinitas de grupos libres . Revista de la Sociedad Australiana de Matemáticas 16 (1973), 458–466
3. V. Diekert y A. Weiß, Grupos libres de contexto y sus árboles estructurales . Revista Internacional de Álgebra y Computación 23 (2013), no. 3, 611–642
4. MJ Dunwoody, La accesibilidad de grupos presentados de forma finita. Invenciones Mathematicae 81 (1985), núm. 3, 449–457
5. AV Anisimov, Idiomas del grupo (en ruso) , Kibernetika, 4 (1971), págs. 18-24
6. PA Linnell, Sobre la accesibilidad de los grupos . Revista de álgebra pura y aplicada 30 (1983), no. 1, 39–46
7. T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi y PE Schupp, Grupos, gráficos, lenguajes, autómatas, juegos y lógica monádica de segundo orden. Revista europea de combinatoria 33 (2012), no. 7, 1330-1368
8. DE Muller y PE Schupp, La teoría de los fines, los autómatas de empuje y la lógica de segundo orden. Informática Teórica 37 (1985), no. 1, 51–75
9. MO Rabin, Decidibilidad de teorías de segundo orden y autómatas en árboles infinitos. Transacciones de la Sociedad Matemática Estadounidense 141 (1969), 1–35
10. D. Kuske, M. Lohrey, Aspectos lógicos de los gráficos de Cayley: el caso del grupo . Anales de lógica pura y aplicada 131 (2005), no. 1–3, 263–286
11. M. Bridson y RH Gilman, Un comentario sobre la combinación de grupos . Revista Internacional de Álgebra y Computación 3 (1993), no. 4, 575–581
12. G. Sénizergues, Sobre los subgrupos finitos de un grupo libre de contexto . Perspectivas geométricas y computacionales sobre grupos infinitos (Minneapolis, MN y New Brunswick, Nueva Jersey, 1994), 201--212, DIMACS Ser. Matemáticas discretas. Teoría. Computadora. Sci., 25, Sociedad Estadounidense de Matemáticas , Providence, RI, 1996
13. RH Gilman, S. Hermiller, D. Holt y S. Rees, Una caracterización de grupos prácticamente libres. Archiv der Mathematik 89 (2007), núm. 4, 289–295
14. T. Ceccherini-Silberstein y W. Woess, Pares de grupos libres de contexto I: pares y gráficos libres de contexto . Revista europea de combinatoria 33 (2012), no. 7, 1449-1466
15. T. Brough, Grupos con problemas verbales sin contexto múltiple. Grupos, Complejidad, Criptología 6 (2014), no. 1, 9–29
16. T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi, PE Schupp y N. Touikan, Autómatas multipaso y problemas planteados en grupo . Informática Teórica 600 (2015), 19-33
17. CF Nyberg-Brodda, Sobre el problema verbal de los monoides especiales , arxiv.org/abs/2011.09466 (2020)
18. Y. Antolin, Sobre gráficos de Cayley de grupos prácticamente libres , Grupos, Complejidad, Criptología 3 (2011), 301–327

enlaces externos

• Grupos libres de contexto y sus árboles estructurales, charla expositiva de Armin Weiß